Abstract
Planning under uncertainty is a fundamental challenge in Artificial Intelligence, typically modeled using Markov Decision Processes (MDPs). However, the practical application of MDPs is often hindered by the "curse of dimensionality," where state space sizes grow exponentially, leading to memory exhaustion in traditional solvers. This research advances the state of the art by introducing a novel generalization framework for Stochastic Shortest Path (SSP) problems. By automatically generating basis functions to represent state information compactly, the proposed approach enables efficient planning in environments previously considered computationally intractable. The work contributes new algorithms—RETRASE, GOTH, and SIXTHSENSE—and extends the mathematical theory of MDPs to handle Generalized Stochastic Shortest-Paths (GSSPs), demonstrating superior performance on international benchmarks and real-world urban traffic scenarios.
Introduction
Since the inception of AI, planning under uncertainty has been a primary objective. Markov Decision Processes (MDPs) provide a robust mathematical framework for this, specifying agent objectives, available actions, and probabilistic state transitions. Solving an MDP involves finding an optimal policy—a mapping of actions to states that maximizes a reward or minimizes a cost.
Despite their elegance, optimal solution methods often require analyzing the entire state space. In realistic scenarios, such as urban traffic routing, the number of possible states is astronomical. Traditional "Find-and-Revise" algorithms use heuristics to focus on relevant states, but even these eventually succumb to memory limits. To bridge this gap, this research proposes a shift from state-level analysis to a generalization-based approach that leverages the underlying structure of the problem.
The Scalability Challenge
Existing approaches to scaling MDPs generally fall into three categories, each with distinct limitations:
- Heuristic Search: While these methods focus on reachable states, they still store individual state values, leading to memory bottlenecks in large domains.
- Determinization: These techniques simplify the problem by ignoring probabilities. While fast, they often fail to account for high-risk, low-probability events that are crucial in stochastic environments.
- Function Approximation: This method compresses state information into "basis functions." However, these functions typically require manual engineering by domain experts, limiting their generalizability.
A Framework for Automatic Generalization
The core contribution of this work is a framework that automates the creation of basis functions, combining the speed of determinization with the accuracy of probabilistic planning. Instead of manual definition, the system discovers essential state features through a process of regression through trajectories.
Key Algorithms
- RETRASE (REgression-TRajectory-based Asynchronous Value Iteration): This planner updates basis functions using Bellman-like backups. It learns probabilistic values across many states simultaneously without the need to store each state individually in memory.
- GOTH: A memory-frugal heuristic that estimates state values based on the costs of the deterministic trajectories used to derive the basis functions. It serves as a more efficient alternative to standard heuristics like "Fast Forward" (FF).
- SIXTHSENSE: A component designed to identify "dead ends"—states from which a goal is unreachable. By pruning these states early, it prevents the planner from wasting computational resources on hopeless paths.
Theoretical Extensions: GSSP
Beyond algorithmic improvements, this research addresses a theoretical gap in MDP classes. Standard SSP solvers often fail in the presence of "zero-cost loops," where an agent can cycle through states without accumulating cost, breaking convergence properties. This work develops the mathematical apparatus for Generalized Stochastic Shortest-Paths (GSSP), introducing new operators that ensure convergence and allow approximation techniques to be applied to a broader range of complex MDPs.
Experimental Results and Impact
The proposed framework was evaluated using benchmarks from the International Probabilistic Planning Competitions (IPPC) and real-world data from Stockholm’s urban traffic network.
- Performance: RETRASE outperformed previous IPPC winners on several complex problems, demonstrating that automatic basis function generation can match or exceed the performance of state-based solvers.
- Efficiency: The GOTH heuristic proved significantly more memory-efficient than traditional counterparts, while SIXTHSENSE appreciably reduced search times by identifying "nogood" states.
- Real-World Application: In the context of urban traffic routing, the research suggests that scalable MDP algorithms can account for probabilistic fluctuations in traffic flow more effectively than deterministic models. Preliminary analysis indicates that such planning could reduce average travel times in major metropolitan areas by over 60%.
Conclusion
This research provides a path forward for scaling probabilistic planning to real-world dimensions. By integrating heuristic search, determinization, and automatic function approximation, the framework overcomes the memory constraints of state-level analysis. The extension of these techniques to GSSPs further broadens the applicability of AI planning, moving the field closer to fulfilling its vision of intelligent agents capable of navigating complex, uncertain environments.
Summary updated