Introduction
In contingent planning, an agent must achieve a goal despite having only partial information about its environment. Success depends on "sensing actions"—such as checking if a door is locked—to update the agent's internal model. A common strategy is to compile these problems into classical planning. However, many existing planners are "optimistic": they assume a specific sensor outcome and plan accordingly, replanning only when expectations are subverted. This "single-path" approach is vulnerable to dead-ends, where an agent takes an irreversible action (like entering a trapped room) before it can gather the necessary information to avoid failure.
Multi-Path Translation
To address this, we introduce Multi-Path Translation, a technique that encodes a branching plan tree into a linear sequence of actions compatible with classical planners like FF. Instead of tracking simple facts, the system tracks conditional knowledge propositions (e.g., "is $p$ true given initial state $s$?") and distinguishability between possible states.
The Multi-Path Sampling Replanner (MPSR) implements this by sampling a small, diverse subset of possible initial states. It then generates a "multi-path" plan guaranteed to succeed for all sampled scenarios. By forcing the planner to find a single sequence that satisfies multiple potential futures, the agent naturally avoids actions that lead to dead-ends in any likely scenario.
Experimental Evaluation
MPSR was evaluated against state-of-the-art planners, including SDR and CLG, across standard benchmarks such as doors, localize, and unix. Additionally, a challenging "Wumpus with Dead-ends" domain was introduced, where moving into a cell with a pit or monster results in immediate failure, punishing overly optimistic strategies.
Key Results
MPSR demonstrates significant improvements in both speed and robustness. In the Wumpus domain, previous leaders like SDR failed 100% of the time due to their optimistic nature, whereas MPSR solved the problems reliably. Furthermore, MPSR exhibits superior scalability; while competing planners often timed out on larger grids, MPSR scaled effectively to 24x24 environments.
As shown in the results table, MPSR is typically faster than its predecessors across most domains. While MPSR's plans can be longer—prioritizing safety and rapid discovery over strict optimality—its ability to avoid catastrophic failures makes it a more robust choice for high-stakes environments.
Conclusion and Future Work
MPSR provides a powerful framework for contingent planning by reasoning about multiple futures. Current limitations include the assumption of deterministic action effects and the potential for sub-optimal plan lengths. Future research will explore using multi-path translations to derive better heuristics and extending the framework to handle non-deterministic outcomes.
Summary updated