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 salesman problem as a special case (when \(k=1\) and all sites have the same weight). We present a polynomial-time algorithm with an approximation factor of \(O(k^2 \log \frac{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 time \((n w_{\max }/w_{\min })^{O(k)}\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abrahamsen, M., de Berg, M., Buchin, K., Mehr, M., Mehrabi, A.D.: Range-clustering queries. In: 33rd International Symposium on Computational Geometry (SoCG 2017), pp. 1–16, 14–17 (2017)
Afshani, P., de Berg, M., Buchin, K., Gao, J., Loffler, M., Nayyeri, A., Raichel, B., Sarkar, R., Wang, H., Yang, H.-T.: Approximation algorithms for multi-robot patrol-scheduling with min-max latency 2020. https://arxiv.org/abs/2005.02530
Alamdari, S., Fata, E., Smith, S.L.: Persistent monitoring in discrete environments: minimizing the maximum weighted latency between observations. Int. J. Robot. Res. 33(1), 138–154 (2014)
Arkin, E.M., Hassin, R., Levin, A.: Approximations for minimum and min-max vehicle routing problems. J. Algorithms 59(1), 1–18 (2006)
Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM (JACM) 45(5), 753–782 (1998)
Asghar, A.B., Smith, S.L., Sundaram, S.: Multi-robot routing for persistent monitoring with latency constraints. In: 2019 American Control Conference (ACC), pp. 2620–2625 (2019)
Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 80–86 (1983)
Chevaleyre, Y.: Theoretical analysis of the multi-agent patrolling problem. In: IEEE/WIC/ACM International Conference on Intelligent Agent Technology, pp. 302–308 (2004)
Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report, Carnegie-Mellon University (1976)
Czyzowicz, J., Gąsieniec, L., Kosowski, A., Kranakis, E.: Boundary patrolling by mobile agents with distinct maximal speeds. In: European Symposium on Algorithms, pp. 701–712 (2011)
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6(1), 80–91 (1959)
Drucker, N., Penn, M., Strichman, O.: Cyclic routing of unmanned aerial vehicles. In: International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pp. 125–141 (2016)
Dumitrescu, A., Ghosh, A., Tóth, C.D.: On fence patrolling by mobile agents. Electron. J. Comb. 21(3), 3–4 (2014)
Elmaliach, Y., Agmon, N., Kaminka, G.A.: Multi-robot area patrol under frequency constraints. Ann. Math. Artif. Intell. 57(3–4), 293–320 (2009)
Elmaliach, Y., Shiloni, A., Kaminka, G.A.: A realistic model of frequency-based multi-robot polyline patrolling. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 63–70 (2008)
Gąsieniec, L., Klasing, R., Levcopoulos, C., Lingas, A., Min, J., Radzik, T.: Bamboo garden trimming problem (perpetual maintenance of machines with different attendance urgency factors). In: SOFSEM 2017: Theory and Practice of Computer Science, pp. 229–240 (2017)
Golden, B.L., Raghavan, S., Wasil, E.A.: The Vehicle Routing Problem: Latest Advances and New Challenges. Springer Science & Business Media, New York (2008)
Iocchi, L., Marchetti, L., Nardi, D.: Multi-robot patrolling with coordinated behaviours in realistic environments. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2796–2801, September 2011
Kawamura, A., Soejima, M.: Simple strategies versus optimal schedules in multi-agent patrolling. In: International Conference on Algorithms and Complexity, pp. 261–273 (2015)
Khachai, M.Y., Neznakhina, E.: A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph. Proc. Steklov Inst. Math. 289(1), 111–125 (2015)
Khachay, M., Neznakhina, K.: Polynomial time approximation scheme for the minimum-weight \(k\)-size cycle cover problem in Euclidean space of an arbitrary fixed dimension. IFAC-Papers OnLine 49(12), 6–10 (2016)
Khani, M.R., Salavatipour, M.R.: Improved approximation algorithms for the min-max tree cover and bounded tree cover problems. Algorithmica 69(2), 443–460 (2014)
Liu, K.S., Mayer, T., Yang, H.T., Arkin, E., Gao, J., Goswami, M., Johnson, M.P., Kumar, N., Lin, S.: Joint sensing duty cycle scheduling for heterogeneous coverage guarantee. INFOCOM 2017, 1–9 (2017)
Mitchell, J.S.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, \(k\)-mst, and related problems. SIAM J. Comput. 28(4), 1298–1309 (1999)
Papadimitriou, C.H.: The Euclidean travelling salesman problem is NP-complete. Theoretical Comput. Sci. 4(3), 237–244 (1977)
Portugal, D., Pippin, C., Rocha, R.P., Christensen, H.: Finding optimal routes for multi-robot patrolling in generic graphs. In: 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 363–369 (2014)
Portugal, D., Rocha, R.P.: On the performance and scalability of multi-robot patrolling algorithms. In: 2011 IEEE International Symposium on Safety, Security, and Rescue Robotics, pp. 50–55, November 2011
Stump, E., Michael, N.: Multi-robot persistent surveillance planning as a vehicle routing problem. In: 2011 IEEE Conference on Automation Science and Engineering (CASE), pp. 569–575, August 2011
Toth, P., Vigo, D.: The vehicle routing problem. SIAM (2002)
Xu, W., Liang, W., Lin, X.: Approximation algorithms for min-max cycle cover problems. IEEE Trans. Comput. 64(3), 600–613 (2013)
Yang, H.-T., Tsai, S.-Y., Liu, K.S., Lin, S., Gao J.: Patrol scheduling against adversaries with varying attack durations. In: Proceedings of the 18th International Conference on Autonomous Agents and Multi-Agent Systems, pp. 1179–1188 (2019)
Acknowledgement
Gao, Wang and Yang would like to acknowledge supports from NSF CNS-1618391, DMS-1737812, OAC-1939459. Raichel would like acknowledge support from NSF CAREER Award 1750780.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Afshani, P. et al. (2021). Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. In: LaValle, S.M., Lin, M., Ojala, T., Shell, D., Yu, J. (eds) Algorithmic Foundations of Robotics XIV. WAFR 2020. Springer Proceedings in Advanced Robotics, vol 17. Springer, Cham. https://doi.org/10.1007/978-3-030-66723-8_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-66723-8_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-66722-1
Online ISBN: 978-3-030-66723-8
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)