Abstract
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(k2logwmaxwmin) 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. If the sites may have different weights, we present a 12-approximate solution, which runs in time (nwmax/wmin)O(k).
Original language | English |
---|---|
Title of host publication | Springer Proceedings in Advanced Robotics |
Publisher | Springer |
Pages | 107-123 |
Number of pages | 17 |
DOIs | |
Publication status | Published - 2021 |
Publication series
Name | Springer Proceedings in Advanced Robotics |
---|---|
Volume | 17 |
ISSN (Print) | 2511-1256 |
ISSN (Electronic) | 2511-1264 |
Bibliographical note
Publisher Copyright:© 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.
Funding
Gao, Wang and Yang would like to acknowledge supports from NSF CNS-1618391, DMS-1737812, OAC-1939459. Raichel would like acknowledge support from NSF CAREER Award 1750780. Acknowledgement. Gao, Wang and Yang would like to acknowledge supports from NSF CNS-1618391, DMS-1737812, OAC-1939459. Raichel would like acknowledge support from NSF CAREER Award 1750780.
Keywords
- Approximation
- Motion planning
- Scheduling