Approximate inference for planning in stochastic relational worlds

ABSTRACT

Relational world models that can be learned from experience in stochastic domains have received significant attention recently. However, efficient planning using these models remains a major issue. We propose to convert learned noisy probabilistic relational rules into a structured dynamic Bayesian network representation. Predicting the effects of action sequences using approximate inference allows for planning in complex worlds. We evaluate the effectiveness of our approach for online planning in a 3D simulated blocksworld with an articulated manipulator and realistic physics. Empirical results show that our method can solve problems where existing methods fail.

REFERENCES

• 1: Botvinick, M. M., & An, J. (2009). Goal-directed decision making in prefrontal cortex: a computational framework. Advances in Neural Information Processing Systems (NIPS) (pp. 169--176).
• 2: Croonenborghs, T., Ramon, J., Blockeel, H., & Bruynooghe, M. (2007). Online learning and exploiting relational models in reinforcement learning. Proc. of the Int. Conf. on Artificial Intelligence (IJ-CAI) (pp. 726--731).
• 3: Peter Dayan , Geoffrey E. Hinton, Using expectation-maximization for reinforcement learning, Neural Computation, v.9 n.2, p.271-278, Feb. 15, 1997 [doi>10.1162/neco.1997.9.2.271]
• 4: Gardiol, N. H., & Kaelbling, L. P. (2007). Action-space partitioning for planning. Proc. of the Nat. Conf. on Artificial Intelligence (AAAI) (pp. 980--986).
• 5: Lise Getoor , Ben Taskar, Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning), The MIT Press, 2007
• 6: Michael Kearns , Yishay Mansour , Andrew Y. Ng, A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes, Machine Learning, v.49 n.2-3, p.193-208, November-December 2002 [doi>10.1023/A:1017932429737]
• 7: Kristian Kersting , Martijn Van Otterlo , Luc De Raedt, Bellman goes relational, Proceedings of the twenty-first international conference on Machine learning, p.59, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015401]
• 8: Kevin P. Murphy , Yair Weiss, The Factored Frontier Algorithm for Approximate Inference in DBNs, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.378-385, August 02-05, 2001
• 9: Pasula, H. M., Zettlemoyer, L. S., & Kaelbling, L. P. (2007). Learning symbolic models of stochastic domains. Artificial Intelligence Research, 29, 309--352.
• 10: Sanghai, S., Domingos, P., & Weld, D. (2005). Relational dynamic Bayesian networks. Artificial Intelligence Research, 24, 759--797.
• 11: Sanner, S., & Boutilier, C. (2007). Approximate solution techniques for factored first-order MDPs. Proc. of the Int. Conf. on Automated Planning and Scheduling (ICAPS) (pp. 288--295).
• 12: Marc Toussaint , Amos Storkey, Probabilistic inference for solving discrete and continuous state Markov Decision Processes, Proceedings of the 23rd international conference on Machine learning, p.945-952, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143963]
• 13: van Otterlo, M. (2009). The logic of adaptive behavior. IOS Press, Amsterdam.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Inference engines

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory