TL;DR
This paper introduces Graphplan, a novel AI planning algorithm that leverages a "planning graph" data structure to efficiently find optimal plans. By analyzing this graph, Graphplan significantly outperforms existing planners on various benchmarks, offering a new perspective on the planning problem.
What Problem Does This Paper Address?
Traditional AI planning systems, particularly those using STRIPS-like domains (where actions have preconditions and effects), often struggle with computational complexity. Finding a plan, especially an optimal one (shortest sequence of actions), can be extremely time-consuming. Existing approaches like total-order planners (e.g., Prodigy) and partial-order planners (e.g., UCPOP) have their own limitations. Total-order planners can be inefficient due to making too many commitments too early, while partial-order planners can suffer from exploring too many possibilities. The challenge is to develop a planning method that is both efficient and capable of finding optimal or near-optimal plans.
Methods
The core innovation is the Planning Graph Analysis (PGA) paradigm. This involves constructing and analyzing a compact structure called a Planning Graph.
- Planning Graph: This is not a graph of world states but rather a layered structure representing propositions and actions over discrete time steps. It alternates between proposition levels (what might be true at time t) and action levels (what actions might be executable at time t).
- Construction: The graph is built incrementally, adding action and proposition levels. Crucially, it incorporates "no-op" actions to maintain propositions across time steps and uses "mutual exclusion" relations to identify actions or propositions that cannot coexist in a valid plan.
- Graphplan Algorithm: The planner, Graphplan, first constructs this planning graph. Then, it searches this graph for a valid plan. The search is backward-chaining, starting from the goals and working backward through the graph to find a sequence of actions that satisfy the initial conditions.
- Mutual Exclusion: A key aspect is identifying and propagating mutual exclusion relations between actions and propositions. This significantly prunes the search space by eliminating impossible combinations.
- Completeness Test: The paper also describes a method to make Graphplan complete, ensuring it will eventually report failure if no plan exists, by detecting when the planning graph "levels off."
Datasets
The paper evaluates Graphplan on the following domains:
- Rocket Domain: A domain involving moving cargo with rockets between locations.
- Flat-tire world: A "natural" domain described by Stuart Russell.
- Artificial domains: Including "Link-repeat," "D'S¹," and "D'S²" domains, defined in previous work (Veloso & Blythe, 1994; Barrett & Weld, 1994).
No new benchmarks were introduced; rather, existing ones were used for comparison.
Key Insights and Ideas
- Planning Graphs as a Search Aid: The planning graph provides a structured, efficient way to organize and maintain search information, reminiscent of shortest-path algorithms.
- "Over-committing" for Efficiency: Counter-intuitively, by fixing actions to specific time steps (a form of commitment), Graphplan gains valuable search information that allows it to quickly identify dead ends and backtrack.
- Mutual Exclusion is Crucial: The propagation and use of mutual exclusion relations are identified as the primary driver of Graphplan's efficiency, drastically reducing the search space.
- Parallel Plans are Sensible: The plans generated by Graphplan are partially-ordered, allowing independent actions within a time step to be executed in parallel. These plans are described as "sensible" and often correspond to intuitive solutions.
- Goal Independence: Graphplan is empirically shown to be less sensitive to the order of goals in a planning task compared to traditional planners.
Key Results
- Performance: Graphplan significantly outperforms Prodigy and UCPOP on the tested domains, particularly the rocket domain and the flat-tire problem.
- Speed: In the rocket domain, Graphplan's running time is largely unaffected by the number of goals. For the flat-tire problem, it finds solutions in 1-13 seconds, whereas UCPOP and Prodigy failed to find solutions within 10 minutes on standard goal orderings.
- Plan Quality: Graphplan consistently finds shortest-possible partial-order plans.
- Efficiency Factors: The paper attributes Graphplan's efficiency to:
- Mutual exclusion propagation.
- Consideration of parallel plans.
- Memoization of unsolvable goal sets.
- Low-level costs due to pre-computing the planning graph.
Limitations and Future Work
- Completeness: The basic algorithm is "weakly complete" (it can prove no plan exists up to a certain length). The paper introduces a modification to achieve full completeness, ensuring it halts if no plan exists.
- Goal Ordering: While less sensitive than other planners, Graphplan currently makes no attempt to order goals within a time step in an advantageous way. The authors are experimenting with standard heuristics for this.
- Mutual Exclusion Discovery: The rules for identifying mutual exclusion relations are not guaranteed to find all such relationships, though they are effective in practice.
- Future Work: The authors suggest exploring heuristics for ordering goals within a time step and further investigating the properties of planning graphs.
Summary updated