TL;DR
This paper extends the classical Stochastic Shortest Path (SSP) MDP framework to handle "dead ends"—states from which a goal can never be reached. The authors introduce three new MDP classes (SSPADE, fSSPUDE, and iSSPUDE) that provide a principled theoretical foundation and efficient heuristic search algorithms for planning in environments where catastrophic failure is a real possibility.
What Problem Does This Paper Address?
In probabilistic planning, the Stochastic Shortest Path (SSP) model is the gold standard for goal-oriented agents. However, it relies on a restrictive assumption: the goal must be reachable from every state with 100% probability (the "proper policy" assumption).
In the real world, this rarely holds. A Mars rover might get stuck in a crevice; a plane might fly into a storm and crash. These are dead ends. Standard SSP algorithms like Value Iteration (VI) fail to converge when dead ends are present. While researchers have previously hacked around this by adding penalties, a rigorous theory for how to optimize behavior when failure is unavoidable—and what those optimization criteria should even be—has been missing.
Methods
The authors propose three nested classes of MDPs to bridge this gap:
- SSPADE (Avoidable Dead Ends): Dead ends exist in the state space, but there is at least one policy that can avoid them entirely starting from the initial state $s_0$.
- fSSPUDE (Finite-penalty Unavoidable Dead Ends): Dead ends are unavoidable, but the agent can assign a finite "price" $D$ to failure. The goal is to minimize the expected cost, including the potential penalty of hitting a dead end.
- iSSPUDE (Infinite-penalty Unavoidable Dead Ends): Dead ends are unavoidable and the cost of failure is considered infinite (e.g., loss of life). Here, the agent follows a lexicographic (multi-objective) priority: first, maximize the probability of reaching the goal; second, among policies that maximize that probability, choose the one with the minimum expected cost.
To solve these, the authors adapt standard algorithms like LRTDP and introduce SHS (Staged Heuristic Search). SHS is a two-stage process for iSSPUDE: it first solves a MAXPROB problem to find the best possible survival probability, then solves an SSP on the resulting "safe" sub-graph to minimize cost.
Datasets
The algorithms were evaluated on two benchmark domains from the International Probabilistic Planning Competitions (IPPC):
- Exploding Blocks World (IPPC-2008): A variation of the classic blocks world where picking up or placing blocks can cause them (or the table) to "explode," leading to dead ends.
- Drive Domain (IPPC-06): A navigation task where the agent must reach a destination while managing probabilistic risks of car breakdowns or traffic issues.
Key Insights and Ideas
- The "Semantic Paradox": Simply adding a penalty $D$ to dead-end states isn't enough. If a state $s$ has a very high cost to reach the goal, its value might exceed $D$, making the agent "prefer" the dead end over the goal. The authors solve this in fSSPUDE by "capping" the cost of any state at $D$.
- Theoretical Equivalence: The authors prove that fSSPUDE and iSSPUDE are related. If you set the penalty $D$ high enough in an fSSPUDE, the resulting optimal policy will be identical to the iSSPUDE policy.
- The Efficiency Gap: Surprisingly, solving the finite-penalty version (fSSPUDE) is often an order of magnitude faster than solving the infinite-penalty version (iSSPUDE), even when they yield the same result.
- The MAXPROB Bottleneck: The slowness of iSSPUDE stems from the need to solve MAXPROB. To prove a survival probability is optimal, the algorithm must often explore the entire reachable state space to ensure no better path exists, whereas cost-based search can prune "expensive" paths much earlier.
Key Results
- Convergence: The authors successfully extended the FIND-AND-REVISE heuristic search framework to these new classes, ensuring optimal solutions can be found without exploring the entire state space.
- Performance: In empirical tests, solving fSSPUDE with a large $D$ (e.g., $D=500$) was consistently faster than the two-stage iSSPUDE approach.
- Heuristic Impact: The use of "SixthSense" (a dead-end detection heuristic) was crucial. Without it, the time to solve fSSPUDE skyrocketed because the agent would spend thousands of iterations "learning" that a dead end is bad by incrementing its cost slowly.
Limitations and Future Work
The primary limitation is the choice of the penalty $D$. While the paper proves a threshold $D_{thres}$ exists where fSSPUDE and iSSPUDE align, there is currently no principled way to calculate this threshold a priori without solving the MDP first.
The authors also point toward a more general class called $S^3P$ (Stochastic Safest and Shortest Path), which was proposed around the same time. They suggest that future work should focus on developing even more efficient heuristic search algorithms for these complex, multi-objective probabilistic environments.
Summary updated