Recent Trends in Robotic Patrolling

Rubio F, Valero F, Llopis-Albert C. A review of mobile robots: Concepts, methods, theoretical framework, and applications. International Journal of Advanced Robotic Systems. 2019;16(2):1729881419839596. Alatise MB, Hancke GP. A review on challenges of autonomous mobile robot and sensor fusion methods. IEEE Access. 2020;8:39830–46. Rizk Y, Awad M, Tunstel EW. Cooperative heterogeneous multi-robot systems: a survey. ACM Computing Surveys (CSUR). 2019;52(2):1–31. Quattrini Li A. Exploration and mapping with groups of robots: Recent trends. Current Robotics Reports. 2020;1(4):227–37. Queralta JP, Taipalmaa J, Pullinen BC, Sarker VK, Gia TN, Tenhunen H, et al. Collaborative multi-robot search and rescue: Planning, coordination, perception, and active vision. Ieee Access. 2020;8:191617–43. Almeida A, Ramalho G, Santana H, Tedesco P, Menezes T, Corruble V, et al. Recent advances on multi-agent patrolling. In: Brazilian Symposium on Artificial Intelligence. Springer; 2004. p. 474-83. Portugal D, Rocha R. A survey on multi-robot patrolling algorithms. In: Doctoral conference on computing, electrical and industrial systems. Springer; 2011. p. 139-46. Huang L, Zhou M, Hao K, Hou E. A survey of multi-robot regular and adversarial patrolling. IEEE/CAA Journal of Automatica Sinica. 2019;6(4):894–903. Samanta S, Sen G, Ghosh SK. A literature review on police patrolling problems. Annals of Operations Research. 2021;1–44. Kartal B, Godoy J, Karamouzas I, Guy SJ, Stochastic tree search with useful cycles for patrolling problems. In,. IEEE international conference on robotics and automation (ICRA). IEEE. 2015;2015:1289–94. Othmani-Guibourg M, El Fallah-Seghrouchni A, Farges JL, Potop-Butucaru M, Multi-agent patrolling in dynamic environments. In,. IEEE international conference on agents (ICA). IEEE. 2017;2017:72–7. Afshani P, Berg Md, Buchin K, Gao J, Löffler M, Nayyeri A, et al. Approximation algorithms for multi-robot patrol-scheduling with min-max latency. In: International Workshop on the Algorithmic Foundations of Robotics. Springer; 2020. p. 107-23. Hari SKK, Rathinam S, Darbha S, Kalyanam K, Manyam SG, Casbeer D. Optimal UAV route planning for persistent monitoring missions. IEEE Transactions on Robotics. 2020;37(2):550–66. Freda L, Gianni M, Pirri F, Gawel A, Dubé R, Siegwart R, et al. 3D multi-robot patrolling with a two-level coordination strategy. Autonomous Robots. 2019;43(7):1747–79. Drucker N, Ho HM, Ouaknine J, Penn M, Strichman O. Cyclic-routing of unmanned aerial vehicles. Journal of Computer and System Sciences. 2019;103:18–45. Basilico N, Carpin S. Balancing unpredictability and coverage in adversarial patrolling settings. In: International Workshop on the Algorithmic Foundations of Robotics. Springer; 2018. p. 762-77. Alvarenga CD, Basilico N, Carpin S. Time-varying graph patrolling against attackers with locally limited and imperfect observation models. In: 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE; 2019. p. 4869-76. Asghar AB, Smith SL. A patrolling game for adversaries with limited observation time. In: 2018 IEEE Conference on Decision and Control (CDC). IEEE; 2018. p. 3305-10. •Alpern S, Chleboun P, Katsikas S, Lin KY. Adversarial Patrolling in a Uniform. Operations Research. 2022;70(1):129–40. This paper derives key theoretical results for a patrolling game where the concept of deterrence is analyzed. Alpern S, Lidbetter T, Papadaki K. Optimizing periodic patrols against short attacks on the line and other networks. European Journal of Operational Research. 2019;273(3):1065–73. Lau B, Sprunk C, Burgard W. Improved updating of Euclidean distance maps and Voronoi diagrams. In: 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE; 2010. p. 281-6. Kostavelis I, Gasteratos A. Semantic mapping for mobile robotics tasks: A survey. Robotics and Autonomous Systems. 2015;66:86–103. Quattrini Li A, Penumarthi PK, Banfi J, Basilico N, O’Kane JM, Rekleitis I, et al. Multi-robot online sensing strategies for the construction of communication maps. Autonomous Robots. 2020;44(3):299-319. Kolling A, Carpin S. Extracting surveillance graphs from robot maps. In: 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE; 2008. p. 2323-8. Portugal D, Rocha RP. Retrieving topological information for mobile robots provided with grid maps. In: International Conference on Agents and Artificial Intelligence. Springer; 2012. p. 204-17. Basilico N, Gatti N. Automated abstractions for patrolling security games. In: Twenty-Fifth AAAI Conference on Artificial Intelligence; 2011. Lee SK, Fekete SP, McLurkin J. Structured triangulation in multi-robot systems: Coverage, patrolling, Voronoi partitions, and geodesic centers. The International Journal of Robotics Research. 2016;35(10):1234–60. Liu B, Xiao X, Stone P. Team orienteering coverage planning with uncertain reward. In: 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE; 2021. p. 9728-33. Welikala S, Cassandras CG. Event-driven receding horizon control for distributed persistent monitoring in network systems. Automatica. 2021;127: 109519. Asghar AB, Smith SL, Sundaram S, Multi-robot routing for persistent monitoring with latency constraints. In,. American Control Conference (ACC). IEEE. 2019;2019:2620–5. Collins J, Chand S, Vanderkop A, Howard D. A review of physics simulators for robotic applications. IEEE Access. 2021. Scherer J, Rinner B. Multi-robot persistent surveillance with connectivity constraints. IEEE Access. 2020;8:15093–109. Oshrat Y, Agmon N, Kraus S. Adversarial Fence Patrolling: Non-Uniform Policies for Asymmetric Environments. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 34; 2020. p. 10377-84. Zhou X, Wang W, Wang T, Lei Y, Zhong F. Bayesian reinforcement learning for multi-robot decentralized patrolling in uncertain environments. IEEE Transactions on Vehicular Technology. 2019;68(12):11691–703. Caraballo LE, Díaz-Báñez JM, Fabila-Monroy R, Hidalgo-Toscano C. Stochastic strategies for patrolling a terrain with a synchronized multi-robot system. European Journal of Operational Research. 2021. Scherer J, Rinner B. Multi-UAV surveillance with minimum information idleness and latency constraints. IEEE Robotics and Automation Letters. 2020;5(3):4812–9. Alam T, Rahman M, Carrillo P, Bobadilla L, Rapp B, et al. Stochastic multi-robot patrolling with limited visibility. Journal of Intelligent & Robotic Systems. 2020;97(2):411–29. Basilico N, De Nittis G, Gatti N. Adversarial patrolling with spatially uncertain alarm signals. Artificial Intelligence. 2017;246:220–57. Wang YW, Wei YW, Liu XK, Zhou N, Cassandras CG. Optimal persistent monitoring using second-order agents with physical constraints. IEEE Transactions on Automatic Control. 2018;64(8):3239–52. Bondi E, Oh H, Xu H, Fang F, Dilkina B, Tambe M. To signal or not to signal: Exploiting uncertain real-time information in signaling games for security and sustainability. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 34; 2020. p. 1369-77. Farinelli A, Iocchi L, Nardi D. Distributed on-line dynamic task assignment for multi-robot patrolling. Autonomous Robots. 2017;41(6):1321–45. Lin KY. Optimal patrol of a perimeter. Operations Research. 2021. Talmor N, Agmon N. On the Power and Limitations of Deception in Multi-Robot Adversarial Patrolling. In: IJCAI; 2017. p. 430-6. •Lin ES, Agmon N, Kraus S. Multi-robot adversarial patrolling: Handling sequential attacks. Artificial Intelligence. 2019;274:1–25. This paper provides a key advancement in adversarial patrolling by considering an attacker capable of multiple, sequential attacking actions. Yang HT, Tsai SY, Liu KS, Lin S, Gao J. Patrol scheduling against adversaries with varying attack durations. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems; 2019. p. 1179-88. Nguyen TH, Butler A, Xu H. Tackling Imitative Attacker Deception in Repeated Bayesian Stackelberg Security Games. In: ECAI; 2020. p. 187-94. Buermann J, Zhang J. Multi-Robot adversarial patrolling strategies via lattice paths. In: Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence; 2021. p. 4213-9. ••Duan X, Paccagnan D, Bullo F. Stochastic Strategies for Robotic Surveillance as Stackelberg Games. IEEE Transactions on Control of Network Systems. 2021;8(2):769–80. This paper provides a universal upper bound on the performance obtainable in Stackelberg patrolling games. Optimal strategies for linear and star graphs are derived. Machado A, Ramalho G, Zucker JD, Drogoul A. Multi-agent patrolling: An empirical analysis of alternative architectures. In: International workshop on multi-agent systems and agent-based simulation. Springer; 2002. p. 155-70. Chevaleyre Y. Theoretical analysis of the multi-agent patrolling problem. In: Proceedings. IEEE/WIC/ACM International Conference on Intelligent Agent Technology, 2004.(IAT 2004). IEEE; 2004. p. 302-8. Feillet D, Dejax P, Gendreau M. Traveling salesman problems with profits. Transportation science. 2005;39(2):188–205. Agatz N, Bouman P, Schmidt M. Optimization approaches for the traveling salesman problem with drone. Transportation Science. 2018;52(4):965–81. Cheikhrouhou O, Khoufi I. A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy. Computer Science Review. 2021;40: 100369. Song C, Liu L, Feng G, Xu S. Optimal control for multi-agent persistent monitoring. Automatica. 2014;50(6):1663–8. Yu J, Schwager M, Rus D. Correlated orienteering problem and its application to persistent monitoring tasks. IEEE Transactions on Robotics. 2016;32(5):1106–18. Hari SKK, Rathinam S, Darbha S, Kalyanam K, Manyam SG, Casbeer D, The generalized persistent monitoring problem. In,. American Control Conference (ACC). IEEE. 2019;2019:2783–8. Lauri F, Créput JC, Koukam A. The multi-agent patrolling problem theoretical results about cyclic strategies. In: International Conference on Practical Applications of Agents and Multi-Agent Systems. Springer; 2014. p. 171-82. Krause A, Guestrin C. Near-optimal observation selection using submodular functions. In: AAAI. vol. 7; 2007. p. 1650-4. Rezazadeh N, Kia SS. A sub-modular receding horizon solution for mobile multi-agent persistent monitoring. Automatica. 2021;127: 109460. Zhou N, Cassandras CG, Yu X, Optimal Andersson SB., Policies Threshold-Based Distributed Control, for Persistent Monitoring on Graphs. In,. American Control Conference (ACC). IEEE. 2019;2019:2030–5. Ho HM, Ouaknine J. The cyclic-routing UAV problem is PSPACE-complete. In: International Conference on Foundations of Software Science and Computation Structures. Springer; 2015. p. 328-42. Elmaliach Y, Agmon N, Kaminka GA. Multi-robot area patrol under frequency constraints. Annals of Mathematics and Artificial Intelligence. 2009;57(3):293–320. Yan C, Zhang T. Multi-robot patrol: A distributed algorithm based on expected idleness. International Journal of Advanced Robotic Systems. 2016;13(6). Rumi SK, Shao W, Salim FD. Realtime predictive patrolling and routing with mobility and emergency calls data. In: Proceedings of the international AAAI conference on web and social media. vol. 14; 2020. p. 964-8. Portugal D, Rocha RP. Cooperative multi-robot patrol with Bayesian learning. Autonomous Robots. 2016;40(5):929–53. Chen J, Baskaran A, Zhang Z, Tokekar P. Multi-Agent Reinforcement Learning for Visibility-based Persistent Monitoring. In: 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE;. p. 2563-70. Velickovic P, Cucurull G, Casanova A, Romero A, Lio P, Bengio Y. Graph attention networks stat. 2017;1050:20. Chu HN, Glad A, Simonin O, Sempé F, Drogoul A, Charpillet F. Swarm approaches for the patrolling problem, information propagation vs. pheromone evaporation. In: 19th IEEE international conference on tools with artificial intelligence (ICTAI 2007). vol. 1. IEEE; 2007. p. 442-9. Azevedo Sampaio P, da Silva Sousa R, Nazário Rocha A. Reducing the range of perception in multi-agent patrolling strategies. Journal of Intelligent & Robotic Systems. 2018;91(2):219–31. Wang T, Dong G, Huang P. Pheromone-Diffusion-based Conscientious Reactive Path Planning for Road Network Persistent Surveillance. In: 2021 IEEE International Conference on Robotics and Automation (ICRA). IEEE; 2021. p. 7922-8. Wang T, Huang P, Dong G. Modeling and path planning for persistent surveillance by unmanned ground vehicle. IEEE Transactions on Automation Science and Engineering. 2020;18(4):1615–25. Scherer J, Rinner B. Multi-robot patrolling with sensing idleness and data delay objectives. Journal of Intelligent & Robotic Systems. 2020;99(3):949–67. Khateri K, Pourgholi M, Montazeri M, Sabattini L. A comparison between decentralized local and global methods for connectivity maintenance of multi-robot networks. IEEE Robotics and Automation Letters. 2019;4(2):633–40. Hosseinalipour S, Rahmati A, Dai H, et al. Energy-aware stochastic UAV-assisted surveillance. IEEE Transactions on Wireless Communications. 2020;20(5):2820–37. Duan X, Bullo F. Markov Chain-Based Stochastic Strategies for Robotic Surveillance. Annual Review of Control, Robotics, and Autonomous Systems. 2021;4:243–64. Sinha A, Fang F, An B, Kiekintveld C, Tambe M. Stackelberg security games: Looking beyond a decade of success. IJCAI; 2018 Basilico N, Gatti N, Amigoni F. Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder. Artificial intelligence. 2012;184:78–123. Clempner JB. A continuous-time Markov Stackelberg security game approach for reasoning about real patrol strategies. International Journal of Control. 2018;91(11):2494–510. Karwowski J, Mańdziuk J. A Monte Carlo Tree Search approach to finding efficient patrolling schemes on graphs. European Journal of Operational Research. 2019;277(1):255–68. Perrault A, Wilder B, Ewing E, Mate A, Dilkina B, Tambe M. End-to-end game-focused learning of adversary behavior in security games. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 34; 2020. p. 1378-86. Alcantara-Jiménez G, Clempner JB. Repeated Stackelberg security games: Learning with incomplete state information. Reliability Engineering & System Safety. 2020;195: 106695. Alpern S, Morton A, Papadaki K. Patrolling games. Operations research. 2011;59(5):1246–57. Garrec T. Continuous patrolling and hiding games. European Journal of Operational Research. 2019;277(1):42–51. Klaška D, Kučera A, Lamser T, Řehák V. Automatic synthesis of efficient regular strategies in adversarial patrolling games. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems; 2018. p. 659-66. Klaška D, Kučera A, Musil V, Řehák V. Regstar: efficient strategy synthesis for adversarial patrolling games. In: Uncertainty in Artificial Intelligence. PMLR; 2021. p. 471-81. Portugal D, Iocchi L, Farinelli A. A ROS-based framework for simulation and benchmarking of multi-robot patrolling algorithms. In: Robot Operating System (ROS); 2019. p. 3-28. Portugal D, Rocha RP. Performance estimation and dimensioning of team size for multirobot patrol. IEEE Intelligent Systems. 2017;32(6):30–8. Huang L, Zhou M, Hao K. Non-dominated immune-endocrine short feedback algorithm for multi-robot maritime patrolling. IEEE Transactions on Intelligent Transportation Systems. 2019;21(1):362–73. Kunze L, Hawes N, Duckett T, Hanheide M, Krajník T. Artificial intelligence for long-term robot autonomy: A survey. IEEE Robotics and Automation Letters. 2018;3(4):4023–30. Portugal D, Araújo A, Couceiro MSA, reliable localization architecture for mobile surveillance robots. In,. IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR). IEEE. 2020;2020:374–9. Chen T, Liu X, Xia B, Wang W, Lai Y. Unsupervised anomaly detection of industrial robots using sliding-window convolutional variational autoencoder. IEEE Access. 2020;8:47072–81. Wardega K, Tron R, Li W, Resilience of multi-robot systems to physical masquerade attacks. In,. IEEE Security and Privacy Workshops (SPW). IEEE. 2019;2019:120–5. Santana H, Ramalho G, Corruble V, Ratitch B. Multi-agent patrolling with reinforcement learning. In: Autonomous Agents and Multiagent Systems, International Joint Conference on. vol. 4. IEEE Computer Society; 2004. p. 1122-9. Theile M, Bayerlein H, Nai R, Gesbert D, Caccamo M. UAV coverage path planning under varying power constraints using deep reinforcement learning. In: 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE; 2020. p. 1444-9. Luis SY, Reina DG, Marín SLT. A deep reinforcement learning approach for the patrolling problem of water resources through autonomous surface vehicles: The ypacarai lake case. IEEE Access. 2020;8:204076–93. Huang Y, Zhu Q. Deceptive reinforcement learning under adversarial manipulations on cost signals. In: International Conference on Decision and Game Theory for Security. Springer; 2019. p. 217-37.