Pursuit and Evasion Strategy of a Differential Game Based on Deep Reinforcement Learning

Can Xu, Yin Zhang⋆, Weigang Wang, Ligang DongFrontiers in Bioengineering and Biotechnology 2022 · DOI

Abstract

Since the emergence of deep neural networks (DNN), they have achieved excellent performance in various research areas. As the combination of DNN and reinforcement learning, deep reinforcement learning (DRL) has become a new paradigm for solving differential game problems. In this study, we build a reinforcement learning environment and apply relevant DRL methods to a specific bio-inspired differential game problem: the dog-sheep game. The dog-sheep game environment is set on a circle where the dog chases down the sheep attempting to escape. According to specific presuppositions, we are able to acquire the kinematic pursuit and evasion strategy. Next, this study implements the value-based deep Q-network (DQN) model and the deep deterministic policy gradient (DDPG) model to the dog-sheep game, attempting to endow the sheep with the ability to escape successfully. To enhance the performance of the DQN model, this study introduced a reward mechanism with a time-out strategy and a game environment with an attenuation mechanism for the sheep's steering angle. These modifications effectively increase the probability of escape for the sheep. Furthermore, the DDPG model is adopted due to its continuous action space. Results show the modifications of the DQN model effectively increase escape probabilities to the same level as the DDPG model. When it comes to learning ability under various environment difficulties, the refined DQN and DDPG models show greater performance enhancement over the naive evasion model in harsh environments than in loose environments.

Problem Formulation: The Dog-Sheep Game

Differential games are mathematical models of conflict where players' states evolve over time, traditionally solved using complex differential equations. While effective, these "handcrafted" solutions are difficult to adapt to new scenarios or constrained environments.

The authors focus on the dog-sheep game: a pursuer (the dog) tries to catch an evader (the sheep) inside a circular arena. While the dog follows a known optimal kinematic pursuit strategy, the sheep must find the best way to escape. The challenge lies in the sheep's limited maneuverability as it approaches the boundary and the need for a strategy that doesn't just rely on running away, but on "out-thinking" the pursuer's geometry.

Diagram of the dog's pursuit strategy within the circular arena, showing the relative positions of the sheep and dog.

Methodology and Model Architecture

The researchers compared two primary DRL architectures to train the sheep:

  1. Deep Q-Network (DQN): A value-based model typically used for discrete actions (e.g., turn left or right).
  2. Deep Deterministic Policy Gradient (DDPG): An actor-critic model designed for continuous action spaces (e.g., choosing any specific angle).

To optimize these models for the pursuit-evasion context, two key refinements were introduced:

  • Steering Angle Attenuation: To prevent the DQN from making erratic, sharp turns that would lead to a quick capture, the researchers implemented a function that restricts the sheep's maximum steering angle based on its distance from the center and its relative angle to the dog. This is based on dividing the sheep's relative position into specific zones.
  • Time-out Reward Strategy: Instead of a simple win/loss reward, they added a penalty for "lingering." If the sheep stays in the circle longer than the theoretical minimum escape time, it receives a growing negative reward, forcing it to prioritize efficiency.
Spatial division of the sheep's relative position into three parts (M0, M1, and Mr\M1) used to formulate the attenuation mechanism.

Experimental Setup

The study utilized a custom simulation environment in Python to serve as a "digital twin" for training and evaluation. Training consisted of 1,500 episodes, followed by 50 rounds of simulation per configuration for evaluation. The primary metric for environment difficulty was the speed ratio ($\eta$), representing the dog's speed relative to the sheep.

Key Results and Insights

  • Bridging the Discrete-Continuous Gap: A significant finding is that a refined DQN (discrete) can perform as well as, or even slightly better than, a DDPG (continuous) model. This suggests that intelligent constraints on the action space (the attenuation mechanism) can be more important than the granularity of the actions themselves.
  • The "Harsh Environment" Advantage: The DRL models showed their greatest "learning gain" in difficult scenarios where the dog was significantly faster. In "loose" environments, simple heuristics (like running straight out) work fine, but in "harsh" environments, the learned DRL strategies provided a massive performance boost.
  • Reward Shaping Efficiency: The "time-out" strategy was critical. Without it, agents often failed to learn the optimal path. The Refined DQN achieved the highest average reward (7.36) compared to DDPG (7.25) and the "naive" DQN-T (6.68).
  • Escape Probability: Both the refined DQN and DDPG models outperformed baseline models (running straight out or random movement) by approximately 50% in standard settings. As the speed ratio ($\eta$) increased, the improvement of DRL methods over the baseline grew exponentially, reaching nearly 140% improvement in the harshest tested environments.

Conclusion

This study demonstrates that DRL can effectively solve complex pursuit-evasion problems in constrained environments. While currently limited to a single-pursuer, single-evader scenario with a fixed pursuer strategy, the results provide a foundation for more complex multi-agent competitive learning. Future work will explore scenarios with multiple agents and competitive learning where both the pursuer and evader evolve strategies simultaneously in irregular or obstacle-filled arenas.

Summary updated

Abstract

Since the emergence of deep neural network (DNN), it has achieved excellent performance in various research areas. As the combination of DNN and reinforcement learning, deep reinforcement learning (DRL) becomes a new paradigm for solving differential game problems. In this study, we build up a reinforcement learning environment and apply relevant DRL methods to a specific bio-inspired differential game problem: the dog sheep game. The dog sheep game environment is set on a circle where the dog chases down the sheep attempting to escape. According to some presuppositions, we are able to acquire the kinematic pursuit and evasion strategy. Next, this study implements the value-based deep Q network (DQN) model and the deep deterministic policy gradient (DDPG) model to the dog sheep game, attempting to endow the sheep the ability to escape successfully. To enhance the performance of the DQN model, this study brought up the reward mechanism with a time-out strategy and the game environment with an attenuation mechanism of the steering angle of sheep. These modifications effectively increase the probability of escape for the sheep. Furthermore, the DDPG model is adopted due to its continuous action space. Results show the modifications of the DQN model effectively increase the escape probabilities to the same level as the DDPG model. When it comes to the learning ability under various environment difficulties, the refined DQN and the DDPG models have bigger performance enhancement over the naive evasion model in harsh environments than in loose environments.
BibTeX
@inproceedings{xu2022pursuit,
  author = {Can Xu and Yin Zhang⋆ and Weigang Wang and Ligang Dong},
  title = {{Pursuit and Evasion Strategy of a Differential Game Based on Deep Reinforcement Learning}},
  booktitle = {Frontiers in Bioengineering and Biotechnology},
  year = {2022},
  doi = {10.3389/fbioe.2022.827408},
}
Figure