Abstract
The merge-and-shrink framework is a powerful tool to construct state space abstractions based on factored representations. One of its core applications in classical planning is the construction of admissible abstraction heuristics. In this paper, we develop a compositional theory of merge-and-shrink in the context of probabilistic planning, focusing on stochastic shortest path problems (SSPs). As the basis for this development, we contribute a novel factored state space model for SSPs. We show how general transformations, including abstractions, can be formulated on this model to derive admissible and/or perfect heuristics. To formalize the merge- and-shrink framework for SSPs, we transfer the fundamental merge-and-shrink transformations from the classical setting: shrinking, merging, and label reduction. We analyze the formal properties of these transformations in detail and show how the conditions under which shrinking and label reduction lead to perfect heuristics can be extended to the SSP setting.
Original language | English |
---|---|
Title of host publication | Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling |
Number of pages | 9 |
Publisher | AAAI Press |
Publication date | 2023 |
Pages | 203-211 |
ISBN (Electronic) | 978-1-57735-881-7 |
DOIs | |
Publication status | Published - 2023 |
Event | 33rd International Conference on Automated Planning and Scheduling, ICAPS 2023 - Prague, Czech Republic Duration: 8 Jul 2023 → 13 Jul 2023 |
Conference
Conference | 33rd International Conference on Automated Planning and Scheduling, ICAPS 2023 |
---|---|
Country/Territory | Czech Republic |
City | Prague |
Period | 08/07/2023 → 13/07/2023 |
Series | Proceedings International Conference on Automated Planning and Scheduling, ICAPS |
---|---|
Number | 1 |
Volume | 33 |
ISSN | 2334-0835 |
Bibliographical note
Publisher Copyright:Copyright © 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Keywords
- Uncertainty and stochasticity in planning and scheduling
- Heuristic search
- Theoretical foundations of planning and scheduling