×

Dynamic multiagent probabilistic inference. (English) Zbl 1184.68498

Summary: Cooperative multiagent probabilistic inference can be applied in areas such as building surveillance and complex system diagnosis to reason about the states of the distributed uncertain domains. In the static cases, multiply sectioned Bayesian networks (MSBNs) have provided a solution when interactions within each agent are structured and those among agents are limited. However, in the dynamic cases, the agents’ inference will not guarantee exact posterior probabilities if each agent evolves separately using a single agent dynamic Bayesian network. Nevertheless, due to the discount of the past, we may not have to use the whole history of a domain to reason about its current state. In this paper, we propose to reason about the state of a distributed dynamic domain period by period using an MSBN. To reduce the influence of the ignored history on the posterior probabilities to a minimum, we propose to observe as many observable variables as possible in the modeled history. Due to the limitations of the problem domains, it could be very costly to observe all observable variables. We present a distributed algorithm to compute all observable variables that are relevant to our concerns. Experimental results on the relationship between the computational complexity and the length of the represented history, and effectiveness of the approach are presented.

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
68T42 Agent technology and artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lesser, V. R.; Erman, L. D., Distributed interpretation: a model and experiment, IEEE Transactions on Computers (12), C-29, 12, 1144-1163 (1980)
[2] Y. Xiang, B. Pant, A. Eisen, M. P. Beddoes, D. Poole, Painulm: a neuromuscular diagnostic aid using multiply sectioned Bayesian networks, in: D. I. Hudson (Ed.), Proceedings of ISMM (International Society for Mini and Microcomputers) International Conference on Mini and Microcomputers in Medicine and Healthcare, Long Beach, CA, 1991, pp. 64-69.; Y. Xiang, B. Pant, A. Eisen, M. P. Beddoes, D. Poole, Painulm: a neuromuscular diagnostic aid using multiply sectioned Bayesian networks, in: D. I. Hudson (Ed.), Proceedings of ISMM (International Society for Mini and Microcomputers) International Conference on Mini and Microcomputers in Medicine and Healthcare, Long Beach, CA, 1991, pp. 64-69.
[3] Xiang, Y.; Pant, B.; Eisen, A.; Beddoes, M. P.; Poole, D., Multiply sectioned Bayesian networks for neuromuscular diagnosis, Artificial Intelligence in Medicine, 5, 293-314 (1993)
[4] Xiang, Y.; Geng, H., Distributed monitoring and diagnosis with multiply sectioned Bayesian networks, (AAAI Spring Symposium on AI in Equipment Service Maintenance and Support (1999), AAAI Press: AAAI Press Stanford, CA), 18-25
[5] A. Ghosh, S. Sen, Agent-based distributed intrusion alert system, in: Proceedings of the Sixth International Workshop on Distributed Computing (IWDC’04), Kolkata, India, 2004, pp. 240-251.; A. Ghosh, S. Sen, Agent-based distributed intrusion alert system, in: Proceedings of the Sixth International Workshop on Distributed Computing (IWDC’04), Kolkata, India, 2004, pp. 240-251.
[6] Xiang, Y., Probabilistic Reasoning in Multiagent Systems: A Graphical Models Approach (2002), Cambridge University Press · Zbl 1119.68198
[7] S. Buchegger, J.-Y.L. Boudec, A robust reputation system for P2P and mobile ad-hoc networks, in: Proceedings of the Second Workshop on the Economics of Peer-to-Peer Systems, Cambridge, MA, 2004.; S. Buchegger, J.-Y.L. Boudec, A robust reputation system for P2P and mobile ad-hoc networks, in: Proceedings of the Second Workshop on the Economics of Peer-to-Peer Systems, Cambridge, MA, 2004.
[8] Skyrms, B.; Pemantle, R., A dynamic model of social network formation, Proceedings of National Academy of Sciences of the United States of America (PNAS), 97, 16, 9340-9346 (2000) · Zbl 0984.91013
[9] H. Li, S. Majumdar, Dynamic Decisions with Short-term Memories, Technical Report, Department of Economics, University of Toronto, 2005.; H. Li, S. Majumdar, Dynamic Decisions with Short-term Memories, Technical Report, Department of Economics, University of Toronto, 2005.
[10] D. Koller, Representation, Reasoning, Learning, Keynote talk at the 17th International Joint Conference on Artificial Intelligence (IJCAI-2001), Seattle, WA.; D. Koller, Representation, Reasoning, Learning, Keynote talk at the 17th International Joint Conference on Artificial Intelligence (IJCAI-2001), Seattle, WA.
[11] L.M. de Campos, J.M. Fernandez-Luna, Reducing propagation effort in large polytrees: an application to information retrieval, in: Proceedings of the First European Workshop on Probabilistic Graphical Models (PGM’02), Cuenca, Spain, 2002, pp. 35-44.; L.M. de Campos, J.M. Fernandez-Luna, Reducing propagation effort in large polytrees: an application to information retrieval, in: Proceedings of the First European Workshop on Probabilistic Graphical Models (PGM’02), Cuenca, Spain, 2002, pp. 35-44.
[12] Shachter, R. D., Bayes-ball: the rational pastime (for determining irrelevance and requisite information in belief networks and influence diagrams), (Cooper, G. F.; Moral, S., Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI-1998) (1998), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers Madison, WI), 480-487
[13] Puterman, M. L., Markov Decision Processes: Discrete Stochastic Dynamic Programming (1994), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York, NY · Zbl 0829.90134
[14] Kaelbling, L. P.; Littman, M.; Cassandra, A. R., Planning and acting in partially observable stochastic domains, Artificial Intelligence, 101, 99-134 (1998) · Zbl 0908.68165
[15] Boutilier, C., Multiagent systems: challenges and opportunities for decision-theoretic planning, AI Magazine, 20, 4, 35-43 (1999)
[16] Bernstein, D. S.; Zilberstein, S.; Immerman, N., The complexity of decentralized control of Markov decision processes, (Boutilier, C.; Goldszmidt, M., Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence (UAI-2000) (2000), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers Stanford, CA), 32-37
[17] Goldman, C. V.; Zilberstein, S., Optimizing information exchange in cooperative multi-agent systems, (Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2003) (2003), ACM Press: ACM Press Melbourne, Australia), 137-144
[18] Nair, R.; Tambe, M.; Yokoo, M.; Pynadath, D.; Marsella, S., Taming decentralized POMDPs: towards efficient policy computation for multiagent settings, (Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI’03) (2003), Morgan Kaufmann: Morgan Kaufmann Acapulco, Mexico), 705-711
[19] M. Littman, Algorithms for Sequential Decision Making, Ph.D. Thesis, Department of Computer Science, Brown University, Providence, Rhode Island, 1996.; M. Littman, Algorithms for Sequential Decision Making, Ph.D. Thesis, Department of Computer Science, Brown University, Providence, Rhode Island, 1996.
[20] Forbes, J.; Huang, T.; Kanazawa, K.; Russell, S., The BATmobile: towards a Bayesian automated taxi, (Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI-1995) (1995), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers Montréal, Québec, Canada), 1878-1885
[21] Sallans, B., Learning factored representations for partially observable Markov decision processes, (Solla, S.; Leen, T.; Muller, K. R., Proceedings of the Advances in Neural Information Processing Systems 12 (NIPS-1999) (1999), MIT Press: MIT Press Denver, CO), 1050-1056
[22] X. Boyen, Inference and Learning in Complex Stochastic Processes, Ph.D. Thesis, Computer Science Department, Stanford University, Stanford, CA, 2002.; X. Boyen, Inference and Learning in Complex Stochastic Processes, Ph.D. Thesis, Computer Science Department, Stanford University, Stanford, CA, 2002.
[23] Murphy, K.; Weiss, Y., The factored frontier algorithm for approximate inference in DBNs, (Breese, J. S.; Koller, D., Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI-2001) (2001), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers Seattle, WA), 378-385
[24] K. Murphy, Dynamic Bayesian Networks: Representation, Inference and Learning, Ph.D. Thesis, CS Division, UC Berkeley, Berkeley, CA, July 2002.; K. Murphy, Dynamic Bayesian Networks: Representation, Inference and Learning, Ph.D. Thesis, CS Division, UC Berkeley, Berkeley, CA, July 2002.
[25] Ihler, A. T.; Fisher, J. W.; Willsky, A. S., Loopy belief propagation: convergence and effects of message errors, Journal of Machine Learning Research, 6, 905-936 (2005) · Zbl 1222.68224
[26] Xiang, Y., Temporally invariant junction tree for inference in dynamic Bayesian networks, (Mercer, R. E.; Neufeld, E., Advances in Artificial Intelligence: Proceedings of the 12th Biennial Conference of the Canadian Society for Computational Studies of Intelligence. Advances in Artificial Intelligence: Proceedings of the 12th Biennial Conference of the Canadian Society for Computational Studies of Intelligence, LNAI, vol. 1418 (1998), Springer: Springer Vancouver, BC, Canada), 363-377
[27] Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufman: Morgan Kaufman Publishers, San Franciso, CA
[28] Pearl, J.; Paz, A., Graphoids: a graph-based logic for reasoning about relevance relations, (Boulay, B. D.; Hogg, D.; Steels, L., Advances in Artificial Intelligence 2. Advances in Artificial Intelligence 2, Amsterdam (1985), NorthHolland), 357-363
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.