摘 要：相对于单个机器人，多机器人在空间搜索、环境监测、随机环境网络部署上具有很大的优势。该研究针对上述应用中任意环境边界机器人均匀部署问题展开，提出了一种二维空间中任意部署边界的机器人均匀部署方法，该方法首先根据已知的部署边界，使用 CVT（Centroidal Voronoi tessellation）对图形进行分割来获取均匀部署目标的位置，然后采用模拟退火算法对随机分布的机器人进行部署分配，通过数值仿真证明了所提方法是有效的。
关键词：多机器人；均匀部署；质心 Voronoi 划分；模拟退火算法；任务分配
DOI:10.19850/j.cnki.2096-4706.2022.17.037
基金项目： 安徽省自然科学基金（1908085QF294）
中图分类号：TP249 文献标识码：A 文章编号：2096-4706（2022）17-0143-07
Uniform Deployment of Multiple Robots Based on CVT and Simulated Annealing
YAN Liping, WU Yuxiu, ZHANG Wenzhong
(School of Electrical and Information Engineering, Anhui University of Technology, Maanshan 243032, China)
Abstract: Compared to a single robot, multiple robots have great advantages in spatial search, environmental monitoring and random environmental network deployment. This study addresses the problem of uniform deployment of robots with arbitrary environmental boundaries in the above applications, and proposes a method for uniform deployment of robots with arbitrary deployment boundaries in two-dimensional space. The method first uses CVT (Centroidal Voronoi tessellation) to segment the graph to obtain the location of uniform deployment targets based on known deployment boundaries, and then it uses the Simulated Annealing algorithm to assign deployment for the randomly distributed robots. The proposed method is proved to be effective by numerical simulation.
Keywords: multiple robots; uniform development; Centroidal Voronoi Tessellation; Simulated Annealing algorithm; task allocation
参考文献：
[1] GUPTA S K，KUILA P，JANA P K. Genetic algorithm approach for k-coverage and m-connected node placement in target based wireless sensor networks [J].Computers & Electrical Engineering，
2016，56：544-556.
[2] ALONSO M J，BREITEN M A，RUFLI M，etal.Image and animation display with multiple mobile robots [J].The International Journal of Robotics Research，2012，31（6）：753-773.
[3] LIAO W，KAO Y，LI Y. A sensor deployment approach using glowworm swarm optimization algorithm in wireless sensor networks [J].Expert Systems with Applications，2011，38（10）：12180-12188.
[4] VATANKHAH A，BABAIE S. An optimized Bidding-based coverage improvement algorithm for hybrid wireless sensor networks [J]. Computers & Electrical Engineering，2018，65：1-17.
[5] MOHAMADI H，SALLEH S，RAZALI M N，Sara Marouf. A new learning automata-based approach for maximizing network lifetime in wireless sensor networks with adjustable sensing ranges [J]. Neurocomputing，2015，153：11-19.
[6] CHOWDHURY A，DE D. Energy-efficient coverage optimization in wireless sensor networks based on Voronoi-Glowworm Swarm Optimization-K-means algorithm [J].Ad Hoc Networks，2021，[J/OL].Ad Hoc Networks，2021，122：1-16[2022-05-20].https://www. nstl.gov.cn/paper_detail.html?id=e36a7fa04f03364e099ebcb22f496026.
[7] 张嵛，刘淑华 . 多机器人任务分配的研究与进展 [J]. 智能系统学报，2008（2）：115-120.
[8] WANG W，ZHAO J，HUANG J. Improved Ant Colony Genetic Algorithm for Solving Traveling Salesman Problem [J/OL]. Journal of Physics：Conference Series，2020，1693：012085[2022-05-03].https: //iopscience.iop.org/article/10.1088/1742-6596/1693/1/012085.
[9] HUSSAIN A，MUHAMMAD Y S，SAJID M N. An Improved Genetic Algorithm Crossover Operator for Traveling Salesman Problem [J].Math. Comput. Sci，2018，x：1-13.
[10] KOOHESTANI B. A crossover operator for improving the efficiency of permutation-based genetic algorithms [J/OL].Expert Systems with Applications，2020，151：113381[2022-05-03].https: // www.sciencedirect.com/science/article/abs/pii/S0957417420302050.
[11] SUN X，QI N，YAO W. Boolean Networks-Based Auction Algorithm for Task Assignment of Multiple UAVs [J/OL].Mathematical Problems in Engineering，2015：425356[2022-05-03].https: //www. hindawi.com/journals/mpe/2015/425356/.
[12] WANG Z，GENG X，SHAO Z. An Effective Simulated Annealing Algorithm for Solving the Traveling Salesman Problem [J]. Journal of Computational and Theoretical Nanoscience，2009，6（7）：1680-1686.
[13] WANG Y，WU S，CHEN Z Y，etal. Coverage problem with uncertain properties in wireless sensor networks：A survey， Computer Networks [J].2017，123：200-232.
[14] QIANG D，VANCE F，MAX G X. Centroidal Voronoi Tessellations：Applications and Algorithms [J].SIAM Review，1999， 41（4）：637-676.
[15] WANG H F，WANG D W，YANG S X. A memetic algorithm with adaptive hill climbing strategy for dynamic optimization problems [J].Soft Computing，2009，13（8-9）：763-780.
作者简介：严李平 (1996—)，男，汉族，安徽安庆人，硕士研究生，主要研究方向 : 多机器人覆盖；吴玉秀 (1982—)，男，汉族，河南汤阴人，教师，硕士生导师，博士，主要研究方向 : 机器人运动控制、定位与环境感知，机器学习；张文忠（1997—），男，汉族，安徽铜陵人，硕士研究生，主要研究方向：多机器人智能调度。