遗传算法在机器人路径规划中的研究综述

李少波， 宋启松， 李志昂， 张星星， 柘龙炫

(贵州大学机械工程学院，贵阳 550025)

从20世纪60年代起，科学家们就开始对机器人进行研究，到现在为止机器人已经在工业生产，交通，医疗等领域得到广泛应用。机器人路径规划是机器人领域的一个关键任务，即在各种场景中寻找从起始位置到目标位置耗时最少，路径最短，无碰撞且最优的路径[1]。

对机器人路径规划的研究一直是中外智能机器人研究的关键内容。从目前的相关研究分析可知，各种智能算法已广泛应用在机器人路径规划研究中并取得了阶段性的进展，这些智能算法包括遗传算法、蚁群算法、粒子群算法、模糊算法、神经网络算法、人工蜂群算法、A*算法等。

现综合相关文献，全面介绍各类遗传算法在机器人路径规划中的研究进展，并对未来发展方向做出展望，为遗传算法在机器人路径规划的推广应用提供相关资料。

1 遗传算法

通过查阅机器人路径规划研究相关文献，将2015年至2019年6月的EI(工程索引)和SCI(科学引文索引)论文数量等进行比较如图1所示。

图1 智能算法论文数量对比

从图1可以直观地看出，近5年来对机器人路径规划的研究中以遗传算法论文数量最多，粒子群算法、蚁群算法、模糊算法和神经网络算法次之，人工蜂群算法最少。结果表明遗传算法在机器人路径规划中研究最多，应用最广，是当今机器人路径规划研究的主流，极具发展前景。

1.1 遗传算法特点

遗传算法是一种通过模拟自然进化过程搜索最优解的方法，与其他应用于机器人路径规划的智能算法相比，遗传算法应用更广，使用更频繁，优点更明确。遗传算法的优点和缺点见表1。

表1 遗传算法优缺点对比

1.2 遗传算法类型

遗传算法类型众多，中外研究人员在基本遗传算法基础上提出更多改进算法，这些遗传算法的分类如图2所示。其中，混合遗传算法是遗传算法与其他智能算法结合而形成的，包含遗传-蚁群混合算法、遗传-粒子群混合算法、遗传-人工蜂群混合算法、遗传-模拟退火混合算法、遗传-神经网络混合算法、模糊遗传算法、混沌遗传算法等。

图2 遗传算法类型

2 路径规划

2.1 路径规划类型

根据机器人关于环境的认识，路径规划可分为两类：第一类机器人具有被建模为地图的环境的先验知识，因此可以基于可用地图计划路径，此类路径称为全局路径规划[2]，全局路径规划属于静态规划；第二类路径规划假设机器人没有环境的先验信息，因此它必须感测障碍物位置并在搜索过程中实时构建预估的环境地图，以避开障碍物并获取朝向目标位置的合适路径。此类路径称为局部路径规划[3]，局部路径规划属于动态规划。

根据研究环境的信息特点，路径规划还可以分为离散域范围内的路径规划和连续域范围内的路径规划，离散域范围内的路径规划属于一维静态优化问题，即环境信息简化后的路线优化问题，而连续范围内的路径规划问题则是连续性多维动态环境下的问题。

2.2 路径规划步骤

路径规划的一般步骤为环境建模，路径搜索，路径平滑，而遗传算法在机器人路径规划中的步骤如图3所示。

图3 遗传算法路径规划流程图

2.2.1 地图的建立和种群编码

编号与坐标转换公式为

x=int(N/Gsize)+1

(1)

y=N%Gsize+1

(2)

式中：Gsize为每行栅格数；int为取整操作；N为栅格总数；x、y为坐标。

2.2.2 初始化种群

栅格连续判别方法为

d=max{abs(xi+1-xi),abs(yi+1-yi)}

(3)

式(3)中：d为相邻两点距离，如果d=1,则栅格连续，否则不连续。

2.2.3 适应度函数计算

适应度函数公式为

(4)

式(4)中：D为路径总长度；f为适应度函数。路径越短，栅格数目越少，适应度值越大。

2.2.4 选择方法

采用基于概率的轮盘赌方法为

(5)

式(5)中：Pi为个体概率；fi为个体适应度。

2.2.5 交叉方式

确定交叉概率Pc，产生0～1随机数P，若P

2.2.6 变异方式

确定变异概率Pm，产生0～1随机数P，若P

3 应用领域

3.1 导航领域

3.1.1 无人机

针对无人机导航中迂回问题，中国Li等[4]采用分层遗传算法评估任务区内威胁源，自动缩小迂回范围。结果表明，能以较低代价获得较短路径，并有效减少绕行，但未能解决迂回中时间较长问题。美国Von Moll等[5]采用改进染色体编码的遗传算法减少周期性重复行走所有站点所用时间。

针对无人机在不确定性环境中导航问题，巴西Arantes等[6]采用多种群遗传算法与可见性图结合来规划导航路线进而降低风险，并对无人机紧急迫降导航进行模拟[7]，但可靠性不高，仅停留在理论层面。中国对多维复杂环境中固定翼[8]无人机导航进行多次仿真，结果表明，能在实际中生成可靠性极高的威胁规避路径。

3.1.2 车辆

针对交通拥堵问题，突尼斯Chebbi等[9]采用遗传算法对实际交通问题的参数进行整定，但未能应用到实践中。中国He等[10]将遗传算法应用到基于全球定位系统(GPS)和地理信息系统(GIS)的车辆导航监控系统，从而实现对车辆的精确定位和实时指挥，为车辆规划合理路线，缓解城市交通道路网的拥堵。

针对无人驾驶汽车安全性问题：日本Kurosaka等[11]将模糊逻辑和遗传算法相结合应用于无人驾驶导航中，但未解决安全性问题，且技术性不强。中国对无人驾驶汽车导航系统进行了深入研究，可在现实环境中实时自动导航和避障，安全性能高[12]。姜勇等[13]还将遗传算法和反向传播神经网络相结合应用于地下无人驾驶汽车导航中，可以模拟人输出行为进行控制，自适应能力强，前沿性高。

3.1.3 帆船和水下机器人

针对海上复杂多变环境导航问题，俄罗斯Yanchin等[14]采用并行遗传算法在复杂海道上建立船舶最优航线。中国Liu等[15]提出基于遗传算法的避碰决策方法，具有较低的避碰成本，可应用于导航实践。巴西Santos等[16-17]采用遗传算法对多艘帆船逆风情况下的航向和初始路径进行优化，设计出导航中的短期路径规划。

针对水下导航控制精度问题：中国张磊[18]采用遗传算法优化模糊控制器控制精度，减少航速误差，使水下机器人在海流干扰的导航中仍具有更好的稳定性。杨帅等[19]将分数阶技术和遗传算法相结合对航向控制器控制参数进行自动整定，实用性强，鲁棒性好。

3.2 探索领域

3.2.1 太空探索

中内外学者都对太空探索做了深入的研究。其中，日本Uwano等[20]提出探索偏向遗传算法对月球表面进行持续探测。韩国Jung等[21]采用多目标遗传算法优化火星探测飞机的低雷诺数翼型的阻力系数。中国Liu等[22]采用非显性排序遗传算法来优化月球探测器的减震器，从而使月球探测器着陆稳定性得到改进。印度Raja等[23]采用遗传算法规划出六轮火星车在粗糙地形中穿越各种障碍的最安全最优路径。美国Mott等[24]采用遗传算法优化火星轨道参数，实现机器人实时导航和通信定位。现阶段对太空探索未取得太大成效，但机器人对太空探索仍然具有潜在价值。

3.2.2 搜索与救援

(1)空中搜救:奥地利Hayat等[25]将遗传算法应用于多目标无人机搜索和救援，可缩短区域覆盖和与地面网络连接的时间，结果表明，随着无人机数量增加，总体任务完成时间可缩短65%。但通信信号在未知环境中可能会消失，因此，需要增强信号的连通性。

(2)陆地搜救：中国Zhu[26]将多种群遗传算法应用于带有履带机构的车辆，使其进行复杂曲线跟踪，能适应更加复杂的搜索和救援环境。这种搜救方式速度较慢，在履带车辆速度方面需加以改进。

(3)矿井搜救：中国Bai等[27]将遗传算法和模糊神经网络相结合应用于具有4个正交关节的煤矿救援蛇形机器人，提高了定位精度，能更好地获取煤矿井下人员的方位信息。但搜救范围较窄，应增大机器人路径覆盖范围。

现阶段，遗传算法在搜索和救援领域取得了很大进展，不仅可以进行上述搜救，还可进行海上群体搜救、城市搜索救援等。

3.2.3 环境探索

(1)未知环境：印度Bhargava等[28]采用遗传算法、实时强化学习和控制器协作的机器人对未知环境进行探测，这种方法能耗较小，速度较快，但不能灵活应对环境中出现的各种障碍物。美国Gunasekaran等[29]先用超声波-激光传感器探测未知环境与障碍物距离，再用遗传算法规划机器人路径，可以精确避障。目前在未知环境探索中机器人实时信息反馈极为关键，需要深入研究。

(2)复杂环境：沙特阿拉伯Alsouly等[30]采用智能交叉遗传算法优化静态和动态环境中的搜索过程，结果表明，此算法比静态中的A*算法和动态中的改进遗传算法在环境搜索的执行时间上更加快速，但耗能较大。马来西亚Samadi等[31]采用改进遗传算法解决复杂环境下距离，安全性，能量问题，使机器人路径轨迹最短，安全性最高，耗能最少。

3.3 农业领域

遗传算法不仅可以对农业产值进行预测，还可以对农业机器人进行路径规划，能节省时间，提高效率。目前，国内外已将遗传算法广泛应用在农业机器人路径规划中。

(1)国外：针对精密农业环境存在凹面障碍物的问题，法国Pham等[32]采用遗传算法最大限度的实现覆盖路径规划并缩短机器人路径长度。针对温室内农药喷洒作业路径规划问题，美国Mahmud等[33]设计虚拟温室环境，采用非支配排序遗传算法规划移动机器人最佳路径。

(2)中国：目前在采摘机器人上应用广泛，Liang等[34]采用遗传算法优化滑模控制，大大提高采果机器人位置跟踪的响应速度，减小位置偏差，使控制系统能跟踪到预期轨迹。Zou等[35]采用非线性规划遗传算法调整西瓜采摘机械臂采摘路径和姿态，减少对西瓜的不必要损伤。Cao等[36]采用遗传算法对荔枝采摘机器人生成的避障路径进行平滑处理，可使路径长度缩短20%。Hu等[37]用遗传算法对高速插秧移栽机器人进行尺寸综合，使其可达工作空间接近需要的工作空间，提高了插秧成功率。

3.4 医疗领域

遗传算法不仅可以应用在医学图像加密，去噪，还广泛应用于手术机器人的路径规划，目前已经取得了突出成就。

(1)国外：美国Wang等[38]采用非支配排序遗传算法等多种进化算法来优化机器人配药路径轨迹，使多机器人在互不干扰的情况下以最短的路径来抓取药物。意大利Stroppa等[39]使用遗传算法求解多边形拟合问题，应用于患者的神经康复。韩国Nguyen等[40]采用遗传算法来解决外科手术机器人系统布局和路径规划问题，使机器人末端执行器与解剖位置偏差降低到毫米级别。印度Roy等[41]采用遗传算法优化脑电控制机器人手臂运动轨迹，使运动障碍患者使用脑电图信号来灵活控制机械臂的活动。

(2)中国： Niu等[42]采用非支配遗传算法来解决微创手术中多机器人碰撞问题，优化了机器人运动学性能指标和刚度指标，提高了绝对位置精度和重复位置精度。Ye等[43]采用改进遗传算法和改进概率路标法结合来解决非共面辐射治疗，可在紧凑区域内与放射治疗系统配合，避免碰撞并节省时间。Liu等[44]采用遗传算法优化猪腹截面轨迹，还可跟踪尸体腹腔切割的轨迹。结果表明，该方法不会产生明显损伤，提高了效率和质量。

3.5 工业领域

3.5.1 工业车间调度

一组作业在多机器人之间运输是个非确定性困难(non-deterministic polynomial hard，NPH)问题，针对这个问题，中外提出了不同的解决方案。

(1)国外：突尼斯Nouri等[45]将基于邻域的遗传算法应用于搜索空间的全局搜索，使机器人动态规划操作更加简单，但消耗时间较长。伊朗Zabihzadeh等[46]将基于双信息素的蚁群算法和遗传算法相结合来提高机器人运动速度，缩短零件转移时间，从而解决耗时较长。

(2)中国：在多机器人制造单元车间调度中，Yang 等[47]采用遗传算法构建多机器人运输关键运动路径，尽量减少最大运输时间。

3.5.2 焊接机器人

(1)国外：韩国Thao等[48]采用遗传算法来预测自动气体金属弧焊的运动轨迹并生成智能模型，效率不高。南非Ogbemhe等[49]采用遗传算法等智能方法对焊接机器人进行焊缝跟踪和轨迹规划，但误差较大，精确度不高。

(2)中国：Wang等[50]采用双全局最优遗传算法-粒子群算法来解决多焊接接头路径规划困难问题，但难以获得最佳路径。Shen[51]采用遗传蚁群混合算法解决焊接机器人路径规划中收敛速度和优化度之间的矛盾，已取得良好的应用。Tong等[52]采用遗传算法和离散粒子群优化算法来优化焊接路径，可提高效率并降低成本。

3.5.3 其他工业领域

遗传算法还可以应用于表面双层喷涂[53]，比单层喷涂更加均匀；应用于工业机械臂[54]，可减少能耗；应用于码垛机器人[55]，可优化关节轨迹进而消除抖动。

3.6 物流领域

现今，物联网迅猛发展，物流作为新兴行业在世界各地得到快速发展，以货物运输和车间自动导引小车(automated guided vehicle, AGV)为代表。

3.6.1 物流运输

(1)国外：针对货物运输中集装箱装卸问题，土耳其Erdem[56]采用遗传算法生成货物装载到集装箱的最大适应数量，从而降低运输成本。针对复杂物料供应量问题，丹麦Nielsen等[57]采用遗传算法来提高机器人运输效率，用于解决大规模问题。

(2)中国：针对运输系统车辆调度问题，Li等[58]将遗传算法和贪婪算法相结合，规划车辆路径轨迹，能有效缩短车辆响应时间。针对行走运输机器人快速移动能耗过大问题， Zhu等[59]采用遗传算法规划行走机器人移动轨迹中的过渡角，进而降低系统能耗，在运输机器人户外操作中有重要意义。

3.6.2 AGV小车

(1)国外：马来西亚Umar等[60]采用混合多目标遗传算法生成完整的AGV动态调度路径和详细的路由路径，并优化了AGV作业延迟时间。

(2)中国：针对多AGV路径规划问题，Cheng等[61]采用改进的小生境遗传算法，设计出三种无碰撞优化路径。Liu等[62]将遗传算法结合到多AGV系统中，对多AGV进行离线和在线两个阶段的路径调度，改变其速度和路径，使其运动协调一致。中国学者还对AGV在静态环境和动态环境下的路径轨迹优化进行了相应研究。

3.7 军事领域

遗传算法在军事领域也有一些关键性的应用，目前，中外都将其应用在无人机的军事活动中，且取得了不俗的成就，但也仍有缺陷需要改进。

(1)国外：针对缺乏可靠通信网络的未知遥远环境，美国Mousavi等[63]采用量子遗传算法行成大规模军用无人机联盟，合理规划无人机的任务和最短路径，减少资源消耗。针对高维动态环境，加拿大Roberge等[64]采用遗传算法实时快速调整军用固定翼型无人机最优安全路径轨迹，最大限度降低能耗和平均飞行高度，避免被敌方雷达探测到。针对复杂多变战场环境，西班牙Ramirez-Atencia等[65]针对复杂多变战场环境，将多目标遗传算法应用于无人机和地面联合军事系统中，规划地面车辆位置和行动，但难以规划出最优路径。

(2)中国：针对日益复杂的战场环境，Cao等[66]采用遗传算法在探测到敌方雷达的最小停留时间内，进行最短路径组合优化，从而实现不同基地多无人机协同侦察。

3.8 其他领域

遗传算法不仅在以上领域取得突破性进展，在其他领域内也有相应的一些成就。在不同类型机器人路径规划上也有广泛应用，如轮式机器人、柔顺机器人、娱乐机器人、仿生机器人等。

4 路径规划技术难点

4.1 最短路径问题

在路径规划中，最短路径问题是现阶段的一个技术难点，通过改进遗传算法中的编码方式、适应度函数、选择算子可规划出最短路径。

4.1.1 编码

(1)实数编码：直接用实数表示基因，容易理解且不需要解码过程，但容易过早收敛，从而陷入局部最优。因此，应减缓陷入局部最优的速度，在过早收敛方面需要加以改进。

(2)二进制编码：稳定性高，种群多样性大，但需要的存储空间大，需要解码且难以理解。因此，在降低解码难度和释放存储空间方面需要加以改进。

对于路径优化问题，现阶段一般有以上两种编码方式，但其各有利弊，可以考虑将两种编码方式相结合来提高路径优化的能力。

4.1.2 适应度函数

适应度函数是遗传算法进化的驱动力，也是进行自然选择的唯一标准，适应度函数值越大，解的质量越高。现阶段，传统适应度函数值很难增加，路径优化能力有限，应当提出新的适应度函数来提高优化能力，在机器人路径规划优化中应结合路径轨迹自身的要求选择相应的适应度函数。

4.1.3 遗传算子

(1)选择：遗传算法中，最优个体的保留是现阶段的一个难点。传统轮盘赌选择方法具有随机性，在选择过程中可能会丢掉较好的个体，使用精英保留机制可将前代最优个体直接选择，更多类似精英保留机制的选择方法是未来研究的重点。

(2)交叉：遗传算法中，待交叉的染色体交换部分基因的序列具有不确定性。在交叉过程中需要提高甄别最优基因序列的能力，尽量选取父代染色体中最优基因进行交叉。优秀基因最大覆盖的交叉方式是未来研究的重点。

(3)变异：遗传算法中，变异方法产生优秀后代的可能性极低，因为变异不确定性极大，不一定能产生最优基因。因此应尽量减少变异概率，使用优秀基因进行变异操作。采用变异提高种群多样性是未来研究的重点。

4.2 最少耗时问题

在路径规划中，最少耗时问题是现阶段另一个技术难点。路径规划中消耗时间的长短主要取决于遗传算法生成路段数量、拓扑数据读取效率、临时表排序效率这三部分。耗时问题研究如图4所示。

图4 耗时问题研究

4.2.1 分区规划

在路经规划中，遍历的路段越多，耗时越大，将路段划分成相对独立的起点区域、中间区域、终点区域。先采用正向邻接表对起点区域进行规划，逆向邻接表对终点区域进行规划，然后再对中间区域路线进行规划，最后整合路线。这样既可获取近似最优路线，也可避免路线冗余。

在分区规划中，采用升降级机制如图5所示，起点区域总体向上升级，即低等级路段过渡到高等级路段；终点区域总体向下降级，即高等级路段过渡到低等级路段；中间区域总体上保持高等级路段。此方式可有效减少遍历路段数量，提高规划效率。

图5 分区规划升降级机制

4.2.2 抽象层规划

在路径规划中，拓扑数据读取效率越高，越能节省时间。采用抽象层规划将拓扑数据分成主干、枝干、详细三个层次，可逐层快速读取拓扑数据。难点在于如何抽象以及三层次之间的连接。现阶段可根据路段等级进行抽象层划分，至于层次间连接，则主要是高低级路段的映射关系。

在抽象层规划中，可利用机器对机器(machine-to-machine，M2M)思想处理抽象层联通问题，如在图幅内进行连通性分析或者以图幅为最底层，用图幅出入度构建图幅连通拓扑关系。抽象层之间联通与映射是未来研究的重点。

4.2.3 排序方法

在路径规划中，临时表排序效率易被忽视，应加以重视，常用排序方法有冒泡排序、斐波那契堆、最小堆。其中，堆排序方法效率较高，而斐波那契堆和最小堆的效率高低在不同场景的路径规划中有变化，应根据场景自动调整排序方法。

4.3 实时性问题

在路径规划中，实时性问题是现阶段丞待解决的难点。路径规划过程中遇到的外界环境在不停变化，障碍信息需要实时反馈给机器人，可通过传感器和运动控制器来实时规划路径。

4.3.1 传感器

在路径规划中，基于传感器数据进行实时规划，首先采用“双向搜索多边形构造”搜索出复杂障碍物的包围多边形，然后以包围多边形顶点构造基于障碍物和机器人关系的可视图，以可视图为基础进行实时路径规划。

4.3.2 运动控制器

在路径规划中，将最优行进路径中的第一个节点定义为控制器目标点。目标点对机器人产生吸引势，障碍物产生排斥势，以吸引势和排斥势构成矢量和输入条件计算出机器人行进速度和转角。在此输出控制基础上实时调整自身姿态，从而逃避障碍物走向目标点。

5 结论和展望

随着机器人的广泛应用，遗传算法在路径规划中已经取得了大量的研究成果，但是遗传算法仍然存在许多问题，在理论和应用研究方面还有进一步的发展空间。根据近些年来相关资料总结，未来发展主要集中在以下几个方面。

(1)混合算法：遗传算法及其他智能算法都有其局限性，但这些算法之间具有互补性。针对实际路径规划中出现遗传算法难以解决的新问题，可将遗传算法与其他智能算法相结合，乃至两种或则三种算法相结合，取长补短，从而产生一系列更优秀的混合算法，解决更多难题。目前中外的一些学者正在不断地发掘不同的混合算法来解决实际路径规划难。

(2)未知复杂环境应用：目前中外在高维动态复杂环境下机器人路径规划方面的研究较少，在未知环境下进行路径规划面临巨大挑战，但也极具前景。在未来，星际探索、军事战争、交通领域等都是在未知复杂的高维空间下进行，会存在很多危险和障碍，因此以后必须要将机器人路径规划研究重点放在未知复杂环境下。

(3)多机器人协作：目前机器人应用场合越来越多，单机器人已无法满足现有需求，需多机器人相互协作。这样可节省时间提高效率，但多机器人比单机器人在路径规划上更加复杂，更有难度。因此，多机器人协调工作机制是未来研究重点。

(4)仿生机器人：近年来，中外学者将生物运动机理中得到的启发应用到机器人设计上，从而研发出仿生机器人，仿生机器人涉及空中、陆地、海洋中的生物研制出如无人机、仿生鱼、仿生蜘蛛等，这些仿生机器人在路径规划上的研究帮助人类解决了很多难题，因此，未来可以设计出更多仿生机器人解决尚未解决的难题。