Univector field method-based multi-agent navigation for pursuit problem in obstacle environments

Abstract

The pursuit problem is a well-known problem in computer science. In this problem, a group of predator agents attempt to capture a prey agent in an environment with various obstacle types, partial observation, and an infinite grid-world. Predator agents are applied algorithms that use the univector field method to reach the prey agent, strategies for avoiding obstacles and strategies for cooperation between predator agents. Obstacle avoidance strategies are generalized and presented through strategies called hitting and following boundary (HFB); trapped and following shortest path (TFSP); and predicted and following shortest path (PFSP). In terms of cooperation, cooperation strategies are employed to more quickly reach and capture the prey agent. Experimental results are shown to illustrate the efficiency of the method in the pursuit problem.

Keywords

pursuit problem / predator agent / prey agent / univector field method / multi-agent systems

References

[1] BendaM, JagannathanV, DodhiawalaROn optimal cooperation of knowledge sources-an empirical investigation [R], 1986, Seattle, WA, USA, Boeing Advanced Technology Center, Boeing Computing Services

[2] ChungT H, HollingerG A, IslerV. Search and pursuit-evasion in mobile robotics [J]. Autonomous Robots, 2011, 31(4): 299-316

[3] SincákD H V. Multi-robot control system for pursuit-evasion problem [J]. Journal of Electrical Engineering, 2009, 60(3): 143-148

[4] StifflerN, O'kaneJA sampling-based algorithm for multirobot visibility-based pursuit-evasion [C]// IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014, Chicago, USA, IEEE: 17821789

[5] BilginA, Kadioglu-UrtisEAn approach to multi-agent pursuit evasion games using reinforcement learning [C]// International Conference on Advanced Robotics, 2015, Istanbul, Turkey, IEEE: 164169

[6] WangH, YueQ, LiuJResearch on Pursuit-evasion games with multiple heterogeneous pursuers and a high speed evader [C]// 27th Chinese Control and Decision Conference, 2015, Qingdao, China, IEEE: 43664370

[7] StifflerN A O JA complete algorithm for visibility-based pursuit-evasion with multiple pursuers [C]// IEEE International Conference on Robotics and Automation, 2014, Hong Kong, China, IEEE: 16601667

[8] AlonsoL, ReingoldE M. Bounds for cops and robber pursuit [J]. Computational Geometry, 2010, 43(9): 749-766

[9] LinW, QuZ, SimaanM. Nash strategies for pursuit-evasion differential games involving limited observations [J]. IEEE Transactions on Aerospace and Electronic Systems, 2015, 51(2): 1347-1356

[10] KleinK, SuriS. Capture bounds for visibility-based pursuit evasion [J]. Computational Geometry, 2015, 48(3): 205-220

[11] KehagiasA, MitscheD, PrałatP. Cops and invisible robbers: The cost of drunkenness [J]. Theoretical Computer Science, 2013, 481: 100-120

[12] NeapolitanR, NaimipourKFoundations of algorithms [M], 2010

[13] UndegerC, PolatF. Multi-agent real-time pursuit [J]. Autonomous Agents and Multi-Agent Systems, 2010, 21(1): 69-107

[14] UndegerC, PolatFReal-time moving target search [M]// Agent Computing and Multi-Agent Systems, 2009, Berlin, Heidelberg, Springer: 110121

[15] VietH, AnS, ChungT. Univector field method based multi-agent navigation for pursuit problem [J]. International Journal of Fuzzy Logic and Intelligent Systems, 2012, 12(1): 86-93

[16] KimY J, KimJ H, KwonD S. Evolutionary programming-based univector field navigation method for past mobile robots [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2001, 31(3): 450-458

[17] HongY, KimJFootstep planning based on univector field method for humanoid robot [M]// Advances in Robotics, 2009, Berlin, Heidelberg, Springer: 125134

[18] LimY, ChoiS H, KimJ H, KimD HEvolutionary univector field-based navigation with collision avoidance for mobile robot [C]// 17th World Congress, The International Federation of Automatic Control, 20081278712792

[19] GasserL, RouquetteN, HillR W, LiebJRepresenting and using organizational knowledge in DAI systems [C]// Distributed Artificial Intelligence, 19902San Francisco, CA, USA, Morgan Kaufmann Publishers Inc.: 5578

[20] KorfRA simple solution to pursuit games [C]// Distributed Artificial Intelligence, 19922Michigan, USA, Springer Verlag: 183194

[21] ReverteJ, GallegoF, LlorensFExtending Korf’s ideas on the pursuit problem [C]// International Symposium on Distributed Computing and Artificial Intelligence 2008, 2009, Spain, Springer: 245249

[22] NgJ, BräunlT. Performance comparison of bug navigation algorithms [J]. Journal of Intelligent and Robotic Systems, 2007, 50(1): 73-84

[23] FergusonD, DarmsM, UrmsonC, KolskiSDetection, prediction, and avoidance of dynamic obstacles in urban environments [C]// IEEE Intelligent Vehicles Symposium, 2008, Eindhoven, Netherlands, IEEE: 11491154

[24] YungN, YeCAvoidance of moving obstacles through behavior fusion and motion prediction [C]// 1998 IEEE International Conference on Systems, Man, and Cybernetics, 1998, San Diego, CA, USA, IEEE: 34243429

[25] StentzAThe focussed D* algorithm for real-time replanning [C]// Proceedings of the International Joint Conference on Artifical Intelligence. Montreal, 1995, Quebec, Canada: AAAI: 16521659

[26] KoenigS, LikhachevM. Fast replanning for navigation in unknown terrain [J]. Transactions on Robotics, 2005, 21(3): 354-363