Probabilistic Approach of Dealing with Uncertainties in Distributed Constraint Optimization Problems and Situation Awareness for Multi-agent Systems

Authors: Sagir M. Yusuf, Chris Baber

Abstract:

In this paper, we describe how Bayesian inferential reasoning will contributes in obtaining a well-satisfied prediction for Distributed Constraint Optimization Problems (DCOPs) with uncertainties. We also demonstrate how DCOPs could be merged to multi-agent knowledge understand and prediction (i.e. Situation Awareness). The DCOPs functions were merged with Bayesian Belief Network (BBN) in the form of situation, awareness, and utility nodes. We describe how the uncertainties can be represented to the BBN and make an effective prediction using the expectation-maximization algorithm or conjugate gradient descent algorithm. The idea of variable prediction using Bayesian inference may reduce the number of variables in agents’ sampling domain and also allow missing variables estimations. Experiment results proved that the BBN perform compelling predictions with samples containing uncertainties than the perfect samples. That is, Bayesian inference can help in handling uncertainties and dynamism of DCOPs, which is the current issue in the DCOPs community. We show how Bayesian inference could be formalized with Distributed Situation Awareness (DSA) using uncertain and missing agents’ data. The whole framework was tested on multi-UAV mission for forest fire searching. Future work focuses on augmenting existing architecture to deal with dynamic DCOPs algorithms and multi-agent information merging.

Keywords: DCOP, multi-agent reasoning, Bayesian reasoning, swarm intelligence.

References:

[1] F. Fioretto, E. Pontelli, and W. Yeoh, “Distributed Constraint Optimization Problems and Applications: A Survey,” jair, vol. 61, pp. 623–698, Mar. 2018, doi: 10.1613/jair.5565.
[2] F. Fioretto, W. Yeoh, and E. Pontelli, “Multi-Variable Agents Decomposition for DCOPs to Exploit Multi-Level Parallelism (Extended Abstract),” p. 2, 2015.
[3] J. Fransman, J. Sijs, H. Dol, E. Theunissen, and B. De Schutter, “Bayesian-DPOP for Continuous Distributed Constraint Optimization Problems,” in Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, Richland, SC, 2019, pp. 1961–1963, Accessed: Nov. 06, 2019. (Online). Available: http://dl.acm.org/citation.cfm?id=3306127.3331977.
[4] W. Yeoh, P. Varakantham, X. Sun, and S. Koenig, “Incremental DCOP Search Algorithms for Solving Dynamic DCOPs (Extended Abstract),” p. 2, 2011.
[5] G. Billiau, C. F. Chang, A. Ghose, and A. A. Miller, “Using Distributed Agents for Patient Scheduling,” in Principles and Practice of Multi-Agent Systems, Berlin, Heidelberg, 2012, pp. 551–560, doi: 10.1007/978-3-642-25920-3_40.
[6] G. Billiau, C. F. Chang, A. Miller, and A. Ghose, “Support-based distributed optimisation: an approach to radiotherapy patient scheduling,” Stud Health Technol Inform, vol. 159, pp. 229–233, 2010.
[7] R. T. Maheswaran, M. Tambe, E. Bowring, J. P. Pearce, and P. Varakantham, “Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling,” in Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 1, Washington, DC, USA, 2004, pp. 310–317, Accessed: Nov. 07, 2019. (Online). Available: http://dl.acm.org/citation.cfm?id=1018409.1018762.
[8] X. Zhou, W. Wang, W. Tao, L. Xiaboo, and J. Tian, “Continuous patrolling in uncertain environment with the UAV swarm,” 2018. https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0202328 (accessed Aug. 18, 2019).
[9] F. Fioretto, W. Yeoh, and E. Pontelli, “A Multiagent System Approach to Scheduling Devices in Smart Homes,” in Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, Richland, SC, 2017, pp. 981–989, Accessed: Nov. 07, 2019.
[Online]. Available: http://dl.acm.org/citation.cfm?id=3091210.3091265.
[10] K. D. Hoang, P. Hou, F. Fioretto, W. Yeoh, R. Zivan, and M. Yokoo, “Infinite-Horizon Proactive Dynamic DCOPs,” in Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, Richland, SC, 2017, pp. 212–220, Accessed: Sep. 17, 2019.
[Online]. Available: http://dl.acm.org/citation.cfm?id=3091125.3091160.
[11] K. D. Hoang, F. Fioretto, P. Hou, M. Yokoo, W. Yeoh, and R. Zivan, “Proactive Dynamic Distributed Constraint Optimization,” p. 9, 2016.
[12] M. Pujol-Gonzalez, “Multi-agent Coordination: Dcops and Beyond,” in Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume Three, Barcelona, Catalonia, Spain, 2011, pp. 2838–2839, doi: 10.5591/978-1-57735-516-8/IJCAI11-491.
[13] S. Yusuf and C. Baber, “Handling Uncertainties in Distributed Constraint Optimization Problems using Bayesian Inferential Reasoning - ICAART 2020.” http://www.insticc.org/node/TechnicalProgram/icaart/presentationDetails/91571 (accessed Feb. 26, 2020).
[14] S. M. Yusuf and C. Baber, “Human-agents Interactions in Multi-Agent Systems: A Case Study of Human-UAVs Team for Forest Fire Lookouts - ICAART 2020.” http://www.insticc.org/node/TechnicalProgram/icaart/presentationDetails/93692 (accessed Feb. 29, 2020).
[15] S. Sathe, T. G. Papaioannou, H. Jeung, and K. Aberer, “A Survey of Model-based Sensor Data Acquisition and Management,” in Managing and Mining Sensor Data, C. C. Aggarwal, Ed. Boston, MA: Springer US, 2013, pp. 9–50.
[16] J. Wang and Z. Xu, “Bayesian Inferential Reasoning Model for Crime Investigation,” p. 11, 2014.
[17] J. Williamson, “Bayesian Networks for Logical Reasoning,” p. 19, 2001.
[18] M. R. Endsley, “Toward a Theory of Situation Awareness in Dynamic Systems,” 1995. https://journals.sagepub.com/doi/10.1518/001872095779049543 (accessed Nov. 14, 2019).
[19] N. A. Stanton et al., “Distributed situation awareness in dynamic systems: theoretical development and application of an ergonomics methodology,” Ergonomics, vol. 49, no. 12–13, pp. 1288–1311, Oct. 2006, doi: 10.1080/00140130600612762.
[20] G. Pavlin, P. de Oude, M. Maris, J. Nunnink, and T. Hood, “A multi-agent systems approach to distributed Bayesian information fusion,” Information Fusion, vol. 11, no. 3, pp. 267–282, Jul. 2010, doi: 10.1016/j.inffus.2009.09.007.
[21] S. Mandt and M. D. Hoffman, “Stochastic Gradient Descent as Approximate Bayesian Inference,” p. 35, 2017.
[22] W. Zhang, G. Wang, Z. Xing, and L. Wittenburg, “Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks,” Artificial Intelligence, vol. 161, no. 1, pp. 55–87, Jan. 2005, doi: 10.1016/j.artint.2004.10.004.
[23] M. Pujol-Gonzalez, J. Cerquides, A. Farinelli, P. Meseguer, and J. A. Rodriguez-Aguilar, “Efficient Inter-Team Task Allocation in RoboCup Rescue,” in Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, Richland, SC, 2015, pp. 413–421, Accessed: Aug. 27, 2019. (Online). Available: http://dl.acm.org/citation.cfm?id=2772879.2772933.
[24] S. Amador, S. Okamoto, and R. Zivan, “Dynamic Multi-agent Task Allocation with Spatial and Temporal Constraints,” in Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems, Richland, SC, 2014, pp. 1495–1496, Accessed: Aug. 27, 2019. (Online). Available: http://dl.acm.org/citation.cfm?id=2615731.2616029.
[25] T. Le, T. C. Son, E. Pontelli, and W. Yeoh, “Solving Distributed Constraint Optimization Problems Using Logic Programming,” arXiv:1705.03916
[cs], May 2017, Accessed: Sep. 26, 2019.
[Online]. Available: http://arxiv.org/abs/1705.03916.
[26] R. T. Maheswaran, J. P. Pearce, and M. Tambe, “Distributed algorithms for DCOP: A graphical-game-based approach,” in In PDCS, 2004.
[27] Y. Xiang, Probabilistic Reasoning in Multi-Agent Systems: A Graphical Models Approach. New York, NY, USA: Cambridge University Press, 2002.
[28] K. Makar and A. Rubin, “A Framework for Thinking about Informal Statistical Inference,” p. 24, 2009.
[29] C. J. Wild, M. Pfannkuch, M. Regan, and N. J. Horton, “Inferential Reasoning: Learning to ‘Make a Call’ in Theory,” p. 6, 2010.
[30] C. C. Aggarwal, “Managing and Mining Sensor Data,” Managing and Mining Sensor Data, p. 547, 2008.
[31] R. F. Stark, M. Farry, and J. Pfautz, “Mixed-initiative data mining with Bayesian networks,” in 2012 IEEE International Multi-Disciplinary Conference on Cognitive Methods in Situation Awareness and Decision Support, Mar. 2012, pp. 107–110, doi: 10.1109/CogSIMA.2012.6188360.
[32] S. M. Yusuf and C. Baber, “Conflicts Resolution and Situation Awareness in Heterogeneous Multi-agent Missions using Publish-subscribe Technique and Inferential Reasoning - ICAART 2020.” http://www.insticc.org/node/TechnicalProgram/icaart/presentationDetails/91474 (accessed Feb. 29, 2020).
[33] M. Romanycia, “Netica-J Reference Manual,” p. 119, 2019.
[34] A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum Likelihood from Incomplete Data via the EM Algorithm,” Journal of the Royal Statistical Society. Series B (Methodological), vol. 39, no. 1, pp. 1–38, 1977.
[35] “Nonlinear Programming: 2nd Edition,” Google Docs, 1999. https://docs.google.com/document/d/158wLNN87gVWPBbtZMyFUQXADwtWa4Mcn-6s03dPY2UE/edit?usp=embed_facebook (accessed Nov. 07, 2019).
[36] G. Billiau, C. F. Chang, and A. Ghose, “SBDO: A New Robust Approach to Dynamic Distributed Constraint Optimisation,” in Principles and Practice of Multi-Agent Systems, Berlin, Heidelberg, 2012, pp. 11–26, doi: 10.1007/978-3-642-25920-3_2.
[37] S. W. Golomb and L. D. Baumert, “Backtrack Programming,” J. ACM, vol. 12, no. 4, pp. 516–524, Oct. 1965, doi: 10.1145/321296.321300.
[38] A. K. Mackworth and E. C. Freuder, “The Complexity of Some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems,” Artif. Intell., vol. 25, no. 1, pp. 65–74, Jan. 1985, doi: 10.1016/0004-3702(85)90041-4.
[39] M. Yokoo, E. H. Durfee, T. Ishida, and K. Kuwabara, “The distributed constraint satisfaction problem: formalization and algorithms,” IEEE Transactions on Knowledge and Data Engineering, vol. 10, no. 5, pp. 673–685, Sep. 1998, doi: 10.1109/69.729707.
[40] K. Apt, Principles of Constraint Programming. New York, NY, USA: Cambridge University Press, 2003.
[41] F. Rossi, P. van Beek, and T. Walsh, Handbook of Constraint Programming (Foundations of Artificial Intelligence). New York, NY, USA: Elsevier Science Inc., 2006.
[42] L. Wittenburg and W. Zhang, “Distributed Breakout Algorithm for Distributed Constraint Optimization Problems – DBArelax,” in Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, New York, NY, USA, 2003, pp. 1158–1159, doi: 10.1145/860575.860844.
[43] M. Yokoo, Distributed Constraint Satisfaction: Foundations of Cooperation in Multi-agent Systems. Berlin, Heidelberg: Springer-Verlag, 2001.
[44] A. Petcu and B. Faltings, “A Scalable Method for Multiagent Constraint Optimization,” in Proceedings of the 19th International Joint Conference on Artificial Intelligence, San Francisco, CA, USA, 2005, pp. 266–271, Accessed: Sep. 26, 2019.
[Online]. Available: http://dl.acm.org/citation.cfm?id=1642293.1642336.
[45] K. Hirayama and M. Yokoo, “The Distributed Breakout Algorithms,” Artif. Intell., vol. 161, no. 1–2, pp. 89–115, Jan. 2005, doi: 10.1016/j.artint.2004.08.004.