Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency

Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, Hao-Tsung Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the problem of finding patrol schedules for k robots to visit a given set of n sites in a metric space. Each robot has the same maximum speed and the goal is to minimize the weighted maximum latency of any site, where the latency of a site is defined as the maximum time duration between consecutive visits of that site. The problem is NP-hard, as it has the traveling sales man problem as a special case (when k = 1and all sites have the same weight). We present a polynomial-time algorithm with an approximation factor of O(k2 log wmax/wmin) to the optimalsolution, where wmax and wmin are the maximum and minimum weigh tof the sites respectively. Further, we consider the special case where the sites are in 1D. When all sites have the same weight, we present a polynomial-time algorithm to solve the problem exactly. If the sites may have different weights, we present a 12-approximate solution, which runs in polynomial time when the number of robots, k, is a constant.
Original languageEnglish
Title of host publicationAlgorithmic Foundations of Robotics XIV
EditorsSteven M. LaValle, Ming Lin, Timo Ojala, Dylan Shell, Jingjin Yu
PublisherSpringer, Cham
Pages107 - 123
Number of pages16
ISBN (Electronic)978-3-030-66723-8
ISBN (Print)978-3-030-66722-1
Publication statusPublished - 9 Feb 2021
Event14th International Workshop on the Algorithmic Foundations of Robotics - Oulu, Finland
Duration: 21 Jun 202023 Jun 2020

Publication series

NameSpringer Proceedings in Advanced Robotics
ISSN (Print)2511-1256
ISSN (Electronic)2511-1264


Workshop14th International Workshop on the Algorithmic Foundations of Robotics
Abbreviated titleWAFR 2020
Internet address


Dive into the research topics of 'Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency'. Together they form a unique fingerprint.

Cite this