Abstract
Recent algorithms like RTDP and LAO* combine the strength of Heuristic Search (HS) and Dynamic Programming (DP) methods by exploiting knowledge of the initial state and an admissible heuristic 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 c) are found and updated until no such states are found, and serves to make explicit the basic idea underlying 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.
Introduction
In classical AI planning, the goal is typically to find a sequence of actions. However, in stochastic environments modeled as Markov Decision Processes (MDPs), we require a policy—a mapping from states to actions. Traditional Dynamic Programming (DP) methods like Value Iteration are exhaustive and do not scale well to large state spaces. Heuristic Search (HS) methods, such as RTDP and LAO*, improve efficiency by focusing on states reachable from the initial state under a greedy policy.
A significant challenge in HS methods is the presence of cycles in the state graph. Standard labeling techniques for identifying "solved" states often struggle with loops, where a state's status depends recursively on its neighbors. This paper addresses these bottlenecks by integrating graph-theoretic techniques into the HS/DP framework.
Methods
The authors propose a hierarchy of three approaches to solve MDPs:
- FIND-and-REVISE: A general schema that identifies "inconsistent" states—those where the current value estimate deviates from the Bellman equation—and updates them until convergence. This provides a clean abstraction of the HS/DP process.
- HDP (Heuristic Dynamic Programming): The primary contribution of this work. HDP performs a Depth-First Search (DFS) on the greedy graph and utilizes Tarjan’s algorithm to identify Strongly Connected Components (SCCs). By identifying SCCs, HDP can label entire loops of states as solved simultaneously once they become consistent and their descendants are solved.
- HDP(i): An approximate version of HDP that uses a "plausibility" measure to prune the search space. By discretizing transition probabilities logarithmically, HDP(i) focuses only on "likely" outcomes, ignoring rare events during planning to achieve significant speed and memory gains.
Empirical Evaluation
The algorithms were evaluated on the Racetrack domain, a standard benchmark for stochastic planning. Tests included standard tracks (large-b, h-track) and custom square and ring tracks with up to 350,000 states. HDP was compared against Value Iteration (VI), Improved LAO (ILAO), and Labeled RTDP (LRTDP).
Key Results
HDP demonstrated superior performance, particularly when using an admissible heuristic ($h_{min}$). On the largest benchmark, ring-4, HDP converged in approximately 30 seconds, significantly faster than ILAO* (145s) and LRTDP (37s).
The approximation variant, HDP(i), also showed promising results. For the h-track instance, HDP(i) evaluated only ~7,000 states compared to the ~35,000 required by the full HDP, with minimal impact on the resulting policy's quality.
Conclusion
HDP effectively combines heuristic search with graph-theoretic cycle detection to accelerate MDP planning. While its performance is sensitive to the quality of the heuristic, it represents a state-of-the-art approach for fully observable stochastic environments. Future work includes automating the selection of plausibility thresholds for HDP(i) and extending these SCC-based techniques to Partially Observable MDPs (POMDPs).
Summary updated