Abstract: Dynamic programming algorithms have been successfully applied to propositional stochastic planning problems by using compact representations, in particular algebraic decision diagrams, to capture domain dynamics and value functions. Work on symbolic dynamic programming lifted these ideas to first order logic using several representation schemes. Recent work introduced a first order variant of decision diagrams (FODD) and developed a value iteration algorithm for this representation. This paper develops several improvements to the FODD algorithm that make the approach practical. These include, new reduction operators that decrease the size of the representation, several speedup techniques, and techniques for value approximation. Incorporating these, the paper presents a planning system, FODD-Planner, for solving relational stochastic planning problems. The system is evaluated on several domains, including problems from the recent international planning competition, and shows competitive performance with top ranking systems. This is the first demonstration of feasibility of this approach and it shows that abstraction through compact representation is a promising approach to stochastic planning.
Introduction
Traditional probabilistic planning often uses Markov Decision Processes (MDPs). While effective, standard "propositional" solvers suffer from the curse of dimensionality: as the number of variables $N$ increases, the state space grows to $2^N$. In complex domains like logistics, grounding every possible combination of trucks and cities makes the problem computationally impossible. Relational MDPs (RMDPs) solve this by "lifting" the logic—planning for generic objects rather than specific instances. However, symbolic dynamic programming often produces value functions that grow exponentially. The challenge is keeping these symbolic representations compact enough to be useful without losing mathematical correctness.
First Order Decision Diagrams (FODDs)
The authors build upon First Order Decision Diagrams (FODDs), which are directed acyclic graphs representing functions over relational states. Nodes in these diagrams represent predicates, and edges represent the truth values of those predicates, leading to leaf nodes that contain numerical values.
Methods and Reduction Operators
A core contribution of this work is making FODD-based planning practical through novel "reduction" operators that simplify diagrams by removing redundant nodes or edges.
- New Reduction Operators (R10 & R11): R10 is a global operator that ranks paths by value and eliminates dominated ones, proving significantly faster than previous local operators like R7. R11 targets redundancies that emerge specifically when diagrams are combined or when background knowledge is applied.
- The R7 Operator: While the paper introduces more efficient global operators, local operators like R7 (illustrated below) provided the foundation for simplifying relational structures by identifying redundant sub-diagrams.
- Value Approximation: To handle the most complex problems, the authors introduced techniques like "Merging Leaves," which groups leaf nodes with similar values. This can lead to a 22-fold speedup in planning time with only a minor hit to success rates.
Key Results and Insights
The system, FODD-Planner, was evaluated on standard benchmarks from the International Planning Competition (IPC), including Fileworld, Tireworld, and Boxworld.
- Efficiency and Scaling: In the Tireworld domain, the system generated a policy in 55 minutes that remained robust across 15 different problem instances of increasing size. In contrast, propositional solvers would have to re-solve each instance from scratch.
- Abstraction as a Power Multiplier: Because the planner works at the relational level, a policy generated for a small version of a problem is mathematically identical and immediately applicable to much larger versions.
- Performance: FODD-Planner showed performance competitive with top-ranking systems like RFF and GPT, achieving 100% coverage in the Fileworld domain.
Limitations and Future Work
While successful, FODDs naturally handle existential quantification better than universal quantification (e.g., "all boxes are at their destinations"). Currently, the authors use an additive decomposition heuristic to bridge this gap. Future research directions include integrating these FODD techniques into Relational Reinforcement Learning, where agents learn diagrams from experience rather than pre-defined domain dynamics.
Summary updated