2025/09/15 by Deepak Mallya, Mallya, Deepak, Arpita Sinha +3
Computer Science · Engineering · #FOS: Electrical engineering #Optimization and Search Problems #Robotic Path Planning Algorithms #Systems and Control (eess.SY) #Vehicle Routing Optimization Methods #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2509.11640
openalex publication_date 2025/09/15 · openalex created_date 2025/10/12 · openalex updated_date 2026/07/28
The multi-agent patrol problem refers to repeatedly visiting different locations in an environment using multiple autonomous agents. For over two decades, researchers have studied this problem in various settings. While providing valuable insights into the problem, the works in existing literature have not commented on the nature of the optimal solutions to the problem. We first show that an ε-approximate recurrent patrol strategy exists for every feasible patrol strategy. Then, we establish the existence of a recurrent patrol strategy that is an ε-optimal solution to the General Patrol Problem. The factor ε is proportional to the discretisation constant D, which can be arbitrarily small and is independent of the number of patrol agents and the size of the environment. This result holds for a variety of problem formulations already studied. We also provide an algorithmic approach to determine an ε-approximate recurrent patrol strategy for a patrol strategy created by any method from the literature. We perform extensive simulations in graphs based on real-life environments to validate the claims made in this work.