Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 15

Proceedings of the 2018 Federated Conference on Computer Science and Information Systems

Autonomous Graph Partitioning for Multi-Agent Patrolling Problems

,

DOI: http://dx.doi.org/10.15439/2018F213

Citation: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, pages 261–268 ()

Full text

Abstract. Patrolling algorithms are coordinating multiple agents with the goal of visiting points of interest in a timely manner. These algorithms play a major role in efficient use of UAVs or other autonomous vehicles for precision agriculture, large area monitoring or security use cases. These algorithms are either centralized and in need of constant connection with the agents or solve NP-hard problems to plan the routes of individual agents on the graph. These requirements become unfeasible when the number of agents or points of interest grow or become dynamic. In this article we further elaborate the performance characteristics of the Partition Based Patrolling algorithm. The partitioning requires only local interactions between agents, therefore it is scalable to a large number of nodes and agents. On these subgraphs agents patrol independently from each other, therefore the approach eliminates interference between agents.

References

  1. Gonçalo Cabrita, Pedro Sousa, Lino Marques, and A de Almeida. Infrastructure monitoring with multi-robot teams. In Proceedings of the 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS, pages 18–22, 2010.
  2. David Portugal and Rui P Rocha. Cooperative multi-robot patrol in an indoor infrastructure. In Human Behavior Understanding in Networked Sensing, pages 339–358. Springer, 2014.
  3. Yann Chevaleyre. Theoretical analysis of the multi-agent patrolling problem. In Intelligent Agent Technology, 2004.(IAT 2004). Proceedings. IEEE/WIC/ACM International Conference on, pages 302–308. IEEE, 2004.
  4. Talita Menezes, Patrícia Tedesco, and Geber Ramalho. Negotiator agents for the patrolling task. In Advances in Artificial Intelligence-IBERAMIA-SBIA 2006, pages 48–57. Springer, 2006.
  5. David Portugal and Rui Rocha. Msp algorithm: multi-robot patrolling based on territory allocation using balanced graph partitioning. In Proceedings of the 2010 ACM Symposium on Applied Computing, pages 1271–1276. ACM, 2010.
  6. Jean-Samuel Marier, Camille Besse, and Brahim Chaib-Draa. Solving the continuous time multiagent patrol problem. In ICRA, pages 941–946. Citeseer, 2010.
  7. Alessandro Almeida, Geber Ramalho, Hugo Santana, Patrícia Tedesco, Talita Menezes, Vincent Corruble, and Yann Chevaleyre. Recent advances on multi-agent patrolling. In Advances in Artificial Intelligence–SBIA 2004, pages 474–483. Springer, 2004.
  8. David Portugal and Rui P Rocha. Distributed multi-robot patrol: A scalable and fault-tolerant framework. Robotics and Autonomous Systems, 61(12):1572–1587, 2013.
  9. Pooyan Fazli, Alireza Davoodi, and Alan K Mackworth. Multi-robot repeated area coverage. Autonomous robots, 34(4):251–276, 2013.
  10. Yoav Gabriely and Elon Rimon. Spanning-tree based coverage of continuous areas by a mobile robot. Annals of mathematics and artificial intelligence, 31(1-4):77–98, 2001.
  11. Tiago Sak, Jacques Wainer, and Siome Klein Goldenstein. Probabilistic multiagent patrolling. In Brazilian Symposium on Artificial Intelligence, pages 124–133. Springer, 2008.
  12. Ruben Stranders, E Munoz De Cote, Alex Rogers, and Nicholas R Jennings. Near-optimal continuous patrolling with teams of mobile information gathering agents. Artificial intelligence, 195:63–105, 2013.
  13. François Sempé and Alexis Drogoul. Adaptive patrol for a group of robots. In Intelligent Robots and Systems, 2003.(IROS 2003). Proceedings. 2003 IEEE/RSJ International Conference on, volume 3, pages 2865–2869. IEEE, 2003.
  14. Oswaldo Aguirre and Heidi Taboada. An evolutionary game theory approach for intelligent patrolling. Procedia computer science, 12:140–145, 2012.
  15. Burcu B Keskin, Shirley Rong Li, Dana Steil, and Sarah Spiller. Analysis of an integrated maximum covering and patrol routing problem. Transportation Research Part E: Logistics and Transportation Review, 48(1):215–232, 2012.
  16. Charles Pippin, Henrik Christensen, and Lora Weiss. Performance based task assignment in multi-robot patrolling. In Proceedings of the 28th annual ACM symposium on applied computing, pages 70–76. ACM, 2013.
  17. Cyril Poulet, Vincent Corruble, and Amal El Fallah Seghrouchni. Working as a team: using social criteria in the timed patrolling problem. In Tools with Artificial Intelligence (ICTAI), 2012 IEEE 24th International Conference on, volume 1, pages 933–938. IEEE, 2012.
  18. Bernát Wiandt, Vilmos Simon, and András Kőkuti. Self-organized graph partitioning approach for multi-agent patrolling in generic graphs. In Smart Technologies, IEEE EUROCON 2017-17th International Conference on, pages 605–610. IEEE, 2017.
  19. David Portugal, Charles Pippin, Rui P Rocha, and Helen Christensen. Finding optimal routes for multi-robot patrolling in generic graphs. In Intelligent Robots and Systems (IROS 2014), 2014 IEEE/RSJ International Conference on, pages 363–369. IEEE, 2014.
  20. Geoff Boeing. Osmnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Browser Download This Paper, 2016.
  21. Aydano Machado, Geber Ramalho, Jean-Daniel Zucker, and Alexis Drogoul. Multi-agent patrolling: An empirical analysis of alternative architectures. In Multi-Agent-Based Simulation II, pages 155–170. Springer, 2002.
  22. Robert McGill, John W Tukey, and Wayne A Larsen. Variations of box plots. The American Statistician, 32(1):12–16, 1978.
  23. DR Cox and PAWL Lewis. The statistical analysis of series of events. 1966.