×

zbMATH — the first resource for mathematics

Sequential pursuit of multiple targets under external disturbances via Zermelo-Voronoi diagrams. (English) Zbl 1373.49047
Summary: We address the problem of pursuit between a collection of targets and a team of pursuers distributed in the plane subject to an environmental disturbance (e.g., wind, sea current). The objective of the pursuers is to intercept the moving targets which, however, are not affected by the presence of the flow field. We first solve the multiple-pursuers/single-target problem by assigning only one pursuer to chase the target at every instant of time, based on a Voronoi-like partition of the plane. During the pursuit, the pursuer assignment changes dynamically based on this partition. We then present an algorithm to efficiently update this Voronoi-like partition online. The results are then extended to the multiple-pursuers/multiple-targets case. Simulations are included to illustrate the theoretical results.

MSC:
49N75 Pursuit and evasion games
91A24 Positional games (pursuit and evasion, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bakolas, E., Decentralized spatial partitioning for multi-vehicle systems in spatiotemporal flow-field, Automatica, 50, 9, 2389-2396, (2014) · Zbl 1297.93007
[2] Bakolas, E., & Tsiotras, P. (2010). Minimum-time paths for a light aircraft in the presence of regionally-varying strong winds. In AIAA Infotech@Aerospace, (Atlanta, GA), AIAA Paper 2010-3380, April 20-22. · Zbl 1206.90204
[3] Bakolas, E.; Tsiotras, P., The Zermelo-Voronoi diagram: A dynamic partition problem, Automatica, 46, 12, 2059-2067, (2010) · Zbl 1206.90204
[4] Bakolas, E.; Tsiotras, P., Feedback navigation in an uncertain flow-field and connections with pursuit strategies, AIAA Journal of Guidance, Control, and Dynamics, 35, 1268-1279, (2012), July-August
[5] Bakolas, E.; Tsiotras, P., Relay pursuit of a maneuvering target using dynamic Voronoi diagrams, Automatica, 48, 2213-2220, (2012) · Zbl 1257.93003
[6] Bakolas, E.; Tsiotras, P., Optimal partitioning for spatiotemporal coverage in a drift field, Automatica, 49, 7, 2064-2073, (2013) · Zbl 1364.93008
[7] Blagodatskikh, A. I., Group pursuit in pontryagin’s nonstationary example, Differential Equations, 44, 1, 40-46, (2008) · Zbl 1148.49035
[8] Blagodatskikh, A. I., Simultaneous multiple capture in a simple pursuit problem, Journal of Applied Mathematics and Mechanics, 73, 1, 36-40, (2009) · Zbl 1199.49076
[9] Bryson, A. E.; Ho, Y.-C., Applied optimal control: optimization, estimation, and control, (1975), Taylor & Francis
[10] De Berg, M.; Cheong, O.; Van Kreveld, M.; Overmars, M., Computational geometry: algorithms and applications, (2008), Springer · Zbl 1140.68069
[11] Devillers, O. (1999). On deletion in Delaunay triangulations. In Proceedings of the fifteenth annual symposium on computational geometry, (New York, USA), (pp. 181-188).
[12] Devillers, O., & Golin, M. (1993). Dog bites postman: Point location in the moving Voronoi diagram and related problems. In Algorithms-ESA’93, (pp. 133-144). · Zbl 1035.68528
[13] Guibas, L., & Russel, D. (2004). An empirical comparison of techniques for updating Delaunay triangulations. In Proceedings of the twentieth annual symposium on computational geometry, (New York, USA), (pp. 170-179). · Zbl 1375.68141
[14] Ibragimov, G. I.; Salimi, M.; Amini, M., Evasion from many pursuers in simple motion differential game with integral constraints, European Journal of Operational Research, 218, 2, 505-511, (2012) · Zbl 1244.91016
[15] Jang, J. S.; Tomlin, C. J., (Control strategies in multi-player pursuit and evasion game, vol. 6239, (2005), AIAA), 15-18
[16] Kao, T., Dynamic maintenance of Delaunay triangulations, Work, 9, 32, (1991)
[17] Khaidarov, B. K., Positional i-capture in the game of a single evader and several pursuers, Journal of Applied Mathematics and Mechanics, 48, 4, 406-409, (1984) · Zbl 0574.90109
[18] Krasovskiǐ, A. N.; Krasovskiǐ, N. N., Control under lack of information, (1994), Springer Science & Business Media · Zbl 0827.93001
[19] Okabe, A.; Boots, B.; Sugihara, K.; Chiu, S. N., Spatial tessellations: concepts and applications of Voronoi diagrams, vol. 501, (2009), Wiley
[20] Pashkov, A. G.; Terekhov, S. D., A differential game of approach with two pursuers and one evader, Journal of Optimization Theory and Applications, 55, 2, 303-311, (1987) · Zbl 0616.90110
[21] Pittsyk, M.; Chikrii, A. A., On a group pursuit problem, Journal of Applied Mathematics and Mechanics, 46, 5, 584-589, (1982) · Zbl 0528.90107
[22] Pshenichnyi, B. N., Simple pursuit by several objects, Cybernetics and Systems Analysis, 12, 3, 484-485, (1976)
[23] Roos, T., Voronoi diagrams over dynamic scenes, Discrete Applied Mathematics, 43, 3, 243-259, (1993) · Zbl 0770.68115
[24] Sun, W.; Tsiotras, P.; Lolla, T.; Subramani, D.; Lermusiaux, P., Multiple-pursuer-one-evader pursuit evasion game in dynamic flow fields, AIAA Journal of Guidance, Control, and Dynamics, (2017)
[25] Vidal, R.; Shakernia, O.; Kim, H. J.; Shim, D. H.; Sastry, S., Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation, IEEE Transactions on Robotics and Automation, 18, 5, 662-669, (2002)
[26] Yeung, D. W.K.; Petrosjan, L. A., Cooperative stochastic differential games, (2006), Springer Science & Business Media · Zbl 1196.91017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.