## 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 sales man problem as a special case (when*k*= 1and all sites have the same weight). We present a polynomial-time algorithm with an approximation factor of*O*(*k*^{2}*log*^{ }*w*) to the optimalsolution, where_{max}/w_{min}*w*and_{max}*w*are the maximum and minimum weigh tof 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,_{min}*k*, is a constant.Original language | English |
---|---|

Title of host publication | Algorithmic Foundations of Robotics XIV |

Editors | Steven M. LaValle, Ming Lin, Timo Ojala, Dylan Shell, Jingjin Yu |

Publisher | Springer, Cham |

Pages | 107 - 123 |

Number of pages | 16 |

ISBN (Electronic) | 978-3-030-66723-8 |

ISBN (Print) | 978-3-030-66722-1 |

DOIs | |

Publication status | Published - 9 Feb 2021 |

Event | 14th International Workshop on the Algorithmic Foundations of Robotics - Oulu, Finland Duration: 21 Jun 2020 → 23 Jun 2020 http://robotics.cs.rutgers.edu/wafr2020/ |

### Publication series

Name | Springer Proceedings in Advanced Robotics |
---|---|

Publisher | Springer |

Volume | 17 |

ISSN (Print) | 2511-1256 |

ISSN (Electronic) | 2511-1264 |

### Workshop

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

Abbreviated title | WAFR 2020 |

Country/Territory | Finland |

City | Oulu |

Period | 21/06/20 → 23/06/20 |

Internet address |