Research on Bounded Rational Game Algorithm for Ship Target Tracking Based on Reinforcement Learning

doi:10.3778/j.issn.1002-8331.2401-0032

Abstract

Abstract: Since decision-makers in reality are not always able to analyze problems perfectly rationally, a pursuit evasion game algorithm based on bounded rationality is proposed. It establishes a pursuit evasion game model and first solves the saddle point strategies of the two players under perfect rationality. Introducing the bounded rationality level-k model, a structural assumption is made on the level of thinking strategies for pursuers and evaders. It allows both parties to have different strategic reasoning abilities, and gives corresponding levels’ value functions and strategies, which satisfy the HJI equation. As the level increases, the strategy will eventually tend towards Nash equilibrium. Due to the difficulty in directly solving the HJI equation, an actor critic algorithm based on reinforcement learning is used to solve it. The algorithm is designed to enable pursuers to estimate the thinking level of evaders and adopt appropriate strategies. Simplify the motion of a ship as a two-dimensional mathematical model, this paper establishes a ship pursuit and evasion game model, and performs algorithm simulation verification on it.

Key words: pursuit-evasion game, target tracking, reinforcement learning, bounded rationality

摘要： 针对现实中的决策者并非总能完全理性分析问题的情况，提出有限理性下的追逃博弈算法。建立追逃博弈模型，先求解完全理性下博弈双方的鞍点策略。引入有限理性level-k模型，对追击者和躲避者思考策略的层次进行结构性假设，允许追逃双方具备不同的策略推理能力，并给出相应等级的值函数和策略，策略满足HJI方程。随着等级的增加，策略最终会趋于纳什均衡。由于HJI方程难以直接求解，基于强化学习的actor-critic算法进行求解，设计算法使追击者能够估算出躲避者的思维等级并采取合适的策略。以舰船为对象，将舰船运动简化为二维的数学模型，建立舰船追逃博弈模型，对其进行算法仿真验证。

关键词: 追逃博弈, 目标跟踪, 强化学习, 有限理性

CHEN Suxia, XU Qingwen, LIU Jiufu, XIE Hui, LIU Xiangwu. Research on Bounded Rational Game Algorithm for Ship Target Tracking Based on Reinforcement Learning[J]. Computer Engineering and Applications, 2024, 60(20): 116-123.

陈素霞, 徐清雯, 刘久富, 解晖, 刘向武. 基于强化学习的舰船目标跟踪有限理性博弈算法研究[J]. 计算机工程与应用, 2024, 60(20): 116-123.

References

[1] CHEN Y L, MA X W, BAI G Q, et al. Multi-autonomous underwater vehicle formation control and cluster search using a fusion control strategy at complex underwater environment[J]. Ocean Engineering, 2020, 216(7): 108048.
[2] CARDONA D, BECERRA I, MURRIETA-CID R. On the equivalence of pursuer strategies and the lack of nash equilibrium in a visibility pursuit-evasion game[J]. Journal of the Franklin Institute, 2022, 359(18): 10420-10454.
[3] MOLL A L V, GARCIA E, CASBEER D, et al. Multiple pursuer single evader border defense differential game[J]. Journal of Aerospace Information Systems, 2019, 17: 407-416.
[4] GENG Y, YUAN L, GUO Y, et al. Impulsive guidance of optimal pursuit with conical imaging zone for the evader[J]. Aerospace Science and Technology, 2023, 142(1): 108604.
[5] CHAUDHARI A, CHAKRABORTY D. Time-optimal feedback control for the game of two Isotropic Rockets[J]. IFAC-PapersOnLine, 2023, 56(2): 1952-1957.
[6] CHUNG T H, HOLLINGER G A, ISLER V. Search and pursuit-evasion in mobile robotics[J]. Autonomous Robots, 2011, 31(4): 299-316.
[7] 刘肇隆, 宋耀, 徐翊铭, 等. 图注意力网络的微分博弈追逃问题最优策略[J]. 计算机工程与应用, 2023, 59(9): 313-318.
LIU Z L, SONG Y, XU Y M, et al. Optimal strategy of differential game pursuit problem in graph attention network[J]. Computer Engineering and Applications, 2023, 59(9): 313-318.
[8] NASROLLAHI S. A constrained cooperative guidance algorithm based on gray wolf optimization against highly maneuvering target[J]. Applied Soft Computing, 2023, 144: 110476.
[9] 袁斐然, 刘春生, 陈必露. 基于自适应动态规划的多对一追逃博弈策略[J]. 电光与控制, 2022, 29(1): 1-6.
YUAN F R, LIU C S, CHEN B L. Many-to-one pursuit-evasion game strategy based on adaptive dynamic programming[J]. Electronics Optics & Control, 2022, 29(1): 1-6.
[10] WANG J, LI G, LIANG L, et al. Pursuit-evasion games of multiple cooperative pursuers and an evader: a biological-inspired perspective[J]. Communications in Nonlinear Science and Numerical Simulation, 2022, 110: 106386.
[11] 许旭升, 党朝辉, 宋斌, 等. 基于多智能体强化学习的轨道追逃博弈方法[J]. 上海航天 (中英文), 2022, 39(2): 24-31.
XU X S, DANG C H, SONG B, et al. Method for cluster satellite orbit pursuit-evasion game based on multi-agent deep deterministic policy gradient algorithm[J]. Aerospace Shanghai (Chinese & English), 2022, 39(2): 24-31.
[12] PAN T, YUAN Y. A region-based relay pursuit scheme for a pursuit-evasion game with a single evader and multiple pursuers[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2023, 53(3): 1958-1969.
[13] WEINTRAUB I E, PACHTER M, GARCIA E. An introduction to pursuit-evasion differential games[C]//Proceedings of the 2020 American Control Conference, 2020: 1049-1066.
[14] YAN R, DUAN X, SHI Z, et al. Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games[J]. Automatica, 2022, 140: 110207.
[15] ISAACS R. Differential games: a mathematical theory with applications to warfare and pursuit control and optimization[M]. New York: John Wiley and Sons, 1965.
[16] LEWIS F L, VRABIE D L, SYRMOS V L. Optimal control[M]. 3rd ed. New Jersey: John Wiley & Sons, 2012.
[17] MITCHELL I M, BAYEN A M, TOMLIN C J. A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games[J]. IEEE Transactions on Automatic Control, 2005, 50(7): 947-957.
[18] SIMON H A. Models of man: social and rational[M]. New York: John Wiley & Sons, 1957.
[19] LUO S, FANG S, ZHANG J, et al. Price competition and cost efficiency facing buyer’s bounded rationality[J]. International Journal of Production Economics, 2023, 266: 109062.
[20] BRAATEN C N, TSAI L C. Effects of bounded rationality on prosecutorial decision making: analysis of penalties on corporate fraud violators[J]. International Journal of Law, Crime and Justice, 2024, 76: 100634.
[21] STAHL D O, WILSON P W. On players’ models of other players: theory and experimental evidence[J]. Games and Economic Behavior, 1995, 10(1): 218-254.
[22] ZHANG J. Level-k reasoning in school choice[J]. Games and Economic Behavior, 2021, 128(3): 1-17.
[23] TEEPLE K. Level-k predatory trading[J]. Journal of Mathematical Economics, 2023, 106: 102847.
[24] DENG Y, ZHANG X, IM N, et al. Model-based event-triggered tracking control of underactuated surface vessels with minimum learning parameters[J]. IEEE Transactions on Neural Networks and Learning Systems, 2019, 31(10): 4001-4014.