Planning and Acting with Non-Deterministic Events: Navigating between Safe States

Lukás Chrpa, Jakub Gemrot, Martin Pilát

Introduction

In classical automated planning, agents typically assume a static world where changes only occur as a result of their own actions. However, real-world environments are inherently dynamic, filled with exogenous events—such as a ship crossing a robot's path or a platform collapsing—that occur independently of the agent.

Standard approaches, such as Planning/Execution/Replanning (PER), often ignore these events during the planning phase, reacting only when a failure occurs. While sufficient in "safe" environments, this reactive strategy is catastrophic in domains with dead-ends, where an event can permanently destroy the agent or block the goal. This paper addresses the need for planning frameworks that can formally guarantee safety by anticipating and navigating around these irreversible failures.

Methodology: Navigating Between Safe States

The authors propose a framework centered on the concept of Safe States: states from which no sequence of external events can force the agent into a dead-end. The core idea is to treat these safe states as "islands" and robust plans as "bridges" between them.

Illustration of the AUV Sampling domain where an agent must navigate between safe states while avoiding non-deterministic ship movements.

Key Components

  1. Robust Plans: These are action sequences guaranteed to reach a target state regardless of which exogenous events occur. The authors use a compilation technique to transform this into a classical planning problem by tracking both optimistic and pessimistic possibilities using "twin" atoms.
  2. Unsafeness Limits: Recognizing that reaching a goal may require passing through unsafe territory (e.g., crossing a busy shipping lane), the authors introduce "unsafeness credits." This system constrains the planner to limit the duration of exposure to risk, ensuring the agent never strays too far from a safe state for too long.
  3. The LIMIT Algorithm: This algorithm generates initial plans with limited unsafe actions. During execution, it identifies the longest "safely applicable" prefix. If an unexpected event occurs, it adaptively generates a new robust plan to reach the next safe state.

Experimental Evaluation

The researchers evaluated the LIMIT method against standard PER and a state-of-the-art "dangerous state" reasoning method (DANG) using two custom benchmarks:

  • AUV Sampling: An Autonomous Underwater Vehicle must collect resources in a grid while avoiding non-deterministic ships.
  • Perestroika: Inspired by the classic game, an agent navigates a grid of disappearing platforms to reach a goal.

Key Results

The experimental results demonstrate the superior reliability of the LIMIT approach in high-risk scenarios.

Performance comparison of the LIMIT algorithm against PER and DANG baselines across various problem instances.
  • Success Rate (SR): In the Perestroika domain, the LIMIT method achieved a 100% success rate across all test cases. Traditional PER methods failed significantly (often <20% success) because they could not anticipate platform disappearances.
  • Efficiency and Robustness: While LIMIT may require more initial planning time (PT) due to the safety compilation, it avoids the frequent, costly replanning cycles required by other methods. In larger AUV scenarios, LIMIT maintained its 100% success rate even as the environment became more complex, whereas DANG's performance began to degrade.

Conclusion and Future Work

By framing safety as a navigation problem between guaranteed safe states, this work provides a robust alternative to purely reactive planning. Current limitations include the requirement for domain experts to define safe states and the potential for the agent to get "stuck" in a safe state if no robust path to the goal exists. Future research will explore temporal planning to reason about event timing and methods to automatically derive safe state descriptions from domain models.

Summary updated

Abstract

Automated Planning addresses the problem of finding a sequence of actions, a plan, transforming the environment from its initial state to some goal state. In real-world environments, exogenous events might occur and might modify the environment without agent's consent. Besides disrupting agent's plan, events might hinder agent's pursuit towards its goals and even cause damage (e.g. destroying the robot).In this paper, we leverage the notion of Safe States in dynamic environments under presence of non-deterministic exogenous events that might eventually cause dead-ends (e.g. “damage” the agent) if the agent is not careful while executing its plan. We introduce a technique for generating plans that constrains the number of consecutive “unsafe” actions in a plan and a technique for generating “robust” plans that effectively evade event effects. Combination of both approaches plans and executes robust plans between safe states. We empirically show that such an approach effectively navigates the agent towards its goals in spite of presence of dead-ends.
BibTeX
@inproceedings{chrpa2020planning,
  author = {Lukás Chrpa and Jakub Gemrot and Martin Pilát},
  title = {{Planning and Acting with Non-Deterministic Events: Navigating between Safe States}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6532},
}
Figure