Cost-Optimal FOND Planning as Bi-Objective Best-First Search

Abstract

In this paper, we tackle the problem of finding cost-optimal solutions in Fully-Observable Non-Deterministic (FOND) planning problems. First, we introduce metrics for FOND problems by interpreting solution policies under both their best and worst possible scenarios, leading to a bi-objective optimization problem. We then propose BOAND*, a novel heuristic search algorithm designed to seek Pareto-optimal solutions by navigating the space of possible policies. We conduct an empirical evaluation of the algorithm, alongside a qualitative comparison with cost-optimal solutions that consider only one objective at a time. Our findings validate this approach, paving the way for new methods of reasoning over FOND problems.