计算机科学 ›› 2024, Vol. 51 ›› Issue (11A): 231200088-9.doi: 10.11896/jsjkx.231200088
马文杰, 李宗刚, 杜亚江, 陈引娟
MA Wenjie, LI Zonggang, DU Yajiang, CHEN Yinjuan
摘要： 针对外来访问者访问环境导致所在分区机器人巡逻工作负荷增大的问题,提出一种访问者访问趋势的多机器人动态分区巡逻策略,以提高多机器人系统在动态环境中巡逻的效率。首先,使用改进k-means策略完成对环境的静态初始化分,通过在不同位置加入机器人的访问频次需求,机器人在各自的区域中执行巡逻任务;其次,当访问者进入环境对不同节点进行访问时,机器人通过关注访问者访问的趋势,与相邻分区机器人协商后,将区域候选节点经过对相邻区域的多次转移以均衡分区机器人的工作负荷,完成对区域的实时动态划分。仿真结果表明,机器人可以在成功检测到访问者的同时保持工作负荷动态均衡,所提访问者访问趋势下多机器人动态分区巡逻策略可以显著提升动态环境下多机器人巡逻的效率。
中图分类号:
| [1]TALMOR N,AGMON N.On the power and limitations of deception in multi-robot adversarial patrolling[C]//Twenty-Sixth International Joint Conference on Artificial Intelligence.2017:430-436. [2]WANG S.Research on decision control problems of mobile robots in complex dynamic environments[D].Hefei:University of Science and Technology of China,2023. [3]YAN C B,ZHANG T.Multi-robot patrol:a distributed algo-rithm based on expected idleness[J].International Journal of Advanced Robotic Systems,2016,13(6):172988141666366. [4]SEA V,KATO C,SUGAWARAT.Coordinated area partitio-ning method by autonomous agents for continuous cooperative tasks[J].J.Inf.Process(JIP),2017,25:75-87. [5]JÜRGEN S,ANGELA P S,BERNHARD R.Min-Max Vertex Cycle Covers with Connectivity Constraints for Multi-Robot Patrolling[J].IEEE Robotics and Automation Letters,2022,7(4):10152-10159. [6]JEONGEUN K,HYOUNG I S.A Voronoi diagram-based workspace partition for weak cooperation of multi-robot system in orchard[J].IEEE Access,2020,8:20676-20686. [7]SUGIYAMA A,SEA V,SUGAWARA T.Effective task allocation by enhancing divisional cooperation in multi-agent conti-nuous patrolling tasks[C]//2016 IEEE 28th International Con-ference on Tools with Artificial Intelligence(ICTAI).IEEE,2016:33-40. [8]CHEN F R,CHEN B,ZHU Z Q,et al.A cost-beneficial area-partition-involved collaborative patrolling game in a large-scale chemical cluster[J].Process Safety and Environmental Protection,2021,145:71-82. [9]DOJIN C,JINSU H AND JONTAE L.Dynamic graph partitioning scheme for supporting load balancing in distributed graph environments[J].IEEE Access,2021,9:65254-65265. [10]PORTUGAL D,ROCHA R P.MSP algorithm:multi-robot patrolling based on territory allocation using balanced graph partitioning[C]//Proceedings of the 2010 ACM Symposium on Applied Computing(SAC).Sierre,2010:22-26. [11]SEA V,SUGIYAMA A,SUGAWARA T.Frequency-basedmulti-agent patrolling model and its area partitioning solution method for balanced workload[C]//Internationa Conference on Integration of Constraint Programming,Artificial Intelligence,and Operations Research.Department of Computer Science and Communication,2018. [12]MAO T,RAYL E.Frequency-based patrolling with heterogeneous agents and limited communication[J].arXiv:1402.1757,2014. [13]OUYANG Z Y,ERIC K H L,YIJI C,et al.Dynamic community partitioning for e-commerce last mile delivery with time window constraints[J].Computers & Operations Research,2023,160:106394. [14]HOSHINO S,TAKAHASHI K.Dynamic partitioning strategies for multi-robot patrolling systems[J].Journal of Robotics and Mechatronics,2019,31(4):535-545. [15]NGUYEN M T,MANIU C S,OLARU S.Optimization-basedcontrol for multi-agent deployment via dynamic Voronoi partition[J].Ifac Papersonline,2017,50(1):1828-1833. [16]PATEL R,FRASCA P,DURHAM J W,et al.Dynamic partitioning and coverage control with asynchronous one-to-base-station communication[J].IEEE Transactions on Control of Network Systems,2016,3(1):24-33. [17]JING R,MIN J,ZHAONING C.A method for topological region division of ocean flow field[J].Journal of Science and Technology of Surveying and Mapping,2020,37(5):545-550. |
|
||
首页