OASIcs.ATMOS.2021.14.pdf
- Filesize: 0.59 MB
- 14 pages
Document
Distance-Based Solution of Patrolling Problems with Individual Waiting Times
Author
Peter Damaschke 
-
Part of:
Volume:
21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-09-27
File
Document Identifiers
Author Details
Acknowledgements
The author would like to thank the master’s students Anton Gustafsson and Iman Radjavi for providing experimental results and for critical discussion of an earlier draft.
Cite As Get BibTex
Peter Damaschke. Distance-Based Solution of Patrolling Problems with Individual Waiting Times. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/OASIcs.ATMOS.2021.14
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.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph theory
Keywords
- Patrolling
- Periodic scheduling
- Shortest path
- Well-quasi ordering
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Huda Chuangpishit, Jurek Czyzowicz, Leszek Gasieniec, Konstantinos Georgiou, Tomasz Jurdzinski, and Evangelos Kranakis. Patrolling a path connecting a set of points with unbalanced frequencies of visits. In A Min Tjoa, Ladjel Bellatreche, Stefan Biffl, Jan van Leeuwen, and Jirí Wiedermann, editors, SOFSEM 2018: Theory and Practice of Computer Science - 44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, January 29 - February 2, 2018, Proceedings, volume 10706 of Lecture Notes in Computer Science, pages 367-380. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-73117-9_26.
- Sofie Coene, Frits C. R. Spieksma, and Gerhard J. Woeginger. Charlemagne’s challenge: The periodic latency problem. Oper. Res., 59(3):674-683, 2011. URL: https://doi.org/10.1287/opre.1110.0919.
- Jurek Czyzowicz, Kostantinos Georgiou, and Evangelos Kranakis. Patrolling. In Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors, Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science, pages 371-400. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-11072-7_15.
- Jurek Czyzowicz, Adrian Kosowski, Evangelos Kranakis, and Najmeh Taleb. Patrolling trees with mobile robots. In Frédéric Cuppens, Lingyu Wang, Nora Cuppens-Boulahia, Nadia Tawbi, and Joaquín García-Alfaro, editors, Foundations and Practice of Security - 9th International Symposium, FPS 2016, Québec City, QC, Canada, October 24-25, 2016, Revised Selected Papers, volume 10128 of Lecture Notes in Computer Science, pages 331-344. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-51966-1_22.
- Peter Damaschke. Two robots patrolling on a line: Integer version and approximability. In Leszek Gasieniec, Ralf Klasing, and Tomasz Radzik, editors, Combinatorial Algorithms - 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8-10, 2020, Proceedings, volume 12126 of Lecture Notes in Computer Science, pages 211-223. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-48966-3_16.
- Peter C. Fishburn and J. C. Lagarias. Pinwheel scheduling: Achievable densities. Algorithmica, 34(1):14-38, 2002. URL: https://doi.org/10.1007/s00453-002-0938-9.
- Leszek Gasieniec, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas, Jie Min, and Tomasz Radzik. Bamboo garden trimming problem (perpetual maintenance of machines with different attendance urgency factors). In Bernhard Steffen, Christel Baier, Mark van den Brand, Johann Eder, Mike Hinchey, and Tiziana Margaria, editors, SOFSEM 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings, volume 10139 of Lecture Notes in Computer Science, pages 229-240. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-51963-0_18.
- Robert Holte, Louis E. Rosier, Igor Tulchinsky, and Donald A. Varvel. Pinwheel scheduling with two distinct numbers. Theor. Comput. Sci., 100(1):105-135, 1992. URL: https://doi.org/10.1016/0304-3975(92)90365-M.
- Shun-Shii Lin and Kwei-Jay Lin. A pinwheel scheduler for three distinct numbers with a tight schedulability bound. Algorithmica, 19(4):411-426, 1997. URL: https://doi.org/10.1007/PL00009181.