• Medientyp: E-Artikel
  • Titel: A Best-First Search Algorithm for FOND Planning and Heuristic Functions to Optimize Decompressed Solution Size
  • Beteiligte: Messa, Frederico; Grahl Pereira, André
  • Erschienen: Association for the Advancement of Artificial Intelligence (AAAI), 2023
  • Erschienen in: Proceedings of the International Conference on Automated Planning and Scheduling
  • Sprache: Nicht zu entscheiden
  • DOI: 10.1609/icaps.v33i1.27205
  • ISSN: 2334-0843; 2334-0835
  • Entstehung:
  • Anmerkungen:
  • Beschreibung: <jats:p>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.</jats:p>