AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
Fast SSP Solvers Using Short-Sighted Labeling
Luis Enrique Pineda, Kyle Hollins Wray, Shlomo Zilberstein

Last modified: 2017-02-12


State-of-the-art methods for solving SSPs often work by limiting planning to restricted regions of the state space. The resulting problems can then be solved quickly, and the process is repeated during execution when states outside the restricted region are encountered. Typically, these approaches focus on states that are within some distance measure of the start state (e.g., number of actions or probability of being reached). However, these short-sighted approaches make it difficult to propagate information from states that are closer to a goal than to the start state, thus missing opportunities to improve planning. We present an alternative approach in which short-sightedness is used only to determine whether a state should be labeled as solved or not, but otherwise the set of states that can be accounted for during planning is unrestricted. Based on this idea, we propose the FLARES algorithm and show that it performs consistently well on a wide range of benchmark problems.


Markov Decision Process; Stochastic Shortest Path Problem; Planning under Uncertainty; Heuristic Search; Short-Sighted Search

Full Text: PDF