Memory-Effcient Symbolic Online Planning for Factored MDPs

Aswin Raghavan, Roni Khardon, Prasad Tadepalli, Alan FernUAI 2015 · OpenReview

Abstract

Planning in large-scale environments often relies on Markov Decision Processes (MDPs). However, Factored MDPs, where states are defined by multiple variables, suffer from exponential state-space growth. Symbolic online planners attempt to mitigate this using Algebraic Decision Diagrams (ADDs) but frequently encounter memory explosions. This paper presents Path Dynamic Programming (PDP) and its robust variant, pPDP, which restrict symbolic updates to specific paths within ADDs. These methods provide significant generalization across states while maintaining a memory footprint comparable to traditional flat-state search, effectively solving large-scale benchmark problems where previous symbolic planners failed.

Introduction: The Challenge of Factored MDPs

Real-world planning problems are rarely "flat." Instead, they are often structured as Factored MDPs, where the state is a vector of variables. For instance, in a network management task, the state depends on the status of every individual computer. As the number of variables increases, the state space grows exponentially, rendering traditional atomic state representations impractical.

Factored MDP representation using Dynamic Bayesian Networks (left) and its corresponding symbolic representation in an Algebraic Decision Diagram (right).

Symbolic planners address this by using Algebraic Decision Diagrams (ADDs) to represent sets of states with identical values or transitions. While powerful, these tools are prone to "memory explosions" during intermediate calculations, often exceeding available RAM even on moderately sized problems.

Methodology: Path Dynamic Programming (PDP)

To bridge the gap between generalization and memory efficiency, the authors introduce the Path Dynamic Programming (PDP) family of algorithms. Unlike full symbolic value iteration, PDP samples trajectories and performs targeted symbolic updates.

Core Variants

  • PDP-V (Value Invariance): Updates a "path" in the value function's ADD. This ensures that the update generalizes to all states sharing the same symbolic value representation.
  • PDP-π (Policy Invariance): Groups states that share the same greedy action. This is particularly effective in domains where the optimal policy is simpler to represent than the value function itself.
  • pPDP (Pruning PDP): The most robust variant, pPDP employs a specialized pruning operator. This operator guarantees that the symbolic representation's size never exceeds that of a standard flat-state update, providing a theoretical safety net against memory spikes.

Experimental Evaluation

The proposed algorithms were tested on benchmarks from the International Probabilistic Planning Competitions (IPPC), including Academic Advising, SysAdmin, and Crossing Traffic. These domains vary in their prerequisite structures and stochasticity, providing a rigorous test for generalization.

Performance comparison in the Academic Advising domain across various course counts and time limits. PDP variants consistently outperform flat methods and avoid the memory limits that plague previous symbolic planners.

Key Results and Discussion

The evaluation revealed several critical insights:

  • Scalability and Robustness: In the Academic Advising domain, PDP methods successfully handled large instances where previous state-of-the-art symbolic planners (sRTDP) hit Exceeded Memory Limits (EML). pPDP, in particular, remained within the 4GB limit across all tests.
  • Generalization Benefits: PDP variants significantly outperformed "flat" search methods like RTDP and LR2TDP. On larger instances, flat methods often failed to perform better than a "No-Op" policy, whereas PDP achieved near-optimal rewards by leveraging the factored structure.
  • Domain Sensitivity: The effectiveness of symbolic generalization is tied to the domain's reward structure. In SysAdmin, complex reward functions can lead to highly specific paths, causing symbolic methods to converge toward flat-state performance.

Conclusion

PDP and pPDP represent a significant step forward in symbolic online planning. By controlling generalization through path-based updates and aggressive pruning, these algorithms avoid the memory pitfalls of traditional symbolic methods while retaining their ability to scale. Future work will explore integrating these symbolic updates with advanced sampling heuristics like those found in UCT.

Summary updated

BibTeX
@inproceedings{raghavan2015memory,
  author = {Aswin Raghavan and Roni Khardon and Prasad Tadepalli and Alan Fern},
  title = {{Memory-Effcient Symbolic Online Planning for Factored MDPs}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=l3EWEHq_Cn},
}
Figure