Is “Early Commitment” in Plan Generation Ever a Good Idea?

AAAI 1996

TL;DR

This paper argues that while "least-commitment" planning is generally beneficial, a purely passive approach to postponing decisions can lead to significant inefficiencies. The authors introduce "active postponement" and a system called Descartes that transforms planning into Constraint Satisfaction Problems (CSPs), enabling more proactive decision-making. They demonstrate that judicious early commitments can sometimes outperform purely least-commitment strategies, especially in complex domains.

What Problem Does This Paper Address?

Traditional Partial-Order Causal Link (POCL) planners often adopt a "least-commitment" strategy, delaying decisions like step ordering until absolutely necessary. However, they still make early commitments for other decisions, such as resolving threats or choosing operators. This raises the question: should we push the least-commitment principle even further, or are there situations where early commitment is actually beneficial? The paper identifies a key issue with existing planners: their "passive postponement" approach, where postponed decisions are essentially ignored until selected, can lead to generating many dead-end search paths. This happens because unresolvable flaws might not be detected until much later, after numerous irrelevant sub-plans have been explored. The authors aim to explore the trade-offs between full least-commitment and incorporating some early commitments to improve planning efficiency.

Methods

The core innovation is the concept of active postponement. Instead of passively deferring decisions, active postponement represents postponed decisions as constrained variables within a Constraint Satisfaction Problem (CSP). These variables have domains representing possible choices, and constraints capture the correctness criteria. A general-purpose constraint engine then enforces these constraints proactively.

The authors implemented this in the Descartes system. Planning problems are transformed into CSPs. The LC-Descartes algorithm embodies a fully least-commitment approach within this CSP framework. It iteratively refines a partial plan and its associated CSP. If a variable has an empty static domain, it signals failure. If a variable has an empty dynamic domain, it indicates a forced decision to add a new step to achieve a goal, triggering a "restricted expansion." If no variables have empty domains, the CSP solver is invoked. If the CSP solver fails, an "unrestricted expansion" is performed, adding new steps more broadly.

To investigate the benefits of early commitment, they developed EC-Descartes. This system behaves like LC-Descartes but deviates when LC-Descartes would perform an unrestricted expansion. Instead, EC-Descartes generates multiple successor nodes, each representing a different early commitment. Two versions are presented:

  • EC(1): Makes early commitments on action selection by choosing a dynamic domain variable with the smallest domain and creating two branches: one forcing a restricted expansion, the other committing to using an existing step.
  • EC(2): Similar to EC(1) but selects a static variable with the minimal domain size and splits its domain, akin to a "divide and conquer" CSP approach.

Datasets

The paper evaluates its approaches on:

  • Blocks World: Randomly generated problems with 3 to 16 blocks, using a single-action encoding. This domain was chosen to test the limits of LC-Descartes, as it simplifies planning significantly.
  • DIPART transportation planning domain: A set of nine problems used to compare LC-Descartes with EC(1) and EC(2).

Key Insights and Ideas

  • Passive postponement is inefficient: Ignoring postponed decisions until they are selected can lead to exploring vast numbers of dead-end sub-plans, especially when unresolvable flaws exist.
  • Active postponement is key: Representing postponed decisions as CSP variables allows for proactive constraint propagation and earlier detection of dead ends or forced decisions.
  • Full least-commitment has limits: While beneficial, a purely least-commitment approach (LC-Descartes) can become computationally prohibitive, requiring many "unrestricted expansions" in complex scenarios.
  • Judicious early commitment pays off: The EC-Descartes variants show that making strategic early commitments, particularly on action selection, can significantly improve performance by guiding the search more effectively and avoiding costly unrestricted expansions.
  • Trading "hard" nodes for "easy" nodes: Early commitments can be viewed as a strategy to exchange a single, difficult-to-solve node (under-constrained) for multiple, easier-to-solve nodes (where constraints force restricted expansions).

Key Results

  • UCPOP vs. LC-Descartes on Blocks World: LC-Descartes performed comparably to UCPOP on problems with half the number of blocks, suggesting that its fully least-commitment approach is more computationally intensive. For example, LC-Descartes could solve problems with up to 15 blocks, while UCPOP struggled beyond 8 blocks.
  • EC-Descartes vs. LC-Descartes on DIPART: EC(1) solved all nine problems, while EC(2) failed on three, and LC-Descartes failed on four, hitting a 600 CPU second limit. LC-Descartes required at least one unrestricted expansion for most problems, and failed when it needed a second. This highlights the advantage of early commitments in this domain.
  • Success of EC(1): EC(1), which makes early commitments on action selection, generally outperformed EC(2) and LC-Descartes, suggesting that this specific type of early commitment is particularly effective.

Limitations and Future Work

  • Unrestricted expansions are still a bottleneck: While EC-Descartes mitigates the need for unrestricted expansions, they can still occur and are computationally expensive.
  • Identifying the "right" early commitment: The paper suggests that finding more effective techniques for making early commitments is a crucial direction for future research. The EC(1) and EC(2) strategies are a step in this direction, but more sophisticated methods might be needed.
  • Generalizing early commitment: The current EC-Descartes focuses on specific types of early commitments. Future work could explore a broader range of commitment types and strategies.

Summary updated

BibTeX
@inproceedings{1996is,
  title = {{Is “Early Commitment” in Plan Generation Ever a Good Idea?}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure