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