FONDANT improves goal-directed planning in uncertain environments
FONDANT: Strong and Best-Effort Planning via Antichains
Artificial Intelligence
Summary
Planning in environments where outcomes are uncertain can be tricky because sometimes no guaranteed plan exists. This paper presents FONDANT, a planning method that finds the best possible plan when no perfect one is available. It classifies situations into ones where success is guaranteed, likely, or unlikely, and creates policies accordingly. The authors show that their method works well compared to existing planners and can handle larger problems more efficiently.
What this means in practice
- •For robotics engineers: Design robot controllers that assure task completion even under uncertain or adversarial conditions by synthesizing strong and best-effort policies.
- •For software developers in automation: Develop automated systems that adaptively choose between guaranteed and best-effort task plans based on environment behavior to improve reliability.
Authors
Benjamin Aminof, Tuan Khai Nguyen, Sasha Rubin
Abstract
A classical solution concept in fully observable nondeterministic (FOND) planning, is the strong policy (aka winning strategy in the closely related area of reactive synthesis), i.e., such a policy ensures that the goal is reached in an adversarial environment. When strong policies are not available or there is no evidence that the environment is adversarial, one can resort to best-effort policies, which always exist, and which follow the classic decision-theoretic principle that an agent should not use a dominated strategy. A typical positional best-effort policy works as follows: from every state, it follows a strong policy if one exists from that state (such states are called ``strong-winning''), else a weak policy if one exists from that state (``weak-winning''), and else is unconstrained (``losing''). In this work, we introduce a sound and complete planner for both best-effort planning and strong planning. The algorithm that underpins the planner is quite simple: it represents certain sets of states, such as the winning regions, by their $\subseteq$-minimal elements. The algorithm returns uniform policies, i.e., it returns a policy $π_t$ that is a strong solution starting in every strong-winning state, and it returns a policy $π_w$ that is a weak solution starting in every weak-winning state, and it provides a certificate for the set of losing states. We implemented the algorithm with some simple optimizations (calling it FONDANT), and evaluated it on a benchmark set consisting of the instances that were used in the evaluation of leading strong planners PR2 and FOND-SAT, and the best-effort planner BeSyftP. On coverage, our implementation is at least as good on all domains, and outperforms on some domains; and on wall time, it is slower on small and medium-sized instances, and outperforms on larger instances.