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

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

doi:10.1007/978-3-030-66723-8_7

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

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

11 Citations (Scopus)

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 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 time (nwmax/wmin)O(k).

Original language	English
Title of host publication	Algorithmic Foundations of Robotics XIV
Subtitle of host publication	Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics
Editors	Steven M. LaValle, Ming Lin, Timo Ojala, Dylan Shell, Jingjin Yu
Publisher	Springer
Pages	107-123
Number of pages	17
ISBN (Electronic)	978-3-030-66723-8
ISBN (Print)	978-3-030-66722-1
DOIs	https://doi.org/10.1007/978-3-030-66723-8_7
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

Access to Document

10.1007/978-3-030-66723-8_7

Cite this

Afshani, P., de Berg, M., Buchin, K., Gao, J., Löffler, M., Nayyeri, A., Raichel, B., Sarkar, R., Wang, H., & Yang, 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: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics (pp. 107-123). (Springer Proceedings in Advanced Robotics; Vol. 17). Springer. https://doi.org/10.1007/978-3-030-66723-8_7

Afshani, Peyman ; de Berg, Mark ; Buchin, Kevin et al. / Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. Algorithmic Foundations of Robotics XIV: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics. editor / Steven M. LaValle ; Ming Lin ; Timo Ojala ; Dylan Shell ; Jingjin Yu. Springer, 2021. pp. 107-123 (Springer Proceedings in Advanced Robotics).

@inproceedings{29d7d491d4384ed989fc46a3f0bff0cb,

title = "Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency",

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).",

keywords = "Approximation, Motion planning, Scheduling",

author = "Peyman Afshani and \{de Berg\}, Mark and Kevin Buchin and Jie Gao and Maarten L{\"o}ffler and Amir Nayyeri and Benjamin Raichel and Rik Sarkar and Haotian Wang and Hao-Tsung Yang",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.",

year = "2021",

doi = "10.1007/978-3-030-66723-8\_7",

language = "English",

isbn = "978-3-030-66722-1",

series = "Springer Proceedings in Advanced Robotics",

publisher = "Springer",

pages = "107--123",

editor = "LaValle, \{Steven M.\} and Ming Lin and Timo Ojala and Dylan Shell and Jingjin Yu",

booktitle = "Algorithmic Foundations of Robotics XIV",

address = "Germany",

}

Afshani, P, de Berg, M, Buchin, K, Gao, J, Löffler, M, Nayyeri, A, Raichel, B, Sarkar, R, Wang, H & Yang, 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: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics. Springer Proceedings in Advanced Robotics, vol. 17, Springer, pp. 107-123. https://doi.org/10.1007/978-3-030-66723-8_7

Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. / Afshani, Peyman; de Berg, Mark; Buchin, Kevin et al.
Algorithmic Foundations of Robotics XIV: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics. ed. / Steven M. LaValle; Ming Lin; Timo Ojala; Dylan Shell; Jingjin Yu. Springer, 2021. p. 107-123 (Springer Proceedings in Advanced Robotics; Vol. 17).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 - Löffler, Maarten

AU - Nayyeri, Amir

AU - Raichel, Benjamin

AU - Sarkar, Rik

AU - Wang, Haotian

AU - Yang, Hao-Tsung

PY - 2021

Y1 - 2021

N2 - 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).

AB - 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).

KW - Approximation

KW - Motion planning

KW - Scheduling

UR - https://www.scopus.com/pages/publications/85107058541

U2 - 10.1007/978-3-030-66723-8_7

DO - 10.1007/978-3-030-66723-8_7

M3 - Conference contribution

AN - SCOPUS:85107058541

SN - 978-3-030-66722-1

T3 - Springer Proceedings in Advanced Robotics

SP - 107

EP - 123

BT - Algorithmic Foundations of Robotics XIV

A2 - LaValle, Steven M.

A2 - Lin, Ming

A2 - Ojala, Timo

A2 - Shell, Dylan

A2 - Yu, Jingjin

PB - Springer

ER -

Afshani P, de Berg M, Buchin K, Gao J, Löffler 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: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics. Springer. 2021. p. 107-123. (Springer Proceedings in Advanced Robotics). doi: 10.1007/978-3-030-66723-8_7

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

Abstract

Publication series

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this