Aarhus University Seal / Aarhus Universitets segl

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

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Peyman Afshani
  • Mark de Berg, TU Eindhoven, Eindhoven, Netherlands
  • Kevin Buchin, TU Eindhoven, Eindhoven, Netherlands
  • Jie Gao, Computer Science Department, Stony Brook University, United States
  • Maarten Loffler, Utrecht University, Netherlands
  • Amir Nayyeri, Oregon State University, United States
  • Benjamin Raichel, University of Texas at Dallas, United States
  • Rik Sarkar, University of Edinburgh, United Kingdom
  • Haotian Wang, Stony Brook University, United States
  • Hao-Tsung Wang, Stony Brook University, United States
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 salesman problem as a special case (when
k = 1 and all sites have the same weight). We present a polynomial-time
algorithm with an approximation factor of O(k^2 log w_max/w_min) to the optimal solution, where w_max and w_min are the maximum and minimum weight
of 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-Part A : Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics
EditorsS.M. LaValle, M. Lin, T. Ojala, D. Shell, J. Yu
Publication year2021
Publication statusPublished - 2021
Event14th International Workshop on the Algorithmic Foundations of Robotics - Oulu, Finland
Duration: 21 Jun 202123 Jun 2021
Conference number: 14


Conference14th International Workshop on the Algorithmic Foundations of Robotics
SeriesSpringer Proceedings in Advanced Robotics

See relations at Aarhus University Citationformats

ID: 207956676