李梓远，黄卫华,b,c，章 政,b,c，张子然，边 琳
(武汉科技大学a.机器人与智能系统研究院；
b.冶金自动化与检测技术教育部工程研究中心；
c.信息科学与工程学院，武汉 430081)
路径规划是机器人实现自主移动的基础。当移动机器人处于大规模环境时，机器人从起点到目标点完成一次完整无碰撞的路径规划过程中，易出现搜索空间大、规划路径拐点较多、能耗大等问题[1-3]。因此，有效降低搜索空间对于提升移动机器人的路径规划效率具有重要意义。
针对大规模环境下的地图建模问题，赵健等[4]在多路况复杂环境下提出了代价地图的构建方法，将代价函数与栅格地图融合，提高机器人运行的安全性并降低其能耗。岳伟韬等[5]提出了以准确度与信息量为变量的代价函数来评估占据栅格地图的精度，获取最佳栅格大小以提升地图准确度。郭书杰等[6]提出了一种关键点路径规划方法，将整个路径规划切分成多个较短的子路径规划，从而降低问题规模，提高规划效率。ZAFAR等[7]使用HPA*分层搜索算法，将复杂环境分为多个抽象层次，逐层搜索后得到完整路径，通过地图的层次抽象表达来减少计算负荷量。对于路径搜索策略而言，蚁群算法由于其正反馈、分布式计算能力、鲁棒性等优点被广泛应用于复杂大环境路径规划并取得了较好的效果。江明等[8]针对蚁群算法在复杂环境下收敛速度慢且易陷入局部最优值的问题，依据起始点和目标点位置信息选择全局有利区域增加初始信息素浓度，提升算法全局性。肖金壮等[9]通过动态更新不同蚂蚁路径上的信息素并引入距离函数和方向函数作为启发因子，加快了蚁群算法在大规模复杂环境中的搜索效率。
基于上述分析，针对大规模环境中路径规划效率的问题，传统蚁群算法缺乏地图信息的引导，搜索时间长且规划所得路径平滑度低。本文采用K-means算法对地图进行预处理，在实现层次环境建模的基础上，采用近处精细远处粗略的路径搜索策略来提升规划效率，并将机器人运动方向引入蚁群路径规划中，有效减小路径的曲折度。实验结果表明，本文所设计的路径规划优化算法具有搜索空间小、速度快、路径转折度小等特点。
对于机器人路径规划过程而言，一次路径规划后得到一条起点至目标点的完整路径并不是必要的[10-12]，在地图量化信息的引导下得到具有方向性的非完整路径同样能引导移动机器人寻优。鉴于此，本文基于非完整路径规划策略，构建了一种层次环境地图模型，如图1所示。其中，A表示规划任务的起点，B表示目标点，黑色区域表示障碍物，环境模型分为底层地图S0和高层地图S1。
图1 层次地图模型
由于对表征区域的高层节点进行检索可以降低搜索空间，因此本文设计了基于层次地图模型的路径搜索策略：对当前节点在底层地图中所处分区进行精细搜索，所处分区外的节点则通过搜索高层节点进行粗略搜索，以此得到一条由S0内详细路径、S1内粗略路径以及S0至S1跃层路径组成的非完整路径。因此由S0至S1的跃层是实现层次地图中路径搜索及减小搜索空间的关键，定义层次地图模型中路径由底层地图S0向高层地图S1跃层的条件为：当前位置节点的父节点不为空，且子节点与当前节点位于底层地图内的不同分区。如式(1)所示：
(1)
针对蚁群路径规划算法在大规模环境中收敛速度慢、易陷入局部最优等问题，本文将所设计的基于层次地图模型的路径搜索策略引入蚁群算法的状态转移中，减小算法的搜索空间，并在启发函数中设置方向奖惩函数来改善路径平滑度。
2.1 分层环境地图下蚁群状态转移策略的设计
对于在底层地图S0中进行路径搜索的蚂蚁，直接采用传统状态转移公式进行计算。考虑到传统状态转移策略依据轮盘赌原则来选出下一行进节点，因此搜索范围较大。在分层环境地图下，当蚁群跃层至高层地图S1中进行节点选择时，为了提高蚁群算法的收敛速度以及寻路的精确度，本文将环境信息与当前位置信息融入状态转移函数中，设计了基于层次地图的蚁群状态转移策略：
(2)
(3)
2.2 启发函数的设计
在路径规划过程中，减小蚁群搜索方向与前进方向的误差，可有效降低机器人由于转角过大导致运动时间增加的问题。为了加强蚂蚁寻路时对路径搜索方向的判断力，本节设计了一种奖惩函数，其表达式为：
(4)
式中，Rmax为奖励最大值；
θi和θj分别为当前节点和下一节点的航向角；
ΔR为奖励差值。
将奖惩函数引入启发函数以增强方向引导性，由此定义一种具有方向奖惩因子的启发函数：
(5)
式中，dij为节点i与节点j之间的欧氏距离；
γ为奖励因子，0<γ<1，其大小决定奖惩函数对启发函数的影响程度。
由于蚁群在前行方向留下的信息素浓度更高，本文去除了八方向搜索中东南、西南方向的子节点，使蚂蚁仅能选择剩余6个方向的子节点，因此，将奖惩函数引入后的6方向搜索方式如图2所示，前向方向具有最大奖励值Rmax，当机器人转向时，其奖励值按45°依次递减ΔR。
图2 方向奖惩函数示意图
优化后的启发函数融入了机器人的行进方向信息，使机器人倾向于前行以获得转折度较小的路径，相比传统启发函数对路径平滑性方面的考虑有明显的提升。
2.3 改进蚁群算法步骤
由上文可知，为提升大规模环境中路径规划的效率，本文使用改进后的蚁群算法进行路径规划，其执行步骤为：
步骤1：地图预处理。环境地图运用栅格法处理后，使用K-means算法对栅格地图障碍物聚类分区，并提取区域内可行节点得到高层地图。
步骤2：初始化蚁群算法的以下参数：种群规模m、信息素因子α、启发式因子β、信息素挥发因子ρ、信息素常量Q和最大迭代次数Zmax(Zmax=Z1+Z2+…+Zk)，设定的迭代次数ω，将迭代次数置为0，清空禁忌表。
步骤3：节点选择。蚂蚁在起点A处，按照式(2)及式(5)计算下一步到达的节点。
步骤5：迭代更新。当m只蚂蚁完成一次寻路后对其信息素进行更新。进行Z1次迭代后，得到一条当前区域内详细，远处区域内粗略的路径。
步骤6：由粗略路径规划至详细路径。将跃层处节点i作为新起点，从节点i处开始迭代Z2次，再一次得到当前区域的详细路径及远处区域的粗略路径。
步骤7：得到最后一个区域的详细路径并整合出从起点至目标点的详细路径。
所设计改进的蚁群算法流程图如图3所示。
图3 改进蚁群算法流程图
随机生成50×50的栅格地图，并初始化以下参数：设置蚂蚁个数为50个，最大迭代次数为100，信息启发式因子α=1，期望启发式因子β=7，信息素常量Q=1，信息素挥发因子ρ0=0.9。使用K-means算法将地图分为15个区域，如图4所示。跃层改进蚁群算法的运行过程如图5所示，其所得最优路径如图6所示。
图4 K-means聚类分区地图
(a) 跃层改进蚁群算法第一阶段 (b) 跃层改进蚁群算法第二阶段
图6 跃层改进蚁群算法最优路径
在相同环境下，分别采用传统蚁群算法、地图分区预处理的改进蚁群算法与仅跃层的蚁群算法进行实验，得到最优路径如图7所示，最短路径长度曲线如图8所示，实验参数如表1所示。
图7 三种算法最优路径对比图 图8 最短路径长度曲线图
表1 实验参数表
图4中路径规划的起点与目标点分别位于区域1与区域15。图5所示的规划过程中，图5a为在区域1中规划出的精确路径并确定后续搜索区域为2→6→11→15，图5b为以跃层节点为起点，在区域2中进行精细搜索，并确定后续搜索区域为6→11→15，循环此过程得到图5c与图5d内路径，最后得到目标点所在区域15内的详细路径。将图5a至图5d的详细路径整合即为图6所示完整路径。
对比图6和图7传统蚁群算法随着搜索范围增大，最优路径上的拐点增多；
地图分区预处理蚁群算法利用分区预处理后的区域量化信息对临近区域搜索，减小了部分区域路径的曲折度；
跃层蚁群算法利用跃层机制降低了搜索空间并使算法跳出局部最优；
图6跃层改进蚁群算法在跃层基础上，优化后的启发函数进一步降低了搜索时间并使路径更平滑。
由表1可知，与无改进蚁群算法相比，本文算法利用高层粗略路径对整体寻优进行引导，机器人的移动时间减少了53.1%；
改进启发函数使最优路径上的拐点减少，转弯次数减少了65.5%；
高层路径增强了算法跳出局部最优解的能力，使迭代次数减少了54.3%。与地图分区预处理的蚁群算法相比，本文算法的机器人的移动时间减少31.5%，转弯的次数减少了41.1%，迭代次数减少了42.4%。与跃层蚁群算法相比，本文算法的机器人移动时间减少了9.4%，转弯次数减少了23.1%，迭代次数减少了12.5%，综合性能更优。实验表明，在高层路径引导下进行规划的蚁群算法通过降低蚂蚁的搜索范围，提高了复杂环境下全局寻优的能力。
针对大规模环境下搜索空间增大造成规划效率降低等问题，设计了基于层次地图模型的改进蚁群算法。将层次地图模型中的路径搜索策略引入蚁群算法的状态转移策略，同时设计了基于方向奖惩的启发函数，提高蚁群算法的路径规划效率。实验结果表明，本文基于层次地图模型的改进蚁群算法相较于传统蚁群算法，对地图区域及层次的划分增强了算法跳出局部最优的能力，将方向奖惩函数引入启发函数，解决了路径转折率大的问题。本文算法具有更短的路径规划时间、更短路径长度及更少拐点，综合性能更优。
猜你喜欢方向机器人规划2022年组稿方向计算机应用(2022年2期)2022-03-012021年组稿方向计算机应用(2021年4期)2021-04-202021年组稿方向计算机应用(2021年1期)2021-01-21规划引领把握未来领导决策信息(2018年50期)2018-02-22快递业十三五规划发布商周刊(2017年5期)2017-08-22多管齐下落实规划中国卫生(2016年2期)2016-11-12迎接“十三五”规划中国工程咨询(2016年4期)2016-02-14机器人来帮你少儿科学周刊·少年版(2015年4期)2015-07-07认识机器人少儿科学周刊·少年版(2015年4期)2015-07-07机器人来啦少儿科学周刊·少年版(2015年4期)2015-07-07