A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 6 Issue 4
Jul.  2019

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2019  >  6(4): 894-903
Li Huang, MengChu Zhou, Kuangrong Hao and Edwin Hou, "A Survey of Multi-robot Regular and Adversarial Patrolling," IEEE/CAA J. Autom. Sinica, vol. 6, no. 4, pp. 894-903, July 2019. doi: 10.1109/JAS.2019.1911537
Citation: Li Huang, MengChu Zhou, Kuangrong Hao and Edwin Hou, "A Survey of Multi-robot Regular and Adversarial Patrolling," IEEE/CAA J. Autom. Sinica, vol. 6, no. 4, pp. 894-903, July 2019. doi: 10.1109/JAS.2019.1911537
shu

A Survey of Multi-robot Regular and Adversarial Patrolling

doi: 10.1109/JAS.2019.1911537
Funds:  This work was supported in part by the International Collaborative Project of the Shanghai Committee of Science and Technology (16510711100), National Natural Science Foundation of China (61603090, 61806051), the Fundamental Research Funds for the Central Universities (2232017D-08, 2232017D-13), Shanghai Sailing Program (17YF1426100) and by FDCT (Fundo para o Desenvolvimento das Ciencias e da Tecnologia) (119/2014/A3)
More Information
    Abstract
  • Multi-robot systems can be applied to patrol a concerned environment for security purposes. According to different goals, this work reviews the existing researches in a multi-robot patrolling field from the perspectives of regular and adversarial patrolling. Regular patrolling requires robots to visit important locations as frequently as possible and a series of deterministic strategies are proposed, while adversarial one focuses on unpredictable robots’ moving patterns to maximize adversary detection probability. Under each category, a systematic survey is done including problem statements and modeling, patrolling objectives and evaluation criteria, and representative patrolling strategies and approaches. Existing problems and open questions are presented accordingly.

     

    • FullText(HTML)
  • loading
    • References(76)
  • [1]
    Z. Yan, N. Jouandeau, and A. A. Cherif, " A survey and analysis of multi-robot coordination,” International Journal of Advanced Robotic Systems, vol. 10, no. 12, pp. 1–18, 2013.
    [2]
    M. Jakob, O. Vanek, and M. Pechoucek, " Using agents to improve international maritime transport security,” IEEE Intelligent Systems, vol. 26, no. 1, pp. 90–96, 2011. doi: 10.1109/MIS.2011.23
    [3]
    H. Chen, T. Cheng, and S. Wise, " Developing an online cooperative police patrol routing strategy,” Computers,Environment and Urban Systems, vol. 62, pp. 19–29, 2017. doi: 10.1016/j.compenvurbsys.2016.10.013
    [4]
    National Plan for Maritime Safety and Rescue 2010/2018. [Online]. Available: http://www.salvamentomaritimo.es.
    [5]
    F. M. Delle Fave, A. Rogers, Z. Xu, S. Sukkarieh, and N. R. Jennings, " Deploying the max-sum algorithm for decentralised coordination and task allocation of unmanned aerial vehicles for live aerial imagery collection,” in Proceedings of the IEEE International Conference on Robotics and Automation, Saint Paul, MN, pp. 469–476, 2012.
    [6]
    P. Fitzpatrick, " Unmanned aircraft hurricane reconnaissance,” in Proceedings of the 25th Gulf of Mexico Information Transfer Meeting, New Orleans, pp. 47–48, 2009.
    [7]
    I. Maza, F. Caballero, J. Capitán, J. R. Martínez-de-Dios and A. Ollero, " Experimental results in multi-UAV coordination for disaster management and civil security applications,” Journal of Intelligent and Robotic Systems, vol. 61, no. 1–4, pp. 563–585, 2011. doi: 10.1007/s10846-010-9497-5
    [8]
    F. R. Abate, The Oxford Dictionary and Thesaurus: The Ultimate Language Reference for American Readers, Oxford University Press, 1996.
    [9]
    A. Machado, A. Alemeida, G. Ramalho, J. D. Zucker, and A. Drogoul, " Multi-agent movement coordination in patrolling,” in Proceedings of the 3rd International Conference on Computers and Games, Edmonton, Canada, 2002.
    [10]
    A. Almeida, G. Ramalho, H. Santana, P. Tedesco, T. Menezes, V. Corruble, and Y. Chevaleyr, " Recent advances on multi-agent patrolling,” Advances in Artificial Intelligence - SBIA, vol. 3171, pp. 474–483, 2004.
    [11]
    D. Portugal and R. Rocha, " A survey on multi-robot patrolling algorithms,” Technological Innovation for Sustainability, vol. 349, pp. 139–146, 2011. doi: 10.1007/978-3-642-19170-1
    [12]
    A. Machado, G. Ramalho, J. D. Zucker, and A. Drogoul, " Multi-agent patrolling: an empirical analysis of alternative architectures,” Multi-Agent-Based Simulation II, vol. 2581, pp. 155–170, 2003. doi: 10.1007/3-540-36483-8
    [13]
    Y. Chevaleyre, " Theoretical analysis of the multi-agent patrolling problem,” in Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology, Beijing, China, pp. 302–308, 2004.
    [14]
    H. Santana, G. Ramalho, V. Corruble, and B. Ratitch, " Multi-agent patrolling with reinforcement learning,” in Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems, New York, NY, pp. 1122–1129, 2004.
    [15]
    F. Pasqualetti, J. W. Durham, and F. Bullo, " Cooperative patrolling via weighted tours: performance analysis and distributed algorithms,” IEEE Transactions on Robotics, vol. 28, no. 5, pp. 1181–1188, 2012. doi: 10.1109/TRO.2012.2201293
    [16]
    F. Pasqualetti, A. Franchi and F. Bullo, " On cooperative patrolling: optimal trajectories, complexity analysis, and approximation algorithms,” IEEE Transactions on Robotics, vol. 28, no. 3, pp. 592–606, 2012. doi: 10.1109/TRO.2011.2179580
    [17]
    C. Pippin, H. Christensen, and L. Weiss, " Performance based task assignment in multi-robot patrolling,” in Proceedings of the 28th Annual ACM Symposium on Applied Computing, Coimbra, Portugal, pp. 70–76, 2013.
    [18]
    C. Yan and T. Zhang, " Multi-robot patrol A distributed algorithm based on expected idleness,” International Journal of Advanced Robotic Systems, vol. 13, no. 6, pp. 1–12, 2016.
    [19]
    V. Sea, A. Sugiyama, and T. Sugawara, " Frequency-based multi-agent patrolling model and its area partitioning solution method for balanced workload,” in Proceedings of the International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 530–545, 2018.
    [20]
    A. Farinelli, L. Locchi, and D. Nardi, " Distributed on-line dynamic task assignment for multi-robot patrolling,” Autonomous Robots, vol. 41, no. 6, pp. 1321–1345, 2017. doi: 10.1007/s10514-016-9579-8
    [21]
    F. Lauri and A. Koukam, " A two-step evolutionary and ACO approach for solving the multi-agent patrolling problem,” in Proceedings of the IEEE Congress on Evolutionary Computation, Hong Kong, China, pp. 861–868, 2008.
    [22]
    X. Chen, " Fast patrol route planning in dynamic environments,” IEEE Transactions on Systems,Man,and Cybernetics-Part A:Systems and Humans, vol. 42, no. 4, pp. 894–904, 2012. doi: 10.1109/TSMCA.2012.2183361
    [23]
    M. Othmani-Guibourg, A. E. Fallah-Seghrouchni, J. Farges, and M. Potop-Butucaru, " Multi-agent patrolling in dynamic environments,” in Proceedings of the IEEE International Conference on Agents, Beijing, China, pp. 72–77, 2017.
    [24]
    L. Iocchi, L. Marchetti, and D. Nardi, " Multi-robot patrolling with coordinated behaviours in realistic environments,” in Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, San Francisco, CA, pp. 2796–2801, 2011.
    [25]
    M. Othmani-Guibourg, A. El Fallah-Seghrouchni and J. Farges, " Path Generation with LSTM Recurrent Neural Networks in the Context of the Multi-Agent Patrolling,” in Proceedings of the 30th IEEE International Conference on Tools with Artificial Intelligence, Volos, pp. 430–437, 2018.
    [26]
    M. Othmani-Guibourg, A. El Fallah-Seghrouchni, and J. Farges, " LSTM Path-Maker: a new LSTM-based strategy for the multi-agent patrolling,” in Proceedings of the 52nd Hawaii International Conference on System Sciences, pp. 616-625, 2019.
    [27]
    D. Portugal and R. Rocha, " MSP algorithm: multi-robot patrolling based on territory allocation using balanced graph partitioning,” in Proceedings of the 2010 ACM Symposium on Applied Computing, Sierre, Switzerland, pp. 1271–1276, 2010.
    [28]
    D. Portugal and R. P. Rocha, " Distributed multi-robot patrol: A scalable and fault-tolerant framework,” Robotics and Autonomous Systems, vol. 61, no. 12, pp. 1572–1587, 2013. doi: 10.1016/j.robot.2013.06.011
    [29]
    D. Portugal, C. Pippin, R. P. Rocha and H. Christensen, " Finding optimal routes for multi-robot patrolling in generic graphs,” in Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, Chicago, IL, pp. 363–369, 2014.
    [30]
    D. Portugal and R. P. Rocha, " Cooperative multi-robot patrol with bayesian learning,” Autonomous Robots, vol. 40, no. 5, pp. 929–953, 2016. doi: 10.1007/s10514-015-9503-7
    [31]
    T. Y. Zhang and C. Y. Suen, " A fast parallel algorithm for thinning digital patterns,” Communications of the ACM, vol. 27, no. 3, pp. 236–239, 1984. doi: 10.1145/357994.358023
    [32]
    P. Beeson, N. K. Jong and B. Kuipers, " Towards autonomous topological place detection using the extended voronoi graph,” in Proceedings of the 2005 IEEE International Conference on Robotics and Automation, Barcelona, Spain, pp. 4373–4379, 2005.
    [33]
    D. Portugal and R. P. Rocha, " Extracting topological information from grid maps for robot navigation,” in Proceedings of International Conference on Agents and Artificial Intelligence, Vilamoura, Algarve, Portugal, pp. 137–143, 2012.
    [34]
    Y. Elmaliach, N. Agmon, and G. A. Kaminka, " Multi-Robot Area Patrol under Frequency Constraints,” in Proceedings of the IEEE International Conference on Robotics and Automation, Roma, pp. 385–390, 2007.
    [35]
    H. N. Chu, A. Glad, O. Simonin, F. Sempe, A. Drogoul, and F. Charpillet, " Swarm approaches for the patrolling problem, information propagation vs. pheromone evaporation,” in Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence, Patras, pp. 442–449, 2007.
    [36]
    A. Glad, O. Buffet, O. Simonin, and F. Charpillet, " Self-Organization of Patrolling-Ant Algorithms,” 3rd IEEE International Conference on Self-Adaptive and Self-Organizing Systems, San Francisco, CA, pp. 61–70, 2009.
    [37]
    A. Glad, O. Simonin, O. Buffet and F. Charpillet, " Theoretical study of ant-based algorithms for multi-agent patrolling,” in Proceedings of the 18th European Conference on Artificial Intelligence, Patras, Greece, pp. 626–630, 2008.
    [38]
    V. Yanovski, I. A. Wagner, A. M. Bruckstein, " A distributed ant algorithm for efficiently patrolling a network,” Algorithmica, vol. 73, no. 3, pp. 165–186, 2003.
    [39]
    Y. Elmaliach, A. Shiloni, and G. A. Kaminka, " A realistic model of frequency-based multi-robot polyline patrolling,” 7th International Joint Conference on Autonomous Agents and Multiagent Systems, Estoril, Portugal, vol. 1, pp. 63–70, 2008.
    [40]
    E. Jensen, M. Franklin, S. Lahr and M. Gini, " Sustainable multi-robot patrol of an open polyline,” in Proceedings of the 2011 Proceedings of the IEEE International Conference on Robotics and Automation, Shanghai, pp. 4792–4797, 2011.
    [41]
    S. Doi, " Proposal and evaluation of a pheromone-based algorithm for the patrolling problem in dynamic environments,” in Proceedings of the IEEE Symposium on Swarm Intelligence, Singapore, pp. 48–55, 2013.
    [42]
    S. Chen, F. Wu, L. Shen, J. Chen, and S. D. Ramchurn, " Decentralized patrolling under constraints in dynamic environments,” IEEE Transactions on Cybernetics, vol. 46, no. 12, pp. 3364–3376, 2016. doi: 10.1109/TCYB.2015.2505737
    [43]
    C. Pippin, H. I. Christensen, and L. Weiss, " Dynamic, cooperative multi-robot patrolling with a team of UAVs,” in Proceedings of the Society of Photo-Optical Instrumentation Engineers Conf. Series, 8741, Baltimore, MD, USA, 2013.
    [44]
    N. Agmon, C. Fok, Y. Emaliah, P. Stone, C. Julien, and S. Vishwanath, " On coordination in practical multi-robot patrol,” in Proceedings of the IEEE International Conference on Robotics and Automation, Saint Paul, MN, pp. 650–656, 2012.
    [45]
    D. Portugal and R. P. Rocha, " Multi-robot patrolling algorithms: examining performance and scalability,” Advanced Robotics, vol. 27, no. 5, pp. 325–336, 2013. doi: 10.1080/01691864.2013.763722
    [46]
    D. Portugal and R. P. Rocha, " On the performance and scalability of multi-robot patrolling algorithms,” in Proceedings of the IEEE International Symposium on Safety, Security, and Rescue Robotics, Kyoto, pp. 50–55, 2011.
    [47]
    D. Portugal, M. S. Couceiro, and R. P. Rocha, " Applying Bayesian learning to multi-robot patrol,” in Proceedings of the IEEE International Symposium on Safety, Security, and Rescue Robotics, Linkoping, pp. 1–6, 2013.
    [48]
    B. Wiandt, V. Simon, and A. Kőkuti, " Self-organized graph partitioning approach for multi-agent patrolling in generic graphs,” in Proceedings of the IEEE EUROCON 2017 -17th International Conference on Smart Technologies, Ohrid, pp. 605–610, 2017.
    [49]
    K. Hwang, J. Lin and Hui-Ling Huang, " Cooperative patrol planning of multi-robot systems by a competitive auction system,” in Proceedings of the ICCAS-SICE, Fukuoka, pp. 4359–4363, 2009.
    [50]
    T. Menezes, P. Tedesco and G. Ramalho, " Negotiator Agents for the Patrolling Task,” Advances in Artificial Intelligence - IBERAMIA-SBIA 2006, vol. 4140, pp. 48–57, 2006. doi: 10.1007/11874850
    [51]
    A. L. Almeida, P. M. Castro, T. R. Menezes and G. L. Ramalho, " Combining idleness and distance to design heuristic agents for the patrolling task,” in Proceedings of the Brazilian Workshop in Games and Digital Entertainment, Salvador, pp. 33–40, 2003.
    [52]
    G. Karypis and V. Kumar, " A fast and high quality multilevel scheme for partitioning irregular graphs,” Society for Industrial and Applied Mathematics Journal of Scientific Computing, vol. 20, no. 1, pp. 359–392, 1998.
    [53]
    J. Li, M. C. Zhou, Q. Sun, X. Dai, and X. Yu, " Colored traveling salesman problem,” IEEE Transactions on Cybernetics, vol. 45, no. 11, pp. 2390–2401, 2015. doi: 10.1109/TCYB.2014.2371918
    [54]
    X. Meng, J. Li, M. C. Zhou, X. Dai, and J. Dou, " Population-Based Incremental Learning Algorithm for a Serial Colored Traveling Salesman Problem,” IEEE Transactions on Systems,Man,and Cybernetics:Systems, vol. 48, no. 2, pp. 277–288, 2018. doi: 10.1109/TSMC.2016.2591267
    [55]
    Z. Yan, J. He and J. Li, " An improved multi-AUV patrol path planning method,” in Proceedings of the IEEE International Conference on Mechatronics and Automation (ICMA), Takamatsu, pp. 1930–1936, 2017.
    [56]
    L. Huang, M. Zhou and K. Hao, " Non-dominated immune-endocrine short feedback algorithm for multi-robot maritime patrolling,” IEEE Transactions on Intelligent Transportation Systems, pp. 1–12, 2019.
    [57]
    J. Henrio, T. Deligne, T. Nakashima, and T. Watanabe, " Route planning for multiple surveillance autonomous drones using a discrete firefly algorithm and a Bayesian optimization method,” Artificial Life and Robotics, vol. 24, no. 1, pp. 100–105, 2019. doi: 10.1007/s10015-018-0454-x
    [58]
    T. Sak, J. Wainer, and S. K. Goldenstein, " Probabilistic multiagent patrolling,” Advances in Artificial Intelligence - SBIA 2008, vol. 5249, pp. 124–133, 2008. doi: 10.1007/978-3-540-88190-2
    [59]
    T. Alam, M. Edwards, L. Bobadilla and D. Shell, " Distributed multi-robot area patrolling in adversarial environments,” in Proceedings of the International Workshop on Robotic Sensor Networks, Seattle, WA, 2015.
    [60]
    E. Hernández, J. del Cerro and A. Barrientos, " Game theory models for multi-robot patrolling of infrastructures,” International Journal of Advanced Robotic Systems, vol. 10, no. 3, pp. 1–9, 2013.
    [61]
    E. Hernández, A. Barrientos, and J. del Cerro, " Selective smooth fictitious play: an approach based on game theory for patrolling infrastructures with a multi-robot system,” Expert Systems with Applications, vol. 41, no. 6, pp. 2897–2913, 2014. doi: 10.1016/j.eswa.2013.10.024
    [62]
    T. Alam, M. M. Rahman, L. Bobadilla, and B. Rapp, " Multi-vehicle patrolling with limited visibility and communication constraints,” in Proceedings of the IEEE Military Communications Conference (MILCOM), Baltimore, MD, pp. 465–470, 2017.
    [63]
    M. Ivanová, P. Surynek and K. Hirayama, " Area protection in adversarial path-finding scenarios with multiple mobile agents on graphs,” in Proceedings of the 10th International Conference on Agents and Artificial Intelligence, vol. 1, pp. 184–191, 2018.
    [64]
    E. Sless, N. Agmon, and S. Kraus, " Multi-robot adversarial patrolling: facing coordinated attacks,” in Proceedings of the International Conference on Autonomous Agents and Multi-agent Systems, Paris, France, pp. 1093–1100, 2014.
    [65]
    N. Agmon, S. Kraus, and G. A. Kaminka, " Multi-robot perimeter patrol in adversarial settings,” in Proceedings of the IEEE International Conference on Robotics and Automation, Pasadena, CA, pp. 2339–2345, 2008.
    [66]
    N. Agmon, " On events in multi-robot patrol in adversarial environments,” in Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, Toronto, Canada, vol. 2, pp. 591–598, 2010.
    [67]
    N. Agmon, G. A. Kaminka, and S. Kraus, " Multi-robot adversarial patrolling: facing a full-knowledge opponent,” Journal of Artificial Intelligence Research, vol. 42, pp. 887–916, 2011.
    [68]
    N. Talmor and N. Agmon, " On the power and limitations of deception in multi-robot adversarial patrolling,” in Proceedings of the 26th International Joint Conference on Artificial Intelligence, Melbourne, Australia, pp. 430–436, 2017.
    [69]
    E. Sless Lin, N. Agmon, and S. Kraus, " Multi-robot adversarial patrolling: Handling sequential attacks,” Artificial Intelligence, vol. 274, pp. 1–25, 2019. doi: 10.1016/j.artint.2019.02.004
    [70]
    P. Paruchuri, J. P. Pearce, J. Marecki, M. Tambe, F. Ordonez and S. Kraus, " Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg Games,” in Proceedings of The 7th International Joint Conference on Autonomous Agents and Multiagent Systems, Estoril, Portugal, pp. 895–902, 2008.
    [71]
    W. Gu, Y. Yu, and W. Hu, " Artificial bee colony algorithm-based parameter estimation of fractional-order chaotic system with time delay,” IEEE/CAA Journal of Automatica Sinica, vol. 4, no. 1, pp. 107–113, 2017. doi: 10.1109/JAS.2017.7510340
    [72]
    J. Zhao, S. X. Liu, M. C. Zhou, X. W. Guo, and L. Qi, " Modified cuckoo search algorithm to solve economic power dispatch optimization problems,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 4, pp. 794–806, 2018. doi: 10.1109/JAS.2018.7511138
    [73]
    W. Han, J. Xu, M. C. Zhou, G. Tian, P. Wang, X. Shen, and S.-H. E. Hou, " Cuckoo search and particle filter-based inversing approach to estimating defects via magnetic flux leakage signals,” IEEE Transactions on Magnetics, vol. 52, no. 4, pp. 1–11, 2016.
    [74]
    L. Peng, F. Guan, L. Perneel, H. Fayyad-Kazan, and M. Timmerman, " Decentralized multi-robot formation control with communication delay and asynchronous clock,” Journal of Intelligent &Robotic Systems, vol. 89, no. 3–4, pp. 465–484, 2018.
    [75]
    X. Ge, Q. Han, and X. Zhang, " Achieving cluster formation of multi-agent systems under aperiodic sampling and communication delays,” IEEE Transactions on Industrial Electronics, vol. 65, no. 4, pp. 3417–3426, 2018. doi: 10.1109/TIE.2017.2752148
    [76]
    E. Garcia, Y. Cao, and D. W. Casbeer, " Periodic event-triggered synchronization of linear multi-agent systems with communication delays,” IEEE Transactions on Automatic Control, vol. 62, no. 1, pp. 366–371, Jan. 2017. doi: 10.1109/TAC.2016.2555484
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Tables(2)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (3477) PDF downloads(211) Cited by()

    Highlights

    • Existing researches in a multi-robot patrolling field are reviewed in this paper.
    • Two categories according to different patrolling goals are summarized.
    • A systematic survey under each category is presented.
    • Existing problems and open questions are discussed.

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return