TL;DR
This paper introduces "A-traps," a novel concept that combines existing dead-end detectors with the idea of "traps" in AI planning. This allows for more effective pruning of unsolvable states during search. Crucially, the authors also present methods for learning these A-traps online during the search process, significantly improving planning performance, especially in resource-constrained domains.
What Problem Does This Paper Address?
Classical AI planning aims to find a sequence of actions to reach a goal state from an initial state. While much research focuses on solvable problems, proving the unsolvability of a planning task is equally important in many real-world scenarios (e.g., oversubscription planning, model checking). A key technique for this is using "dead-end detectors" (Δ) which identify states from which no goal can be reached. These detectors prune the search space.
However, existing dead-end detectors often suffer from "transitivity": if a state is a dead-end, all states reachable from it are also considered dead-ends. This can lead to redundant pruning and missed opportunities for learning. Furthermore, prior work on "traps" (sets of states from which escape is impossible) was typically done offline, before the search even begins. This paper addresses the limitations of transitivity and offline analysis by proposing a way to combine dead-end detectors with traps and, more importantly, to learn these traps dynamically during the search.
Methods
The core contribution is the introduction of A-traps. An A-trap is a set of non-goal states where any action taken from a state within the trap leads to either another state within the trap or a state already identified as a dead-end by a given dead-end detector Δ. This is a generalization of the original "trap" concept, allowing for synergy with existing Δ detectors.
The paper then proposes two main ways to leverage A-traps:
- Offline A-trap Representation: This involves identifying compact representations (sets of partial states, Θ) of A-traps before the search begins. This is achieved by adapting existing algorithms for trap computation, but crucially, incorporating the Δ detector into the process. This allows the trap to be complementary to Δ, rather than forcing Δ to subsume the trap.
- Online A-trap Learning: This is the more significant contribution. The authors propose a method to learn A-trap representations (Θ) dynamically during search. When the search encounters states that form an A-trap (but are not yet covered by the current Θ), the algorithm attempts to generalize this knowledge into a more compact representation. This learned Θ is then used alongside the original Δ detector to prune further states. This online learning approach allows the system to adapt to the specific problem instance and the knowledge gained during the search.
Datasets
The experiments were conducted on several benchmark suites:
- UIPC'16 benchmarks: A standard set of planning problems used in the Unsolvability International Planning Competition.
- Unsolvable benchmark collection by Hoffmann et al. [2014]: A collection of unsolvable planning tasks.
- Resource-constrained benchmarks by Nakhost et al. [2012]: Scaled versions of existing benchmarks with limited resources, designed to make planning harder.
The paper notes that in 9 instances of the "Diagnosis" domain, conditional effects were introduced during FD's grounding procedure, which were not supported by the tested configurations, and these instances were excluded from the experiments.
Key Insights and Ideas
- Synergy between Dead-End Detectors and Traps: The core insight is that traps don't need to be "harder" than dead-end detectors; they can be complementary. A-traps allow for a more nuanced pruning strategy by leveraging the strengths of both.
- Online Learning is Key: The most impactful finding is that learning A-traps during the search (online) dramatically improves performance. This is because the learned traps are tailored to the specific problem instance and the knowledge gained during exploration, unlike static offline methods.
- Generalization is Crucial: The online learning method focuses on generalizing discovered traps into compact representations. This generalization is what allows the learned knowledge to prune states not yet visited by the search, leading to significant speedups.
- Transitivity is a Bottleneck: The paper highlights how the transitivity of traditional dead-end detectors limits their ability to learn and synergize. A-traps overcome this by not requiring the trap to subsume the dead-end detector's findings.
Key Results
- Improved Coverage: Online A-trap learning, even with a trivial dead-end detector (Δ⁰), significantly improves the coverage (number of unsolvable instances solved) across various benchmark domains.
- State-of-the-Art Performance: The proposed online A-trap learning approach, especially when combined with existing dead-end detectors like PDB heuristics, achieves state-of-the-art performance on resource-constrained domains.
- Significant Speedups: Figure 3(c) demonstrates that online A-trap learning can lead to substantial reductions in search effort (number of states visited) and runtime, with some instances showing speedups of several orders of magnitude.
- Offline A-traps are Less Effective: While offline A-trap computation shows some benefits, it generally cannot compete with state-of-the-art methods on its own. The real power lies in the online learning aspect.
- Synergistic Effects: The paper reports synergistic effects where the combination of A-trap learning with specific dead-end detectors solves instances that neither component could solve alone.
Limitations and Future Work
- Generalization Step Optimization: The authors suggest that the generalization step in online learning could be further optimized for computational cost and generalization power.
- Exploiting Partial Search Knowledge: A major open question is how to effectively exploit search knowledge that falls short of fully identifying dead-end components.
- Resource Limits: Designing learning methods that are specifically targeted at resource limits (e.g., time or memory constraints) is identified as a promising future direction.
- Offline Trap Computation Overhead: The paper notes that offline A-trap construction can incur overhead from evaluating the dead-end detectors, which can sometimes be detrimental.
- Domain-Specific Performance: While generally beneficial, the performance of A-trap learning can vary across domains, with some domains showing less improvement or even slight degradation.
Summary updated