When faced with a massive, high-dimensional state space, a standard algorithmic response is to divide and conquer. Whether in classical automated planning, multi-agent pathfinding, or reinforcement learning, breaking a long-horizon problem into a sequence of smaller subgoals makes an otherwise intractable search space manageable.
However, this computational savings comes with a hidden cost: concatenation-induced inefficiency. While decomposing a problem allows an agent to find a valid solution quickly, sequentially stitching together locally optimal choices rarely yields a globally optimal plan. Understanding why this suboptimality occurs—and why it is so difficult to avoid—is a central focus of recent research across planning paradigms.
Recursive Optimality vs. Global Optimality
The core reason sequential decomposition fails to achieve global efficiency lies in the concept of recursive optimality. In a hierarchical framework, an agent is tasked with solving individual sub-problems perfectly. However, because the agent optimizes each segment in isolation, its behavior becomes myopic.
As explained by David Kuric et al. in Planning with a Learned Policy Basis to Optimally Solve Complex Tasks, a recursively optimal agent fails to account for how its local choices impact the global path. For example, the absolute best way to achieve Subgoal A might leave the agent in a state or configuration that makes reaching Subgoal B incredibly inefficient.
This phenomenon is clearly visible in robotics and motor skill acquisition. Visak C. V. Kumar et al. studied this in Expanding Motor Skills using Relay Networks, demonstrating that chaining specialized, locally optimal controllers together does not guarantee globally optimal end-to-end behavior. The sequence of handoffs between controllers often prioritizes local success over the most efficient overall trajectory for the complete task.
The Blind Spots of Greedy Chaining
Why can't we simply look ahead to avoid these bad handoffs? In sequential multi-goal search strategies, subproblems are typically solved one after another. This "greedy chaining" introduces a subtle but severe blind spot: it misses opportunities for early, strategic adjustments.
Global Search: [Start] -----------------------------> [Goal A] -------> [Goal B] (Shortest Path)
Greedy Chain: [Start] ===> [Local Optima Goal A] ------------> [Goal B] (Longer Path)
In Fools Rush in Where Angels Fear to Tread in Multi-Goal CBS, Grigorios Mouratidis and Bernhard Nebel exposed this flaw within multi-agent pathfinding. When an algorithm solves a series of single-goal problems sequentially, agents rush toward their immediate goals. By doing so, they miss early deviations that would prevent downstream conflicts or detours. The authors demonstrate that the gap between these chained solutions and the true global optimum can be arbitrarily large, making the suboptimality both dangerous and difficult to detect.
This issue is not unique to multi-agent settings. In long-horizon trajectory planning, Bo Liu et al. noted in Team Orienteering Coverage Planning with Uncertain Reward that an optimal plan for a single iteration rarely contributes to the overall optimal plan across all iterations, even when local costs are perfectly known.
Feasibility vs. Cost Optimization
Another structural driver of suboptimality is that decomposition frameworks are frequently designed to optimize for feasibility rather than cost. When a problem is too complex to solve holistically, the primary goal of decomposition is simply to find any valid path.
For instance, Michael Aichmüller and Hector Geffner explored this trade-off in Sketch Decompositions for Classical Planning via Deep Reinforcement Learning. They pointed out that when learning problem decompositions, agents optimize for subgoals that simplify the problem structure. However, because the framework does not explicitly consider the actual cost of solving those decomposed sub-problems, the final plan lengths remain suboptimal.
We see a similar trade-off when planners exploit problem symmetries. Mohammad Abdulaziz et al. showed in Exploiting Symmetries by Planning for a Descriptive Quotient that solving a compressed "quotient space" and stitching the resulting sub-plans together drastically reduces search time. Yet, because the search is confined to this abstract, reduced space, the concatenated path is highly unlikely to be the shortest path available in the original, uncompressed state space. As Marc Schoenauer et al. summarized in Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning, the final plan duration is sacrificed as a direct trade-off for discovering a feasible solution in large-scale instances.
A Universal Challenge Across Planning Paradigms
The tension between local efficiency and global optimality manifests across entirely different engineering domains:
- Classical & Factored Planning: Breaking down complex searches into independent state variables or individual capabilities improves scalability and memory efficiency, but it causes plan quality degradation. This has been documented from early work on Domain Transition Graphs by Peter Gregory et al. (Exploiting Path Refinement Abstraction in Domain Transition Graphs) to smart-home action planning by Jongjin Kim et al. (Dependency-aware action planning for smart home). As proved by Ronen I. Brafman and Carmel Domshlak in Factored Planning: How, When, and When Not, factoring reduces exponential computational complexity but inherently struggles to satisfy applications requiring global sequential optimality.
- Large Language Models (LLMs): Even when modern language models are used as planners, they fall into the same trap. Swarnadeep Saha et al. demonstrated in System 1.x: Learning to Balance Fast and Slow Planning with Language Models that while modular decomposition strategies help LLMs avoid reasoning errors, ensuring that these local planning decisions align with global optimality remains a significant hurdle, frequently resulting in valid paths that are longer than necessary.
Ultimately, sequential policy suboptimality is a fundamental mathematical tax. When we break a global search problem into a chain of independent subgoals, we trade global awareness for computational feasibility. The ongoing challenge for the field is to design decomposition methods that can anticipate downstream costs without re-introducing the exponential complexity they were invented to avoid.
Key Foundational Work
Factored Planning: How, When, and When Not (2006) — contributed 2 concept elements to this direction.
Exploiting Path Refinement Abstraction in Domain Transition Graphs (2011) — contributed 1 concept elements to this direction.
Divide-and-Evolve: a New Memetic Scheme for Domain-Independent Temporal Planning (2006) — contributed 1 concept elements to this direction.