2013/06/26 by Saket Joshi, S. Joshi, Roni Khardon +12
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Machine Learning (cs.LG) #Multi-Agent Systems and Negotiation #cs.AI #cs.LG
paper · pdf · doi:10.48550/arxiv.1306.6302
This is an extended version of our ECML/PKDD 2013 paper including all proofs. (v2 corrects typos and updates ref [10] to cite this report as the full version)
openalex publication_date 2013/06/26 · arxiv created 2013/06/27 · arxiv updated 2013/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.