You are here:
» Approximation Algorithms for Multi-Robot Patrol-Schedulin...
About Aarhus University
Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
Links
- https://arxiv.org/abs/2005.02530
Other version
- Peyman Afshani
- Mark de Berg, Eindhoven University of Technology, Netherlands
- Kevin Buchin, Eindhoven University of Technology, Netherlands
- Jie Gao, 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
max
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.
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
max
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 language | English |
|---|---|
| Title of host publication | Algorithmic Foundations of Robotics XIV-Part A : Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics |
| Editors | S.M. LaValle, M. Lin, T. Ojala, D. Shell, J. Yu |
| Publisher | Springer |
| Publication year | 2021 |
| Publication status | Published - 2021 |
| Event | 14th International Workshop on the Algorithmic Foundations of Robotics - Oulu, Finland Duration: 21 Jun 2021 → 23 Jun 2021 Conference number: 14 |
Conference
| Conference | 14th International Workshop on the Algorithmic Foundations of Robotics |
|---|---|
| Nummer | 14 |
| Land | Finland |
| By | Oulu |
| Periode | 21/06/2021 → 23/06/2021 |
| Series | Springer Proceedings in Advanced Robotics |
|---|
See relations at Aarhus University Citationformats
ID: 207956676