多机器人从正六边形区域在线撤离算法研究  

Online algorithms of multi-robot evacuation from regular hexagon

作　　者：张妍 魏琦 刘銮 孙洁 张文馨 Zhang Yan;Wei Qi;Liu Luan;Sun Jie;Zhang Wenxin(School of Computer&Information Technology,Liaoning Normal University,Dalian Liaoning 116033,China)

机构地区：[1]辽宁师范大学计算机与信息技术学院,辽宁大连116033

出　　处：《计算机应用研究》2022年第12期3644-3650,共7页Application Research of Computers

基　　金：国家自然科学基金资助项目(61702242)。

摘　　要：针对多机器人在线撤离未知多边形区域展开研究,在原有撤离区域模型(三角形、正方形、圆形)的基础上提出多机器人从正六边形区域在线撤离问题。设置出口在正六边形区域的边界上,2 k(k≥1)个具有无线通信能力的机器人从相同起点出发,协作搜索出口并撤离。使用机器人全部从出口撤离的时间作为算法的开销,分析算法的效率。根据机器人数量和初始位置分情况讨论,k=1时,机器人的初始位置分别位于正六边形区域的边界和内部;k>1时,机器人初始位置在正六边形区域的边界。针对上述几种情况,分别给出了高效的多机器人协作在线撤离算法,并证明在机器人起点相同的情况下,增加机器人数量对减少算法开销具有正向的意义。Aiming at multi-robot online evacuation from unknown polygon,this paper proposed the problem of multi-robot online evacuation from a regular hexagon based on the original evacuation model(triangle,square,circle).2 k(k≥1)robots with wireless communication start from the same starting point,search for the exit on the regular hexagon boundary cooperatively and evacuate.The evacuation cost was the time that took for all robots to be evacuated from the exit.This paper analyzed the efficiency of the algorithm using evacuation overhead.According to the number of robots and the initial position,when k=1,robots were initially at the regular hexagonal boundary or inside;when k>1,robots were initially at the regular hexagon boundary.This paper proposed respectively efficient online algorithms of multi-robot evacuation for the above situations.It proves that increasing the number of robots has a positive significance in reducing the algorithm overhead when the starting point of the robots is the same.

关 键 词：计算几何 在线搜索 正六边形区域 移动机器人 无线通信 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]