Soft Labeling in Stochastic Shortest Path Problems

Abstract

The Stochastic Shortest Path (SSP) problem is an established model for goal-directed probabilistic planning. Despite its broad applicability, wide adoption of the model has been impaired by its high computational complexity. Efforts to address this challenge have produced promising algorithms that leverage two popular mechanisms: labeling and short-sightedness. The resulting algorithms can generate near-optimal solutions much faster than optimal solvers, albeit at the cost of poor theoretical guarantees. In this work, we introduce a generalization of labeling, called soft labeling, which results in a framework that encompasses a wide spectrum of efficient labeling algorithms, and offers better theoretical guarantees than existing short-sighted labeling approaches. We also propose a novel instantiation of this framework, the soft-FLARES algorithm, which achieves state-of-the-art performance on a diverse set of benchmarks.