On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem

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



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.2.pdf
  • Filesize: 0.94 MB
  • 14 pages

Document Identifiers

Author Details

Peyman Afshani
  • Department of Computer Science, Aarhus University, Denmark
Mark de Berg
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands
Kevin Buchin
  • Department of Computer Science, TU Dortmund, Germany
Jie Gao
  • Department of Computer Science, Rutgers University, New Brunswick, NJ, USA
Maarten Löffler
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
Amir Nayyeri
  • School of Electrical Engineering and Computer Science, Oregon State University, Corvallis, OR, USA
Benjamin Raichel
  • Department of Computer Science, University of Texas at Dallas, Richardson, TX, USA
Rik Sarkar
  • School of Informatics, University of Edinburgh, UK
Haotian Wang
  • Department of Computer Science, Rutgers University, New Brunswick, NJ, USA
Hao-Tsung Yang
  • School of Informatics, University of Edinburgh, UK

Cite AsGet BibTex

Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, and Hao-Tsung Yang. On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.2

Abstract

We consider the following surveillance problem: Given a set P of n sites in a metric space and a set R of k robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency L of a schedule is the maximum latency of any site, where the latency of a site s is the supremum of the lengths of the time intervals between consecutive visits to s. When k = 1 the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. For k ≥ 2 (which is the version we are interested in) the problem becomes even more challenging; for example, it is not even clear if the decision version of the problem is decidable, in particular in the Euclidean case. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into 𝓁 groups, for some 𝓁 ≤ k, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a 1+ε factor loss in the approximation factor and an O((k/ε) ^k) factor loss in the runtime, for any ε > 0. Our second main result shows that an optimal cyclic solution is a 2(1-1/k)-approximation of the overall optimal solution. Note that for k = 2 this implies that an optimal cyclic solution is optimal overall. We conjecture that this is true for k ≥ 3 as well. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a (2(1-1/k)+ε)-approximation of the optimal unrestricted (not necessarily cyclic) solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting. Similar results can be obtained by combining our results with other known TSP algorithms in non-Euclidean metrics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Approximation
  • Motion Planning
  • Scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, and Hao-Tsung Yang. Approximation algorithms for multi-robot patrol-scheduling with min-max latency. In Algorithmic Foundations of Robotics XIV, pages 107-123, 2021. Google Scholar
  2. Soroush Alamdari, Elaheh Fata, and Stephen L Smith. Persistent monitoring in discrete environments: Minimizing the maximum weighted latency between observations. The International Journal of Robotics Research, 33(1):138-154, 2014. Google Scholar
  3. Esther M Arkin, Refael Hassin, and Asaf Levin. Approximations for minimum and min-max vehicle routing problems. Journal of Algorithms, 59(1):1-18, 2006. Google Scholar
  4. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM), 45(5):753-782, 1998. Google Scholar
  5. Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon Univ., Pittsburgh, 1976. Google Scholar
  6. George B Dantzig and John H Ramser. The truck dispatching problem. Management science, 6(1):80-91, 1959. Google Scholar
  7. Yehuda Elmaliach, Asaf Shiloni, and Gal A. Kaminka. A realistic model of frequency-based multi-robot polyline patrolling. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 1, AAMAS '08, pages 63-70, Richland, SC, 2008. International Foundation for Autonomous Agents and Multiagent Systems. Google Scholar
  8. Bruce L Golden, Subramanian Raghavan, and Edward A Wasil. The vehicle routing problem: latest advances and new challenges, volume 43. Springer Science & Business Media, 2008. Google Scholar
  9. L. Iocchi, L. Marchetti, and D. Nardi. Multi-robot patrolling with coordinated behaviours in realistic environments. In 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2796-2801, September 2011. URL: https://doi.org/10.1109/IROS.2011.6094844.
  10. Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric TSP. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 32-45, 2021. Google Scholar
  11. M Yu Khachai and ED Neznakhina. A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph. Proceedings of the Steklov Institute of Mathematics, 289(1):111-125, 2015. Google Scholar
  12. Michael Khachay and Katherine Neznakhina. Polynomial time approximation scheme for the minimum-weight k-size cycle cover problem in Euclidean space of an arbitrary fixed dimension. IFAC-PapersOnLine, 49(12):6-10, 2016. Google Scholar
  13. M Reza Khani and Mohammad R Salavatipour. Improved approximation algorithms for the min-max tree cover and bounded tree cover problems. Algorithmica, 69(2):443-460, 2014. Google Scholar
  14. Kin Sum Liu, Tyler Mayer, Hao-Tsung Yang, Esther Arkin, Jie Gao, Mayank Goswami, Matthew P. Johnson, Nirman Kumar, and Shan Lin. Joint sensing duty cycle scheduling for heterogeneous coverage guarantee. In INFOCOM 2017-IEEE Conference on Computer Communications, IEEE, pages 1-9. IEEE, 2017. Google Scholar
  15. Joseph SB Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on computing, 28(4):1298-1309, 1999. Google Scholar
  16. Christos H Papadimitriou. The Euclidean travelling salesman problem is NP-complete. Theoretical computer science, 4(3):237-244, 1977. Google Scholar
  17. D. Portugal and R. P. Rocha. On the performance and scalability of multi-robot patrolling algorithms. In 2011 IEEE International Symposium on Safety, Security, and Rescue Robotics, pages 50-55, November 2011. URL: https://doi.org/10.1109/SSRR.2011.6106761.
  18. E. Stump and N. Michael. Multi-robot persistent surveillance planning as a vehicle routing problem. In Automation Science and Engineering (CASE), 2011 IEEE Conference on, pages 569-575, August 2011. URL: https://doi.org/10.1109/CASE.2011.6042503.
  19. Paolo Toth and Daniele Vigo. The vehicle routing problem. SIAM, 2002. Google Scholar
  20. Wenzheng Xu, Weifa Liang, and Xiaola Lin. Approximation algorithms for min-max cycle cover problems. IEEE Transactions on Computers, 64(3):600-613, 2013. Google Scholar
  21. Hao-Tsung Yang, Shih-Yu Tsai, Kin Sum Liu, Shan Lin, and Jie Gao. Patrol scheduling against adversaries with varying attack durations. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 1179-1188, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail