Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

- https://arxiv.org/abs/2005.02530
Other version

- Peyman Afshani
- Mark de Berg, TU Eindhoven, Eindhoven, Netherlands
- Kevin Buchin, TU Eindhoven, Eindhoven, Netherlands
- Jie Gao, Computer Science Department, Stony Brook University, United States
- Maarten Loffler, Utrecht University, Utrecht, Netherlands
- Amir Nayyeri, Oregon State University, United States
- Benjamin Raichel, University of Texas at Dallas, United States
- Rik Sarkar, Edinburgh University, 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 | 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