Agent Planning Programs as Non-deterministic Planning under Fairness

Abstract

We propose an approach for solving Agent Planning Programs (APP) based on a reduction to (strong-cyclic) Fully Observable Non-Deterministic (FOND) planning. APPs represent a middle-ground between automated planning and agent-oriented programming, in which the space of possible agent behavior is "programmed" as a network of declarative goals wrt an underlying planning domain. Each transition in an APP represents a local planning problem that may need to be addressed by the agent executing the APP. APPs allow the specification of continuous goal-driven behavior in which the "next" goal is externally chosen, thus going beyond one-shot planning. Two methods have been proposed for solving APPs: a principled but inefficient LTL reactive synthesis technique; and a more efficient but arguably ad-hoc approach that relies on multiple "local" classical planning and meta-level backtracking. We demonstrate how APPs can be solved in a principled manner by developing an elegant reduction to non-deterministic planning under fairness assumptions, and show experimentally with existing FOND solvers its practical value. We also provide a new solution concept that is simpler and closer to mainstream planning than the existing one.