Abstract
Being able to compactly represent large state spaces is crucial in solving a vast majority of practical stochastic planning problems. This requirement is even more stringent in the context of multi-agent systems, in which the world to be modeled also includes the mental state of other agents. This leads to a hierarchy of beliefs that results in a continuous, unbounded set of possible interactive states, as in the case of Interactive POMDPs. In this paper, we describe a novel representation for interactive belief hierarchies that combines first-order logic and probability. The semantics of this new formalism is based on recursively partitioning the belief space at each level of the hierarchy; in particular, the partitions of the belief simplex at one level constitute the vertices of the simplex at the next higher level. Since in general a set of probabilistic statements only partially specifies a probability distribution over the space of interest, we adopt the maximum entropy principle in order to convert it to a full specification.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aumann, R.J.: Interactive epistemology II: Probability. International Journal of Game Theory 28(3), 301–314 (1999)
Bacchus, F.: Representing and reasoning with probabilistic knowledge: a logical approach to probabilities. MIT Press, Cambridge (1990)
Boutilier, C., Poole, D.: Computing optimal policies for partially observable decision processes using compact representations. In: Proceedings of the National Conference on Artificial Intelligence, pp.1168–1175 (1996)
Boutilier, C., Reiter, R., Price, B.: Symbolic Dynamic Programming for First-Order MDPs. In: IJCAI 2001, pp. 690–700. Morgan Kaufmann, San Francisco (2001)
Doshi, P., Gmytrasiewicz, P.J.: Monte Carlo sampling methods for approximating interactive POMDPs. J. Artif. Int. Res. 34, 297–337 (2009)
Doshi, P., Perez, D.: Generalized point based value iteration for interactive POMDPs. In: Proceedings of the 23rd National Conference on Artificial Intelligence, vol. 1, pp. 63–68. AAAI Press, Menlo Park (2008)
Fagin, R., Halpern, J.Y.: Reasoning about knowledge and probability. J. ACM 41, 340–367 (1994)
Gmytrasiewicz, P.J., Doshi, P.: A framework for sequential planning in multi-agent settings. Journal of Artificial Intelligence Research 24, 24–49 (2005)
Halpern, J.Y.: An analysis of first-order logics of probability. In: Proceedings of the 11th International Joint Conference on Artificial Intelligence, vol. 2, pp. 1375–1381. Morgan Kaufmann Publishers Inc., San Francisco (1989)
Halpern, J.Y.: Reasoning about Uncertainty. MIT Press, Cambridge (2003)
Halpern, J.Y., Moses, Y.: Knowledge and common knowledge in a distributed environment. J. ACM 37, 549–587 (1990)
Harsanyi, J.C.: Games with Incomplete Information Played by “Bayesian” Players, I-III. Part I. The Basic Model. Management Science 14(3), 159–182 (1967)
Jaynes, E.T.: Information Theory and Statistical Mechanics. Physical Review Online Archive (Prola) 106(4), 620–630 (1957)
Kern-Isberner, G., Thimm, M.: Novel semantical approaches to relational probabilistic conditionals. In: Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning (2010)
Koller, D., Pfeffer, A.: Probabilistic frame-based systems. In: Proceedings of the 15th National Conference on Artificial Intelligence (AAAI), pp. 580–587 (1998)
Lukasiewicz, T., Kern-Isberner, G.: Probabilistic logic programming under maximum entropy. In: Hunter, A., Parsons, S. (eds.) ECSQARU 1999. LNCS (LNAI), vol. 1638, pp. 279–292. Springer, Heidelberg (1999)
Milch, B., Marthi, B., Russell, S.J., Sontag, D., Ong, D.L., Kolobov, A.: Blog: Probabilistic models with unknown objects. In: Probabilistic, Logical and Relational Learning (2005)
Nilsson, N.J.: Probabilistic logic. Artif. Intell. 28, 71–88 (1986)
Poupart, P.: Exploiting structure to efficiently solve large scale Partially Observable Markov Decision Processes. Ph.D. thesis, University of Toronto, Toronto, Ont., Canada (2005), aAINR02727
Richardson, M., Domingos, P.: Markov logic networks. Mach. Learn. 62, 107–136 (2006)
Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 3rd edn. Pearson Education, London (2010)
Sanner, S., Boutilier, C.: Practical solution techniques for first-order MDPs. Artif. Intell. 173, 748–788 (2009)
Sanner, S., Kersting, K.: Symbolic dynamic programming for first-order POMDPs. In: AAAI 2010, pp. 1140–1146 (2010)
Shirazi, A., Amir, E.: Factored models for probabilistic modal logic. In: Proceedings of the 23rd National Conference on Artificial Intelligence, vol. 1, pp. 541–547. AAAI Press, Menlo Park (2008)
Wang, C., Joshi, S., Khardon, R.: First order decision diagrams for relational MDPs. J. Artif. Int. Res. 31, 431–472 (2008)
Wang, C., Khardon, R.: Relational partially observable MDPs. In: AAAI 2010, pp. 1153–1157 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Panella, A., Gmytrasiewicz, P. (2011). A Partition-Based First-Order Probabilistic Logic to Represent Interactive Beliefs. In: Benferhat, S., Grant, J. (eds) Scalable Uncertainty Management. SUM 2011. Lecture Notes in Computer Science(), vol 6929. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23963-2_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-23963-2_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23962-5
Online ISBN: 978-3-642-23963-2
eBook Packages: Computer ScienceComputer Science (R0)