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.
Key Components
- 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.
- 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.
- 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.
- 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