TL;DR
This paper introduces a novel local search approach for AI planning, leveraging planning graphs to efficiently find solutions to complex problems that often stump traditional systematic planners. By combining greedy local search with systematic repair mechanisms, their system, GPG, achieves significant speedups and finds plans with fewer actions on challenging benchmarks.
What Problem Does This Paper Address?
Domain-independent AI planning, the task of finding a sequence of actions to achieve a goal from an initial state, is notoriously difficult. While systematic search algorithms theoretically guarantee finding a solution if one exists, they often fail in practice because the search space is too vast to explore. Existing methods, even those based on powerful techniques like planning graphs (e.g., Graphplan, IPP), struggle with problems that require exploring a huge number of states. This paper tackles this "combinatorial explosion" by proposing an alternative: local search. Local search methods are incomplete (they might not find a solution even if one exists), but they can be remarkably efficient in practice, often solving problems that are intractable for systematic approaches. The authors aim to bridge this gap by applying local search to the planning graph framework, a representation that has proven effective for planning.
Methods
The core contribution is a new local search method for planning, built upon the "planning through planning graph analysis" approach. Instead of exhaustively searching the entire planning graph, the authors define the search space as subgraphs of the planning graph that represent partial plans.
Here's a breakdown of their approach:
- Planning Graphs: The foundation is the planning graph, a layered graph representing facts and actions over time. Level 0 contains initial facts, and subsequent levels alternate between actions and facts, showing preconditions and effects.
- Action Subgraphs: The search operates on "action subgraphs," which are subsets of the planning graph. An action subgraph is valid if all its preconditions and effects are consistent with the actions it includes.
- Local Search: The search starts with an initial action subgraph (a partial plan) and iteratively "improves" it by adding or removing actions. This process is guided by an objective function that measures the "quality" of the current partial plan, aiming to minimize unsatisfied preconditions, mutual exclusion violations between actions, and unsupported goals.
- Heuristics: Three specific local search heuristics are introduced:
- Walkplan: Inspired by stochastic local search (like Walksat), it uses a greedy bias to minimize constraint violations but incorporates a random walk to escape local minima.
- Tabuplan: Employs a "tabu list" to prevent recently performed actions (insertions/deletions) from being immediately reversed, helping to avoid cycling.
- T-Walkplan: Similar to Tabuplan but uses the tabu list to penalize certain moves rather than outright forbidding them, allowing more flexibility.
- Combining Local and Systematic Search: Recognizing the strengths of both approaches, the authors propose two hybrid methods:
- Alternating Search: Systematically search the planning graph until a time limit is reached, then switch to local search, and repeat. This leverages systematic search for provable unsolvability and local search for speed.
- Local Search + Plan Adjustment: Use local search to quickly find a "quasi-solution" (a plan with only a few flaws). Then, a systematic search algorithm called
ADJUST-PLANis used to repair these flaws and produce a valid solution.ADJUST-PLANintelligently expands the search window if initial repair attempts fail.
Datasets
The paper evaluates their methods on several standard AI planning domains: Rocket, Logistics, Gripper, Blocks-world, Tyre-world, TSP, Fridge-world, and Monkey-world. These domains and their problem formalizations are noted as being available as part of the IPP package. No new benchmarks were introduced.
Key Insights and Ideas
- Local Search for Planning is Viable: The paper demonstrates that local search, often overlooked for planning due to its incompleteness, can be highly effective and outperform systematic methods on hard problems.
- Planning Graphs as a Search Space: Framing the search space as subgraphs of the planning graph provides a structured and semantically rich environment for local search.
- Hybridization is Powerful: Combining the speed of local search with the completeness guarantees of systematic search (via
ADJUST-PLANor alternating search) offers a robust approach that mitigates the weaknesses of each individual method. - Quasi-Solutions are Useful: The idea of finding "almost correct" plans with local search and then repairing them is a key insight. This is often faster than finding a perfect solution directly with local search or waiting for a systematic search to complete.
- Action Graph Semantics: The authors highlight that their direct manipulation of planning graph structures allows for more semantically rich search operators than methods that rely on SAT encodings, which can lose this information.
Key Results
- Speedup on Hard Problems: For problems that are difficult for systematic planners like IPP and Graphplan, the local search heuristics (Walkplan, Tabuplan, T-Walkplan) achieved speedups of up to four orders of magnitude.
- Competitive on Easy Problems: For problems that are easy for systematic planners, the local search methods performed competitively, often finding solutions within a few seconds.
- GPG Performance: The system GPG, which combines local search and plan adjustment, was significantly faster than Blackbox (a planner using SAT solvers and local search) on many problems.
- Plan Quality: In terms of the number of actions in the plan, GPG's solutions were generally comparable to or better than those found by IPP.
- Plan Adaptation Efficiency: The
ADJUST-PLANalgorithm for repairing plans was significantly more efficient than complete replanning with IPP, often by orders of magnitude.
Limitations and Future Work
- Incompleteness of Local Search: The authors acknowledge that local search methods are inherently incomplete and cannot prove the absence of a solution. This is addressed by their hybrid approaches.
- Optimality: The local search methods do not guarantee optimal plans (e.g., minimum number of time steps). While they mention an attempt to optimize adjusted plans, this process is omitted for brevity.
- Parameter Tuning: While their hybrid approach is noted as not being overly sensitive to parameter settings, the initial local search heuristics might still benefit from careful tuning.
- Future Work: The authors suggest further experimental analysis, exploring additional heuristics for local search and plan adjustment, and investigating the combination of local search and plan adjustment for plan adaptation tasks. They also mention the potential for more semantically rich search operators based on graph structure.
Summary updated