Proceedings

A Formal Account of Nondeterministic and Failed Actions

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 861-867.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

Nondeterminism is pervasive in all but the simplest action domains: an agent may flip a coin or pick up a different object than intended, or an action may fail and may fail in different ways. In this paper we provide a qualitative theory of nondeterminism. The account is based on an epistemic extension to the situation calculus that accommodates sensing actions. Our position is that nondeterminism is an epistemic phenomenon, and that the world is most usefully regarded as deterministic. Nondeterminism arises from an agent's limited awareness and perception. The account offers several advantages: an agent has a set of categorical (as opposed to probabilistic) beliefs, yet can deal with equally-likely outcomes (such as in flipping a fair coin) or with outcomes of differing plausibility (such as an action that may on rare occasion fail).

  1. [Bacchus et al., 1999] F. Bacchus, J.Y. Halpern, and H.J. Levesque. Reasoning about noisy sensors and effectors in the situation calculus. Artificial Intelligence, 111(1- 2):171-208, 1999.
  2. [Baral, 1995] Chitta Baral. Reasoning about actions: Non- deterministic effects, constraints, and qualification. In Pro- ceedings of the International Joint Conference on Artificial Intelligence, pages 2017-2026, Montréal, Canada, 1995.
  3. [Boutilier et al., 2000] Craig Boutilier, Raymond Reiter, Mikhail Soutchanski, and Sebastian Thrun. Decision- theoretic, high-level agent programming in the situation calculus. In Proceedings of the AAAI National Confer- ence on Artificial Intelligence, pages 355-362, Austin, TX, 2000.
  4. [Cassandra et al., 1994] Anthony R. Cassandra, Leslie Pack Kaelbling, and Michael L. Littman. Acting optimally in partially observable stochastic domains. In Proceedings of the AAAI National Conference on Artificial Intelligence, pages 1023-1028, Seattle, WA, 1994.
  5. [Cimatti et al., 2003] Alessandro Cimatti, Marco Pistore, Marco Roveri, and Paolo Traverso. Weak, strong, and strong cyclic planning via symbolic model checking. Arti- ficial Intelligence, 147(1-2):35-84, 2003.
  6. [Darwiche and Pearl, 1997] A. Darwiche and J. Pearl. On the logic of iterated belief revision. Artificial Intelligence, 89:1-29, 1997.
  7. [Delgrande and Levesque, 2012] J.P. Delgrande and Hec- tor J. Levesque. Belief revision with sensing and fallible actions. In Thirteenth International Conference on Princi- ples of Knowledge Representation and Reasoning, Rome, Italy, 2012.
  8. [Gärdenfors, 1988] P. Gärdenfors. Knowledge in Flux: Mod- elling the Dynamics of Epistemic States. The MIT Press, Cambridge, MA, 1988.
  9. [Gelfond and Lifschitz, 1998] Michael Gelfond and Vladimir Lifschitz. Action languages. Electronic Transactions on AI, 3, 1998.
  10. [Ginsberg and Smith, 1988] Matthew L. Ginsberg and David E. Smith. Reasoning about action ii: The quali- fication problem. Artificial Intelligence, 35(3):311-342, 1988.
  11. [Giunchiglia et al., 2004] E. Giunchiglia, J. Lee, V. Lifs- chitz, N. McCain, and H. Turner. Nonmonotonic causal theories. Artificial Intelligence, 153(1-2):49-104, 2004.
  12. [Jensen et al., 2004] Rune M. Jensen, Manuela M. Veloso, and Randal E. Bryant. Fault tolerant planning: To- ward probabilistic uncertainty models in symbolic non- deterministic planning. In Shlomo Zilberstein, Jana Koehler, and Sven Koenig, editors, Proceedings of the Fourteenth International Conference on Automated Plan- ning and Scheduling (ICAPS 2004), pages 335-344. AAAI Press, 2004.
  13. [Laplace, 1814] P. Laplace. Essai philosophique sur les probabilités. (English trans: Dover, 1952), Paris, first edi- tion, 1814.
  14. [Levesque et al., 1997] H.J. Levesque, R. Reiter, F. Lin, and R.B. Scherl. Golog: A logic programming language for dynamic domains. Journal of Logic Programming, 31, 1997.
  15. [Levesque et al., 1998] H.J. Levesque, F. Pirri, and R. Re- iter. Foundations for the situation calculus. Linköping Electronic Articles in Computer and Information Science, 3(18), 1998.
  16. [McCarthy, 1977] J. McCarthy. Epistemological problems in artificial intelligence. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1038- 1044, Cambridge, MA, 1977.
  17. [Peppas, 2008] P. Peppas. Belief revision. In F. van Harme- len, V. Lifschitz, and B. Porter, editors, Handbook of Knowledge Representation, pages 317-359. Elsevier Sci- ence, San Diego, USA, 2008.
  18. [Poole, 2008] David Poole. The independent choice logic and beyond. In Luc De Raedt, Paolo Frasconi, Kris- tian Kersting, and Stephen Muggleton, editors, Probabilis- tic Inductive Logic Programming, volume 4911 of LNAI, Berlin, 2008. Springer.
  19. [Pratt, 1976] V. Pratt. Semantical considerations on Floyd- Hoare logic. In 17th IEEE Symposium on Foundations of Computer Science, pages 109-121, 1976.
  20. [Puterman, 1994] M. L. Puterman. Markov Decision Pro- cesses. Wiley, 1994.
  21. [Reiter, 2001] R. Reiter. Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems. The MIT Press, Cambridge, MA, 2001.
  22. [Scherl and Levesque, 2003] R.B. Scherl and H.J. Levesque. Knowledge, action, and the frame problem. Artificial In- telligence, 144(1-2):1-39, 2003.
  23. [Shanahan, 1997] Murray Shanahan. Solving the frame problem -a mathematical investigation of the common sense law of inertia. MIT Press, 1997.
  24. [Shapiro et al., 2011] Steven Shapiro, Maurice Pagnucco, Yves Lespérance, and Hector J. Levesque. Iterated be- lief change in the situation calculus. Artificial Intelligence, 175(1):165-192, 2011.
  25. [Son and Baral, 2001] T. Son and C. Baral. Formalizing sensing actions: A transition function based approach. Ar- tificial Intelligence, 125(1-2):19-91, 2001.
  26. [Spohn, 1988] W. Spohn. Ordinal conditional functions: A dynamic theory of epistemic states. In W.L. Harper and B. Skyrms, editors, Causation in Decision, Belief Change, and Statistics, volume II, pages 105-134. Kluwer Aca- demic Publishers, 1988.
  27. [Thielscher, 2001] M. Thielscher. The qualification problem: A solution to the problem of anomalous models. Artificial Intelligence, 131(1-2):1-37, 2001.

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

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