Proceedings

Probabilistic Knowledge-Based Programs

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 1594-1599.

© 2015 International Joint Conferences on Artificial Intelligence

Abstract

We introduce Probabilistic Knowledge-Based Programs (PKBPs), a new, compact representation of policies for factored partially observable Markov decision processes. PKBPs use branching conditions such as if the probability of Φ is larger than p, and many more. While similar in spirit to value-based policies, PKBPs leverage the factored representation for more compactness. They also cope with more general goals than standard state-based rewards, such as pure information-gathering goals. Compactness comes at the price of reactivity, since evaluating branching conditions on-line is not polynomial in general. In this sense, PKBPs are complementary to other representations. Our intended application is as a tool for experts to specify policies in a natural, compact language, then have them verified automatically. We study succinctness and the complexity of verification for PKBPs.

  1. [Araya-López et al., 2010] M. Araya-López, O. Buffet, V. Thomas, and F. Charpillet. A POMDP extension with belief-dependent rewards. In NIPS, pages 64-72, 2010.
  2. [Aucher, 2007] G. Aucher. Interpreting an action from what we perceive and what we expect. J. of Applied Non-classical Logics, 17(1):9-38, 2007.
  3. [Bacchus et al., 1999] F. Bacchus, J. Halpern, and H. Levesque. Reasoning about noisy sensors and effectors in the situation cal- culus. AIJ, 111(1-2):171-208, 1999.
  4. [Bäckström and Jonsson, 2011] C. Bäckström and P. Jonsson. Lim- its for compact representations of plans. In ICAPS, pages 146- 153, 2011.
  5. [Belle and Lakemeyer, 2011] V. Belle and G. Lakemeyer. A seman- tical account of progression in the presence of uncertainty. In AAAI, 2011.
  6. [Belle and Levesque, 2013] V. Belle and H. Levesque. Reasoning about probabilities in dynamic systems using goal regression. In UAI, 2013.
  7. [Bonet et al., 2010] B. Bonet, H. Palacios, and H. Geffner. Auto- matic derivation of finite-state machines for behavior control. In AAAI, 2010.
  8. [Boutilier and Poole, 1996] C. Boutilier and D. Poole. Computing optimal policies for partially observable decision processes using compact representations. In AAAI, pages 1168-1175, 1996.
  9. [Boutilier et al., 1999] C. Boutilier, T.. Dean, and S. Hanks. Decision-theoretic planning: Structural assumptions and compu- tational leverage. JAIR, 11:1-94, 1999.
  10. [Claßen and Lakemeyer, 2006] J. Claßen and G. Lakemeyer. Foun- dations for knowledge-based programs using ES. In KR, pages 318-328, 2006.
  11. [Darwiche, 2009] A. Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge Univ. Press, 2009.
  12. [Dean and Kanazawa, 1989] T. Dean and K. Kanazawa. A Model for Reasoning about Persistence and Causation. Computational Intelligence, 5:142-150, 1989.
  13. [Fagin et al., 1990] R. Fagin, J. Halpern, and N. Megiddo. A logic for reasoning about probabilities. Information and Computation, 87(1/2):78-128, 1990.
  14. [Fagin et al., 1995] R. Fagin, J. Halpern, Y. Moses, and M. Vardi. Reasoning about knowledge. MIT Press, 1995.
  15. [Gabaldon and Lakemeyer, 2007] A. Gabaldon and G. Lakemeyer. ESP: A logic of only-knowing, noisy sensing and acting. In AAAI, pages 974-979, 2007.
  16. [Hajishirzi and Amir, 2010] H. Hajishirzi and E. Amir. Reasoning about deterministic actions with probabilistic prior and applica- tion to stochastic filtering. In KR, 2010.
  17. [Hamilton et al., 2014] W. Hamilton, M. Milani Fard, and J. Pineau. Efficient learning and planning with compressed predictive states. JMLR, 15:3395-3439, 2014.
  18. [Hansen and Feng, 2000] E. Hansen and Z. Feng. Dynamic pro- gramming for POMDPs using a factored state representation. In AIPS, pages 130-139, 2000.
  19. [Herzig et al., 2003] A. Herzig, J. Lang, and P. Marquis. Action representation and partially observable planning using epistemic logic. In IJCAI, pages 1067-1072, 2003. IJCAI
  20. [Iocchi et al., 2009] L. Iocchi, T. Lukasiewicz, D. Nardi, and R. Rosati. Reasoning about actions with sensing under quali- tative and probabilistic uncertainty. ACM Trans. Comput. Log., 10(1), 2009.
  21. [Kushmerick et al., 1995] N. Kushmerick, S. Hanks, and D. Weld. An algorithm for probabilistic planning. AIJ, 76:239-286, 1995.
  22. [Lang and Zanuttini, 2012] J. Lang and B. Zanuttini. Knowledge- based programs as plans -the complexity of plan verification. In ECAI, pages 504-509, 2012.
  23. [Lang and Zanuttini, 2013] J. Lang and B. Zanuttini. Knowledge- based programs as plans: Succinctness and the complexity of plan existence. In TARK, 2013.
  24. [Laverny and Lang, 2005] N. Laverny and J. Lang. From knowledge-based programs to graded belief-based programs, part II: off-line reasoning. In IJCAI, pages 497-502, 2005. IJCAI
  25. [Madani et al., 2003] O. Madani, S. Hanks, and A. Condon. On the undecidability of probabilistic planning and related stochastic optimization problems. AIJ, pages 5-34, 2003.
  26. [Mundhenk et al., 2000] M. Mundhenk, J. Goldsmith, C. Lusena, and E. Allender. Complexity of finite-horizon Markov decision process problems. J. ACM, 47(4):681-720, 2000.
  27. [Poupart, 2005] P. Poupart. Exploiting Structure to efficiently solve large scale partially observable Markov decision processes. PhD thesis, University of Toronto, 2005.
  28. [Reiter, 2001] R. Reiter. Knowledge in action: logical foundations for specifying and implementing dynamical systems. MIT press, 2001.
  29. [Rens et al., 2014] G. Rens, T. Meyer, and G. Lakemeyer. SLAP: specification logic of actions with probability. J. Applied Logic, 12(2):128-150, 2014.
  30. [Sabbadin et al., 2007] R. Sabbadin, J. Lang, and N. Ravoanjana- hary. Purely epistemic Markov decision processes. In AAAI, 2007.
  31. [Sanner and Boutilier, 2009] S. Sanner and C. Boutilier. Practical solution techniques for first-order MDPs. AIJ, 173(5):748-788, 2009.
  32. [Shani et al., 2008] G. Shani, R. Brafman, S. Shimony, and P. Poupart. Efficient ADD operations for point-based algorithms. In ICAPS, pages 330-337, 2008.
  33. [Shani et al., 2013] G. Shani, J. Pineau, and R. Kaplow. A survey of point-based POMDP solvers. Autonomous Agents and Multi- Agent Systems, 27(1):1-51, 2013.
  34. [Sim et al., 2008] H. Sim, K.-E. Kim, J. Kim, D.-S. Chang, and M.- W. Koo. Symbolic heuristic search value iteration for factored POMDPs. In AAAI, pages 1088-1093, 2008.
  35. [Son and Baral, 2001] T. C. Son and C. Baral. Formalizing sensing actions: A transition function based approach. AIJ, 125(1-2):19- 91, 2001.
  36. [van Eijck and Schwarzentruber, 2014] J. van Eijck and F. Schwarzentruber. Epistemic probability logic simplified. In Advances in Modal Logic, pages 158-177, 2014.
  37. [Wang and Schmolze, 2005] C. Wang and J. Schmolze. Planning with POMDPs using a compact, logic-based representation. In ICTAI, pages 523-530, 2005.
  38. [Younes et al., 2005] H. Younes, M. Littman, D. Weissman, and J. Asmuth. The first probabilistic track of the international plan- ning competition. JAIR, 24:851-887, 2005.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards