Multi-Agent Searching Adaptation Using Levy Flight and Inferential Reasoning

Authors: Sagir M. Yusuf, Chris Baber

Abstract:

In this paper, we describe how to achieve knowledge understanding and prediction (Situation Awareness (SA)) for multiple-agents conducting searching activity using Bayesian inferential reasoning and learning. Bayesian Belief Network was used to monitor agents' knowledge about their environment, and cases are recorded for the network training using expectation-maximisation or gradient descent algorithm. The well trained network will be used for decision making and environmental situation prediction. Forest fire searching by multiple UAVs was the use case. UAVs are tasked to explore a forest and find a fire for urgent actions by the fire wardens. The paper focused on two problems: (i) effective agents’ path planning strategy and (ii) knowledge understanding and prediction (SA). The path planning problem by inspiring animal mode of foraging using Lévy distribution augmented with Bayesian reasoning was fully described in this paper. Results proof that the Lévy flight strategy performs better than the previous fixed-pattern (e.g., parallel sweeps) approaches in terms of energy and time utilisation. We also introduced a waypoint assessment strategy called k-previous waypoints assessment. It improves the performance of the ordinary levy flight by saving agent’s resources and mission time through redundant search avoidance. The agents (UAVs) are to report their mission knowledge at the central server for interpretation and prediction purposes. Bayesian reasoning and learning were used for the SA and results proof effectiveness in different environments scenario in terms of prediction and effective knowledge representation. The prediction accuracy was measured using learning error rate, logarithm loss, and Brier score and the result proves that little agents mission that can be used for prediction within the same or different environment. Finally, we described a situation-based knowledge visualization and prediction technique for heterogeneous multi-UAV mission. While this paper proves linkage of Bayesian reasoning and learning with SA and effective searching strategy, future works is focusing on simplifying the architecture.

Keywords: Lèvy flight, situation awareness, multi-agent system, multi-robot coordination, autonomous system, swarm intelligence.

References:

[1] M. Turpin, N. Michael, and V. Kumar, “Capt: Concurrent assignment and planning of trajectories for multiple robots,” The International Journal of Robotics Research, vol. 33, no. 1, pp. 98–112, Jan. 2014, doi: 10.1177/0278364913515307.
[2] J. P. Desai, J. Ostrowski, and V. Kumar, “Controlling formations of multiple mobile robots,” 1998, vol. 4, pp. 2864–2869 vol.4, doi: 10.1109/ROBOT.1998.680621.
[3] D. T. Nguyen, W. Yeoh, H. C. Lau, S. Zilberstein, and C. Zhang, “Decentralized Multi-agent Reinforcement Learning in Average-reward Dynamic DCOPs,” in Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, Québec City, Québec, Canada, 2014, pp. 1447–1455, Accessed: Nov. 30, 2019. (Online). Available: http://dl.acm.org/citation.cfm?id=2892753.2892754.
[4] M. Vasile and F. Zuiani, “Multi-agent collaborative search : an agent-based memetic multi-objective optimization algorithm applied to space trajectory design,” Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, vol. 225, pp. 1211–1227, Nov. 2011.
[5] J. Cortés and M. Egerstedt, “Coordinated Control of Multi-Robot Systems: A Survey,” SICE Journal of Control, Measurement, and System Integration, vol. 10, no. 6, pp. 495–503, 2017, doi: 10.9746/jcmsi.10.495.
[6] T. Setter and M. Egerstedt, “Energy-Constrained Coordination of Multi-Robot Teams,” IEEE Transactions on Control Systems Technology, vol. 25, no. 4, pp. 1257–1263, Jul. 2017, doi: 10.1109/TCST.2016.2599486.
[7] G. Bevacqua, J. Cacace, A. Finzi, and V. Lippiello, “Mixed-initiative Planning and Execution for Multiple Drones in Search and Rescue Missions,” in Proceedings of the Twenty-Fifth International Conference on International Conference on Automated Planning and Scheduling, Jerusalem, Israel, 2015, pp. 315–323, Accessed: Feb. 19, 2019. (Online). Available: http://dl.acm.org/citation.cfm?id=3038662.3038706.
[8] “pattern.pdf.” Accessed: May 26, 2019. (Online). Available: https://paginas.fe.up.pt/~ee07245/wp-content/uploads/2012/04/pattern.pdf.
[9] “IAMSAR Search Patterns Explained with Sketches,” Oways Online, Aug. 14, 2019. https://owaysonline.com/iamsar-search-patterns/ (accessed Apr. 19, 2020).
[10] S. G. Nurzaman, Y. Matsumoto, Y. Nakamura, S. Koizumi, and H. Ishiguro, “Biologically inspired adaptive mobile robot search with and without gradient sensing,” in 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, St. Louis, MO, USA, Oct. 2009, pp. 142–147, doi: 10.1109/IROS.2009.5353998.
[11] X. Yang and Suash Deb, “Cuckoo Search via Lévy flights,” in 2009 World Congress on Nature Biologically Inspired Computing (NaBIC), Dec. 2009, pp. 210–214, doi: 10.1109/NABIC.2009.5393690.
[12] M. Chawla and M. Duhan, “Lévy Flights in Metaheuristics Optimization Algorithms – A Review,” Applied Artificial Intelligence, vol. 32, no. 9–10, pp. 802–821, Nov. 2018, doi: 10.1080/08839514.2018.1508807.
[13] D. K. Sutantyo, S. Kernbach, V. A. Nepomnyashchikh, and P. Levi, “Multi-Robot Searching Algorithm Using Lévy Flight and Artificial Potential Field,” arXiv:1108.5624 (cs), Aug. 2011, Accessed: May 25, 2019. (Online). Available: http://arxiv.org/abs/1108.5624.
[14] Donald Knuth, The art of computer programming, Third edition, vol. Volume 2. 1997.
[15] A. Khan, E. Yanmaz, and B. Rinner, “Information Exchange and Decision Making in Micro Aerial Vehicle Networks for Cooperative Search,” IEEE Transactions on Control of Network Systems, vol. 2, no. 4, pp. 335–347, Dec. 2015, doi: 10.1109/TCNS.2015.2426771.
[16] Y. Yang, M. M. Polycarpou, and A. A. Minai, “Multi-UAV Cooperative Search Using an Opportunistic Learning Method,” J. Dyn. Sys., Meas., Control, vol. 129, no. 5, pp. 716–728, Jan. 2007, doi: 10.1115/1.2764515.
[17] 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.
[18] J. Wang and Z. Xu, “Bayesian Inferential Reasoning Model for Crime Investigation,” p. 11, 2014.
[19] L. Bottou, “Large-Scale Machine Learning with Stochastic Gradient Descent,” p. 10, 2010.
[20] 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.
[21] M. Kallmann, “Path Planning in Triangulations,” p. 6.
[22] X.-S. Yang, “Bat Algorithm for Multi-objective Optimisation,” arXiv:1203.6571 (math), Mar. 2012, Accessed: Oct. 24, 2019. (Online). Available: http://arxiv.org/abs/1203.6571.
[23] X.-S. Yang, “Firefly Algorithm, Lévy Flights and Global Optimization,” in Research and Development in Intelligent Systems XXVI, 2010, pp. 209–218.
[24] V. J. Lumelsky and K. R. Harinarayan, “Decentralized Motion Planning for Multiple Mobile Robots: The Cocktail Party Model,” Autonomous Robots, vol. 4, no. 1, pp. 121–135, Mar. 1997, doi: 10.1023/A:1008815304810.
[25] L. Merino, F. Caballero, J. R. M. Dios, J. Ferruz, and A. Ollero, “A cooperative perception system for multiple UAVs: Application to automatic detection of forest fires,” Journal of Field Robotics, vol. 23, no. 3–4, pp. 165–184, 2006, doi: 10.1002/rob.20108.
[26] M. Erdelj, E. Natalizio, K. R. Chowdhury, and I. F. Akyildiz, “Help from the Sky: Leveraging UAVs for Disaster Management,” IEEE Pervasive Computing, vol. 16, no. 1, pp. 24–32, Jan. 2017, doi: 10.1109/MPRV.2017.11.
[27] P. Bouvry et al., “Using heterogeneous multilevel swarms of UAVs and high-level data fusion to support situation management in surveillance scenarios,” in 2016 IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems (MFI), Sep. 2016, pp. 424–429, doi: 10.1109/MFI.2016.7849525.
[28] 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).
[29] 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.
[30] https://github.com/afrl-rq/OpenAMASE. afrl-rq, 2019.
[31] M. Romanycia, “Netica-J Reference Manual,” p. 119, 2019.
[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] 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).
[34] F. Fioretto, E. Pontelli, and W. Yeoh, “Distributed Constraint Optimization Problems and Applications: A Survey,” J. Artif. Int. Res., vol. 61, no. 1, pp. 623–698, Jan. 2018.