Reasoning about actions with sensing under qualitative and probabilistic uncertainty

ABSTRACT

We focus on the aspect of sensing in reasoning about actions under qualitative and probabilistic uncertainty. We first define the action language E for reasoning about actions with sensing, which has a semantics based on the autoepistemic description logic ALCK_NF, and which is given a formal semantics via a system of deterministic transitions between epistemic states. As an important feature, the main computational tasks in E can be done in linear and quadratic time. We then introduce the action language E+ for reasoning about actions with sensing under qualitative and probabilistic uncertainty, which is an extension of E by actions with nondeterministic and probabilistic effects, and which is given a formal semantics in a system of deterministic, nondeterministic, and probabilistic transitions between epistemic states. We also define the notion of a belief graph, which represents the belief state of an agent after a sequence of deterministic, nondeterministic, and probabilistic actions, and which compactly represents a set of unnormalized probability distributions. Using belief graphs, we then introduce the notion of a conditional plan and its goodness for reasoning about actions under qualitative and probabilistic uncertainty. We formulate the problems of optimal and threshold conditional planning under qualitative and probabilistic uncertainty, and show that they are both uncomputable in general. We then give two algorithms for conditional planning in our framework. The first one is always sound, and it is also complete for the special case in which the relevant transitions between epistemic states are cycle-free. The second algorithm is a sound and complete solution to the problem of finite-horizon conditional planning in our framework. Under suitable assumptions, it computes every optimal finite-horizon conditional plan in polynomial time. We also describe an application of our formalism in a robotic-soccer scenario, which underlines its usefulness in realistic applications.

REFERENCES

• 1: Baader, F., Lutz, C., Milicic, M., Sattler, U., and Wolter, F. 2005. Integrating description logics and action formalisms: First results. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI-2005). AAAI Press/MIT Press, Cambridge, MA, 572--577.
• 2: Bacchus, F., Halpern, J. Y., and Levesque, H. J. 1995. Reasoning about noisy sensors and effectors in the situation calculus. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-1995). Morgan-Kaufmann, San Francisco, CA, 1933--1940.
• 3: Fahiem Bacchus , Joseph Y. Halpern , Hector J. Levesque, Reasoning about noisy sensors and effectors in the situation calculus, Artificial Intelligence, v.111 n.1-2, p.171-208, July 1999 [doi>10.1016/S0004-3702(99)00031-4]
• 4: Chitta Baral , Nam Tran , Le-Chi Tuan, Reasoning about actions in a probabilistic setting, Eighteenth national conference on Artificial intelligence, p.507-512, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 5: Berners-Lee, T. 1999. Weaving the Web. Harper, San Francisco, CA.
• 6: Boutilier, C., Reiter, R., and Price, B. 2001. Symbolic dynamic programming for first-order MDPs. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-2001). Morgan-Kaufmann, San Francisco, CA, 690--700.
• 7: Craig Boutilier , Raymond Reiter , Mikhail Soutchanski , Sebastian Thrun, Decision-Theoretic, High-Level Agent Programming in the Situation Calculus, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.355-362, July 30-August 03, 2000
• 8: A. Condon , R. J. Lipton, On the complexity of space bounded interactive proofs, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.462-467, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63519]
• 9: Jürgen Dix , Sarit Kraus , V. S. Subrahmanian, Heterogeneous temporal probabilistic agents, ACM Transactions on Computational Logic (TOCL), v.7 n.1, p.151-198, January 2006 [doi>10.1145/1119439.1119444]
• 10: Jürgen Dix , Mirco Nanni , V. S. Subrahmanian, Probabilistic agent programs, ACM Transactions on Computational Logic (TOCL), v.1 n.2, p.208-246, Oct. 2000 [doi>10.1145/359496.359508]
• 11: Francesco M. Donini , Daniele Nardi , Riccardo Rosati, Description logics of minimal knowledge and negation as failure, ACM Transactions on Computational Logic (TOCL), v.3 n.2, p.177-225, April 2002 [doi>10.1145/505372.505373]
• 12: Draper, D., Hanks, S., and Weld, D. S. 1994. Probabilistic planning with information gathering and contingent execution. In Proceedings of the International Conference on Artificial Intelligence Planning Systems (AIPS-1994). AAAI Press, Menlo Park, CA, 31--36.
• 13: Thomas Eiter , Wolfgang Faber , Nicola Leone , Gerald Pfeifer , Axel Polleres, A logic programming approach to knowledge-state planning, II: the DLV^k system, Artificial Intelligence, v.144 n.1-2, p.157-211, March 2003 [doi>10.1016/S0004-3702(02)00367-3]
• 14: Eiter, T. and Lukasiewicz, T. 2003. Probabilistic reasoning about actions in nonmonotonic causal theories. In Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence (UAI-2003). Morgan-Kaufmann, San Francisco, CA, 192--199.
• 15: Thomas Eiter , V. S. Subrahmanian , George Pick, Heterogeneous active agents, I: semantics, Artificial Intelligence, v.108 n.1-2, p.179-255, March 1999 [doi>10.1016/S0004-3702(99)00005-3]
• 16: Dieter Fensel , Wolfgang Wahlster , Henry Lieberman, Spinning the Semantic Web: Bringing the World Wide Web to Its Full Potential, MIT Press, Cambridge, MA, 2002
• 17: Finzi, A. and Pirri, F. 2001. Combining probabilities, failures and safety in robot control. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-2001). Morgan-Kaufmann, San Francisco, CA, 1331--1336.
• 18: Héctor Geffner, Perspectives on artificial intelligence planning, Eighteenth national conference on Artificial intelligence, p.1013-1023, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 19: Gelfond, M. and Lifschitz, V. 1993. Representing action and change by logic programs. J. Logic Program. 17, 301--322.
• 20: Enrico Giunchiglia , Joohyung Lee , Vladimir Lifschitz , Norman McCain , Hudson Turner, Nonmonotonic causal theories, Artificial Intelligence, v.153 n.1-2, p.49-104, March 2004 [doi>10.1016/j.artint.2002.12.001]
• 21: Henrik Grosskreutz , Gerhard Lakemeyer, Belief Update in the pGOLOG Framework, Proceedings of the Joint German/Austrian Conference on AI: Advances in Artificial Intelligence, p.213-228, September 19-21, 2001
• 22: Joseph Y. Halpern , Mark R. Tuttle, Knowledge, probability, and adversaries, Journal of the ACM (JACM), v.40 n.4, p.917-960, Sept. 1993 [doi>10.1145/153724.153770]
• 23: Horrocks, I., Patel-Schneider, P. F., and van Harmelen, F. 2003. From SHIQ and RDF to OWL: The making of a web ontology language. J. Web Semantics 1, 1, 7--26.
• 24: Iocchi, L. 1999. Design and Development of Cognitive Robots. Ph.D. dissertation. University of Rome “La Sapienza”, Rome, Italy. Available at www.dis.uniroma1.it/~iocchi/publications.html.
• 25: Iocchi, L., Lukasiewicz, T., Nardi, D., and Rosati, R. 2006. Reasoning about actions with sensing under qualitative and probabilistic uncertainty. Tech. Rep. INFSYS RR-1843-03-05, Institut für Informationssysteme, Technische Universität Wien. March.
• 26: Iocchi, L., Nardi, D., and Rosati, R. 2000. Planning with sensing, concurrency, and exogenous events: Logical framework and implementation. In Proceedings KR-2000. Morgan-Kaufmann, San Francisco, CA, 678--689.
• 27: Leslie Pack Kaelbling , Michael L. Littman , Anthony R. Cassandra, Planning and acting in partially observable stochastic domains, Artificial Intelligence, v.101 n.1-2, p.99-134, May 1998 [doi>10.1016/S0004-3702(98)00023-X]
• 28: Lars Karlsson, Conditional Progressive Planning: A Preliminary Report, Proceedings of the Seventh Scandinavian Conference on Artificial Intelligence, p.90-100, February 19-21, 2001
• 29: Lang, J., Lin, F., and Marquis, P. 2003. Causal theories of action: A computational core. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-2003). Morgan-Kaufmann, San Francisco, CA, 1073--1078.
• 30: Levesque, H. J. 1996. What is planning in presence of sensing? In Proceedings of the National Conference on Artificial Intelligence (AAAI-1996). AAAI Press/MIT Press, Cambridge, MA, 1139--1149.
• 31: Vladimir Lifschitz, Minimal belief and negation as failure, Artificial Intelligence, v.70 n.1-2, p.53-72, Oct. 1994 [doi>10.1016/0004-3702(94)90103-1]
• 32: Lobo, J., Mendez, G., and Taylor, S. R. 1997. Adding knowledge to the action description language A. In Proceedings of the National Conference on Artificial Intelligence (AAAI-1997). AAAI Press/MIT Press, Cambridge, MA, 454--459.
• 33: Omid Madani , Steve Hanks , Anne Condon, On the undecidability of probabilistic planning and related stochastic optimization problems, Artificial Intelligence, v.147 n.1-2, p.5-34, July 2003 [doi>10.1016/S0004-3702(02)00378-8]
• 34: Paulo Mateus , António Pacheco , Javier Pinto , Amílcar Sernadas , Cristina Sernadas, Probabilistic Situation Calculus, Annals of Mathematics and Artificial Intelligence, v.32 n.1-4, p.393-431, August 2001 [doi>10.1023/A:1016738205696]
• 35: Motik, B., Horrocks, I., Rosati, R., and Sattler, U. 2006. Can OWL and logic programming live together happily ever after? In Proceedings of the 5th International Semantic Web Conference (ISWC-2006). Lecture Notes in Computer Science, vol. 4273, Springer-Verlag, Berlin, Germany, 501--514.
• 36: Motik, B. and Rosati, R. 2007. A faithful integration of description logics with logic programming. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-2007). 477--482.
• 37: Nilufer Onder , Martha E. Pollack, Conditional, probabilistic planning: a unifying algorithm and effective search control mechanisms, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.577-584, July 18-22, 1999, Orlando, Florida, United States
• 38: Azaria Paz, Introduction to probabilistic automata (Computer science and applied mathematics), Academic Press, Inc., Orlando, FL, 1971
• 39: Fiora Pirri , Ray Reiter, Some contributions to the metatheory of the situation calculus, Journal of the ACM (JACM), v.46 n.3, p.325-361, May 1999 [doi>10.1145/316542.316545]
• 40: David Poole, The independent choice logic for modelling multiple agents under uncertainty, Artificial Intelligence, v.94 n.1-2, p.7-56, July 1997 [doi>10.1016/S0004-3702(97)00027-1]
• 41: David Poole, Logic, Knowledge Representation, and Bayesian Decision Theory, Proceedings of the First International Conference on Computational Logic, p.70-86, July 01, 2000
• 42: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 43: Knowlege in action: logical foundations for specifying and implementing dynamical systems, MIT Press, Cambridge, MA, 2001
• 44: Shapiro, S. 2005. Belief change with noisy sensing and introspection. In Proceedings on Nonmonotonic Reasoning, Action, and Change (NRAC-2005).
• 45: Tran Cao Son , Chitta Baral, Formalizing sensing actions—a transition function based approach, Artificial Intelligence, v.125 n.1-2, p.19-91, Jan. 2001 [doi>10.1016/S0004-3702(00)00080-1]
• 46: Son, T. C., Tu, P. H., and Baral, C. 2004. Planning with sensing actions and incomplete information using logic programming. In Proceedings LPNMR-2004. Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, vol. 2923. Springer-Verlag, Berlin, Germany, 261--274.
• 47: V. S. Subrahmanian , Charlie Ward, A Deductive Database Approach to Planning in Uncertain Environments, Proceedings of the International Workshop on Logic in Databases, p.83-98, July 01-02, 1996
• 48: W3C. 2004. OWL web ontology language overview. W3C Recommendation (10 February 2004). Available at www.w3.org/TR/2004/REC-owl-features-20040210/.
• 49: Dongmo Zhang , Samir Chopra , Norman Y. Foo, Consistency of Action Descriptions, Proceedings of the 7th Pacific Rim International Conference on Artificial Intelligence: Trends in Artificial Intelligence, p.70-79, August 18-22, 2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representation languages

General Terms:
Algorithms, Languages

Keywords:
Reasoning about actions, action languages, description logics, imprecise probabilities, qualitative and probabilistic uncertainty, sensing