Asymptotically Optimal Solutions for 3D Reach-Avoid Games with Exclusion Zones Using Informed-Expansive-Spaces-Tree

This paper addresses the reach-avoid game in 3D, where a pursuer attempts to capture an evader while avoiding danger zones, and the evader seeks to reach a target without being captured. Traditional control-based methods struggle with complex scenarios or lack the solution’s guarantees. This paper casts the reach-avoid problem as a planning task, enabling probabilistic complete and asymptotically optimal open-loop solutions assuming the worst-case of the evader in more complex scenarios (i.e., optimal control). To solve this planning problem, this paper proposes the Informed-Expansive-Spaces-Tree (Informed-EST) to restrict the search space after an initial path is found, reducing computational overhead compared with other sampling-based planning algorithms while maintaining the asymptotically optimal guarantees. Evaluations against Rapidly-exploring random tree (RRT), EST and RRT* in reach-avoid scenarios with static and moving exclusion zones highlight improvements in computational efficiency and performance. Additionally, critical limitations of RRT* in reach-avoid scenarios are identified and discussed.

• Publication year

  2025

• Venue

  2025 33rd Mediterranean Conference on Control and Automation (MED)

• Publication date

  2025-06-10

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1109/MED64031.2025.11073302
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Combining Dense and Sparse Rewards to Improve Deep Reinforcement Learning Policies in Reach-Avoid Games with Faster Evaders in Two vs. One Scenarios

  2024cited by this paper
• Optimal Strategies and Cooperative Teaming for 3-D Multiplayer Reach-Avoid Games

  2024cited by this paper
• Transfer reinforcement learning for multi‐agent pursuit‐evasion differential game with obstacles in a continuous environment

  2024cited by this paper
• One Apollonius Circle is enough for many pursuit-evasion games

  2021cited by this paper
• Optimal Strategies for a Class of Multi-Player Reach-Avoid Differential Games in 3D Space

  2020cited by this paper
• A Path Optimization Algorithm for Motion Planning with the Moving Target

  2018cited by this paper
• Real-Time Path Planning Algorithm for Autonomous Border Patrol: Design, Simulation, and Experimentation

  2014influential reference
• Batch Informed Trees (BIT*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs

  2014cited by this paper
• Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic

  2014cited by this paper
• Time-based RRT algorithm for rendezvous planning of two dynamic systems

  2014cited by this paper
• Incremental Sampling-Based Algorithms for a Class of Pursuit-Evasion Games

  2010cited by this paper
• Randomized Kinodynamic Motion Planning with Moving Obstacles

  2002cited by this paper

• No citing papers are available for this paper.