2022/04/08 by Ramon Fraga Pereira, Pereira, Ramon Fraga, André G. Pereira +5
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Formal Methods in Verification #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2204.04322
openalex publication_date 2022/04/08 · openalex created_date 2022/04/15 · openalex updated_date 2026/07/28
Fully Observable Non-Deterministic (FOND) planning models uncertainty through actions with non-deterministic effects. Existing FOND planning algorithms are effective and employ a wide range of techniques. However, most of the existing algorithms are not robust for dealing with both non-determinism and task size. In this paper, we develop a novel iterative depth-first search algorithm that solves FOND planning tasks and produces strong cyclic policies. Our algorithm is explicitly designed for FOND planning, addressing more directly the non-deterministic aspect of FOND planning, and it also exploits the benefits of heuristic functions to make the algorithm more effective during the iterative searching process. We compare our proposed algorithm to well-known FOND planners, and show that it has robust performance over several distinct types of FOND domains considering different metrics.