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

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

Standard

Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. / Afshani, Peyman; de Berg, Mark; Buchin, Kevin; Gao, Jie; Loffler, Maarten; Nayyeri, Amir; Raichel, Benjamin; Sarkar, Rik; Wang, Haotian; Wang, Hao-Tsung.

Algorithmic Foundations of Robotics XIV-Part A: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics. ed. / S.M. LaValle; M. Lin; T. Ojala; D. Shell; J. Yu. Springer, 2021. (Springer Proceedings in Advanced Robotics).

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

Harvard

Afshani, P, de Berg, M, Buchin, K, Gao, J, Loffler, M, Nayyeri, A, Raichel, B, Sarkar, R, Wang, H & Wang, H-T 2021, Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. in SM LaValle, M Lin, T Ojala, D Shell & J Yu (eds), Algorithmic Foundations of Robotics XIV-Part A: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics. Springer, Springer Proceedings in Advanced Robotics, 14th International Workshop on the Algorithmic Foundations of Robotics, Oulu, Finland, 21/06/2021. <https://arxiv.org/abs/2005.02530>

APA

Afshani, P., de Berg, M., Buchin, K., Gao, J., Loffler, M., Nayyeri, A., Raichel, B., Sarkar, R., Wang, H., & Wang, H-T. (2021). Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. In S. M. LaValle, M. Lin, T. Ojala, D. Shell, & J. Yu (Eds.), Algorithmic Foundations of Robotics XIV-Part A: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics Springer. Springer Proceedings in Advanced Robotics https://arxiv.org/abs/2005.02530

CBE

Afshani P, de Berg M, Buchin K, Gao J, Loffler M, Nayyeri A, Raichel B, Sarkar R, Wang H, Wang H-T. 2021. Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. LaValle SM, Lin M, Ojala T, Shell D, Yu J, editors. In Algorithmic Foundations of Robotics XIV-Part A: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics. Springer. (Springer Proceedings in Advanced Robotics).

MLA

Afshani, Peyman et al. "Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency"., LaValle, S.M., Lin, M. Ojala, T. Shell, D. Yu, J. (editors). Algorithmic Foundations of Robotics XIV-Part A: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics. Springer. (Springer Proceedings in Advanced Robotics). 2021.

Vancouver

Afshani P, de Berg M, Buchin K, Gao J, Loffler M, Nayyeri A et al. Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. In LaValle SM, Lin M, Ojala T, Shell D, Yu J, editors, Algorithmic Foundations of Robotics XIV-Part A: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics. Springer. 2021. (Springer Proceedings in Advanced Robotics).

Author

Afshani, Peyman ; de Berg, Mark ; Buchin, Kevin ; Gao, Jie ; Loffler, Maarten ; Nayyeri, Amir ; Raichel, Benjamin ; Sarkar, Rik ; Wang, Haotian ; Wang, Hao-Tsung. / Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. Algorithmic Foundations of Robotics XIV-Part A: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics. editor / S.M. LaValle ; M. Lin ; T. Ojala ; D. Shell ; J. Yu. Springer, 2021. (Springer Proceedings in Advanced Robotics).

Bibtex

@inproceedings{ee5ea42726c14515bc4bc1b37dbda1a6,
title = "Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency",
abstract = "We consider the problem of finding patrol schedules for krobots to visit a given set of n sites in a metric space. Each robot has thesame maximum speed and the goal is to minimize the weighted maximumlatency of any site, where the latency of a site is defined as the maximumtime duration between consecutive visits of that site. The problem isNP-hard, as it has the traveling salesman problem as a special case (whenk = 1 and all sites have the same weight). We present a polynomial-timemaxalgorithm 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 weightof the sites respectively. Further, we consider the special case wherethe sites are in 1D. When all sites have the same weight, we present apolynomial-time algorithm to solve the problem exactly. If the sites mayhave different weights, we present a 12-approximate solution, which runsin polynomial time when the number of robots, k, is a constant.",
author = "Peyman Afshani and {de Berg}, Mark and Kevin Buchin and Jie Gao and Maarten Loffler and Amir Nayyeri and Benjamin Raichel and Rik Sarkar and Haotian Wang and Hao-Tsung Wang",
year = "2021",
language = "English",
series = "Springer Proceedings in Advanced Robotics",
editor = "S.M. LaValle and M. Lin and T. Ojala and D. Shell and J. Yu",
booktitle = "Algorithmic Foundations of Robotics XIV-Part A",
publisher = "Springer",
note = "14th International Workshop on the Algorithmic Foundations of Robotics, WAFR ; Conference date: 21-06-2021 Through 23-06-2021",

}

RIS

TY - GEN

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

AU - Afshani, Peyman

AU - de Berg, Mark

AU - Buchin, Kevin

AU - Gao, Jie

AU - Loffler, Maarten

AU - Nayyeri, Amir

AU - Raichel, Benjamin

AU - Sarkar, Rik

AU - Wang, Haotian

AU - Wang, Hao-Tsung

N1 - Conference code: 14

PY - 2021

Y1 - 2021

N2 - We consider the problem of finding patrol schedules for krobots to visit a given set of n sites in a metric space. Each robot has thesame maximum speed and the goal is to minimize the weighted maximumlatency of any site, where the latency of a site is defined as the maximumtime duration between consecutive visits of that site. The problem isNP-hard, as it has the traveling salesman problem as a special case (whenk = 1 and all sites have the same weight). We present a polynomial-timemaxalgorithm 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 weightof the sites respectively. Further, we consider the special case wherethe sites are in 1D. When all sites have the same weight, we present apolynomial-time algorithm to solve the problem exactly. If the sites mayhave different weights, we present a 12-approximate solution, which runsin polynomial time when the number of robots, k, is a constant.

AB - We consider the problem of finding patrol schedules for krobots to visit a given set of n sites in a metric space. Each robot has thesame maximum speed and the goal is to minimize the weighted maximumlatency of any site, where the latency of a site is defined as the maximumtime duration between consecutive visits of that site. The problem isNP-hard, as it has the traveling salesman problem as a special case (whenk = 1 and all sites have the same weight). We present a polynomial-timemaxalgorithm 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 weightof the sites respectively. Further, we consider the special case wherethe sites are in 1D. When all sites have the same weight, we present apolynomial-time algorithm to solve the problem exactly. If the sites mayhave different weights, we present a 12-approximate solution, which runsin polynomial time when the number of robots, k, is a constant.

M3 - Article in proceedings

T3 - Springer Proceedings in Advanced Robotics

BT - Algorithmic Foundations of Robotics XIV-Part A

A2 - LaValle, S.M.

A2 - Lin, M.

A2 - Ojala, T.

A2 - Shell, D.

A2 - Yu, J.

PB - Springer

T2 - 14th International Workshop on the Algorithmic Foundations of Robotics

Y2 - 21 June 2021 through 23 June 2021

ER -