TL;DR
This paper introduces "dominance" techniques for satisficing AI planning, aiming to find any valid plan quickly, not necessarily the optimal one. They propose a new way to define dominance that guarantees completeness, meaning the search won't get stuck in dead ends, and show how this can be used to improve existing search algorithms like Enforced Hill-Climbing.
What Problem Does This Paper Address?
In AI planning, the goal is to find a sequence of actions to get from a starting state to a goal state. There are two main types of planning: optimal planning (finding the shortest or cheapest plan) and satisficing planning (finding any valid plan as quickly as possible). While dominance techniques have been successful in reducing the search space for optimal planning by pruning "dominated" states (states that are provably worse than others), applying them directly to satisficing planning is tricky. The core challenge is that in satisficing planning, we don't care about the cost of the plan, only its existence. This means the traditional definition of dominance based on goal distance isn't directly applicable, and naive application could lead to pruning all possible solutions, making the planner incomplete.
Methods
The authors redefine dominance for satisficing planning, shifting the focus from optimality guarantees to completeness guarantees. Instead of states being "closer" to the goal, a state might dominate another if it has achieved more "serializable sub-goals." They introduce a method to automatically discover these dominance relations by serializing the planning task's components (represented as Labelled Transition Systems or LTSs).
Key techniques include:
- Satisficing Dominance Relation: A preorder relation that approximates a descending and dead-end aware heuristic. This ensures that if a state is pruned, it's because a "better" state exists, and importantly, that unsolvable states don't dominate solvable ones.
- Dominance-Based Enforced Hill-Climbing (DEHC): They adapt the Enforced Hill-Climbing (EHC) algorithm. Instead of restarting EHC based on a heuristic value falling below the initial state's heuristic, DEHC restarts when it finds a state that dominates the current initial state according to their new satisficing dominance relation. This makes EHC complete.
- Serialized Dominance Relations: A novel method to compute dominance relations by ordering the LTSs that represent different aspects of the planning problem. This allows for dominance to be established based on progress in certain aspects (e.g., visiting more locations) without requiring other aspects (e.g., robot position) to be optimal.
- Recursive and Positive T-Labels: Extensions to the concept of "T-labels" (transitions that only affect one part of the state) to find coarser dominance relations, making the techniques more applicable.
Datasets
The experiments were conducted on instances from the International Planning Competitions (IPC'98 – IPC'14), specifically using benchmarks where dominance techniques were expected to have a non-negligible effect.
Key Insights and Ideas
- Dominance for Completeness, Not Just Optimality: The core insight is that dominance can be adapted to guarantee that a solution will be found (completeness) in satisficing planning, even if it doesn't guarantee optimality. This is achieved by redefining dominance to focus on preserving solvability rather than minimizing cost.
- Serializing Sub-problems is Key: The idea of "serialized dominance" is powerful. It allows for progress in one part of the problem (e.g., visiting more cells) to dominate a state where less progress has been made, even if the robot's position isn't ideal. This is crucial for problems with mixed complexity sub-goals.
- Dominance as a Complement to Heuristics: While heuristics guide search towards goals, dominance relations can identify states that are fundamentally "better" in a way that heuristics might miss, especially in complex or mixed-difficulty problems. DEHC can leverage this to escape plateaus and ensure progress.
- Dominance Relations are More Expressive than Heuristics: Dominance relations are partial preorders, meaning they can capture relationships between states that total preorders (like heuristics) cannot. This allows for more nuanced comparisons and potentially more effective pruning.
Key Results
The paper demonstrates that DEHC, guided by their new dominance relations, significantly improves performance on certain IPC domains compared to a baseline GBFS with the hFF heuristic. Specifically:
- Improved Coverage: DEHC with serialized dominance relations shows notable improvements in coverage on domains where dominance is effective, both in terms of restarting the search and pruning states.
- DEHC vs. Baseline: DEHC consistently outperforms the baseline GBFS, especially in domains where dominance pruning is beneficial.
- DEHC vs. State-of-the-Art: While DEHC shows promise, it still lags behind highly optimized planners like LAMA and Mercury on many benchmarks. However, the paper highlights specific scenarios (like their running example with mixed sub-goal complexity) where DEHC's approach is more robust.
Limitations and Future Work
- Preprocessing Overhead: The computation of dominance relations can be computationally expensive, especially for large planning tasks. The authors note that their implementation was not able to finish preprocessing for the largest tasks in some domains.
- Synergy with Heuristics: The current DEHC implementation doesn't fully exploit the synergy between dominance relations and heuristics. The authors suggest that heuristics could be made aware of dominance relations to improve performance.
- Finding Stronger Dominance: The authors believe that considering more than one variable at a time when computing dominance could lead to stronger and more effective relations.
- Automatic Discovery of Serializability: While serialized dominance is a powerful concept, there's no automatic way to prove that a set of sub-goals is serializable. Developing such methods would be valuable.
Summary updated