机器人路径规划算法综述

2023-07-08王鹤静王丽娜

桂林理工大学学报 2023年1期

王鹤静，王丽娜

(中国计量大学 a.机电工程学院；b.浙江省智能制造质量大数据溯源与应用重点实验室，杭州 310018)

0 引言

机器人是人工智能的重点研究领域, 其中路径规划是机器人研究与发展中必不可少的核心内容之一, 是机器人在一定环境中完成既定任务的基础, 机器人的路径规划能力直观体现了其作业能力和风险管控能力。路径规划是指在规定区域内规划出一条从起始点到目标点的最优解路径, 且要保证与障碍物无碰撞。机器人路径规划存在的难点问题主要有环境建模计算量大、算法收敛速度慢以及容易陷入局部最优解问题。

对于二维环境建模问题, 主要采用栅格法进行环境建模。栅格法对机器人工作环境的描述更直观, 对障碍物和机器人相对位置的处理更简便, 可以最大程度上简化路径的求解过程。而在三维环境中, 如水下机器人, 可以将平面栅格法进行高度上的叠加, 将复杂的三维建模问题简化为多个二维建模问题, 在一定程度上提高了解路径的质量和路径规划算法的适应能力。对于路径规划算法普遍存在的收敛速度慢和容易陷入局部最优解问题, 通常对算法进行结构上的优化, 如增加算法参数的自适应调整能力, 可以降低算法陷入局部最优解的概率; 也可以将多个算法结合, 取长补短, 优化算法性能, 如蚁群算法可与人工势场法结合, 利用人工势场法生成初始可行路径, 并调整该路径和周围区域的初始信息素浓度, 可以极大加快蚁群算法的早期收敛速度。

综上, 路径规划可以分为传统算法路径规划和智能仿生算法路径规划两类, 其中传统路径规划算法又可以分为全局路径规划算法和局部路径规划算法。全局路径规划是在已知的环境中进行路径规划, 环境信息已经给定且障碍物位置等信息基本不发生变化, 一般只需按照事先规划的全局路径进行工作即可。而局部路径规划是在未知的环境中进行路径规划, 通过传感器等工具获取当前的局部环境信息, 主要是动态障碍物的位置信息等, 在此基础上进行路径规划和避障, 如水下机器人所处环境的障碍物分布极易发生改变, 机器人需要实时获取环境信息进行局部路径规划, 对其而言, 需要在全局路径规划的基础上, 多次进行局部路径规划,从而安全到达目标点。在这种环境中, 局部路径规划更为重要。智能仿生路径规划算法是仿生学在路径规划问题中的应用。机器人路径规划算法框架见图1, 本文从传统路径规划和智能仿生路径规划两方面分别给出一些常用算法, 并进行分析总结。

图1 机器人路径规划算法框架图Fig.1 Framework of robot path planning algorithm

1 传统算法路径规划

传统路径规划算法可以根据对环境信息的把握程度分为全局路径规划算法和局部路径规划算法。

1.1 全局路径规划

全局路径规划主要应用于给定环境信息的情况下进行路径规划, 不要求机器人具有较强的实时计算能力。目前常用的全局路径规划算法主要有A*算法、禁忌搜索算法等。

1.1.1 基于A*算法的路径规划 A*算法是一种常用的路径规划算法, 收敛速度快, 鲁棒性较强。A*算法最早发表于1968年, 由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael发表, 它可以算作是Dijkstra算法的扩展, 由于借助启发函数的引导, A*算法通常拥有更好的性能[1-4]。A*算法的流程如图2所示。其中, Open表和Close表分别存放算法还未遍历的节点和已经遍历的节点。

图2 A*算法流程图Fig.2 Flow chart of A* algorithm

A*算法中单个节点的综合优先级由f(n)=g(n)+h(n)决定[2]。其中,f(n)是节点n的综合优先级;g(n)是节点n距离起点的代价;h(n)是节点n距离终点的预计代价。由h(n)值的变化可知, 启发函数的调节可以改变算法的性能[3]。在实际问题中, 算法的收敛速度可能是首要标准, 路径的长度则是次要标准, 可见A*算法的运用较灵活, 这是其主要优点, 但也存在目标不可达、实时性差等缺陷。

近年来, 针对A*算法在路径规划问题的应用上, 有许多不同看法。王维等[4]针对复杂室内环境下移动机器人路径规划中存在实时性差的问题, 首先对算法运行的当前节点及之前节点的路径估计代价以指数衰减的方式加权, 使得离目标点较远时能够快速缩短与目标点的距离, 在靠近目标点之后进行更为细致的搜索, 保证在障碍物情况复杂的情况下路径依然具有可达性, 然后对生成的初始路径以高次函数进行平滑处理, 使得路径更短。Shi等[5]针对传统A*算法得出的路径转弯较多且不平滑, 并且在U形地区的路径可能会与障碍物发生接触的问题, 先选择余弦距离作为启发式函数, 加入方向信息并归一化, 再用36阶邻域搜索矩阵解决U形弯曲拟合问题, 最后提出了一种基于贝塞尔曲线的路径处理方法, 使规划的路径曲率不断变化。Liu等[6]针对机器人在物流仓库和制造车间的路径规划问题提出了基于Delaunay三角剖分和改进A*的动态融合寻路算法(DFPA), 首先采用Delaunay三角剖分算法处理复杂障碍物, 生成Voronoi点作为寻路优先节点, 然后利用网格的概念提取障碍物边缘, 为机器人寻路提供避障策略, 最后使用改进A*算法搜索可行路径。

王维等[4]的改进算法收敛速度大大提高, 路径更短且得到了平滑处理, 便于机器人进行转向等操作, 在复杂环境下具有较强的适应性和实时性。Shi等[5]改进的A*算法能够很好地考虑机器人与障碍物的关系, 解决传统A*算法路径接触障碍物的问题, 并通过贝塞尔曲线处理生成的路径, 达到平滑路径的效果, 改进后的A*算法能够更好地在机器人自主导航中发挥全局引导作用。Liu等[6]提出的地图构建方法和寻路策略减少了移动机器人的规划路径长度、路径节点数量和整体转弯消耗成本, 提高了路径获取成功率, 新的动态地图构建方法和寻路策略对处理混沌地图、促进智能导航和选址规划具有重要的参考意义。

针对A*算法的改进主要解决了算法在搜索速度和复杂环境中目标可达性上的问题, 切实提高了A*算法在路径规划上的实际应用效果。

1.1.2 基于禁忌搜索算法的路径规划禁忌搜索算法(tabu search, TS)是美国科学家Glover等[7]于1986年提出的一种优化算法, 具有全局逐步寻优的能力, 能很好地应用于机器人的路径规划问题。禁忌搜索算法是局部搜索算法的优化与发展, 是一种基于贪婪思想的邻域搜索算法, 但邻域搜索算法最大的缺点就是容易陷入局部最优[8], 为了解决这一问题, 引入禁忌表, 形成了禁忌搜索算法, 使其具有了较强的全局搜索寻优能力。应用于路径规划问题时, 禁忌表主要是用来存放已经搜索过的路径点, 表中的内容是动态更新的, 表的长度称为禁忌长度。搜索时, 直接跳过禁忌表中已有的路径点, 从而使得算法具有全局搜索的特性。

禁忌搜索算法主要由禁忌表、禁忌长度[9]、特赦准则、代价函数[10]和停止规则等部分组成。禁忌搜索算法应用于路径规划问题的流程如图3所示。禁忌搜索算法的主要思想有以下3点: ① 在进行领域搜索时尽量避免循环行为的产生; ② 通过禁忌表实现只进不退, 即跳过搜索过的路径点; ③ 算法旨在寻找全局最优解, 要在局部最优解的基础上获取更大的搜索区域, 实现全局寻优。

图3 禁忌搜索算法流程图Fig.3 Flow chart of tabu search algorithm

禁忌搜索算法在搜索过程中可以接受劣解, 具有较强的“爬山”能力, 可以跳出局部最优解, 转向解空间的其他区域, 从而提高获得更好的全局最优解的概率, 是具有较强搜索能力的全局迭代寻优算法[11]。然而, 在这些优点之外, 禁忌搜索算法也存在容易陷入死锁等问题。

为了禁忌搜索算法在机器人路径规划问题上的进一步应用, 研究者们作了许多优化与改进。Lee等[12]提出了基于混合禁忌搜索和2-opt路径规划的距离受限多机器人任务路径规划算法, 这是一个两阶段的启发式算法, 旨在最大限度地减少时间和能量消耗, 协调多机器人任务的路径。在第一阶段, 使用禁忌搜索算法和2-opt节点交换方法生成单一最优路径; 再根据机器人编号将解决方案分成多个集群, 作为每个集群的初始解决方案。在第二阶段, 结合2-opt路径交换的禁忌算法被用于进一步改进每条路线的路线内和路线间的解决方案。为了更好地解决未知环境下的路径规划问题, Khaksar等[13]提出了基于采样的禁忌搜索路径规划算法, 该方法是一种满足低内存和低计算要求的方法,在未知环境下基于采样的禁忌搜索路径规划算法中, 禁忌搜索部分指导采样, 在最有希望的区域找到样本, 并使采样过程更加智能。陈展等[14]提出了基于禁忌搜索的多自动导引车(AGV)系统路径优化算法, 为了满足多AGV系统的工作需要, 在任务区域内求解出符合要求的可行路径是必须解决的问题。多AGV系统的路径规划问题属于NP问题, 约束条件复杂、问题规模和求解难度大[15], 陈展等[14]将拓扑建模法与禁忌搜索算法结合, 在信息结构更加灵活简洁的地图中应用禁忌搜索算法。

Lee等[12]的算法在路径优化和算法运行时间方面都具有优势, 得出的路径更短, 更加平滑, 多个机器人之间协调完成任务消耗的能量更少。Khaksar等[13]的算法结合了禁忌搜索来实现智能采样, 在路径规划过程中使用了两种采样策略, 包括均匀采样和高斯采样, 在不同类型的环境中具有不同的效率, 得出的路径长度较其他算法更短, 运行速度更快, 在内存和计算方面要求更低。陈展等[14]的算法较传统路径规划算法具有显著优越性: 当地图规模较大、项目较为复杂时, 与其他算法相比, 规划路径所需时间更少、路径长度更短, 多AGV系统运行更加流畅, 能耗明显降低。

禁忌搜索算法与其他算法相结合后, 求解的路径在长度和平滑度等方面有明显提升。当结合适当的环境建模方法, 在更加简洁的地图上进行路径规划时, 禁忌搜索算法的死锁率也相应降低, 效率提高, 有了更明显的优越性。

1.2 局部路径规划

局部路径规划是在环境信息未知的情况下进行路径规划, 通过传感器等工具实时获取当前的环境状况, 从而进行路径规划和实时避障。目前常用的局部路径规划算法有人工势场法、 D*算法等。

1.2.1 基于人工势场法的路径规划 1986年, Khatib首先提出人工势场算法并应用于到机器人路径规划领域[16]。人工势场法的本质是将机器人在规定区域内的运动类比于在虚拟力场中的合力运动, 即障碍物对机器人产生使其远离当前位置的斥力, 目标点对机器人产生使其靠近目标位置的吸力, 机器人在虚拟力场的合力方向指引下快速逼近目标点位置。人工势场算法具有结构简洁明了、生成路径平滑易操作以及算法运行稳定的特点[17], 颇受研究人员的青睐。人工势场法的收敛速度较快, 得出的路径具有较高的可达性, 非常适合于对路径生成实时性和安全性要求较高的规划任务, 得到的规划路径是最平滑、最安全的[18]。

为了方便建立模型, 可将机器人和目标点等效为质点、将障碍物等效为圆, 建立二维势场模型, 如图4所示。机器人从起点开始, 根据合力方向确定下一个节点, 直至目标点。由此得到的一系列路径点, 整合之后就是可行路径。由于人工势场法是把所有环境信息转变为虚拟力场的斥力与引力, 忽略了障碍物的分布特点, 仅通过最后的合力指向机器人的下一个运动节点, 在复杂的现实环境中可能发生目标不可达现象, 这是人工势场法不能忽略的问题。

图4 人工势场模型中机器人受力示意图Fig.4 Force diagram of robot in artificial potential field model

针对人工势场法的不足, 研究者从不同方面提出了许多改进策略。刘义等[19]首先在算法中引入机器人与目标点相对位置这一变量, 然后将原有的斥力场函数乘以一个系数, 最终使得目标点处的斥力场函数值为0。如此一来, 不但解决了人工势场法容易陷入局部最小值的问题, 而且经过优化之后, 机器人在距离目标点较近时不再因为目标点引力减小, 障碍物斥力增强而减缓收敛速度甚至无法真正到达目标点。Azzabi等[20]针对有限环境下传统人工势场法在移动机器人路径规划时的局部极小值和障碍物附近目标不可达问题, 采用更强的吸引函数来保证机器人成功到达目标, 同时提出了一种新的排斥函数, 当检测到局部极小值时, 会激活一个虚逃逸力, 允许机器人从死锁位置逃脱, 并沿着目标方向平稳地转向, 远离障碍物。Fan等[21]基于改进的人工势场法, 提出了一种更高效率的水下机器人路径规划方法: 在排斥势场函数中加入距离修正因子来求解障碍物附近目标不可达问题, 针对局部极小值问题, 提出了正六边形引导法; 针对动态环境, 提出了运动目标检测和回避的相对速度法。该方法不仅考虑了运动物体的空间位置, 还考虑了运动物体速度的大小和方向。Zhao等[22]提出了基于改进人工势场法的评估碰撞风险的方法和避免碰撞的策略, 以解决多机器人系统协作执行给定任务时机器人之间的动态实时避碰问题。碰撞风险评估方法基于机器人的运动方向和位置, 避碰策略基于人工势场法和模糊推理系统。传统的人工势场法存在局部极小值的问题, 该算法通过改进排斥函数来优化局部极小值。为了自适应调整机器人的速度, 提高系统的安全性能, 采用模糊推理系统规划机器人的速度。

刘义等[19]主要通过修改斥力场函数对传统人工势场法进行优化, 较好地解决了传统算法中的局部最小问题, 这种优化算法构造简单, 可操作性较强。Azzabi等[20]的算法不仅能够解决局部极小值和障碍物附近目标不可达问题, 而且与其他算法比较, 所得路径长度和算法运行时间更短, 在收敛过程中不存在明显振荡, 性能更优。Fan等[21]的算法经仿真和真实环境的验证, 在水下机器人实时路径规划中具有良好的可行性和有效性, 能够准确避开障碍物, 找到最优路径。Zhao等[22]的算法为多机器人系统中的每个机器人都规划了从起始点到目标点的无碰撞平滑最优路径,并且在真实环境的比较中, 收敛速度更快、所得路径更短, 机器人更快到达目标点。

通过优化斥力场函数等方法有效解决了人工势场算法容易陷入局部最小值和障碍物附近目标不可达问题, 提高了机器人的避障率, 保障了算法在路径规划中的目标可达性。

1.2.2 基于D*算法的路径规划在A*算法的基础上, Stentz提出了一种动态路径规划算法, 即D*算法, 适用于动态环境下的路径规划[23]。算法中Open、 Close和New 3个列表分别用来存储未经访问的节点、已经访问的节点以及待更新节点的路径代价, 并用A、B、C来表示[24]。

在利用 D*算法进行路径规划的过程中, 机器人如果遇到障碍物, 需要重新寻找可行路径以达到避障的目的时, 算法能够从存储了路径点信息的3个列表中找到当前点和已规划路径的具体信息, 从而可以快速找到新的可行路径以确保目标可达。D*算法具有极佳的实时性, 使其更适合复杂环境下的动态路径规划[25]。但是, D*算法通常在较大空间范围内搜索可行路径点, 使得算法的收敛速度无法令人满意。

为了解决D*算法存在的问题, 研究者们结合其他算法对D*算法进行优化。张希闻等[26]使用拓展Moore型元胞邻居结构来优化路径长度, 结合跳点搜索算法来减少搜索时间, 较原D*算法收敛更快、所得路径更短。张贺等[27]采用改进D*算法与A*算法、动态窗口法(DWA)相结合, 切实提高了算法的效率和实时性。Maurovic等[28]为了在自主探索未知环境时提高定位精度, 要求机器人重新访问以前看到的位置, 为此提出了一种主动式定位与地图构建(simultaneous localization and mapping, SLAM)的路径规划算法, 该算法在机器人平稳、不间断地向目标位置移动的同时, 不断提高机器人的定位精度, 基于D*最短路径搜索算法可用于定位不确定性的情况下寻找最短路径。

张希闻等[26]改进后的D*算法规划得出的路径较传统算法长度更短、遍历节点减少, 具有较好的可操作性和实用性, 同时路径更为平滑。张贺等[27]改进的D*算法通过栅格更新的路径重规划方法在路径避障效果上有了明显提升, 在地图中只有受障碍物影响的栅格需要进行重新处理, 机器人的避障能力显著提高, 算法的性能也有了质的提升。Maurovic等[28]的主动式SLAM路径规划算法能够有效处理环境中的动态变化信息, 包括移动障碍物和机器人移动时可能出现的定位需求。在真实环境的测试中, 机器人的路径是连续的, 当定位点出现时, 机器人的速度不会快速改变, 这使得机器人运动更快, 探索更快, 同时提高了定位的准确性; 当动态障碍物出现时, 最短路径仅局部改变, 从而确保了机器人到达目标位置所需的时间不发生明显变化。

通过改进算法结构和结合其他算法, D*算法在路径规划上的收敛速度、实时性和避障能力有了明显提高, 在实际环境中的应用也不断拓宽。

2 智能仿生算法路径规划

智能仿生算法是一类模拟自然生物进化或者群体社会行为的随机搜索方法, 由于其求解时不依赖梯度信息, 故而广泛应用于路径规划等实际问题[29]。智能仿生算法主要包括蚁群算法、遗传算法以及粒子群算法等。

2.1 基于蚁群算法的路径规划

蚁群算法 (ant colony optimization)首次出现于意大利学者Marco Dorigo于1992发表的博士论文中, 其脱胎于自然界中的蚂蚁因觅食需要而寻找前往食物源的最优路径的行为[30]。算法具有的创新性和正反馈机制优势使其广泛应用于路径规划问题, 同时, 算法具有较强的鲁棒性, 输出不易受外部扰动的影响。

蚂蚁在外出觅食的途中, 更倾向于选择信息素浓度较高的路径, 由此形成了一种正反馈机制, 这条路径也就演变成了蚂蚁前往食物源的最优解路径[31]。蚁群系统的基本结构如图5所示, 算法的两个关键过程为状态转移和信息素更新[32]。

图5 蚁群系统结构图Fig.5 Structure diagram of ant colony system

状态转移概率可表示为

(1)

其中:τij为节点i到节点j之间路径的信息素浓度;ηij为启发函数;dij为节点i到节点j的欧氏距离;α为信息素启发因子, 表示信息素浓度对状态转移概率的影响;β为期望启发因子, 表示路径信息对状态转移概率的影响[33]。

信息素更新可表示为

τij(t+1)=(1-ρ)*τij(t)+Δτij(t),

(2)

其中:ρ为信息素挥发系数; 1-ρ则表示信息素残留系数; Δτij为本轮迭代中节点i到节点j之间路径总的信息素浓度增量[34]。

蚁群算法最早应用于旅行商问题, 并逐渐在其他领域得到广泛实践与改良。在机器人路径规划、交通拥堵状况下的车辆动态路径规划及公众场所人群疏散等多个领域, 都取得了令人满意的结果[35-37]。蚁群算法应用于机器人路径规划分为初始化、解构建和信息素更新3部分[38]。蚁群算法可以与其他算法进行有机结合, 从而优化其收敛速度慢和容易陷入局部最优解问题。

赵娟平等[39]为解决算法可能陷入局部最优解的问题, 引入差分演化算法和混沌扰动因子改良算法中的信息素更新方式, 再根据障碍物分布的复杂程度、路径平滑需要以保证机器人转向方便以及距离最短等指标提出了新的综合评价函数。Yang等[40]结合并行计算方法和精英策略, 提出了并行精英蚁群算法: 先生成初始可行路径, 扩大了蚁群的搜索多样性, 加快了收敛速度, 并在此基础上加入了拐点优化算法——分段b样条插值算法, 使得路径更加平滑, 由此组成了稳定性更好、路径更短更平滑、环境适应性更强的双层蚁群优化算法(DL-ACO)。Luo等[41]针对蚁群算法存在的局部最优、收敛速度慢、搜索效率低等问题, 提出了一种改进的蚁群优化算法: 在路径规划初期构建了不等分配的初始信息素, 避免了早期规划时的盲目搜索; 同时, 采用伪随机状态转移规则选择路径, 并根据当前最优解和迭代次数计算状态转移概率, 自适应调整确定或随机选择的比例; 此外, 引入最优解和最差解来改进全局信息素更新方法, 引入动态惩罚方法解决死锁问题。Chen等[42]为了克服蚁群系统在求解机器人路径时的全局优化能力不足, 容易陷入局部最优解的缺点, 提出了融合分流分层混合神经网络算法(SHAA)的自适应蚁群算法: 为了综合考虑算法的全局搜索能力和收敛速度, 提出了动态自适应信息素挥发系数; 同时, 将SHAA算法的激活值概念引入到原启发函数中。

赵娟平等[39]设计的算法在保证收敛速度的前提下提高了算法的创新性, 且保证算法可以得到全局最优解, 将混沌扰动因子引入算法的信息素更新方式中, 使得算法不会轻易陷入死锁现象; 此外, 采用了综合考虑环境中多种复杂因素, 而不仅仅只以最短路径为标准的多目标评价函数, 在实际的复杂环境中算法也能规划出行之有效、令人满意的路径。Yang等[40]的算法采用双层计算结构, 具有良好的稳定性, 每次都能提供良好的可行解, 鲁棒性较强, 且当机器人在平滑路径上跟踪时, 可以避免颠簸, 简化运动控制。Luo等[41]的算法在多种模拟环境中与其他路径规划算法进行比较, 证明了该算法的有效性和优越性, 并且在障碍物越复杂的环境, 算法的收敛速度越是快于其他算法, 不易陷入局部最优解, 有较强的鲁棒性。Chen等[42]的算法不仅保证了在各种简单障碍物环境下路径的优越和收敛速度, 而且在复杂环境下也具有良好的全局搜索能力和鲁棒性。

蚁群算法通过与其他算法的结合, 更好地解决了算法在实际环境中进行路径规划时存在的死锁现象、收敛速度慢和局部极值问题, 使得算法的可信赖程度大大提高。

2.2 基于遗传算法的路径规划

遗传算法最早是由美国的 John Holland于20世纪70年代提出, 是根据自然界中的生物进化规律, 模拟其自然进化过程而搜索最优解的一种算法, 是一种基于自然选择和自然遗传的全局优化算法[43]。在进化过程中, 遗传算法主要进行选择、交叉、变异3种操作, 经过编码的一个字符串对应一个可行解, 遗传算法的操作主要是针对多个可行解组成的群体进行[44]。

1)选择: 将父代个体的信息不作改变地复制传递给子代。每个个体对当前环境的适应度存在差异, 在复制过程中, 适应度值越高的个体被选中复制的概率越大, 这一原则体现了自然界的优胜劣汰法则, 使得群体中的优秀个体所占比例不断提高。随着迭代的进行, 适应度值越高的路径越容易被保存, 整体路径不断优化。选择操作采用轮盘赌方式进行

(3)

其中:Pi为第i名个体被选中复制保存的概率;fi为第i名个体的适应度值。

2)交叉: 主要使得同一代不同个体间的部分基因进行交换, 产生不同基因组合的新个体, 有别于选择操作的单纯复制, 在择优的基础上进一步催生更加优秀的个体。将交叉操作应用于路径规划问题时, 有利于产生新的路径, 在面对复杂环境或动态障碍物时能有更多选择。在进行交叉操作之前, 要确定交叉概率Pc, 之后随机生成概率Pi,Pi∈(0, 1), 如果Pi

3)变异: 可使个体的基因型发生突变, 从而提供更多的基因组合。上述两种操作的实质是择优和重组, 是在较小范围内寻找最优解, 而变异操作增加了基因型种类, 使得排列组合有了更多可能性, 算法的寻优范围进一步扩大。应用于路径规划时, 变异操作可以增、删某个路径点或者移动该路径点, 从而获得避开障碍物的新路径, 但是变异操作具有一定的不确定性, 所获得路径的适应度值有提高或降低的可能。

在进行变异操作之前, 要先确定变异概率Pv, 之后随机生成概率Pj,Pj∈(0, 1), 如果Pj

图6 遗传算法流程图Fig.6 Flow chart of genetic algorithm

遗传算法的适应度函数可表示为

(4)

其中:D为当前规划路径的总长度;N为路径穿过的栅格数, 规划路径越短, 则穿过的栅格数越少, 对应的适应度值f越大, 该路径被选中保存至下一次迭代的概率越大[46]。

然而, 遗传算法局部搜索能力较差、易早熟、易陷入局部最优的缺陷, 促使了大量学者对遗传算法进行优化与改进。Hao等[47]提出了基于多种群迁移遗传算法的移动机器人路径规划。该算法将一个较大的种群随机划分为若干个种群数目相同的小种群, 利用种群间的迁移机制代替选择算子的筛选机制, 对交叉算子、变异算子等操作也进行了改进。Karami等[48]提出了二维复杂环境下机器人运动规划的自适应遗传算法, 设计了一种新的选择算子,在每次迭代中, 如果需要, 将通过使用来自适应度函数值的标准偏差的反馈信息来更新选择性压力。Chen等[49]提出了基于自适应遗传算法的足球机器人路径规划, 主要改变了遗传操作中的交叉概率和变异概率。

Hao等[47]的算法通过使用新的算子或改进原有算子, 打破了局部最优解, 解决了种群个体严重同质化的现象, 加快了算法的收敛速度, 提高了收敛个体的质量, 其不仅适用于各种比例尺和各种障碍物分布的仿真地图, 而且性能优越。Karami等[48]的算法用自适应选择算子代替了遗传算法中传统的选择算子, 自适应选择算子通过使用搜索过程的反馈信息, 即个体适应值的标准偏差, 在整个算法运行过程中适当地控制选择压力; 此外, 选择算子通过使用其新颖的自动调整过程来防止过早收敛, 个体的多样性被很好地保存, 将所提出的自适应选择算子引入遗传算法切实提高了求解质量。Chen等[49]的自适应遗传算法收敛速度明显提高, 求解的路径实现了即时的避障行为, 优于传统的遗传算法。

针对遗传算法, 通过新的机制代替原有的选择算子或结合自适应算法改变遗传操作中的交叉概率和变异概率, 改善了其局部搜索能力较差、易早熟和易陷入局部最优的缺陷, 进一步增强了算法的鲁棒性和扩展性。

2.3 基于粒子群优化算法的路径规划

粒子群算法是1995年由美国的心理学家Kenndy和电气工程师Eberhart首次提出来的一种集群优化算法。粒子群优化算法起源于对自然界中鸟群、鱼群觅食行为的研究, 并通过模拟群觅食行为中的相互合作机制寻求问题的最优解[50-52]。算法首先初始化分布在解空间中的粒子, 然后粒子经过迭代寻找到全局最优解。在迭代过程中, 粒子依据两个极值来更新自身的速度和位置: 一是粒子个体极值(pbest), 二是解空间中的群体极值(gbest)。每个粒子都时刻更新速度, 以求搜索到全局最优解。设解空间为n维, 则第i个粒子在时刻t的位置、速度为

xi(t)=[xi1(t),xi2(t), …,xin(t)];

(5)

vi(t)=[vi1(t),vi2(t), …,vin(t)];

(6)

vi+1(t+1)=wvi(t)+c1r1(pbesti(t)-xi(t))+

c2r2(gbesti(t)-xi(t));

(7)

xi+1(t+1)=xi(t)+vi+1(t+1)。

(8)

其中:w为惯性权重系数, 它决定了上次迭代速度保留的多少, 取适当值可以保证粒子的均衡发展和探索能力;c1和c2为学习因子, 用于调控算法的局部收敛性;r1和r2为[0, 1]间分布的随机数, 用于增加种群多样性[53]。

粒子群算法具有结构简单、参数简洁以及容易实现等优点, 因此, 被广泛应用于解决路径规划等问题。粒子群算法应用于机器人路径规划问题的流程如图7所示。其中, 每个粒子代表一条可行路径, 粒子的维度分量则对应该路径上各节点与起始点至目标点连线的距离。

图7 粒子群算法流程图Fig.7 Flow chart of particle swarm optimization

粒子群算法虽然在路径规划问题上得到广泛应用, 但是其本身也存在缺点: ① 算法比较容易陷入局部最优解; ② 算法的收敛速度随着迭代次数和搜索范围的增加而不断变慢, 甚至最终停滞; ③ 算法开始时的参数设定大多是依据经验, 具有一定的不确定性。

为了提高粒子群算法在求解路径规划问题上的可靠性, Wang等[54]提出了基于多目标粒子群优化算法的粗糙地形类车移动机器人路径规划方法: 先用一种新的工作空间建模方法对粗糙地形环境进行建模, 寻找长度和地形粗糙度最小的无碰撞可行路径; 然后, 考虑类车机器人的非完整约束, 采用基于多目标粒子群优化的方法进行求解; 最后, 采用一种新的基于拥挤半径的粒子全局最优位置更新方法来增加种群多样性, 当路径与障碍物发生碰撞时, 采用非均匀因子来更新粒子的位置。Lian等[53]提出了基于3次样条插值的混沌自适应粒子群算法的机器人路径规划方法: 选择多个路径节点作为3次样条插值的控制点, 通过在起始点、控制点和目标点的路径上插值, 形成光滑路径; 采用甲虫觅食策略对粒子群算法的位置更新方程进行了修正; 用三角函数对优化算法的控制参数进行自适应调整; 在算法开始时, 粒子以较大的速度步长在全局范围内搜索; 搜索后期, 粒子围绕极值点进行精细搜索; 利用混沌映射代替粒子群算法的随机参数, 提高了粒子群算法的多样性, 保持了原有的随机特性。Wang等[55]提出了基于改进量子粒子群算法的水下机器人离线路径规划方法: 采用球面建模方法将不规则水下障碍物表示为具有特定半径的球体; 针对传统粒子群优化算法在收敛和优化能力上的局限性, 提出了量子粒子群优化算法, 并对水下机器人的最佳路径进行了识别; 通过构造适应度函数以满足路径安全、路径长度和路径点角度变化3个因素的约束; 此外, 利用3次样条插值算法对路径进行了光滑处理。Zhang等[56]提出了基于改进局部粒子群算法的移动机器人路径规划方法: 首先, 改进了惯性权重、加速和定位因子; 其次, 采用的扩展高斯分布增加了粒子的多样性, 而多样性的增加可以帮助克服算法早熟的缺点; 最后, 将平滑原理应用于路径规划。

Wang等[54]的算法在仿真环境下较其他算法有最短的可行路径, 且路径最为平缓, 性能最优。当工作空间较大且环境较为复杂时, 算法也不易陷入局部极小值, 可以搜索到全局最优解, 能够满足粗糙地形的路径规划要求。Lian等[53]的改进提高了传统粒子群算法的全局搜索能力和收敛速度, 实现了静态环境中的机器人最优路径规划。该算法在不同环境中均具有较好性能和较强的鲁棒性, 与其他路径规划算法相比, 解得的路径更短、更平滑。Wang等[55]提出的方法不需要对三维环境进行网格建模, 节省了时间, 降低了计算成本, 具有更大的灵活性, 显著提高了传统算法的收敛性和优化能力。在不同的实验环境下, 该算法较其他算法具有更强的路径规划能力和更高的稳定性, 并能更快地收敛到最优解。Zhang等[56]的算法能够快速找到最优路径, 具有较高的精度和鲁棒性, 在复杂、大规模和三维环境中也具有一定的有效性。

粒子群算法结合其他策略对位置更新方式的改进, 极大提高了算法的全局搜索能力和收敛速度。算法经过特定函数对参数的调整, 具有了更强的局部搜索能力, 鲁棒性和灵活性有了明显提升。