Implicit abstraction heuristics
From MaRDI portal
Publication:3055801
DOI10.1613/JAIR.3063zbMATH Open1205.68377arXiv1401.3853OpenAlexW2150289807WikidataQ129520526 ScholiaQ129520526MaRDI QIDQ3055801FDOQ3055801
Authors:
Publication date: 10 November 2010
Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1401.3853
Recommendations
Cited In (15)
- ``Distance? Who cares? Tailoring merge-and-shrink heuristics to detect unsolvability
- Analysing approximability and heuristics in planning using the exponential-time hypothesis
- 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
- Title not available (Why is that?)
- 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)
