Erschienen:
Association for the Advancement of Artificial Intelligence (AAAI), 2023
Erschienen in:
Proceedings of the International Conference on Automated Planning and Scheduling, 33 (2023) 1, Seite 277-285
Sprache:
Ohne Angabe
DOI:
10.1609/icaps.v33i1.27205
ISSN:
2334-0843;
2334-0835
Entstehung:
Anmerkungen:
Beschreibung:
In this work, we study fully-observable non-deterministic (FOND) planning, which models uncertainty through actions with non-deterministic effects. We present a best-first heuristic search algorithm called AND* that searches the policy-space of the FOND task to find a solution policy. We generalize the concepts of optimality, admissibility, and goal-awareness for FOND. Using these new concepts, we formalize the concept of heuristic functions that can guide a policy-space search. We analyze different aspects of the general structure of FOND solutions to introduce and characterize a set of FOND heuristics that estimate how far a policy is from becoming a solution. One of these heuristics applies a novel insight. Guided by them AND* returns only solutions with the minimal possible number of mapped states. We systematically study these FOND heuristics theoretically and empirically. We observe that our best heuristic makes AND* much more effective than the straightforward heuristics. We believe that our work allows a better understanding of how to design algorithms and heuristics to solve FOND tasks.