TL;DR
This paper introduces quantitative dominance, a novel approach to pruning states in optimal planning that goes beyond simple "better or worse" comparisons. By measuring how much better one state is than another, it enables more aggressive pruning and a new "action selection" strategy that significantly speeds up planning.
What Problem Does This Paper Address?
Classical AI planners often struggle with the sheer size of the search space. To tackle this, they employ "pruning" techniques to eliminate redundant or suboptimal states and actions. Dominance pruning is a powerful method where a state s is pruned if another state t is found that is "at least as good" in terms of reaching the goal. However, this qualitative "yes/no" comparison is limited. It can't distinguish between states that are only slightly better and those that are significantly closer to the goal, nor can it leverage information when no strict dominance exists. This paper aims to overcome these limitations by introducing a quantitative measure of dominance.
Methods
The core contribution is the generalization of qualitative dominance to a quantitative function, D(s, t), which measures "by how much" state t dominates state s. This function provides more nuanced information:
D(s, t) > 0:tis strictly closer to the goal thans.D(s, t) < 0:tis not strictly closer, but the negative value bounds the difference in goal distance.D(s, t) = 0:tis at least as close ass.
This quantitative measure is integrated into a "Quantitative Compositional LD Simulation" framework, which extends previous label-dominance simulation methods. The paper also introduces:
- Quantitative Dominance Relation:
s <_C tifD(s, t) >= C, allowing for flexible pruning thresholds. - Action Selection Pruning: A novel technique where if a state
shas an applicable actionasuch thatD(s, s[a]) >= c(a)(meanings[a]is sufficiently better thansgiven the action cost), thenais the only action considered froms. This drastically reduces branching.
Datasets
The paper evaluates its methods on a comprehensive set of benchmark domains from the International Planning Competition (IPC'98 – IPC'14). These include domains like Airport, Driverlog, Floortile, Gripper, Logistics, Miconic, OpenStack, ParcPrint, Rovers, Satellite, Sokoban, Tidybot, and Woodwork. No new benchmarks were introduced.
Key Insights and Ideas
- Beyond "Good Enough": The most significant insight is that quantifying dominance provides much richer information than a binary "better/worse" relation. This allows for more aggressive pruning and the discovery of finer-grained relationships between states.
- Action Selection is Powerful: The "action selection" pruning strategy, enabled by quantitative dominance, is a game-changer. By identifying a single "best" action from a state, it can reduce the branching factor to one, dramatically simplifying the search.
- Complementarity: Quantitative dominance, especially through action selection, is highly complementary to existing pruning methods (like qualitative dominance and partial-order reduction). Combining them yields superior results.
- Trading Off Dominance and Cost: The quantitative measure allows for trading off dominance information with state costs (
g-values). This is crucial for heuristics-based search, where a state with a slightly higherg-value might still be pruned if it's significantly closer to the goal according to the dominance function.
Key Results
- Reduced Search Space: Quantitative dominance pruning, particularly with action selection, significantly reduces the number of expanded states. In experiments, it achieved reductions of "several orders of magnitude" compared to baselines.
- Improved Planner Performance: This reduction in search space directly translates to much faster planning times. For example, action selection pruning solved 128 more instances than the blind search baseline and 61 more with the LM-cut heuristic.
- Coarser Relations: Quantitative dominance can discover coarser relations than qualitative methods, leading to more effective pruning in domains where qualitative dominance offers little benefit (e.g., Scanalyzer).
- Action Selection Efficiency: Action selection pruning is shown to be highly effective with very low overhead, making it a practical addition to planners.
Limitations and Future Work
- Computational Overhead: While action selection pruning has low overhead, computing the full quantitative dominance function can be computationally expensive. The paper notes that approximations might be necessary for some domains.
- Approximation Trade-offs: The paper explored approximations for quantitative dominance (e.g.,
D+which disables T-labels) and found that while some approximations are useful, fully exploiting quantitative dominance can sometimes be too costly. - Future Work: The authors suggest exploring further trade-offs between pruning power and overhead, potentially by using dominance-based methods for irrelevance pruning. They also highlight the potential for combining quantitative dominance with other heuristic or learning methods.
Summary updated