Abstract
Multi-robot pursuit-evasion (MPE) in cluttered environments requires a delicate balance between coordination, collision avoidance, and computational efficiency. This paper presents the Obstacle-Aware Evader-Centered Bounded Voronoi Cell (OA-ECBVC), a decentralized control framework designed to surround and capture a dynamic evader while navigating complex obstacles. By integrating spatial partitioning with a shrinking boundary logic, the approach ensures that a team of pursuers can effectively "box in" an agent and close the distance without collisions or the computational overhead of centralized planning.
Introduction
The challenge of intercepting an adversarial agent—known as pursuit-evasion—is a foundational problem in robotics with critical applications in security, search-and-rescue, and environmental monitoring. While many solutions exist for open-space scenarios, real-world environments are often cluttered with obstacles like trees or buildings. Existing methods frequently struggle with three primary issues: the "computational explosion" of centralized solvers as robot counts increase, the risk of collisions in dense environments, and the failure to prevent an evader from escaping through gaps in the pursuit formation.
To address these limitations, this research introduces OA-ECBVC, a decentralized algorithm that guarantees collision-free trajectories while maintaining a robust encirclement formation.
Methodology
The OA-ECBVC algorithm relies on a combination of geometric spatial partitioning and dynamic boundary constraints to manage the pursuit.
Spatial Partitioning and Obstacle Awareness
The system utilizes Voronoi diagrams to divide the environment into distinct territories for each robot. By restricting each pursuer's movement to its own cell, the algorithm inherently prevents inter-robot collisions. To account for environmental obstacles, the framework employs the Separating Hyperplane Theorem. This allows the algorithm to treat obstacles as additional boundaries, defining a "safe zone" for each robot that is guaranteed to be clear of both teammates and environmental hazards.
Encirclement and Capture Strategy
The pursuit is executed in two primary phases:
- Encirclement: Pursuers are driven toward the centroid of their respective Voronoi cells. This Centroidal Voronoi Tessellation (CVT) naturally causes the robots to distribute themselves evenly around the evader, effectively blocking all potential escape routes.
- Capture: Once the evader is surrounded, the algorithm defines a virtual bounding box ($\mathcal{E}$) centered on the evader. By systematically shrinking this box, the pursuers are forced into a coordinated "pincer" movement, closing the gap until the capture distance is achieved.
Dynamic Control
The framework is adaptable to different robot dynamics. For simple systems, reactive control is used; for more complex triple-integrator dynamics, the system employs Model Predictive Control (MPC) to ensure smooth, feasible trajectories that respect physical constraints such as velocity, acceleration, and jerk.
Experimental Evaluation
The efficacy of OA-ECBVC was evaluated through both high-fidelity simulations and real-world hardware tests.
- Simulated Environments: The authors conducted randomized MATLAB simulations in "forest" environments featuring 16+ cluttered obstacles and varying initial configurations.
- Hardware Validation: The system was deployed on a decentralized multi-robot team using mobile robots equipped with Intel i7 CPUs. The robots operated under the Robot Operating System (ROS) and were tracked using a NOKOV motion capture system to simulate a real-world "tunnel" pursuit scenario.
Results and Key Insights
Experimental results demonstrate that OA-ECBVC outperforms existing state-of-the-art methods, such as "Surrounding and Hunting" (SH) and standard Obstacle-Aware Voronoi Cells (OAVC):
- Increased Efficiency: OA-ECBVC achieved capture times approximately 20% faster than competing methods.
- Robustness to Clutter: While other algorithms saw success rates drop as obstacle density increased, OA-ECBVC remained stable, maintaining a high success rate even in highly cluttered environments.
- Guaranteed Safety: In all trials, the minimum distance to obstacles ($d_{mo}$) and teammates ($d_{mp}$) remained strictly above safety thresholds, validating the framework's collision-free claims.
- Scalability: Because each robot calculates its own Voronoi cell and centroid locally, the system scales efficiently without the exponential computational cost associated with centralized solvers.
Conclusion
OA-ECBVC provides a robust, decentralized solution for multi-robot pursuit in complex environments. By combining the "shrinking box" logic with obstacle-aware Voronoi partitioning, the framework ensures safe and efficient capture. Future work will focus on relaxing the requirement for global positioning data, moving toward systems that can operate using only local, line-of-sight sensors, and extending the logic to handle multiple simultaneous evaders.
Summary updated