Probabilistic relational planning with first order decision diagrams Dynamic programming algorithms have been successfully applied to propositional stochastic planning problems by using compact representations, in particular algebraic decision diagrams, to capture domain dynamics and value functions. Work on symbolic dynamic programming lifted these ideas to first order logic using several representation schemes. Recent work introduced a first order variant of decision diagrams (FODD) and developed a value iteration algorithm for this representation. This paper develops several improvements to the FODD algorithm that make the approach practical. These include new reduction operators that decrease the size of the representation, several speedup techniques, and techniques for value approximation. Incorporating these, the paper presents a planning system, FODD-Planner, for solving relational stochastic planning problems. The system is evaluated on several domains, including problems from the recent international planning competition, and shows competitive performance with top ranking systems. This is the first demonstration of feasibility of this approach and it shows that abstraction through compact representation is a promising approach to stochastic planning.

References in zbMATH (referenced in 14 articles , 1 standard article )

Showing results 1 to 14 of 14.
Sorted by year (citations)

  1. Magnan, Jean-Christophe; Wuillemin, Pierre-Henri: Efficient incremental planning and learning with multi-valued decision diagrams (2017)
  2. Nitti, Davide; Belle, Vaishak; De Laet, Tinne; De Raedt, Luc: Planning in hybrid relational MDPs (2017)
  3. Arruda, E. F.; Fragoso, M. D.: Solving average cost Markov decision processes by means of a two-phase time aggregation algorithm (2015)
  4. Hescott, Benjamin J.; Khardon, Roni: The complexity of reasoning with FODD and GFODD (2015)
  5. Neubert, Stefanie; Belzner, Lenz; Wirsing, Martin: Algebraic reinforcement learning. Hypothesis induction for relational reinforcement learning using term generalization. (2015)
  6. Brafman, Ronen I.: Relational preference rules for control (2011) ioport
  7. Fern, Alan; Khardon, Roni; Tadepalli, Prasad: The first learning track of the international planning competition (2011) ioport
  8. Joshi, Saket; Kersting, Kristian; Khardon, Roni: Decision-theoretic planning with generalized first-order decision diagrams (2011)
  9. Joshi, S.; Khardon, R.: Probabilistic relational planning with first order decision diagrams (2011)
  10. Lang, Tobias; Toussaint, Marc: Planning with noisy probabilistic relational rules (2010)
  11. Sanner, Scott; Boutilier, Craig: Practical solution techniques for first-order MDPs (2009)
  12. van Otterlo, Martijn: Intensional dynamic programming. A rosetta stone for structured dynamic programming (2009)
  13. van Otterlo, Martijn: The logic of adaptive behavior. Knowledge representation and algorithms for adaptive sequential decision making under uncertainty in first-order and relational domains. (2009)
  14. Wang, C.; Joshi, S.; Khardon, R.: First order decision diagrams for relational MDPS (2008)