Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Dynamic Games and Applications 4/2019

03-07-2019

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

Authors: Venkata Ramana Makkapati, Panagiotis Tsiotras

Published in: Dynamic Games and Applications | Issue 4/2019

Login to get access
share
SHARE

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.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 15 Tage kostenlos.

Literature
1.
go back to reference 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.
3.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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
34.
go back to reference 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.
36.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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
Metadata
Title
Optimal Evading Strategies and Task Allocation in Multi-player Pursuit–Evasion Problems
Authors
Venkata Ramana Makkapati
Panagiotis Tsiotras
Publication date
03-07-2019
Publisher
Springer US
Published in
Dynamic Games and Applications / Issue 4/2019
Print ISSN: 2153-0785
Electronic ISSN: 2153-0793
DOI
https://doi.org/10.1007/s13235-019-00319-x

Other articles of this Issue 4/2019

Dynamic Games and Applications 4/2019 Go to the issue

Premium Partner