基于关键点编码遗传算法的机器人路径规划方法

《Algorithms》：A Robot Path Planning Method Based on a Key Point Encoding Genetic Algorithm Chuanyu Yang, Zhenxue He, Xiaojun Zhao, Yijin Wang and Xiaodan Zhang

　　

路径规划是机器人导航中的一项关键技术，长期以来受到广泛关注。然而，在障碍物高密度或非结构化分布的场景中，基于群体智能优化的路径规划方法仍面临计算效率低和路径质量差的问题，限制了其在实时应用中的性能。为解决这些挑战，本文定义了路径关键点，并提出了一种基于关键点编码遗传算法（Key-Points Encoding Genetic Algorithm, KEGA）的路径规划方法。首先，设计了一种编码方案，将关键点序列映射为二进制编码，引导群体进行高效探索。然后，综合目标点方向、局部环境信息和历史路径信息，集成了一种新的路径生成模块，以生成高质量的关键点序列，从而提高路径质量。此外，通过评估关键点序列作为完整路径评估的代理，每次迭代仅需进行一次精确的路径构建，显著降低了计算开销。在四种具有不同障碍物分布特征的模拟地图和八张真实街道地图上进行了实验，以验证该方法的鲁棒性和泛化能力。结果表明，与现有的最先进机器人路径规划方法相比，所提方法实现了平均75.40%的运行时间节省、35.65%的路径长度缩短和68%的路径平滑度提升。

随着移动机器人的广泛应用，路径规划技术在复杂环境中面临诸多挑战。近年来，路径规划问题吸引了跨学科领域的广泛关注，形成了多种解决方案，包括基于图搜索的方法、基于采样的方法、基于群体智能的方法和基于学习的方法。图搜索算法以A*为代表，在二维网格规划中因其最优性保证而得到广泛应用，但可扩展性有限；基于采样的方法以RRT*为典型，在高维机器人规划中表现良好，但路径质量不稳定；以蚁群优化（Ant Colony Optimization, ACO）为代表的元启发式方法在解决复杂优化问题方面具有明显优势，但计算成本较高；以Q学习为代表的基于学习的算法采用新颖技术直接求解路径规划，但通常需要昂贵的训练开销。遗传算法（Genetic Algorithm, GA）作为一种优秀的群体智能优化方法，通过引入增强的并行操作和改进或提出新算子等方式不断改进，在解决复杂优化问题方面表现出显著效果，已广泛应用于交通控制、物流配送、任务分配和特征提取等优化任务。许多研究人员将GA应用于机器人系统中的路径规划任务，但现有方法直接使用地图上的路径坐标作为GA染色体，导致个体长度可变，难以利用个体和群体在地图上的探索趋势等信息，信息利用效率低，算法优化性能不佳。

为应对上述问题，研究人员开展了基于关键点编码遗传算法的机器人路径规划方法研究。该研究定义了路径关键点和陷阱（Trap）概念：陷阱是指地图中由障碍物分布形成的局部封闭或半封闭区域，机器人容易在此类区域被障碍物包围，导致局部路径规划失败或生成非最优绕行路径；关键点则是指在机器人路径规划中可作为从局部陷阱区域可行逃逸出口的网格节点。研究提出了路径与关键点生成模块，该模块利用目标点方向、局部环境信息和历史路径信息，生成趋近障碍物凸包的避障路径并提取关键点，为群体提供探索区域，改善路径优化质量。同时，研究设计了一种编码方案，将路径关键点序列编码为二进制串，使得同一代内所有个体保持一致的编码长度，便于标准遗传算子的统一应用，避免了传统可变长度编码中反复定位有效位点的额外计算开销。研究还提出了替代评估策略，用关键点序列的评估代理完整路径评估，将每代精确路径构建次数从"种群规模×编码长度"降至"仅对最优个体进行一次"，显著降低了计算开销。

研究得出以下主要结论：第一，路径构建过程依赖目标点方向、节点周围的局部信息以及当前障碍物的探索信息，重点在于陷阱回避；第二，构建的路径趋向于直接接近目标点或沿凸包绕行障碍物，从而获得较短的路径长度；第三，所提算法在实验中表现出良好的时间性能，在避障和陷阱逃逸方面能够在局部区域内提供路径方向引导。该研究发表在《Algorithms》期刊。该研究的重要意义在于：通过关键点编码机制将路径规划问题转化为相对低维的搜索空间，有效压缩了搜索空间；结合精英保留策略和编解码方法，加速了算法收敛；提出的KEGA方法在计算效率、路径长度和平滑度等关键指标上均显著优于现有最先进的对比算法，为复杂环境下的机器人实时路径规划提供了有效的解决方案。

研究人员为开展研究用到的主要关键技术方法包括：采用离散二维网格空间进行环境建模，机器人基于8连通性移动；设计路径与关键点生成模块，通过双路径绕行策略初始化陷阱栈记录嵌套障碍物边界的绕行方向信息，利用目标点方向、局部环境信息和历史路径信息判断障碍物局部几何特征，选择探索或退出陷阱；提出关键点编码方案，以当前种群最优个体的方向趋势为基准进行二进制编码，编码具有"代内定长、代际可变"的特征；设计对应的解码策略，利用编码生成的分组及其覆盖区域为每个关键点位 location 提供有偏采样空间；采用替代评估策略减少精确路径构建频率；使用精英保留策略选择父代和子代种群中的最优个体形成下一代种群；通过正交实验设计确定交叉概率和变异概率等算法参数。

研究结果部分，参数调优与敏感性分析表明，交叉概率在0.7至0.9范围内性能稳定且优异，变异概率的影响更为突出，较高值（0.1至0.3）倾向于获得更低的路径成本，这与传统可变长度编码遗传算法中常用的低变异率形成鲜明对比。最终确定的参数组合为：种群规模N_pop=50，交叉概率r_cross=0.9，变异概率r_mutate=0.3。

消融研究在14张测试地图上进行，比较了仅使用路径与关键点生成模块的KE、集成关键点编码遗传算法与路径生成模块的KEGA-1、以及进一步加入替代评估策略的KEGA三种配置。结果表明：IGA仅在非结构化地图上成功规划路径，在其他三张复杂地图上成功率为0；KE在所有地图上均成功规划路径且运行时间极短（0.01-0.03秒），但路径长度和平滑度并非最优。在非结构化地图上，KEGA将KE的路径长度从120.47缩短至112.47（降幅6.6%）；在类迷宫地图上，从471.25缩短至397.00（降幅15.8%）；在U形地图上，从146.28缩短至135.10（降幅7.6%）；之字形地图上，从274.31缩短至219.00（降幅20.2%）。KEGA-1在类迷宫地图上运行时间为112.33秒，而KEGA仅需2.48秒（降幅97.8%）；在之字形地图上，KEGA将运行时间从48.41秒降至2.42秒（降幅95.0%）。在256×256城市地图上，KEGA将上海地图的路径长度从IGA的761.54降至259.08（降幅66.0%），平滑度从14.94提升至2.47（提升83.5%），运行时间控制在4秒以内。在512×512随机障碍物地图上，KEGA仍保持优势，Random20地图运行时间为92.71秒，较KEGA-1的233.69秒降低60.3%。收敛曲线显示IGA基本停留在迭代早期水平，易陷入局部最优；KEGA-1和KEGA继承KE特性，通过关键点编码机制在迭代中进一步缩短路径长度。

对比研究选取了DIGA、IGA、IHMACO和MACOGA四种先进算法在14张地图上进行比较。在100×100地图上，IGA、DIGA、IHMACO和MACOGA在类迷宫、U形和之字形地图上均失败（成功率0），而KEGA保持100%成功率。在非结构化地图上，KEGA路径长度为112.47±3.15，较IGA（300.94±27.2）缩短62.6%，较DIGA（268.61±54.14）缩短58.1%，较IHMACO（132.01±10.3）缩短14.8%，较MACOGA（121.65±3.88）缩短7.6%。在平滑度方面，KEGA的5.84±3.04较IGA（66.84±4.17）和DIGA（67.47±1.79）提升超过91%。在运行时间上，KEGA的0.95±0.39秒较IHMACO（7.57秒）和MACOGA（7.37秒）分别降低87.5%和87.1%。在256×256城市地图上，KEGA在所有八张地图上均保持100%成功率，而IHMACO在米兰地图上仅达80%。在米兰地图上，KEGA路径长度为268.63±8.74，较IHMACO（478.70）和MACOGA（461.30）分别缩短43.9%和41.8%；运行时间3.84±0.43秒，较IHMACO（10.14秒）和MACOGA（12.80秒）分别降低62.1%和70.0%。Wilcoxon符号秩检验表明，在10项可比较地图任务中，KEGA的路径长度较所有对比算法均有显著优势（p<0.05）；在11项任务中，KEGA的平滑度显著优于IGA和DIGA，也显著优于IHMACO；运行时间显著优于IHMACO和MACOGA。

基于街道地图的实验显示，KEGA在路径长度、平滑度和运行时间方面表现良好。在莫斯科和纽约两张地图上，KEGA相对MACOGA的平滑度分别出现-58.36%和-44.16%的负值，p值分别为3.26×10^-17和2.83×10^-30，这主要归因于两张地图上障碍物边界的连续阶梯形状特征。为保证逃离陷阱区域和确定离开障碍物的最佳时机，KEGA的路径生成模块沿障碍物边界构建路径，增加了路径转向次数和平均转向角。这是为保证路径可行性而做出的有意权衡：KEGA的路径长度仍显著优于MACOGA（分别缩短3.89%和7.53%），运行时间节省分别高达73.15%和77.90%。

讨论部分分析了算法的收敛行为。关键点编码显著降低了搜索空间的维度：传统基于GA的路径规划将路径表示为网格坐标序列，搜索空间大小随路径长度快速增长；KEGA仅编码少量关键点（与两点间需要绕行的障碍物数量相关），将问题转化为相对低维的搜索空间，有效压缩了搜索空间。精英保留策略结合编解码方法加速了收敛：种群个体围绕最优路径的探索趋势进行编码，维持了对高质量方向的选择压力。这些机制共同构建了有向的进化轨迹：初始种群由方向引导的可行路径种子生成，后续迭代在 promising 区域内细化关键点，而非盲目探索。非结构化环境需要路径规划方法在多个可能方向中找到最优遍历路径，编码方案通过方向趋势分组为种群提供潜在的路径探索方向，引导种群逐渐绕过障碍物沿目标点方向前进。水平观察显示编码方案在路径生成初始阶段更注重方向探索，通过早期优化实现路径在障碍物间的大跨度跨越；垂直视角表明，尽管关键点序列评估作为精确路径构建的粗略替代，该方法能从整个种群角度为精确路径构建提供有效指导，从而减少精确路径构建的调用次数，提高算法效率。这些分析结果与KEGA在真实街道地图实验中观察到的分段路径特征一致，进一步证明了该编码机制在复杂环境中的适用性。

研究结论部分总结：该研究从路径生成的角度分析了现有算法在解决路径规划问题中的局限性，提出了一种新颖的关键点编码方案和路径生成模块，通过利用路径特征来提高算法的优化性能。路径构建过程依赖目标点方向、节点周围的局部信息以及当前障碍物的探索信息，重点在于陷阱回避；构建的路径趋向于直接接近目标点或沿凸包绕行障碍物，从而获得较短的路径长度；所提算法在实验中表现出良好的时间性能，在避障和陷阱逃逸方面能够在局部区域内提供路径方向引导。一个潜在的改进方向是在动态环境中构建分层路径规划框架，结合动态窗口法（Dynamic Window Approach, DWA）等局部避障方法：KEGA可用于框架的全局规划层，其生成的关键点序列可为局部规划层提供清晰的区域 guidance。未来工作可探索开发遗传算子以进一步提升算法效率和优化性能，或将该算法嵌入其他规划框架作为规划器使用。