复杂动态环境下机器人避撞路径规划沈 杰 （上海第二工业大学，上海 201209） 摘 要：为了使机器人在复杂动态环境中实现最优路径规划，提出了改进人工蜂群算法的路径规划方法。分析了传统的人工蜂群算法原理，引入了小步长侦查蜂为跟随蜂提供障碍物分布的先验信息；为了防止机器人与动态障碍物发生碰撞，对动态障碍物周围的可行节点进行障碍化处理，将节点障碍指数与节点与目标点距离糅合为节点选择准则，同时提出了障碍避撞预测和障碍避撞策略。由仿真实验可以看出，改进算法不仅成功实现避撞，而且规划出避撞条件下的最优路径。 关键词：机器人避撞路径规划；动态未知环境；避撞策略；节点障碍指数 1 引言机器人可以代替人类完成重复性工作、危险工作和人类无法完成的工作等，这对于节约生产成本、保证人身安全具有重要意义。机器人路径规划[1-2]是机器人导航的关键问题，根据对环境的掌握情况，分为已知环境的路径规划和未知环境的路径规划；根据规划目标的不同，可以分为点对点路径规划和遍历路径规划。研究的是复杂动态环境中的机器人点对点路径规划问题，对于机器人在未知环境中执行复杂任务具有重要意义。 机器人路径规划问题，当前已经取得了很多成果。在静态已知环境中规划方法包括可视图法[3]、栅格法、Dijkstra算法[4]等；对于未知环境的规划方法包括人工势场法[5]、增强式学习[6]、神经网络法[7]等。不同算法在特定环境中都取得了成果，但是也都存在一些缺陷。可视图法只适用于工作环境简单时，栅格法中栅格大小的选取限制了其使用，Dijkstra算法没有充分使用目标点启发信息导致规划时间过长，人工势场法存在局部极小值和目标不可达问题，增强式学习法存在学习时间过长的问题。在分析传统人工蜂群的基础上，引入了小步长侦查蜂，使跟随蜂选择前进方向时具有障碍物分布的先验信息；为了满足复杂动态环境的路径规划要求，提出了避撞预测策略和障碍物防撞策略，实现了避撞和路径最优规划的双重目标。 2 改进人工蜂群算法人工蜂群算法[8-9]是模拟蜂群发现花源过程而提出的群智能算法，在此算法中启发信心、摇摆舞、觅食行为等根据解决问题不同定义也不同。 2.1 结合路径规划的人工蜂群算法 进行路径规划之前，首先要对环境进行建模，使工作环境变成机器人可以识别的数字地图，选用栅格法[10]对工作环境进行建模，机器人出发点Gstart视为蜂巢，目标点Gend视为花源。在人工蜂群算法中，将蜂群分为侦查蜂和跟随蜂两类，在寻找花源过程中侦查蜂以花源浓度为启发信息，进行进行大步长搜索，以视觉清晰度为判断标准评判是否发现花源；对于发现花源的侦查蜂，以摇摆舞的方式召唤跟随蜂，跟随蜂以自身位置为出发点，以侦查蜂所在位置为子目标点，以路径最短为目标进行路径规划，要求一只跟随蜂走过的栅格其他跟随蜂不许再选。若有SWnum只侦查蜂发现花源，则相应地分配SWnum只跟随蜂，每只跟随蜂规划出一条路径，则就规划出SWnum条局部路径，保留其中最短的路径并将此跟随蜂设置为引领蜂，而后以此蜂位置为起点继续进行侦查蜂大步长搜索和跟随蜂路径规划，直至到达花源。 将每个栅格边长统一化为1，栅格用g表示，工作区域栅格的集合记为Sgrid，障碍物栅格集合为Oobs，种群中存在n只侦查蜂，侦查步长为m，所有侦查蜂共用一个禁忌表记为Tabuscout，发现花源的侦查蜂有SWnum只，不同跟随蜂禁忌表不同，第i只侦查蜂的禁忌表记为Tabuibee，所有跟随蜂禁忌表记为Tabubee。将栅格之间的距离定义为栅格中心点之间的距离，记跟随蜂fb当前位置为gb，则其邻域栅格定义为blank（gb）=｛g d（g，g0）≤ ■ 2 ，g∈Sgrid∩g∉Oobs }，其可行栅格定义为feasible（gb）=｛g g∈blank（gb）∩g∉Tabubee }。侦查蜂fs的邻域栅格集合U（fs）=｛g g∈Vm∩g∉Vm-1}，式中 Vm为以fs为中心、以（2m+1）为边长的正方形区域栅格，侦查蜂fs的大步长无障碍栅格集合为seek（fs）=｛g g∈U（fs）∩g∉Oobs}。在人工蜂群算法中以花香浓度为侦查蜂搜索的启发信息，结合路径规划问题实际，将其定义为侦查蜂当前位置P与目标位置Gend的距离倒数。  另外，侦查蜂以“视觉清晰度”为评判标准判断是否发现花源，结合路径规划问题，将“视觉清晰度”R（fs）定义为： R（fs）=Mlen-d（P，Gend） 式中：Mlen—出发点与目标点距离； d（P，Gend）—当前位置P与目标点距离。 将人工蜂群发现花源的过程分为侦查蜂花源搜索和跟随蜂局部路径规划两个过程。侦查蜂搜索花源过程中共用一个禁忌表Tabuscout，而且栅格经任意侦查蜂选过后自动加入到禁忌表中，因此侦查蜂 fs（s∈［1，n］）的可行栅格集合为：  在此可行栅格集合中计算花香浓度，最大浓度记为Fmax，所处栅格记为gbest，则侦查蜂fs下一栅格gnext选择规则为：  式中：p—［0，1］间的随机数； p0—［0，1］间的常值； g0—赌轮盘规则得到的位置。 当n只侦查蜂均选择栅格后，计算每只侦查蜂的视觉清晰度，当大于某一阈值时认为发现花源，视觉清晰度阈值Treso为：  式中：α—［0，1］间的参数，改变其大小可以改变发现花源侦查蜂数量。 发现花源的侦查蜂会跳摇摆舞召唤对应的跟随蜂，为了模拟这一过程，为每只侦查蜂分配一个参数Wflag，若SWflag=1说明此侦查蜂发现花源，若SWflag=0则此侦查蜂没有发现花源。为所有发现花源的侦查蜂分配跟随蜂，以侦查蜂位置为子目标进行路径规划。 跟随蜂局部路径规划问题。记跟随蜂fb当前位为gb，局部目标点为gblocal，得到 fb邻域栅格集合 blank（gb），fb可行栅格集合feasible（gb），为每只跟随蜂建立一张禁忌表Tabuibee和路径表Pathb。根据gb邻域栅格情况不同，分三种情况进行节点选择：（1）当 feasible（gb）≥1 时，下一节点 gnext选择为 gnext=min d（gi，gblocal），式中 gi∈feasible（gb）；（2）当 feasible（gb）=0 且 blank（gb）＞1 时，说明fb邻域栅格均被选过，此时下一节点gnext选择为gnext=min d（gi，gblocal），式中 gi∈blank（gb）；（3）当 feasible（gb）=0 且 blank（gb）=1时，说明跟随蜂进入了U形陷阱，此时跟随蜂回到上步栅格，即gnext=glast。为了避免其它跟随蜂再次进入U形陷阱，将当前位置gb设置为障碍物栅格，添加到所有跟随蜂的禁忌表中。 2.2 改进人工蜂群算法 小步长侦查蜂节点选择说明。小步长侦查蜂的引入是为了侦查跟随蜂可行方向上的障碍物复杂度。障碍侦查区的大小影响对障碍物信息掌握的详略程度和算法速度，综合考虑这两个方面，将障碍物侦查区定义为（3×3）的方形区域。小步长侦查蜂frech下一节点选择方法：记跟随蜂fk当前位置为gk，设P1为其一个可 为了使人工蜂群算法适用于未知环境和复杂环境，引入了小步长侦查蜂的概念，提出了改进人工蜂群算法。改进人工蜂群算法的基本思想是：大步长侦查蜂从起始点出发，以m为步长，以花香浓度为启发信息，为每只SWflag=1的大步长侦查蜂分配跟随蜂，为每只跟随蜂分配若干只小步长侦查蜂，小步长侦查蜂用于探索跟随蜂可能前进方向的障碍物情况，然后根据此方向的障碍物分布和离目标点距离对每个可行节点进行评分，当节点得分小于某一标准时，说明此方向障碍物分布简单，由此方向根据跟随蜂节点选择策略移动至局部目标点；当节点得分大于某一标准时，说明此方向障碍物复杂，在此方向进行路径搜索会遇到复杂障碍物，此时放弃此大步长侦查蜂，召回为其分配的跟随蜂，重新选择一只大步长侦查蜂对其进行替代。若所有大步长侦查蜂均无法使用，则认为此位置对花源搜索失败，那么由起点根据跟随蜂节点选择策略前进若干步，再由大步长侦查蜂进行花源搜索，直至搜索到目标为止。 记跟随蜂fb栅格位置为gb，则跟随蜂可能前进方向为其邻域栅格中可行栅格的方向。记小步长侦查蜂frech栅格位置为P，则以P为中心、以r为步长的邻域内所有栅格为frech的障碍物侦查行栅格，则P1在处放置一只小步长侦查蜂frech，若frech位于非边界栅格时，其下一节点g→kP1为方向上与紧邻的栅格；若frech位于边界栅格时，如图 1（a）所示。圆形代表跟随蜂当前位置，数字 1、2、3、4代表小步长侦查蜂当前位置，则小步长侦查蜂下一节点位置为图中三角形位置；对于如图1（b）所示的特殊情况，跟随蜂的可行节点位于边界交界处，此时小步长侦查蜂不再选择下一节点，直接将环境复杂度置0。  图1 可行节点位于边界的所有情况 可行节点评分策略。提到的小步长侦查蜂根据障碍物侦查区内障碍物分布情况计算出障碍物复杂度mark（gi），综合评分S（gi）根据障碍物复杂度mark（gi）和与目标点距离给出，即： S（gi）=μd（gi，Gnd）+μmark（gi） 式中：μ、η—（0，1）间的系数，用于调节障碍物复杂度和与目标点 距离之间的比重。 跟随蜂节点选择策略。记跟随蜂fk当前位置为gk，获取邻域栅格集 blank（fk）、可行栅格集 feasible（fk）。当 feasible（fk）≥1 时，此时可行节点数大于1，按照可行节点评分方法计算每个可行节点得分，得分最少的节点为最优节点，跟随蜂fk下一步移动至此节点；当feasible（gb）=0、blank（gb）gt;1 或 feasible（gb）=0、blank（gb）=1 时，跟随蜂的节点选择策略与传统算法一致，这里不再赘述。 3 未知动态环境下改进人工蜂群算法3.1 改进人工蜂群算法基本思想 当未知环境中存在动态障碍物时，滚动优化算法能够根据环境变化实时调整策略，很好地解决动态环境路径规划问题。针对环境中的动态障碍物，模仿动物躲避危险的行为，当障碍物在危险范围内时进行规避。基于以上想法，给出改进人工蜂群算法的基本思想：机器人进行一定范围的环境探测，当目标点出现在视野时，则探测视野内是否存在动态障碍物，若不存在则按照2.2节中给出的方法运动至目标点，若存在动态障碍物则调用动态避撞策略，直至移动至目标点；当目标点没出现在视野时，首先选择子目标点，然后按照动态障碍物存在与否的不同策略移动至子目标点，而后重新探测环境信息，进行路径规划，直至移动至目标点。 3.2 改进算法数学描述 记机器人的探测半径为r，当前位置为grob，则机器人探测范围FV（grob）=｛g d（g，grob）≤ ■ 2 r，g∈Sgrid }，视野域的边界栅格集合∂FV（grob）=｛g r≤d（g，grob）≤ ■ 2 r，g∈Sgrid∩g∉Oobs}。若目标点在探测范围内，即Gend∈FV（grob），则子目标gsub=Gend，若目标点不在探测范围内，则子目标gsub选择方法为mind（grob，gsub）+d（gsub，Gend）。工作区域内所有非障碍物区域记为FD=｛g g∈Sgrid∩g∉Oobs}。机器人邻域栅格集合为blank（grob）=｛g d（g，grob）≤ ■ 2 ，g∈FD }，动态路径表Path，可行栅格集合为 feasible（grob）=｛g∈blank（grob）∩g∉Path}。记动态障碍物当前位置为gobc。 碰撞预测策略。参照机器人和障碍物大小，给出距离安全阈值SD，若 d（grob，gobc）≤SD，说明此时两者具有碰撞的危险，应该调用障碍物避碰策略；若 d（grob，gobc）＞SD，则两者距离较远，没有碰撞的可能，则按照各自运动方式继续前进。安全阈值SD过大时，机器人规避过早，容易使规划路线与最优路线偏差较大；安全阈值SD过小时，就有发生碰撞的危险。一般情况下有：SD∈［vrob+vobc，r］ 式中：vrob—机器人运动速度；vobc—障碍物运动速度。 障碍物避碰策略。当机器人与动态障碍物距离小于阈值时，为防止两者之间发生碰撞，对动态障碍物周围可行节点进行障碍化处理。节点障碍指数DI（g）为：  式中：step（g，gobc）—从栅格g到栅格gobc的最少步数。对可行节 点进行障碍化处理后，栅格与子目标距离定义为Len（g）= d（g，gsub）+DI（g）。避撞算法为： Step1：更新机器人当前位置gsub，将其加入到动态路径表Path，设探测到动态障碍物位置 gobc，若 d（grob，gobc）＞SD 则算法结束；否则转至Step2； Step2：若 ■ Step3：此时机器人与动态障碍物相邻，调用相邻避撞规则后转至Step1。 相邻避撞规则四种情况，如图2所示。图中深色为机器人，浅色为动态障碍物：对于第一种情况，将动态障碍物视为静态障碍物，进行可行节点选择，若没有可行节点，则退回上一栅格；对于第二种和第三种情况，两者不会碰撞，按原方向继续移动；对于第四种情况，为避免因躲避障碍物与最优路径相差太大，机器人在此等待，等障碍物通过后再前进。  图2 相邻避撞规则 4 仿真验证使用仿真的方法对算法进行验证。实验环境为WIN7、IntelCore2、2GB memory，所用软件为Visual Studio。参数设置为m＝4、λ＝0.1、μ＝η=1、σ＝0.65、iter=10、n=4、α=0.1、SD= ■ 第一次防碰撞：当机器人移动至（3，7）栅格时，动态障碍物处于（5，6）栅格，若机器人不采用防撞策略，则两者在（5，8）栅格发生碰撞，采用防撞策略后路线，如图5（b）所示。第二次防碰撞：当机器人移动至（3，10）栅格时，动态障碍物处于（5，9）栅格，若机器人不采用防撞策略，则两者在（5，11）栅格发生碰撞，采用防撞策略后路线，如图5（b）所示。第三次防避撞：当机器人运动至（13，21）栅格，探测到动态障碍物位于（15，22）栅格，调用避撞算法后机器人运动至（13，22），动态障碍物运动至（14，22）点，两者相邻扔具有碰撞危险，此时调用相邻避撞规则，防止了碰撞的发生。第二次避撞，如图6所示。  图3 动态环境中路径规划结果 图4 静态环境中路径规划结果 图5 第一次避撞 图6 第二次避撞 通过以上分析可知，提出的改进人工蜂群算法可以有效防止机器人与动态障碍物的碰撞，同时实现了避撞前提下的路径最优规划。 5 结论经过以上分析，可以得到以下结论：（1）引入了小步长侦查蜂，使算法能够适应复杂环境的路径规划问题；（2）提出了避撞预测策略和障碍物避撞策略，使算法适用于复杂动态环境中。 参考文献 ［1］徐晓晴，朱庆保.动态环境下基于多人工鱼群算法和避碰规则库的机器人路径规划［J］.电子学报，2012，40（8）：1694-1700.（Xu Xiao-qing，Zhu Qing-bao.Robot path planning based on artificial fish swarm algorithm and collision avoidance rule library in dynamic environment［J］.Journal of Electronics，2012，40（8）：1694-1700.） ［2］刘传领.基于势场法和遗传算法的机器人路径规划技术研究［D］.南京：南京理工大学，2012.（Liu Chuan-ling.Researches on technologies for robot path planning based on artificial potential field and genetic algorithm［D］.Nanjing：Nanjing University of Scienceamp;Technology，2012.） ［3］陈超，唐坚，靳祖光.一种基于可视图法导盲机器人路径规划的研究［J］.机械科学与技术，2014，33（4）：490-495.（Chen Chao，Tang Jian，Zan Zu-guang.A path planning algorithm for seeing eye robot based on v-graph［J］.Mechanical Secience and Technology for Acrospace Engineering，2014，33（4）：490-495.） ［4］邹益民，高阳，高碧悦.一种基于Dijkstra算法的机器人避障问题路径规划［J］.数学的实践与认识，2013，43（10）：111-118.（Zou Yi-min，Gao Yang，Gao Bi-yue.A path planning method for mobile robot obstacle avoidance based on dijkstra algorithm［J］.Mathematics in Practice and Theory，2013，43（10）：111-118.） ［5］卢路秋.基于模糊人工势场法的多移动机器人路径规划研究［D］.天津：天津工业大学，2015.（Lu Lu-qiu.Research on path planning of multiple mobile robots based on fuzzy artificial potential field method［D］.Tianjing：Tianjing Polytechnic University，2015.） ［6］杨玉君，程君实，陈佳品.基于连接增强式学习的移动机器人控制［J］.上海交通大学学报，2003，37（11）：1662-1664.（Yang Yu-jun，Cheng Jun-shi，Chen Jia-pin.Connectionist reinforcement learning for mobile robot［J］.Journal of Shanghai Jiaotong University，2003，37（11）：1662-1664.） ［7］吕战永，曹江涛.自反馈生物激励神经网络机器人路径规划［J］.计算机工程与应用，2014，50（16）：255-258.（Lv Zhan-yong，Cao Jiang-tao.Robot path planning method based on biologically incentives neural network with self-feedback［J］.Computer Engineering and Applications，2014，50（16）：255-258.） ［8］张冬丽.人工蜂群算法的改进及相关应用研究［D］.秦皇岛：燕山大学，2014.（Zhang Dong-li.Improved artificial bee colony algorithm and its applications［D］.Qinhuangdao：Yanshan University，2014.） ［9］宁爱平，张雪英.人工蜂群算法的收敛性分析［J］.控制与决策，2013（10）：1554-1558.（Ning Ai-ping，Zhang Xue-ying.Convergence analysis of artificial bee colony algorithm［J］.Control and Decision，2013（10）：1554-1558.） ［10］柴寅，唐秋华，邓明星.机器人路径规划的栅格模型构建与蚁群算法求解［J］.机械设计与制造，2016（4）：178-181.（Chai Ying，Tang Qiu-hua，Deng Ming-xing.Grid model and ant colony algorithm for robot path planning［J］.Machinery Designamp;Manufacture，2016（4）：178-181.） Robot Anti-Collision Path Planning Under Complex Dynamic Environment SHEN Jie Abstract：To plan optimal path for robot under complex dynamic environment，path planning based on improved artificial bee colony algorithm is proposed.Principle of traditional artificial bee colony algorithm is analyzed.Short step scout bee is imported to detect obstacles condition in every possible forward direction of following bee，which is prior information for following bee to choose forward direction.In order to prevent collision of robot and dynamic barrier，feasible grids around dynamic barrier are treated to some degree of barrier.Grid barrier index and distance of the grid and goal are mixed as grid choice criteria.Anti-collision prediction and anti-collision strategy are put forward.Simulation experiment is executed to clarify the algorithm，the improved algorithm can not only prevent collision successfully，but it also can plan a optimal path. Key Words：RobotAnti-CollisionPathPlanning；Dynamic Unknown Environment；Anti-Collision Strategy；Grid Barrier Index 中图分类号：TH16；TP242 文献标识码：A 文章编号：1001-3997（2017）11-0255-04 来稿日期：2017-05-13 基金项目：国家自然科学基金（61272470）；上海第二工业大学校级重点学科建设资助（NO：XXKPY1603） 作者简介：沈 杰，（1981-），男，上海人，本科，讲师，主要研究方向：工业设计、产品设计 |
|
|
式中r为障碍物侦查区半径，且有 r∈［1，m］。在障碍物侦查区 Obc（f
lt;d（g
、r=9。仿真出一个（30×30）的方形工作区域，区域中黑色栅格表示障碍物栅格，白色栅格为可行栅格，实心圆为两个动态障碍物，机器人速度与动态障碍物移动速度一致。使用改进人工蜂群算法对路径进行规划结果，如图3所示。为了展示避撞效果，将其与不存在动态障碍物的静态环境进行比较，在静态环境中规划结果，如图4所示。图3中由于障碍物的存在，其路径长度为50.97，图4中路径长度为48.04，也就是说为了躲避动态障碍物，多走了2.93长度的路径。
