Homicidal Chauffeur Reach-Avoid Games via Guaranteed Winning Strategies

• 成果类型: Article
• 署名作者: Yan, Rui; Deng, Ruiliang; Lai, Haowen; Zhang, Weixian; Shi, Zongying; Zhong, Yisheng
• 署名单位: Tsinghua University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3329693
• 发表日期: 2024
• 页码: 2367-2382
• 关键词: games; differential games; mathematical models; Turning; computational modeling; automobiles; Analytical models; homicidal chauffeur; multiagent systems; reach-avoid games; winning strategies

摘要

This article studies a planar Homicidal Chauffeur reach-avoid differential game, where the pursuer is a Dubins car and the evader has simple motion. The pursuer aims to protect a goal region from the evader. The game is solved in an analytical approach instead of solving Hamilton-Jacobi-Isaacs equations numerically. First, an evasion region is introduced, based on which a pursuit strategy guaranteeing the winning of a simple-motion pursuer under specific conditions is proposed. Motivated by the simple-motion pursuer, a strategy for a Dubins-car pursuer is proposed when the pursuer-evader configuration satisfies separation condition (SC) and interception orientation (IO). The necessary and sufficient condition on capture radius, minimum turning radius, and speed ratio to guarantee the pursuit winning is derived. When the IO is deviated (Non-IO), a heading adjustment pursuit strategy is proposed, and the condition to achieve IO within a finite time is given. Based on it, a two-step pursuit strategy is proposed for the SC and Non-IO case. A nonconvex optimization problem is introduced to give a condition guaranteeing the winning of the pursuer. A polynomial equation gives a lower bound of the nonconvex problem, providing a sufficient and efficient pursuit winning condition. Finally, we extend to multiplayer games by collecting pairwise outcomes for pursuer-evader matchings. Simulations are provided to illustrate the theoretical results.