Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency: Proceedings of the 14th International Workshop on the Algorithmic Foundations of Robotics (WAFR 20)

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

Onderzoeksoutput: Andere bijdrageOverige bijdrageAcademic

Samenvatting

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(klogwmaxwmin) to the optimal solution, where wmax and wmin 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. When the sites may have different weights, we use dynamic programming to generate an 8-approximate solution, which also runs in polynomial time.
Originele taal-2Engels
UitgeverCornell university
Aantal pagina's25
StatusGepubliceerd - 2020

Vingerafdruk Duik in de onderzoeksthema's van 'Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency: Proceedings of the 14th International Workshop on the Algorithmic Foundations of Robotics (WAFR 20)'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit