Abstract
We formalize a simple but natural subclass of service domains for relational planning problems with object-centered, independent exogenous events and additive rewards capturing, for example, problems in inventory control. Focusing on this subclass, we present a new symbolic planning algorithm which is the first algorithm that has explicit performance guarantees for relational MDPs with exogenous events. In particular, under some technical conditions, our planning algorithm provides a monotonic lower bound on the optimal value function. To support this algorithm we present novel evaluation and reduction techniques for generalized first order decision diagrams, a knowledge representation for real-valued functions over relational world states. Our planning algorithm uses a set of focus states, which serves as a training set, to simplify and approximate the symbolic solution, and can thus be seen to perform learning for planning. A preliminary experimental evaluation demonstrates the validity of our approach.
Introduction
In traditional automated planning, the world is often assumed to be static unless the agent acts. However, real-world "service domains"—such as inventory control, emergency response, or taxi dispatching—are constantly influenced by exogenous events (external service requests). Modeling these in a Relational MDP (RMDP) is computationally challenging because the number of possible next states grows exponentially with the number of objects in the domain. This "stochastic branching factor" makes standard grounded planning infeasible. While Symbolic Dynamic Programming (SDP) allows for abstract reasoning without knowing the exact number of objects, existing SDP methods have struggled to handle the complexity of simultaneous external events alongside additive rewards.
The Template Method
The authors propose the Template Method, a new symbolic algorithm designed for a subclass of RMDPs. Instead of calculating every possible combination of exogenous events, it utilizes a "ground-regress-lift" approach. The method grounds a value function using a generic "Skolem constant" (a placeholder object), performs regression for a single generic exogenous action, and then "lifts" the result back into an aggregate form using averages.
Under specific technical assumptions (A1–A4), the authors prove that this method provides a monotonic lower bound on the true value function, offering a mathematical certificate of quality for the resulting policies.
Efficient GFODD Evaluation and Reduction
To implement the Template Method, the authors utilize Generalized First Order Decision Diagrams (GFODDs) to represent reward and value functions. They developed two major technical enhancements for GFODD manipulation:
- Variable Elimination (VE): A new model evaluation algorithm inspired by VE that aggregates variables early in the computation tree. This replaces "brute force" evaluation and significantly speeds up symbolic manipulation.
- Model Checking Reduction: The algorithm uses a set of "focus states" (a training set) to simplify complex symbolic diagrams. If a part of a diagram does not contribute to the value in the focus states, it is pruned, maintaining computational efficiency.
Experimental Evaluation
The approach was evaluated using the Inventory Control (IC) domain, comparing it against propositional solvers like SPUDD and MADCAP.
- Scalability: Propositional solvers, which ground the problem into specific instances, failed at 4–5 shops due to memory limits. The symbolic approach remained "domain-size agnostic," meaning the planning time was constant regardless of whether there were 5 shops or 500.
- Policy Quality: In standard IC domains, the approximate symbolic policy was indistinguishable from the optimal policy. In Advanced IC domains (where theoretical assumptions were intentionally violated), the policy remained robust and far outperformed random baselines.
Conclusion
The Template Method represents a significant step forward in relational planning, providing the first symbolic algorithm with explicit performance guarantees for domains with exogenous events. By assuming exogenous events are object-centered and independent, the authors successfully modeled complex transitions as manageable sequences. Future work will focus on relaxing the technical assumptions required for the lower bound proof and further improving the speed of diagram reduction techniques.
Summary updated