Minimizing Conditional Cost with Goal-Reachability Guarantee in Stochastic Shortest Paths with Dead-Ends

Abstract

In several stochastic shortest path (SSP) planning domains, a planner must find a strategy to reach a goal in an uncertain environment in which some states are irrecoverable dead-ends. When dead-ends cannot always be avoided, the planner may face a tension between being safe and being efficient. Existing policy optimization criteria do not let the human operator control this trade-off directly: S3P imposes a strict priority on success probability before considering path cost, while fSSP relies on a failure penalty parameter whose tuning offers implicit control over the resulting trade-off. We introduce the Safety-constrained Conditional-Cost SSP (SCC-SSP), where the human operator chooses a minimum acceptable success probability and the planner minimizes the expected cost conditioned on reaching the goal. The ratio structure of this objective introduces a coupling between path costs and future goal reachability that places SCC-SSP outside the scope of standard Constrained Markov Decision Processes (C-MDPs). To resolve this coupling, we build an augmented MDP that tracks cumulative cost in the state, and prove that the optimal policy depends not only on the current state but also on the cost accumulated until the current state, with the optimum achieved by a mixture of at most two deterministic cost-dependent policies. This results in a class of policies strictly richer than stationary policies. To compute such policies, our algorithm combines Dinkelbach's method for fractional objectives with a Lagrangian relaxation of the safety constraint. Experiments on classical benchmarks indicate that SCC-SSP can trace the full Pareto front between success probability and conditional cost, whereas C-MDP produces operating points governed by the penalty parameter rather than the safety threshold.