TL;DR
This paper introduces FODD-Planner, a system that solves complex probabilistic planning problems by reasoning about objects and relations directly, rather than grounding them into massive propositional state spaces. By introducing novel "reduction" operators and approximation techniques for First Order Decision Diagrams (FODDs), the authors demonstrate the first practical application of pure relational value iteration on international competition-scale benchmarks.
What Problem Does This Paper Address?
Traditional probabilistic planning often uses Markov Decision Processes (MDPs). While effective, standard "propositional" solvers (like SPUDD) suffer from the curse of dimensionality: if you have $N$ binary variables, you have $2^N$ states. In a logistics domain with 100 cities and 1000 trucks, grounding every possible combination makes the problem computationally impossible.
Relational MDPs (RMDPs) solve this by "lifting" the logic—planning for a generic "truck" or "city" rather than specific ones. However, symbolic dynamic programming (SDP) often produces value functions that grow exponentially in size. The challenge is keeping these symbolic representations compact enough to be useful without losing the mathematical correctness required for optimal planning.
Methods
The authors build upon First Order Decision Diagrams (FODDs), which are directed acyclic graphs that represent functions over relational states. Their core contributions to making this approach practical include:
- New Reduction Operators (R10 & R11): Reductions are rules that simplify diagrams by removing redundant nodes or edges.
- R10 is a global operator that ranks paths by value and eliminates dominated ones. It is significantly faster than previous local operators (like R7).
- R11 targets redundancies that emerge specifically when diagrams are combined or when background knowledge (e.g., "a box can only be in one city at a time") is applied.
- The
sub-apartOperation: A novel algorithm that identifies the minimal conditions under which one diagram dominates another, allowing for more aggressive simplification. - Value Approximation Techniques:
- Merging Leaves: Grouping leaf nodes with similar values (within a precision $\epsilon$) to drastically shrink diagram size.
- Non-Standardizing Apart: A heuristic that skips the expensive process of renaming variables during certain operations, providing a lower-bound approximation that is much faster to compute.
- Domain Determinization: Pretending the world is deterministic during policy generation to save computation, then applying the resulting policy to the stochastic environment.
Datasets
The system was evaluated on standard benchmarks from the International Planning Competition (IPC):
- Fileworld (IPC-4): Managing files and folders with associated costs.
- Tireworld (IPC-5): Navigating a car through a network of cities where tires can go flat and spares must be found.
- Boxworld (IPC-2008): A complex logistics domain involving trucks, planes, and weather conditions (raining vs. not raining).
Key Insights and Ideas
- Global vs. Local Simplification: The "aha moment" for performance was realizing that local reduction operators (checking pairs of edges) were too slow. R10 treats the diagram globally, allowing the planner to prune entire branches of the search space in one pass.
- Abstraction is a Power Multiplier: Because the planner works at the relational level, a policy generated for a small version of a problem (e.g., 2 cities) is mathematically identical and immediately applicable to a version with 2,000 cities.
- The Cost of Exactness: The authors found that while exact symbolic value iteration is elegant, practical success requires "controlled" approximation. Merging leaves by just 10% of the total value can lead to a 22-fold speedup in planning time with only a minor hit to success rates.
Key Results
- Competitive Performance: FODD-Planner showed performance competitive with (and sometimes superior to) top-ranking systems like RFF and GPT in the IPC benchmarks.
- Efficiency: In the Fileworld domain, FODD-Planner achieved 100% coverage and higher rewards than existing policy iteration methods, converging in under 2 minutes.
- Scaling: In Tireworld, the system generated a policy in 55 minutes that remained robust across 15 different problem instances of increasing size, whereas propositional solvers would have to re-solve each instance from scratch.
- Reduction Impact: The new R10 operator was shown to be orders of magnitude more efficient than the previous state-of-the-art (R7), making iterations that previously took hours finish in seconds.
Limitations and Future Work
- Universal Goals: FODDs naturally handle existential quantification ("there exists a box in Paris") but struggle with universal quantification ("all boxes are in their destinations"). The authors used an additive decomposition heuristic to bridge this gap, but a more native representation is needed.
- Infinite Value Functions: In domains like Tireworld, the value function can technically be unbounded (as the path length increases). This forces the use of approximations to prevent the diagrams from growing forever.
- Online Execution Time: While off-line planning is efficient, evaluating the complex relational paths during "live" execution can still be slow (up to 10 minutes per round on very hard problems).
- Future Direction: The authors suggest integrating these FODD techniques into Relational Reinforcement Learning, where the agent learns the diagrams from experience rather than having the domain dynamics pre-defined.
Summary updated