First Order Decision Diagrams for Relational MDPs

By Chenggang Wang, Saket Joshi, Roni Khardon. 2007

94 citations recorded by the source corpus.

Markov decision processes capture sequential decision making under uncertainty, where an agent must choose actions so as to optimize long term reward. The paper studies efficient reasoning mechanisms for Relational Markov Decision Processes (RMDP) where world states have an internal relational structure that can be naturally described in terms of objects and relations among them. Two contributions are presented. First, the paper develops First Order Decision Diagrams (FODD), a new compact representation for functions over relational structures, together with a set of operators to combine FODDs, and novel reduction techniques to keep the representation small. Second, the paper shows how FODDs can be used to develop solutions for RMDPs, where reasoning is performed at the abstract level and the resulting optimal policy is independent of domain size (number of objects) or instantiation. In particular, a variant of the value iteration algorithm is developed by using special operations over FODDs, and the algorithm is shown to converge to the optimal policy.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Fitted Q-Learning for Relational Domains (2020, background): “…worlds, and methods that directly learn and reason at the ﬁrst-order level have been developed in the broad area of Relational Reinforcement Learning (RRL) (Price and Boutilier 2001; Sanner and Boutilier 2009; Wang, Joshi, and Khardon 2008; Tadepalli, Givan, and Driessens 2004; Wu and Givan 2007).”
Practical solution techniques for first-order MDPs (2009, methodology): “First-order decision diagrams (FODDs) (Wang et al., 2008) have been introduced to compactly represent case statements and to permit efficient application of symbolic dynamic programming operations to another restricted class of relational MDPs via value iteration (Wang et al.”
Statistical Relational Artificial Intelligence: Logic, Probability, and Computation (2016, methodology): “In addition, first-order decision diagrams (FODDs) have been introduced to compactly represent case statements and to permit efficient application of symbolic dynamic programming operations to solve RMDPs via value iteration and policy iteration [Wang et al., 2008].”
Non-parametric policy gradients: a unified treatment of propositional and relational domains (2008, background): “NPPG is naturally applicable in this case and, hence, paves the way towards (model-free) solutions of what can be called relational POMDPs.”
Learning Features and Abstract Actions for Computing Generalized Plans (2018, methodology): “…been formulated as a problem in ﬁrst-order logic (Srivastava, Immerman, and Zilberstein 2011), and general plans over ﬁnite horizons have been derived using ﬁrst-order regression (Boutilier, Reiter, and Price 2001; Wang, Joshi, and Khardon 2008; van Otterlo, M. 2012; Sanner and Boutilier 2009).”