Abstract
In patrolling problems, robots (or other vehicles) must perpetually visit certain points without exceeding given individual waiting times. Some obvious applications are monitoring, maintenance, and periodic fetching of resources. We propose a new generic formulation of the problem. As its main advantage, it enables a reduction of the multi-robot case to the one-robot case in a certain graph/hypergraph pair, which also relates the problem to some classic path problems in graphs: NP-hardness is shown by a reduction from the Hamiltonian cycle problem, and on the positive side, the formulation allows solution heuristics using distances in the mentioned graph. We demonstrate this approach for the case of two robots patrolling on a line, a problem whose complexity status is open, apart from approximation results. Specifically, we solve all instances with up to 6 equidistant points, and we find some surprising effects, e.g., critical problem instances (which are feasible instances that become infeasible when any waiting time is diminished) may contain rather large individual waiting times.
BibTeX - Entry
@InProceedings{damaschke:OASIcs.ATMOS.2021.14,
author = {Damaschke, Peter},
title = {{Distance-Based Solution of Patrolling Problems with Individual Waiting Times}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {14:1--14:14},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14883},
URN = {urn:nbn:de:0030-drops-148838},
doi = {10.4230/OASIcs.ATMOS.2021.14},
annote = {Keywords: Patrolling, Periodic scheduling, Shortest path, Well-quasi ordering}
}
|
Keywords: |
|
Patrolling, Periodic scheduling, Shortest path, Well-quasi ordering |
|
Collection: |
|
21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
27.09.2021 |
Creative Commons Attribution 4.0 International license (CC BY 4.0)