Implicit abstraction heuristics
From MaRDI portal
Publication:3055801
Abstract: State-space search with explicit abstraction heuristics is at the state of the art of cost-optimal planning. These heuristics are inherently limited, nonetheless, because the size of the abstract space must be bounded by some, even if a very large, constant. Targeting this shortcoming, we introduce the notion of (additive) implicit abstractions, in which the planning task is abstracted by instances of tractable fragments of optimal planning. We then introduce a concrete setting of this framework, called fork-decomposition, that is based on two novel fragments of tractable cost-optimal planning. The induced admissible heuristics are then studied formally and empirically. This study testifies for the accuracy of the fork decomposition heuristics, yet our empirical evaluation also stresses the tradeoff between their accuracy and the runtime complexity of computing them. Indeed, some of the power of the explicit abstraction heuristics comes from precomputing the heuristic function offline and then determining h(s) for each evaluated state s by a very fast lookup in a database. By contrast, while fork-decomposition heuristics can be calculated in polynomial time, computing them is far from being fast. To address this problem, we show that the time-per-node complexity bottleneck of the fork-decomposition heuristics can be successfully overcome. We demonstrate that an equivalent of the explicit abstraction notion of a database exists for the fork-decomposition abstractions as well, despite their exponential-size abstract spaces. We then verify empirically that heuristic search with the databased" fork-decomposition heuristics favorably competes with the state of the art of cost-optimal planning.
Recommendations
Cited in
(15)- Analysing approximability and heuristics in planning using the exponential-time hypothesis
- ``Distance? Who cares? Tailoring merge-and-shrink heuristics to detect unsolvability
- Optimal Sokoban solving using pattern databases with specific domain knowledge
- Optimal admissible composition of abstraction heuristics
- Tunneling and decomposition-based state reduction for optimal planning
- Counterexample-guided Cartesian abstraction refinement for classical planning
- On the complexity of planning for agent teams and its implications for single agent planning
- Symbolic perimeter abstraction heuristics for cost-optimal planning
- A general theory of additive state space abstractions
- Set-structured and cost-sharing heuristics for classical planning
- scientific article; zbMATH DE number 4166913 (Why is no real title available?)
- Efficient symbolic search for cost-optimal planning
- Landmark-enhanced abstraction heuristics
- Saturated cost partitioning for optimal classical planning
- Behavioral abstraction is hiding information
This page was built for publication: Implicit abstraction heuristics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3055801)
