Compiling Planning Problems with Non-deterministic Events into FOND Planning

Lukás Chrpa, Martin Pilát, Jakub GemrotRCRA/RiCeRcA@AI*IA 2019 · OpenReview

In classical automated planning, the environment is typically treated as static, with the agent acting as the sole catalyst for change. However, real-world applications—ranging from robotics to distributed systems—are rarely so predictable. Exogenous events, such as communication failures or environmental shifts, can occur independently of an agent's actions. This paper, originally presented at the 2019 Workshop on Distributed and Multi-Agent Planning, proposes a robust method for handling these uncertainties by compiling planning problems with exogenous events into Fully-Observable Non-Deterministic (FOND) planning.

The Problem: The Optimism of Replanning

The most common strategy for dealing with environmental uncertainty is Planning/Execution/Replanning (PER). In this model, an agent generates a plan under the assumption that no external interference will occur. If an event disrupts the plan, the agent simply stops and recalculates.

While PER is computationally efficient, it is fundamentally "optimistic." It fails to account for potential events during the initial planning phase, which can lead the agent into "dead-ends"—states where the goal becomes impossible to reach. For example, in a navigation task, a PER agent might step onto a temporary platform that disappears, leaving it stranded. A robust planner must be "pessimistic" enough to avoid such irreversible failures.

Methodology: Compilation to FOND

The authors address this by translating domains with exogenous events into standard FOND domains. FOND planners are designed to handle actions with multiple possible outcomes (e.g., an attempt to pick up an object might result in "success" or "dropped"). By framing environmental events as non-deterministic outcomes of a "meta-action," the authors can utilize existing FOND solvers like PRP (Planner for Relevant Policies).

The Turn-Based Logic

To facilitate this translation, the authors introduce a turn-based system using specific logic atoms to manage the state space:

  • act-turn and ev-turn: These force the planner to alternate between the agent's move and the environment's potential response.
  • enab-ei and disab-ei: These track which events are currently possible in the environment.
  • The wenab (will be enabled) logic: For complex scenarios involving independent events, these atoms ensure that one event occurring does not "legally" trigger another within the same turn, preserving the independence of the events.

Modeling Assumptions

The compilation supports two primary models of environmental behavior:

  1. Single Event Assumption: At most one environment event can occur after every agent action.
  2. Independent Events Assumption: A set of independent events may occur simultaneously after an action.

Experimental Evaluation

The authors evaluated their approach using three distinct benchmarks designed to test robustness:

  • Modified BlocksWorld: Variations where blocks can become "sticky" (permanently fixed) or "slippery" (dropped during transit).
  • AUV Sampling: An Autonomous Underwater Vehicle navigating a grid while dodging unpredictably moving ships.
  • Perestroika Domain: A high-risk environment where the agent navigates a grid of platforms that shrink and disappear over time, creating numerous dead-ends.

Key Results and Trade-offs

The research highlights a significant trade-off between robustness and computational performance:

  • Success Rate: In the Perestroika domain, the traditional PER approach failed frequently, with success rates as low as 14-24% because it could not anticipate disappearing platforms. In contrast, the FOND approach achieved a 100% success rate whenever a plan was found, as it only selects actions that guarantee a path to the goal regardless of event outcomes.
  • Computational Overhead: FOND planning is significantly slower. In the AUV domain, where a replanner took less than a second, the FOND compiler often required over 200 seconds or timed out.
  • Scalability: The "Independent Events" model suffers from a state-space explosion. For example, in the Perestroika domain, just four shrinking platforms result in 16 possible event combinations every turn, making global reasoning mathematically expensive.

Conclusion and Future Work

The compilation of exogenous events into FOND planning provides a rigorous framework for generating robust policies in dangerous environments. While the method guarantees success where PER fails, its current form is limited by the scalability of FOND solvers when faced with exponential event combinations.

The authors suggest that future work should move toward local policies. Rather than calculating a global policy for the entire world, agents could identify high-risk areas and generate robust sub-policies for those specific segments. This "divide and conquer" approach aims to combine the safety of FOND planning with the speed required for real-world, large-scale applications.

Summary updated

BibTeX
@inproceedings{chrpa2019compiling,
  author = {Lukás Chrpa and Martin Pilát and Jakub Gemrot},
  title = {{Compiling Planning Problems with Non-deterministic Events into FOND Planning}},
  booktitle = {RCRA/RiCeRcA@AI*IA},
  year = {2019},
  url = {https://openreview.net/forum?id=UC1X0UmOwY},
}
Figure