Voronoi-cell based pursuit and evasion strategies in a cluttered environment

The field of pursuit and evasion strategies plays a critical role in control theory, robotics, and autonomous navigation. Despite extensive prior research, it continues to pose significant challenges and attract interest. In this paper, we present and evaluate several algorithms for pursuit and evasion in a two-dimensional bounded environment with static obstacles. The core strategies are based on Voronoi cell decompositions, guiding multiple pursuers in an effort to encircle an evader who, in turn, attempts to break free from this encirclement. By combining Voronoi-based movement planning with independent obstacle avoidance, our approach enables low communication overhead between agents while maintaining high adaptability. We investigate and compare both a naïve evasion strategy and several Voronoi-based alternatives, including a more advanced variant that introduces a fixed critical area threshold, offering a contrast to strategies relying on a dynamic threshold. In parallel, we implement a pursuit strategy based on centroid-directed motion within Voronoi partitions. Obstacle avoidance is handled independently via a directional repulsive force algorithm that responds to local proximity data. To evaluate the effectiveness of these strategies, we conduct extensive simulations with randomized initial positions and varied obstacle configurations. Performance is assessed primarily in terms of mean capture time and visualized through spatial dynamics. Results show that the proposed Voronoi-based strategy with a fixed critical area significantly enhances evader survivability compared to other methods.