Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in: Dynamic Games and Applications 4/2019

03.07.2019

Optimal Evading Strategies and Task Allocation in Multi-player Pursuit–Evasion Problems

verfasst von: Venkata Ramana Makkapati, Panagiotis Tsiotras

Erschienen in: Dynamic Games and Applications | Ausgabe 4/2019

Einloggen, um Zugang zu erhalten
share
TEILEN

Abstract

Pursuit–evasion problems involving multiple pursuers and evaders are studied in this paper. The pursuers and the evaders are all assumed to be identical, and the pursuers are assumed to follow either a constant bearing or a pure pursuit strategy, giving rise to two distinct cases. The problem is simplified by adopting a dynamic divide and conquer approach, where at every time instant each evader is assigned to a set of pursuers based on the instantaneous positions of all the players. In this regard, the corresponding multi-pursuer single-evader problem is analyzed first. Assuming that the evader knows the positions of all the pursuers and their pursuit strategy, the time-optimal evading strategies are derived for both constant bearing and pure pursuit cases for the pursuers using tools from optimal control theory. In the case of a constant bearing strategy, and assuming that the evader can follow any strategy, a dynamic task allocation algorithm is proposed for the pursuers. The algorithm is based on the well-known Apollonius circle and allows the pursuers to allocate their resources in an intelligent manner while guaranteeing the capture of the evader in minimum time. For the case of pure pursuit, the algorithm is modified using the counterpart of the Apollonius circle leading to an “Apollonius closed curve.” Finally, the proposed algorithms are extended to assign pursuers in the case of a problem with multiple pursuers and multiple evaders. Numerical simulations are included to demonstrate the performance of the proposed algorithms.
Literatur
1.
Zurück zum Zitat Antoniades A, Kim HJ, Sastry S (2003) Pursuit–evasion strategies for teams of multiple agents with incomplete information. In: Proceedings of the 42nd IEEE conference on decision and control, Maui, pp 756–761 Antoniades A, Kim HJ, Sastry S (2003) Pursuit–evasion strategies for teams of multiple agents with incomplete information. In: Proceedings of the 42nd IEEE conference on decision and control, Maui, pp 756–761
2.
Zurück zum Zitat Bakolas E, Tsiotras P (2012) Relay pursuit of a maneuvering target using dynamic Voronoi diagrams. Automatica 48(9):2213–2220 MathSciNetMATHCrossRef Bakolas E, Tsiotras P (2012) Relay pursuit of a maneuvering target using dynamic Voronoi diagrams. Automatica 48(9):2213–2220 MathSciNetMATHCrossRef
3.
Zurück zum Zitat Bakolas E, Tsiotras P (2012) Feedback navigation in an uncertain flowfield and connections with pursuit strategies. J Guidance Control Dyn 35(4):1268–1279 CrossRef Bakolas E, Tsiotras P (2012) Feedback navigation in an uncertain flowfield and connections with pursuit strategies. J Guidance Control Dyn 35(4):1268–1279 CrossRef
4.
Zurück zum Zitat Bakolas E, Tsiotras P (December 2011) On the relay pursuit of a maneuvering target by a group of pursuers. In: Proceedings of the 50th IEEE conference on decision and control and European control conference, Orlando, pp 4270–4275 Bakolas E, Tsiotras P (December 2011) On the relay pursuit of a maneuvering target by a group of pursuers. In: Proceedings of the 50th IEEE conference on decision and control and European control conference, Orlando, pp 4270–4275
5.
Zurück zum Zitat Beckman BC, Haskin M, Rolnik M, Vule Y (2017) Maneuvering a package following in-flight release from an unmanned aerial vehicle (UAV). Patent No. US 9,567,081 B1, 14 Feb 2017 Beckman BC, Haskin M, Rolnik M, Vule Y (2017) Maneuvering a package following in-flight release from an unmanned aerial vehicle (UAV). Patent No. US 9,567,081 B1, 14 Feb 2017
9.
Zurück zum Zitat Cesari L (1983) Optimization-theory and applications: problems with ordinary differential equations. Springer, New York, pp 310–313 ( Chapter 9) MATHCrossRef Cesari L (1983) Optimization-theory and applications: problems with ordinary differential equations. Springer, New York, pp 310–313 ( Chapter 9) MATHCrossRef
12.
Zurück zum Zitat Exarchos I, Tsiotras P, Pachter M (2016) UAV collision avoidance based on the solution of the suicidal pedestrian differential game. In: Guidance, navigation, and control conference. AIAA SciTech Forum, San Diego Exarchos I, Tsiotras P, Pachter M (2016) UAV collision avoidance based on the solution of the suicidal pedestrian differential game. In: Guidance, navigation, and control conference. AIAA SciTech Forum, San Diego
13.
Zurück zum Zitat Ezequiel CAF, Cua M, Libatique NC, Tangonan GL, Alampay R, Labuguen RT, Favila CM, Honrado JLE, Canos V, Devaney C et al (2014) UAV aerial imaging applications for post-disaster assessment, environmental management and infrastructure development. In: International conference on unmanned aircraft systems. IEEE, Orlando, pp 274–283 Ezequiel CAF, Cua M, Libatique NC, Tangonan GL, Alampay R, Labuguen RT, Favila CM, Honrado JLE, Canos V, Devaney C et al (2014) UAV aerial imaging applications for post-disaster assessment, environmental management and infrastructure development. In: International conference on unmanned aircraft systems. IEEE, Orlando, pp 274–283
14.
Zurück zum Zitat Garcia E, Casbeer DW, Pachter M (2015) Cooperative strategies for optimal aircraft defense from an attacking missile. J Guidance Control Dyn 38(8):1510–1520 CrossRef Garcia E, Casbeer DW, Pachter M (2015) Cooperative strategies for optimal aircraft defense from an attacking missile. J Guidance Control Dyn 38(8):1510–1520 CrossRef
15.
Zurück zum Zitat Ge J, Tang L, Reimann J, Vachtsevanos G (2006) Suboptimal approaches to multiplayer pursuit–evasion differential games. In: Guidance, navigation, and control conference and exhibit. AIAA, Keystone Ge J, Tang L, Reimann J, Vachtsevanos G (2006) Suboptimal approaches to multiplayer pursuit–evasion differential games. In: Guidance, navigation, and control conference and exhibit. AIAA, Keystone
16.
Zurück zum Zitat Hespanha JP, Kim HJ, Sastry S (1999) Multiple-agent probabilistic pursuit–evasion games. In: Proceedings of the 38th IEEE conference on decision and control, vol 3, Phoenix, pp 2432–2437 Hespanha JP, Kim HJ, Sastry S (1999) Multiple-agent probabilistic pursuit–evasion games. In: Proceedings of the 38th IEEE conference on decision and control, vol 3, Phoenix, pp 2432–2437
17.
Zurück zum Zitat Huang Y, Thomson SJ, Hoffmann WC, Lan Y, Fritz BK (2013) Development and prospect of unmanned aerial vehicle technologies for agricultural production management. Int J Agric Biol Eng 6(3):1–10 Huang Y, Thomson SJ, Hoffmann WC, Lan Y, Fritz BK (2013) Development and prospect of unmanned aerial vehicle technologies for agricultural production management. Int J Agric Biol Eng 6(3):1–10
19.
Zurück zum Zitat Ibragimov GI, Rikhsiev BB (2012) On some sufficient conditions for optimality of the pursuit time in the differential game with multiple pursuers. Autom Remote Control 67(4):529–537 MATHCrossRef Ibragimov GI, Rikhsiev BB (2012) On some sufficient conditions for optimality of the pursuit time in the differential game with multiple pursuers. Autom Remote Control 67(4):529–537 MATHCrossRef
20.
Zurück zum Zitat Ibragimov GI, Salimi M, Amini M (2012) Evasion from many pursuers in simple motion differential game with integral constraints. Eur J Oper Res 218(2):505–511 MathSciNetMATHCrossRef Ibragimov GI, Salimi M, Amini M (2012) Evasion from many pursuers in simple motion differential game with integral constraints. Eur J Oper Res 218(2):505–511 MathSciNetMATHCrossRef
21.
Zurück zum Zitat Isaacs R (1999) Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization. Dover, Mineola ( Chapter 6) MATH Isaacs R (1999) Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization. Dover, Mineola ( Chapter 6) MATH
22.
Zurück zum Zitat Isler V, Sun D, Sastry S (2005) Roadmap based pursuit–evasion and collision avoidance. Robot Sci Syst 1:257–264 Isler V, Sun D, Sastry S (2005) Roadmap based pursuit–evasion and collision avoidance. Robot Sci Syst 1:257–264
23.
Zurück zum Zitat Jang JS, Tomlin CJ (, August 2005) Control strategies in multi-player pursuit and evasion game. In: AIAA guidance, navigation, and control conference and exhibit, San Francisco, CA, AIAA Paper 2005-6239 Jang JS, Tomlin CJ (, August 2005) Control strategies in multi-player pursuit and evasion game. In: AIAA guidance, navigation, and control conference and exhibit, San Francisco, CA, AIAA Paper 2005-6239
24.
Zurück zum Zitat Jin S, Qu Z (2011) A heuristic task scheduling for multi-pursuer multi-evader games. In: International conference on information and automation. IEEE, Shenzhen, pp 528–533 Jin S, Qu Z (2011) A heuristic task scheduling for multi-pursuer multi-evader games. In: International conference on information and automation. IEEE, Shenzhen, pp 528–533
25.
Zurück zum Zitat Kumkov SS, Le Ménec S, Patsko VS (2016) Zero-sum pursuit–evasion differential games with many objects: survey of publications. Dyn Games Appl 7:1–25 MathSciNetMATH Kumkov SS, Le Ménec S, Patsko VS (2016) Zero-sum pursuit–evasion differential games with many objects: survey of publications. Dyn Games Appl 7:1–25 MathSciNetMATH
26.
Zurück zum Zitat Las Fargeas J, Kabamba P, Girard A (2015) Cooperative surveillance and pursuit using unmanned aerial vehicles and unattended ground sensors. Sensors 15(1):1365–1388 CrossRef Las Fargeas J, Kabamba P, Girard A (2015) Cooperative surveillance and pursuit using unmanned aerial vehicles and unattended ground sensors. Sensors 15(1):1365–1388 CrossRef
27.
Zurück zum Zitat Li D, Cruz JB, Chen G, Kwan C, Chang M-H (2005) A hierarchical approach to multi-player pursuit–evasion differential games. In: Proceedings of the 44th IEEE conference on decision and control and European control conference. IEEE, Seville, pp 5674–5679 Li D, Cruz JB, Chen G, Kwan C, Chang M-H (2005) A hierarchical approach to multi-player pursuit–evasion differential games. In: Proceedings of the 44th IEEE conference on decision and control and European control conference. IEEE, Seville, pp 5674–5679
28.
Zurück zum Zitat Lin W, Qu Z, Simaan MA (2013) Multi-pursuer single-evader differential games with limited observations. In: Proceedings of the American control conference. IEEE, Washington, DC, pp 2711–2716 Lin W, Qu Z, Simaan MA (2013) Multi-pursuer single-evader differential games with limited observations. In: Proceedings of the American control conference. IEEE, Washington, DC, pp 2711–2716
29.
Zurück zum Zitat Makkapati VR, Sun W, Tsiotras P (2018) Pursuit–evasion problems involving two pursuers and one evader. In: Guidance, navigation, and control conference. AIAA Scitech Forum, Kissimmee Makkapati VR, Sun W, Tsiotras P (2018) Pursuit–evasion problems involving two pursuers and one evader. In: Guidance, navigation, and control conference. AIAA Scitech Forum, Kissimmee
30.
Zurück zum Zitat Morgan RW, Riel JL (2016) Blind evasion by random switching maneuvers. In: Proceedings of the American control conference. IEEE, Boston, pp 3126–3131 Morgan RW, Riel JL (2016) Blind evasion by random switching maneuvers. In: Proceedings of the American control conference. IEEE, Boston, pp 3126–3131
31.
Zurück zum Zitat Mylvaganam T, Sassano M, Astolfi A (2014) A constructive differential game approach to collision avoidance in multi-agent systems. In: Proceedings of the American control conference, IEEE, Orlando, pp 311–316 Mylvaganam T, Sassano M, Astolfi A (2014) A constructive differential game approach to collision avoidance in multi-agent systems. In: Proceedings of the American control conference, IEEE, Orlando, pp 311–316
32.
Zurück zum Zitat Nex F, Remondino F (2014) UAV for 3D mapping applications: a review. Appl Geomat 6(1):1–15 CrossRef Nex F, Remondino F (2014) UAV for 3D mapping applications: a review. Appl Geomat 6(1):1–15 CrossRef
33.
34.
Zurück zum Zitat Pan S, Huang H, Ding J, Zhang W, Tomlin CJ et al (June 2012) Pursuit, evasion and defense in the plane. In: Proceedings of the American control conference. IEEE, Montréal, pp 4167–4173 Pan S, Huang H, Ding J, Zhang W, Tomlin CJ et al (June 2012) Pursuit, evasion and defense in the plane. In: Proceedings of the American control conference. IEEE, Montréal, pp 4167–4173
35.
Zurück zum Zitat Petrov NN, Shuravina IN (2009) On the “soft” capture in one group pursuit problem. J Comput Syst Sci Int 48(4):521–526 MathSciNetMATHCrossRef Petrov NN, Shuravina IN (2009) On the “soft” capture in one group pursuit problem. J Comput Syst Sci Int 48(4):521–526 MathSciNetMATHCrossRef
36.
Zurück zum Zitat Pierson A, Wang Z, Schwager M (2017) Intercepting rogue robots: an algorithm for capturing multiple evaders with multiple pursuers. IEEE Robot Autom Lett 2(2):530–537 CrossRef Pierson A, Wang Z, Schwager M (2017) Intercepting rogue robots: an algorithm for capturing multiple evaders with multiple pursuers. IEEE Robot Autom Lett 2(2):530–537 CrossRef
37.
Zurück zum Zitat Pierson A, Ataei A, Paschalidis IC, Schwager M (2016) Cooperative multi-quadrotor pursuit of an evader in an environment with no-fly zones. In: International conference on robotics and automation. IEEE, Stockholm, pp 320–326 Pierson A, Ataei A, Paschalidis IC, Schwager M (2016) Cooperative multi-quadrotor pursuit of an evader in an environment with no-fly zones. In: International conference on robotics and automation. IEEE, Stockholm, pp 320–326
39.
Zurück zum Zitat Pshenichnyi B (1976) Simple pursuit by several objects. Cybern Syst Anal 12(3):484–485 MathSciNet Pshenichnyi B (1976) Simple pursuit by several objects. Cybern Syst Anal 12(3):484–485 MathSciNet
40.
Zurück zum Zitat Ramana MV, Kothari M (2017) Pursuit strategy to capture high-speed evaders using multiple pursuers. J Guidance Control Dyn 40(1):139–149 CrossRef Ramana MV, Kothari M (2017) Pursuit strategy to capture high-speed evaders using multiple pursuers. J Guidance Control Dyn 40(1):139–149 CrossRef
41.
Zurück zum Zitat Ramana MV, Kothari M (2017) Pursuit–evasion games of high speed evader. J Intell Robot Syst 85(2):293–306 CrossRef Ramana MV, Kothari M (2017) Pursuit–evasion games of high speed evader. J Intell Robot Syst 85(2):293–306 CrossRef
42.
Zurück zum Zitat Rizk Y, Awad M, Tunstel EW (2018) Decision making in multi-agent systems: a survey. IEEE Trans Cogn Dev Syst 10:514–529 CrossRef Rizk Y, Awad M, Tunstel EW (2018) Decision making in multi-agent systems: a survey. IEEE Trans Cogn Dev Syst 10:514–529 CrossRef
43.
Zurück zum Zitat Rusnak I (2005) A two team dynamic game, or how to play football. In: Proceedings of the 5th international ISDG workshop, international society of dynamic games, Segovia Rusnak I (2005) A two team dynamic game, or how to play football. In: Proceedings of the 5th international ISDG workshop, international society of dynamic games, Segovia
44.
Zurück zum Zitat Rusnak I (2005) The lady, the bandits and the body-guards—a two team dynamic game. In: Proceedings of the 16th IFAC world congress, Czech Republic, pp 441–446 Rusnak I (2005) The lady, the bandits and the body-guards—a two team dynamic game. In: Proceedings of the 16th IFAC world congress, Czech Republic, pp 441–446
45.
Zurück zum Zitat Schenato L, Oh S, Sastry S, Bose P (2005) Swarm coordination for pursuit–evasion games using sensor networks. In: International conference on robotics and automation. IEEE, Barcelona, pp 2493–2498 Schenato L, Oh S, Sastry S, Bose P (2005) Swarm coordination for pursuit–evasion games using sensor networks. In: International conference on robotics and automation. IEEE, Barcelona, pp 2493–2498
46.
Zurück zum Zitat Shima T (2011) Optimal cooperative pursuit and evasion strategies against a homing missile. J Guidance Control Dyn 34(2):414–425 CrossRef Shima T (2011) Optimal cooperative pursuit and evasion strategies against a homing missile. J Guidance Control Dyn 34(2):414–425 CrossRef
47.
Zurück zum Zitat Shneydor NA (1998) Missile guidance and pursuit: kinematics, dynamics and control. Horwood Publishing Limited, Cambridge ( Chapters 3, 4) CrossRef Shneydor NA (1998) Missile guidance and pursuit: kinematics, dynamics and control. Horwood Publishing Limited, Cambridge ( Chapters 3, 4) CrossRef
48.
Zurück zum Zitat Stipanović DM, Melikyan A, Hovakimyan N (2009) Some sufficient conditions for multi-player pursuit-evasion games with continuous and discrete observations. In: Pourtallier O, Gaitsgory V, Bernhard P (eds) Advances in dynamic games and their applications. Springer, Berlin, pp 1–13 MATH Stipanović DM, Melikyan A, Hovakimyan N (2009) Some sufficient conditions for multi-player pursuit-evasion games with continuous and discrete observations. In: Pourtallier O, Gaitsgory V, Bernhard P (eds) Advances in dynamic games and their applications. Springer, Berlin, pp 1–13 MATH
49.
Zurück zum Zitat Stipanović DM, Melikyan A, Hovakimyan N (2010) Guaranteed strategies for nonlinear multi-player pursuit–evasion games. Int Game Theory Rev 12(01):1–17 MathSciNetMATHCrossRef Stipanović DM, Melikyan A, Hovakimyan N (2010) Guaranteed strategies for nonlinear multi-player pursuit–evasion games. Int Game Theory Rev 12(01):1–17 MathSciNetMATHCrossRef
50.
Zurück zum Zitat Sun W, Tsiotras P (2017) Sequential pursuit of multiple targets under external disturbances via Zermelo–Voronoi diagrams. Automatica 81:253–260 MathSciNetMATHCrossRef Sun W, Tsiotras P (2017) Sequential pursuit of multiple targets under external disturbances via Zermelo–Voronoi diagrams. Automatica 81:253–260 MathSciNetMATHCrossRef
51.
Zurück zum Zitat Toponogov VA (2006) Differential geometry of curves and surfaces: a concise guide. Birkhäuser, Boston ( Chapter 1) MATH Toponogov VA (2006) Differential geometry of curves and surfaces: a concise guide. Birkhäuser, Boston ( Chapter 1) MATH
52.
Zurück zum Zitat Vieira MA, Govindan R, Sukhatme GS (2009) Scalable and practical pursuit–evasion with networked robots. Intell Serv Robot 2(4):247 CrossRef Vieira MA, Govindan R, Sukhatme GS (2009) Scalable and practical pursuit–evasion with networked robots. Intell Serv Robot 2(4):247 CrossRef
53.
Zurück zum Zitat Von Neumann J, Morgenstern O (1947) Theory of games and economic behavior. Princeton University Press, Princeton MATH Von Neumann J, Morgenstern O (1947) Theory of games and economic behavior. Princeton University Press, Princeton MATH
54.
Zurück zum Zitat Weisstein EW (2003) Circle–circle intersection. From MathWorld—a wolfram web resource Weisstein EW (2003) Circle–circle intersection. From MathWorld—a wolfram web resource
55.
Zurück zum Zitat Yuan C, Zhang Y, Liu Z (2015) A survey on technologies for automatic forest fire monitoring, detection, and fighting using unmanned aerial vehicles and remote sensing techniques. Can J For Res 45(7):783–792 CrossRef Yuan C, Zhang Y, Liu Z (2015) A survey on technologies for automatic forest fire monitoring, detection, and fighting using unmanned aerial vehicles and remote sensing techniques. Can J For Res 45(7):783–792 CrossRef
Metadaten
Titel
Optimal Evading Strategies and Task Allocation in Multi-player Pursuit–Evasion Problems
verfasst von
Venkata Ramana Makkapati
Panagiotis Tsiotras
Publikationsdatum
03.07.2019
Verlag
Springer US
Erschienen in
Dynamic Games and Applications / Ausgabe 4/2019
Print ISSN: 2153-0785
Elektronische ISSN: 2153-0793
DOI
https://doi.org/10.1007/s13235-019-00319-x

Weitere Artikel der Ausgabe 4/2019

Dynamic Games and Applications 4/2019 Zur Ausgabe

Premium Partner