Heuristic artificial bee colony algorithm for solving the Homicidal Chauffeur differential game

Document Type : Original Article

Authors

1 Department of Applied Mathematics, Faculty of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

2 Department of Electrical and Computer Engineering, SYSTEC, Faculdade de Engenharia, Universidade do Porto, 4200-465, Porto, Portugal

Abstract

In this paper, we consider the Homicidal Chauffeur (HC) problem as an interesting and practical differential game. At first, we introduce a bilevel optimal control problem (BOCP) and prove that a saddle point solution for this game exists if and only if this BOCP has an optimal solution in which the optimal value of the objective function is equal to 1. Then, BOCP is discretized and converted to a nonlinear bilevel programming problem. Finally, an Artificial Bee Colony (ABC) algorithm is used for solving this problem, in which the lower-level problem will be considered as a constraint and solved by an NLP-solver. Finally, to demonstrate the effectiveness of the presented method, various cases of HC problem are solved and the simulation results are reported.

Keywords

Main Subjects

References

[1] S. Aslan, H. Badem, D. Karaboga, Improved quick artificial bee colony (iqABC) algorithm for global opti[1]mization, Soft Computing, 2019.
[2] T. Ba¸sar, G. Olsder, Dynamic Noncooperative Game Theory, 2nd Edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998.
[3] J. F. Bard, Practical bilevel optimization: algorithms and applications, volume 30. Springer Science & Business Media, 2013.
[4] J. Betts, Practical Methods for Optimal Control and Estimation Using Nonlinear Programming, Society for Industrial and Applied Mathematics, second edition, 2010.
[5] J. T. Betts, Survey of numerical methods for trajectory optimization, Journal of Guidance, Control, and Dynamics, 21(2) (1998) 193-207.
[6] A. E. Bryson, Applied optimal control: optimization, estimation and control, Routledge, 2018.
[7] A. E. Bryson, Y-C. Ho, Applied optimal control: optimization, estimation and control, Hemisphere, 1975.
[8] B. Colson, P. Marcotte, G. Savard, An overview of bilevel optimization, Annals of Operations Research, 153(1) (2007) 235-256.
[9] H. Ehtamo, T. Raivio, On applied nonlinear and bilevel programming or pursuit-evasion games, Journal of Optimization Theory and Applications, 108(1) (2001) 65-96.
[10] I. Exarchos, P. Tsiotras, M. Pachter, On the suicidal pedestrian differential game, Dynamic Games and Applications, 5(3) (2015) 297-317.
[11] I. Exarchos, P. Tsiotras, M. Pachter, UAV collision avoidance based on the solution of the suicidal pedestrian differential game, 2016.
[12] M. Falcone, Numerical methods for differential games based on partial differential equations, International Game Theory Review, 8(2) (2006) 231-272.
[13] L. Guo, J. J. Ye, Necessary optimality conditions for optimal control problems with equilibrium constraints, SIAM Journal on Control and Optimization, 54(5) (2016) 2710-2733.
[14] K. Horie, Collocation with nonlinear programming for two-sided flight path optimization, PhD thesis, Univer[1]sity of Illinois at Urbana-Champaign, 2002.
[15] K. Horie, B. A. Conway, Genetic algorithm preprocessing for numerical solution of differential games problems, Journal of Guidance, Control, and Dynamics, 27(6) (2004) 1075-1078.
[16] K. Horie, B. A. Conway, Optimal fighter pursuit-evasion maneuvers found via two-sided optimization, Journal of Guidance, Control, and Dynamics, 29(1) (2006)105-112.
[17] R. Isaacs, Differential games. A mathematical theory with applications to warfare and pursuit, control and optimization, John Wiley & Sons, Inc., New York-London-Sydney, 1965.
[18] P. A. Johnson, Numerical Solution Methods for Differential Game Problems, PhD thesis, Massachusetts Institute of Technology, 2009.
[19] J. Lewin, J. V. Breakwell, The surveillance-evasion game of degree, Journal of Optimization Theory and Applications, 16(3-4) (1975) 339-353. [20] V. S. Patsko, V. L. Turova, Families of semipermeable curves in differential games with the homicidal chauffeur dynamics, Automatica, 40(12) (2004) 2059-2068.
[21] V. S. Patsko, V. L. Turova, Numerical investigation of the value function for the homicidal chauffeur problem with a more agile pursuer, Annals of the International Society of Dynamic Games, 10 (2009) 231-258.
[22] V. S. Patsko, V. L. Turova, Homicidal chauffeur game: History and modern studies, Annals of the International Society of Dynamic Games, 11 (2011) 227-251.
[23] M. Pontani, Differential games treated by a gradient–restoration approach. In Variational Analysis and Aerospace Engineering, pages 379-396. Springer, 2009.
[24] M. Pontani, Numerical solution of orbital combat games involving missiles and spacecraft, Dynamic Games and Applications, 1(4) (2011) 534-557.
[25] M. Pontani, B. A. Conway, Numerical solution of the three-dimensional orbital pursuit-evasion game, Journal of Guidance, Control, and Dynamics, 32(2) (2009) 474-487.
[26] S. Sun, Q. Zhang, R. Loxton, B. Li, Numerical solution of a pursuit-evasion differential game involving two spacecraft in low earth orbit. Journal of Industrial and Management Optimization, 11(4) (2015) 1127-1147.
[27] A. W¨achter, L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106(1, Ser. A) (2006) 25-57.
AUT Journal of Mathematics and Computing
Volume 1, Issue 2
September 2020
Pages 153-163

Files

Share

How to cite

Statistics