Title: Graphical Voronoi study for enhancing pursuer-evader robot games strategies: improved spatial awareness and decision-making

Authors: Imen Ben Omrane; Khaled Khnissi; Hassene Seddik; Ahmad Hably

Addresses: RIFTSI-Lab, National Superior School of Engineers of Tunis, University of Tunis (ENSIT), 05 Ave Taha Hussein, Montfleury, 1008 Tunis, Tunisia ' RIFTSI-Lab, National Superior School of Engineers of Tunis, University of Tunis (ENSIT), 05 Ave Taha Hussein, Montfleury, 1008 Tunis, Tunisia ' RIFTSI-Lab, National Superior School of Engineers of Tunis, University of Tunis (ENSIT), 05 Ave Taha Hussein, Montfleury, 1008 Tunis, Tunisia ' University Grenoble Alpes, Institute of Engineering Univ. Grenoble Alpes, CNRS, Grenoble INP, GIPSA-Lab, France

Abstract: This research examines a differential multi-agent pursuit-evasion capture game based on an improved graphical Voronoi partition method. The objective is to capture all evaders within a specified time limit. By applying the modified Voronoi graph technique, every pursuer can detect nearby evaders and move to catch them. The pursuer performs capturing by surrounding the evader within its Voronoi cell. As the pursuit intensifies, the area of the evader's cell shrinks since the agents work in a constrained environment. The general applicability of this graphical method for resolving multi-agent pursuit-evasion games is shown using Voronoi partitioning and control policies. The Voronoi diagram provides a discrete abstraction of the continuous space which enables decentralised collision-free motion planning. To assess the computational difficulty of the multi-agent capture method, the joint capture conditions are established. The pursuers coordinate based on local information to converge on the evaders. This research provides a novel graph-based technique for cooperative multi-agent capture scenarios and may have broader applications in robotics and distributed control. Overall, this work establishes the theoretical foundations and demonstrates the universality of an improved Voronoi-based approach for multi-pursuer multi-evader capture.

Keywords: differential game; pursuit-evasion game; mobile robots; AI; Voronoi; decision-making; autonomous navigation.

DOI: 10.1504/IJMIC.2025.147945

International Journal of Modelling, Identification and Control, 2025 Vol.46 No.1, pp.47 - 62

Received: 01 May 2024
Accepted: 22 Aug 2024
Published online: 11 Aug 2025 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article