In this paper, the mission for mobile patrolling robots is to detect as many incoming visitors as possible by monitoring the environment. For multi-robot mobile patrolling systems, task assignment in the common environment is one of the problems. For this problem, we use a territorial approach and partition the environment into territories. Thus, each robot is allowed to patrol a separate territory regardless of the others. In this regard, however, the workload balancing of the patrolling tasks in the territories is a challenge. For this challenge, we propose dynamic partitioning strategies focusing on visitor trends. The system transfers a part of the territory with the maximum workload to others so as to equalize the workloads. As a result, while the sizes of the territories without visitor trends increase, others with the trends decrease. Therefore, the territorial approach enables robots to intensively monitor areas in accordance with the number of the visitors. This is the main contribution of this paper. Simulation experiments show that the patrolling robots successfully detect visitors through workload balancing.

1. [1] Y. Elmaliach et al., “Multi-Robot Area Patrol under Frequency Constraints,” IEEE Int. Conf. on Robotics and Automation, pp. 385-390, 2007.
2. [2] N. Agmon et al., “Multi-Robot Perimeter Patrol in Adversarial Settings,” IEEE Int. Conf. on Robotics and Automation, pp. 2339-2345, 2008.
3. [3] D. Portugal and R. Rocha, “A Survey on Multi-robot Patrolling Algorithms,” Technological Innovation for Sustainability, pp. 139-146, 2011.
4. [4] S. Hoshino et al., “Patrolling Robot based on Bayesian Learning for Multiple Intruders,” IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 603-609, 2015.
5. [5] S. Hoshino and S. Ugajin, “Adaptive Patrolling by Mobile Robot for Changing Visitor Trends,” IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 104-110, 2016.
6. [6] S. Hoshino and T. Ishiwata, “Probabilistic Surveillance by Mobile Robot for Unknown Intruders,” IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 623-629, 2015.
7. [7] S. Hoshino et al., “Optimal Patrolling Methodology of Mobile Robot for Unknown Visitors,” Advanced Robotics, Vol.30, No.16, pp. 1072-1085, 2016.
8. [8] B. P. Gerkey and M. J. Matarić, “A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems,” Int. J. of Robotics Research, Vol.23, No.9, pp. 939-954, 2004.
9. [9] J. Ota, “Multi-Agent Robot Systems as Distributed Autonomous Systems,” Advanced Engineering Informatics, Vol.20, No.1, pp. 59-70, 2006.
10. [10] B. P. Gerkey and M. J. Matarić, “Sold!: Auction Methods for Multirobot Coordination,” IEEE Trans. on Robotics and Automation, Vol.18, No.5, pp. 758-768, 2002.
11. [11] M. Nanjanath and M. Gini, “Dynamic Task Allocation for Robots via Auctions,” IEEE Int. Conf. on Robotics and Automation, pp. 2781-2786, 2006.
12. [12] N. Fujii et al., “Multiple Robot Rearrangement Planning Using a Territorial Approach and an Extended Project Scheduling Problem Solver,” Advanced Robotics, Vol.24, Nos.1-2, pp. 103-122, 2010.
13. [13] M. Ahmadi and P. Stone, “A Multi-Robot System for Continuous Area Sweeping Tasks,” IEEE Int. Conf. on Robotics and Automation, pp. 1724-1729, 2006.
14. [14] A. Okabe et al., “Spatial Tessellations: Concepts and Applications of Voronoi Diagrams,” Wiley Series in Probability and Statistics, 2000.
15. [15] J. Cortés et al., “Coverage Control for Mobile Sensing Networks,” IEEE Trans. on Robotics and Automation, Vol.20, No.2, pp. 243-255, 2004.
16. [16] R. Patel et al., “Centroidal Area-Constrained Partitioning for Robotic Networks,” ASME J. of Dynamic Systems, Measurement, and Control, Vol.136, No.3, 031024, 2014.
17. [17] M. Pavone et al., “Sharing the Load: Mobile Robotic Networks in Dynamic Environments,” IEEE Robotics and Automation Magazine, Vol.16, No.2, pp. 52-61, 2009.
18. [18] H. Choset and J. Burdick, “Sensor-Based Exploration: the Hierarchical Generalized Voronoi Graph,” Int. J. of Robotics Research, Vol.19, No.2, pp. 96-125, 2000.
19. [19] H. Choset et al., “Sensor-Based Exploration: Incremental Construction of the Hierarchical Generalized Voronoi Graph,” Int. J. of Robotics Research, Vol.19, No.2, pp. 125-148, 2000.
20. [20] H. Choset and K. Nagatani, “Topological Simultaneous Localization and Mapping (SLAM): toward Exact Localization without Explicit Localization,” IEEE Trans. on Robotics and Automation, Vol.17, No.2, pp. 125-137, 2001.
21. [21] P. Beeson et al., “Towards Autonomous Topological Place Detection Using the Extended Voronoi Graph,” Int. Conf. on Robotics and Automation, pp. 4384-4390, 2005.
22. [22] P. Fazli et al., “Fault-Tolerant Multi-Robot Area Coverage with Limited Visibility,” IEEE Int. Conf. on Robotics and Automation, 2010.
23. [23] J. O’Rourke, “Art Gallery Theorems and Algorithms,” Oxford University Press, 1987.
24. [24] M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of Np-Completeness,” W. H. Freeman Company, 1979.
25. [25] T. Ohtsuki, “Minimum Dissection of Rectilinear Regions,” IEEE Int. Symp. on Circuits and Systems, pp. 1210-1213, 1982.
26. [26] S. Nahar and S. Sahni, “Fast Algorithm for Polygon Decomposition,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol.7, No.4, pp. 473-483, 1988.
27. [27] S. Ozaki and M. Harao, “An Automatic Exit Sign Placement Algorithm Based on Rectangle Division,” IEICE Trans. on Information and Systems, Vol.J98-D, No.6, pp. 916-925, 2015.
28. [28] G. Karypis and V. Kumar, “A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs,” SIAM J. of Scientific Computing, Society for Industrial and Applied Mathematics, pp. 359-392, Vol.20, No.1, 1998.
29. [29] D. Portugal and R. Rocha, “MSP Algorithm: Multi-Robot Patrolling based on Territory Allocation Using Balanced Graph Partitioning,” ACM Symp. on Applied Computing, pp. 22-26, 2010.
30. [30] D. Portugal et al., “Finding Optimal Routes for Multi-Robot Patrolling in Generic Graphs,” IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 363-369, 2014.
31. [31] C. Pippin et al., “Performance Based Task Assignment in Multi-Robot Patrolling,” ACM Symp. on Applied Computing, pp. 70-76, 2013.