State Decomposition for Long-Horizon AI Planning

20 concepts12 papers1 proposal

Imagine trying to navigate a massive, intricate maze. If you attempt to plan a single, continuous path from the entrance to the exit, the number of possible choices multiplies at every intersection. This exponential growth creates a combinatorial explosion, making long-horizon planning computationally intractable for classical AI planners.

But what if you were given a sequence of five intermediate rooms that you must pass through in order? Suddenly, the daunting global problem collapses into six trivial mini-mazes. Finding a path from one room to the next is simple because the search horizon is drastically shortened.

This is the core intuition behind state decomposition. Instead of forcing a planner to discover a massive end-to-end sequence of actions directly, this paradigm breaks the problem apart by identifying intermediate partial states—often called subgoals, milestones, or stations. By searching for the optimal decomposition at a high level, we can unleash fast, local planners to solve the low-level segments with ease.

The Dual-Layer Architecture: Divide and Evolve

The foundational framework for this approach is Divide-and-Evolve (DAE), originally introduced by Schoenauer et al. in Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning. DAE splits the planning responsibility into a two-layer architecture:

  1. The Metaheuristic Layer (Evolutionary Search): An evolutionary algorithm operates in the space of problem decompositions. An individual in this population is not a plan, but a sequence of partial states (subgoals). The algorithm uses genetic operators like crossover and mutation to evolve the composition and order of these subgoals.
  2. The Base Planner Layer (Local Search): An embedded classical planner takes consecutive subgoals from an evolved sequence and attempts to find valid action sequences to bridge them. The fitness of a subgoal sequence is determined by the quality (such as the total time or makespan) of the complete plan generated by concatenating these local sub-solutions.
[Initial State] -> (Subgoal 1) -> (Subgoal 2) -> [Goal State]  <-- Evolved by Metaheuristic
       |              |              |              |
       +--- Local ----+--- Local ----+--- Local ----+          <-- Solved by Base Planner
            Plan 1         Plan 2         Plan 3

As Bibaï et al. demonstrated in $DAE_X$, this metaheuristic wrapper can take a fast but otherwise "greedy" local planner and make it competitive with state-of-the-art systems. It shifts the burden of long-horizon exploration away from action-space search and into the more abstract space of state milestones.

Why It Works: Reducing Planning Width

To understand why this shift works so effectively, we can look to the theoretical foundations of automated planning. In General Policies, Subgoal Structure, and Planning Width, Bonet et al. formalized how problem difficulty scales using the concept of planning width.

Many classical planning problems have an unmanageably high or unbounded planning width when processed monolithically, meaning a planner must consider huge combinations of variables simultaneously to guarantee a solution. However, the authors showed that by introducing "sketches"—structured sequences of subgoals—a problem with high width can be partitioned into a series of subproblems that each possess a strictly bounded, low width. Because low-width problems can be solved in polynomial time, state decomposition fundamentally changes the computational complexity class of the task at hand.

Pruning the Subgoal Space

We cannot simply choose arbitrary states as subgoals; a poorly chosen milestone might be physically impossible to reach or might create a dead-end that prevents the planner from ever reaching the final goal.

To prevent the evolutionary search from wasting time on invalid decompositions, Bibaï et al. injected domain-independent planning heuristics directly into the subgoal generation process in An Evolutionary Metaheuristic for Domain-Independent Satisficing Planning. By utilizing classical heuristics like $h^1$, the system estimates the earliest possible time specific state components (atoms) can appear and actively prunes mutually exclusive or contradictory atoms.

An alternative strategy involves building subgoals dynamically. In Incremental Heuristic Search for Planning with Temporally Extended Goals and Uncontrollable Events, Botea et al. proposed an incremental search algorithm that decomposes complex temporal logic goals into a sequence of cumulative subgoals. The planner progressively satisfies an increasing subset of constraints, building upon prior partial solutions while retaining the ability to backtrack if a local solution inadvertently blocks the global goal.

Unlocking Multi-Objective Planning

One of the most powerful advantages of state decomposition is its natural affinity for multi-objective optimization. In real-world scenarios, we rarely want just any plan; we want a plan that balances conflicting objectives, such as minimizing execution time while minimizing financial cost or risk.

Tracking multiple objectives across a massive, monolithic action-search tree is computationally devastating. State decomposition elegantly bypasses this. As Schoenauer et al. demonstrated in Multi-objective AI Planning: Comparing Aggregation and Pareto Approaches, the evolutionary layer can maintain a population representing a Pareto front of candidate subgoal sequences.

The underlying local planner doesn't need to know anything about multi-objective trade-offs; it remains a simple, single-objective solver. Yet, by evolving the milestones themselves to optimize different trade-offs, the overall system can discover a diverse set of globally Pareto-optimal plans. This capability allows the framework to scale successfully to massive, highly constrained logistics benchmarks, as shown by Quemy et al. in Solving Large MultiZenoTravel Benchmarks with Divide-and-Evolve.

Key Foundational Work

Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning (2006) — contributed 2 concept elements to this direction.
DAE: Planning as Artificial Evolution -- (Deterministic part) (2008) — contributed 2 concept elements to this direction.
Divide-and-Evolve : une nouvelle méta-heuristique pour la planification temporelle indépendante du domaine (2006) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_incremental_goal_decomposition_b1c82552,
  title = {incremental goal decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/incremental-goal-decomposition/rdr_b1c82552cff9486bbaed3bf265ec3e85},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_incremental_goal_decomposition_b1c82552_v1,
  title = {incremental goal decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/incremental-goal-decomposition/rdr_b1c82552cff9486bbaed3bf265ec3e85/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake