Faster Heuristic Search Algorithms for Planning with Uncertainty and Full Feedback

Abstract

Recent algorithms like RTDP and LAO* combine the strength of Heuristic Search (HS) and Dynamic Programming (DP) methods by exp~oi~ing kno~l edge of the initial state and an admiSSible heunstic function for producing optimal policies without evaluating the entire space. In this paper, we introduce and analyze three new HS/DP algorithms. A first general algorithm schema that is a simple loop in which 'inconsistent' reachable states (i.e., with residuals greater than a given E) are found and updated until no such states are found, .and serves to make explicit the basic idea underlymg HS/DP algorithms, leaving other commitments aside. A second algorithm, that builds on the first and adds a labeling mechanism for detecting solved states based on Tarjan's strongly-connected components procedure, which is very competitive with existing approaches. And a third algorithm, that approximates the latter by enforcing the consistency of the value function over the 'likely' reachable states only, and leads to great time and memory savings, with no much apparent loss in quality, when transitions have probabilities that differ greatly in value.