Practical solution techniques for first-order MDPs

By Scott Sanner, Craig Boutilier. 2009

110 citations recorded by the source corpus.

Many traditional solution approaches to relationally specified decision-theoretic planning problems (e.g., those stated in the probabilistic planning domain description language, or PPDDL) ground the specification with respect to a specific instantiation of domain objects and apply a solution approach directly to the resulting ground Markov decision process (MDP). Unfortunately, the space and time complexity of these grounded solution approaches are polynomial in the number of domain objects and exponential in the predicate arity and the number of nested quantifiers in the relational problem specification. An alternative to grounding a relational planning problem is to tackle the problem directly at the relational level. In this article, we propose one such approach that translates an expressive subset of the PPDDL representation to a first-order MDP (FOMDP) specification and then derives a domain-independent policy without grounding at any intermediate step. However, such generality does not come without its own set of challenges-the purpose of this article is to explore practical solution techniques for solving FOMDPs. To demonstrate the applicability of our techniques, we present proof-of-concept results of our first-order approximate linear programming (FOALP) planner on problems from the probabilistic track of the ICAPS 2004 and 2006 International Planning Competitions.

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).”
A Survey on Machine-Learning Techniques in Cognitive Radios (2013, methodology): “The value-iteration algorithm is an iterative algorithm that is based on the Bellman’s principl e of optimality [88], [89].”
Learning Features and Abstract Actions for Computing Generalized Plans (2018, methodology): “Generalized planning has also been formulated as a problem in first-order logic (Srivastava, Immerman, and Zilberstein 2011), and general plans over finite horizons have been derived using first-order regression (Boutilier, Reiter, and Price 2001; Wang, Joshi, and Khardon 2008; van Otterlo, M. 2012;”
Statistical Relational Artificial Intelligence: Logic, Probability, and Computation (2016, methodology): “First-order approximate linear programming (FOALP) [Sanner and Boutilier, 2009] directly approximates the FOMDP value function using a linear program.”