林梓健 刘凯 林群煦

摘  要：路径规划算法广泛应用于机器人、无人驾驶设备、自动导航等领域，是推动自动化和智能化发展的技术支撑。文章对几何搜索算法、智能搜索算法、人工智能算法、混合算法和局部规划算法等路径规划算法进行了简要介绍，内容包括若干典型算法以及由不同算法相互模仿混合而成的混合算法的特点、优缺点和重要改进。对路径规划算法的发展趋势进行总结，对路径规划算法的发展前景进行展望，以期为相关的研究提供参考。

关键词：路径规划；算法综述；自动导航

中图分类号：TP242  文献标识码：A  文章编号：2096-4706（2023）04-0075-06

Research Review of the Path Planning Algorithms

LIN Zijian， LIU Kai， LIN Qunxu

（School of Rail Transportation， Wuyi University， Jiangmen  529020， China）

Abstract： The path planning algorithms are widely used in robots， driverless equipments， automatic navigation and other fields， and they are the technical support for promoting the development of automation and intelligence. This paper briefly introduces path planning algorithms such as geometric search algorithm， intelligent search algorithm， artificial intelligence algorithm， hybrid algorithm and local planning algorithm， including the characteristics， advantages and disadvantages and important improvements of several typical algorithms as well as hybrid algorithms formed by mutual imitation and mixing of different algorithms. Summarize the development trend of path planning algorithms， and prospect the development prospect of path planning algorithms， in order to provide reference for relevant research.

Keywords： path planning; algorithm review; automatic navigation

0  引  言

路径规划是机器人、自动驾驶等领域里的一个重要部分，包括移动设备的路径规划、机械臂的轨迹规划等内容。规划良好的路径对设备的工作能力和工作效率，乃至工作场所的安全等要素有至关重要的影响。本文将介绍其中一些典型的算法，如图1所示，分为几何搜索算法、智能搜索算法、人工智能算法、混合算法和局部规划算法5个部分进行介绍。

1  几何搜索算法

1.1  A*算法

A*算法是一种经典的寻路算法，该算法的核心公式是每一步的代价G加估算代价H得到总代价F，常用的H是“曼哈顿距离”，此外也有欧氏距离、对角线距离等可以选择，系统选择F最小的路线作为结果。该算法计算快，应用广泛，但考虑的信息较少，得到的路径会不够平顺或出现多余的段落。

Zhang[1]等人通过加进类似人工势场法的目标引力和障碍物斥力，把合力作为一个要素加进A*算法的代价函数里，使得改进后的算法更充分考虑地图信息，并用B样条曲线进行平滑处理，得到比传统A*算法更平顺更合理的路径，在实验中同样直线距离的情况下算法会选择更平直、更少转弯的路线。Tang[2]等人通过设置函数对传统A*算法的路径进行过滤修整，去除交叉或锯齿形等不合理的路径，并用B样条曲线平滑处理，得到更合理、更适合设备执行的路径。Hong[3]等人通过优化数据结构，并且让算法在距离目标点只剩一段距离之前不执行传统A*算法中搜索终点是否在列表中的步骤，因为在大部分时间里这一步都是没什么意义的，尤其是在尺寸比较大的地图上，因而大大提升了计算速度和适用范围。

1.2  Dijkstra算法

Dijkstra算法是一种经典的路径搜索算法，该算法基于贪婪策略，从起始点开始，一层层地向外搜索直到到达目标。不过传统的Dijkstra算法有不考虑平滑度等局部情况、某些情况下计算量大和计算复杂、搜索速度慢等不足。

Sun[4]等通過改进让Dijkstra算法在8个方向上进行搜索，得到比4个方向进行搜索的传统Dijkstra算法更平顺、更优化的路径。Dijkstra算法的不足也可以通过与其他算法混合使用以弥补，比如Zhao[5]等使用Dijkstra算法搜索初始的路径后，再使用蚁群算法进行进一步优化。

1.3 Voronoi图算法

Voronoi图是一种基于几何图形的路径规划算法，该算法先按移动设备的尺寸等条件给障碍物“膨胀”处理确保安全距离，并且提取特征点，然后按边界与两特征点保持相同距离的方式把区域划分成若干单元，得到Voronoi图路径，边界线就是可行路径。

Huang[6]等在传统的Voronoi图算法的基础上，通过在两个机器人相遇时在低优先权的机器人上添加Voronoi特征点使低优先权的机器人使用的Voronoi图和路径发生改变并绕开高优先级机器人的方式，进行多机器人的路径规划。AL-Dahhan[7]等通过在传统的Voronoi图得到的初步结果上，删除一些不必要的点，增加一些新的引导点，使路径得到进一步优化。Chi[8]等通过1个特征矩阵“过滤”传统的Voronoi图得到的特征点，删除不必要的特征点，得到更优化的路径。

2  智能搜索算法

2.1  蚁群算法

蚁群算法由Dorigo[9]提出，源于对蚂蚁寻找食物的研究，蚂蚁释放信息素也受已有信息素的影响 ，在一定的时间后蚂蚁们会由于信息素而集中在比较理想的路线上。随后出现了精英蚁群算法、极大极小值蚁群算法、等级蚁群算法等改进[10]。该算法被广泛使用，是效率和适用性很高的一种算法。但是蚁群算法有陷入局部最优解、过度依赖信息素、初始时盲目搜索等不足。

Abolhosein[11]等人通过让蚁群算法的每一次更新都按一定的权重考虑前面已经获得结果，设计了一种“带有记忆”的动态蚁群算法，每次更新都在考虑已有结果的基础上进行而不是地图稍有改变就从头开始搜索，大大减少了动态环境下所需的计算时间。Pohan[12]等人通过让启发函数不只是考虑当前节点到下一節点的距离，也考虑节点到目标点的距离来设定启发因子，使得蚂蚁不必搜索所有节点，也不必每次都搜索最接近的下一个节点，减少了搜索的盲目性，提高了效率。Zhang[13]等人通过在更新信息素时考虑当下迭代得到的最优解和目前最流行的解，额外增强两者共同包括的节点的信息素，并且让信息素能辐射出去影响周边的其他节点，增加了蚂蚁之间的协作性，比传统的蚁群算法能获得更快更优化的路径。Li[14]等人通过引入适应策略，根据信息素的浓度动态调整各点信息素的挥发系数，不让系统过早收敛而陷入局部最优解，增加了系统的全局搜索能力。Song[15]等在已有的精英蚁群算法基础上引入序列，找出一群精英蚂蚁并排序，同时在信息素更新环节加入模糊逻辑，不仅提升了蚁群算法的计算速度和动态环境搜索能力，还能同时考虑多种其他条件的约束而不只是最短路径。

2.2  遗传算法

遗传算法由约翰·H·霍兰[16]等人提出，模仿遗传物质在适应环境的过程中优胜劣汰，使遗传物质得到优化。该算法让各个解进行交换、突变、繁殖复制，淘汰不能适应的解，由“适应度”决定繁殖和淘汰。在著作中约翰·H·霍兰解释道，突变的作用是以免过早收敛陷入局部最优解，比如一个早先因某些原因恰好被删掉的信息，是有可能在遇到其他信息后组合出更好的解的，还能增加多样性；而交换则能在大程度保持众多优秀小片段的同时，打乱由这些小片段组成的大片段来增加多样性，实现众多小片段逐渐优化，同时由这些小片段组合出多样的大片段以供选择，并且这两个操作都能扩大搜索空间，使搜索不局限于初始条件。遗传算法不断改进以提高搜索能力，缓解该算法计算量大、计算时间长等不足。

Wang[17]等人在传统的遗传算法的基础上，增加了直接保留适应度高的个体，删除和替换掉效果不太好的基因段的步骤，提高了遗传算法的计算速度和求解性能。Xing[18]等人通过引入精英直接复制到下一代和分组进行适应不同的目标，然后混合并在下一代再分组适应不同目标的策略，提高计算速度的同时使得改进后的遗传算法能求解多目标的优化问题。Li[19]等在传统的单一种群进行求解的遗传算法的基础上，设置若干个种群同时求解，并通过“迁徙”让种群之间互相流通，改进基因交叉的算法，并且也设置让较优的个体直接保留下来，提高了算法的性能和求解速度，如图2所示。

Li[20]等为适应度判别引入了奖惩因素提高搜索能力，并且每轮搜索直接保留第一维基因里的优秀个体，和由这些优秀个体产生二维基因，使得遗传算法能求解多维度的问题。遗传算法的突变和交叉概率是一个重要的改进方向，比如袁梦飞[21]等让群体在早期扩大突变和交叉的概率以扩大搜索空间，后期则减少突变和交叉的概率以加速收敛，提高了算法的搜索性能和计算速度；王吉岱[22]等通过模糊推理设置动态的突变概率和交叉概率，在种群适应度方差过低或进化速度过慢时增大概率，扩大搜索空间和避免系统早熟或陷入局部最优解，反之则减小概率，加速算法的收敛。

2.3  人工势场法

人工势场法来自对物理学的力场的模仿，让目标发出“吸引力”，障碍物则发出“排斥力”，形成一个组合力场。该算法简单而高效，广泛应用在局部路径优化、避障等。但是该算法也有一些明显的不足，例如陷入力平衡而锁死，由于排斥力的作用要和障碍物保持一端距离导致路线有时候达不到最短、在目标周围或前往目标的途中的障碍物的排斥力使得机器人无法前往目标点等问题。

针对陷入力平衡的死锁问题，以往有通过增加虚拟障碍物或虚拟目标打破死锁的做法，主要是随机添加的，但该方法被认为不稳定，甚至导致偏离目标。Yuan[23]等通过在陷入死锁时，计算一个相邻范围内的障碍物数量和整个空间的障碍物数量，并由此数量关系产生额外的斥力使得路线因此发生膨胀绕开死锁地点。Yang[24]等人通过在目标点附近添加一些虚拟目标点供路线陷入死锁时切换目标为这些虚拟目标点以脱离死点，并且在距离目标点小于某设定值后，使吸引力保持为常数或增大，确保路线能到达目标点，如图3所示。

Wang[25]等通过在判断有陷入死锁的危险时，在行进物体与临近的某选定障碍物的连线方向上添加额外的“逃脱力”以脱离死锁状态。Yao[26]等人在传统的人工势场上，在目标点附近施加极大的吸引力，而全局的吸引力则缓慢变化，使得每个目标点成为一个“黑洞”，缓解了传统人工势场法中可能由于多个目标的吸引力达成平衡而死锁的问题，提高了算法解决多目标问题的能力。He[27]等人让目标物的吸引力不是按传统方式那样与距离成正比，而是会变化的，以免过大的吸引力导致撞上障碍物。Wang[28]等人让人工势场法搜索陷入死锁时，沿着障碍物的外表进行“沿墙壁搜索”以脱离死锁，并让人工力场外部引导前往目标，内部用于保持间距，应用于多机器人路径规划。

2.4  RRT算法

快速搜索随机树算法简称RRT算法，该算法模仿1棵树随机地生长，直到“发芽点”与终点连接上，双向版本的RRT则模拟2棵树随机生长直到两棵树的树枝连接上。该算法原理简单但是计算量大，而且在一些狭窄通道处难以搜索。

传统的RRT算法要遍历整个空间里的所有节点去寻路，导致大量的时间消耗和计算量，Zhou[29]等人提出一种“Cell method”方法，把搜索空间分成若干个尺寸相同的单元，每次搜索优先在节点所属的单元内搜索，大大减少了计算量。Kang[30]等人提出一种“三角形重连接”的方法，如图4所示，在已有的RRT算法得到的结果的基础上进行检查，如果3个节点之间的连线长度（q1q2和q2q3长度之和）大于首尾两节点的距离（q1q3的长度），则删除原来的连线（q1q2和q2q3），重新连接为直接连接收尾的2个节点q1和q3，大幅度优化了路线。

Chen[31]等人在起点和终点之间设置中点为第三点，然后让4棵搜集树从这3个点之间相向地同时开始搜索，并且通过公式修正随机采样点，让随机树的每一次生长都有意地倾向于终点所在的方向，极大地提高了计算速度。

2.5  PRM算法

概率路线图算法简称PRM算法，该算法的原理是在地图上撒播一些随机采样点，然后删除不合理的点，再把剩下的点互相連接成线，从这些连线里选取组成最短路径的若干线段作为输出结果。该方法最大的特点是采样点越多结果越好，但同时采样点越多计算量就越大。

传统的PRM算法在障碍物比较多的地方效率下降，因为很多落入障碍物的采样点被直接删除掉了，为此Chen[32]等人引进了一个“虚拟力”的作用，把落在障碍物范围内的采样点，按最快离开障碍物范围的方向施加一个力的作用，把这些采样点送回可行空间内的边界位置上，提高了采样点的使用率，提高了算法的搜索能力。Xu[33]等人为PRM算法引入一种动态的策略，完成一段路径后在新的环境里撒播采样点连接已有的采样点网络，充分利用已有的信息，并且只允许互相保持了一定间距的采样点为有效采样点，大大提升了计算效率和面对动态环境的能力。Ravankar[34]等人把地图分成若干区域，区域再细分为网格，然后根据区域和网格里障碍物的情况设置一个“斥力值”，障碍物越多该数值越大，搜索时只在斥力值低于所在区域的平均斥力值的网格里撒播采样点，并且每个区域的总采样点数固定，使得采样点集中在可通行区域里，提高了计算速度和效率。

3  人工智能算法

3.1  Q-Learning

Q-Learning（Q学习）是强化学习的一种，其原理是模仿生物的学习行为，获得奖励的行为更倾向于再次去做，受到惩罚的行为则倾向于去避开。在学习过程中，系统让agent去尝试和学习，探索外界环境，寻找更优的行事方式。Q学习的学习过程中每处于一个状态，agent就会选择当下已知的Q值最高的行为去执行，并由环境的反馈不断更新Q值表。Q学习如今在机器人等领域已获得广泛应用，在一些领域甚至表现得比人工表现更好。而Q学习在起始阶段随机、盲目地搜索，有些易损坏环境下不适宜让系统盲目试错、计算量大和耗费时间长等不足，也在实践的过程中逐渐获得改善。此外Q学习可以与神经网络结合组成DQN算法。

传统的Q学习在初始的时候Q值表全部内容置为0，然后agent开始盲目随机地探索，浪费了计算时间和资源，Low[35]等人在初始时通过FPA算法给Q值表赋予初始值，实验结果表明合理地赋予Q值表初始值能大程度提高系统的学习效率和速度。同样为了减少盲目搜索的浪费，Sun[36]等给Q学习加入了对比类似情况的环节，在新环境中对比位置、能耗等因素，从已有经验中获得帮助加速学习，提高了Q学习面对动态和新环境的性能。Li[37]等人使用基于与Q值相关的概率选择策略取代传统Q学习的选择最大Q值的策略，减少噪音影响和陷入局部最优解的几率，并通过引入来自相关任务领域的先验知识和设定先验规则加速系统训练。

3.2  深度学习

深度学习是近年来人工智能领域里的一个新兴技术，如图5所示，该技术模仿人的大脑和神经系统，在提供充足的数据时能输出良好的结果，目前已经广泛应用在数据分析、机器视觉、信号处理等领域。深度学习技术也可以用在路径规划领域，并且可以和其他算法结合获得很好的实验结果。比如混合算法段落将介绍的Hamdia[38]等人结合深度学习和遗传算法。Abdi[39]等人结合Q-Learning和深度学习，让前者负责学习机械臂的轨迹规划和避障，后者则负责学习机械臂的末端执行器的各关节角度，根据这两类任务的特点，分别发挥两种算法的优势，节省了大量的计算时间和计算量。

4  局部规划算法

4.1  DWA算法

动态窗口算法简称DWA算法，该算法不需要完整的地图环境信息，而是在指定环境空间内，通过移动机器人自身传感器不断获取周围的最新信息和环境变化，对每一时刻的速度空间的线速度vt和角速度wt进行多组采样，如图6所示，再结合当前移动机器人的状态对未来可能运动的轨迹进行预测，通过算法对每条路径进行打分，判断出分数最高，即距离目标最短以及最快到达的路径，获取可下达的对应最佳速度，最后选取并发布至下位机实现导航。

传统的DWA算法在复杂环境下生成的路径不平滑，Xiang[40]等针对原DWA的评价函数权系数不变的情况，采用模糊控制器算法，加入航向角的变化，并与模糊控制器结合获取较低的航向角变化率，使路径更平稳，避免角度变化过大。Chang[41]等基于强化学习动态调整DWA参数，提高了规划成功率。在人类相似性方面，传统DWA结果较差，因此Ballesteros[42]等提出BDWA，BDWA定义一种新的奖励功能，这种奖励功能通过聚类从志愿者在医院环境中使用被动滚轮的真实导航轨迹中提取的，以产生与需要滚动器的人类非常接近的轨迹，使DWA能模仿真实行人轨迹，平衡了人类相似性和安全约束。

4.2  局部优化算法

使用轨迹规划算法得到的路线往往不够合理，带有锐角或直角的转角、不必要的曲折、走回头路等不合理因素使得不便于马上让机器人执行。因此可以使用一些局部优化算法进行优化，得到更合理的路线。常用的局部优化算法有平滑处理、考虑速度和加速度变化的五次多项式、贝塞尔曲线、B样条曲线等。

Wang[43]等把軌迹分为3个部分，分别设置开始时加速度为0、结束时加速度为0以及运行中轨迹的三阶导数连续，3个约束条件，获得比传统B样条曲线更平稳和精确的改进B样条曲线。古劲[44]等人通过曲线首末端切矢条件反求曲线上的点进行插补计算，提出了一种比传统B样条曲线更平滑、更光顺的改进三次B样条曲线轨迹，实现G2级连续。Luan[45]等人结合A*算法和贝塞尔曲线，在A*算法得到的点的基础上应用分段三次贝塞尔曲线，并考虑机器人的起始和终止运动时刻，得到C2级连续光顺的曲线。

5  混合算法

各种路径规划算法各有特点各有优劣，因此在单个算法进行改进之外，人们也尝试把不同的算法混合起来，取长补短优势互补，有时能取得单一算法难以得到的效果。

Yuan[23]等结合RRT算法和人工势场法，在相对空旷的地方采用人工势场法快速求解，在遇到障碍物时用RRT算法避障，该混合算法一方面缓解了RRT算法计算慢的不足，另一方面避开了传统人工势场法当障碍物在目标点旁边时会导致到达不了目标点的缺陷。Zeng[46]等人结合RRT算法与迪杰斯特拉算法，先用RRT算法连接起始点和目标点，然后再用迪杰斯特拉算法在前者得到的结果的基础上搜索最优路径。Hamdia[38]等结合神经网络深度学习和遗传算法，让遗传算法优化神经网络的一些参数，比如网络的层数、每层的神经元数等，比传统的神经网络深度学习提高了很高的效率。Chen[47]等人结合人工势场法和PRM算法，让障碍物发出排斥力，迫使采样点必须远离障碍物直到可以认定排斥力为0的距离或位于两个障碍物之间的“力平衡点”，从而省略了传统的PRM算法的碰撞检查部分，提高了算法的计算速度。如图7所示。

Li[48]等人结合遗传算法和A*算法，使用A*算法的成本函数作为启发信息，加速遗传算法的计算收敛和获得最优结果。Wang[28]等人结合人工势场法和Q学习，让人工势场法在外部条件约束下规划路径同时让Q学习在实际经验中学习进行具体调整和优化路径。Chen[49]等人结合蚁群算法和人工势场法，使用蚁群算法规划全局的路径，然后使用人工势场法进行局部避障，并根据周围障碍物的情况动态调整步幅，以在未知的环境下进行路径规划。He[27]等在人工势场法陷入死锁时，启动模拟退火算法以脱离死锁点。

6  结  论

本文介绍了一些常用的路径规划算法以及它们的特点、优缺点和改进。以下对路径规划算法的发展趋势和前景做一展望：

（1）混合算法把不同特点的算法结合起来使用，取长补短优势互补，这些混合算法展现了强大的搜索能力，能弥补原来的单一算法的不足，甚至青出于蓝而胜于蓝，达到比原来的单一算法更好的效果。

（2）有一些算法会经历一个盲目、随机搜索的阶段，比如传统的蚁群算法，或者收敛的过程可能陷入振荡或死锁，比如传统的人工势场法，这些缺陷制约了计算效率和计算速度，因此缩减甚至消除这些缺陷是重要的改进方向。

（3）在路径规划的同时，也要考虑到相关设备的特殊要求，比如动作或线路是否平稳流畅、路径是否足够安全、考虑设备的惯性和受力状况等。在多机器人协同、多移动设备等领域，还要考虑多设备之间的协调、防撞、队形等要求。此外，应急能力也是一个重要的研究内容，比如设备突然被障碍物干扰或阻挡、多个设备的路径发生冲突等。

（4）为了让算法更广泛适用，如何让设备一边探索未知的环境一边进行路径规划、如何减少算法的计算量和提高计算效率以降低算法对设备条件的要求等改进，也是重要的研究内容。

尽管有些情况下可能为了综合性能，而需要付出一些计算时间或精度的代价，但路径规划算法领域已获得的进步是令人瞩目的。此外，随着如今相关领域积累的日益丰富的经验，性能发展迅速的软硬件设备，以及机器学习、传感器、物联网、激光雷达、机器视觉等高新技术的结合下，路径规划算法将走向更强大的未来，发挥更大的作用。

参考文献：

[1] ZHANG J，WU J，SHEN X，et al. Autonomous land vehicle path planning algorithm based on improved heuristic function of A-Star [J/OL].International Journal of Advanced Robotic Systems，2021，18（5）：[2022-08-20].https：//doi.org/10.1177/17298814211042730.

[2] TANG G，TANG C，CLARAMUNT C，et al. Geometric A-Star Algorithm：An Improved A-Star Algorithm for AGV Path Planning in a Port Environment [J].IEEE Access，2021，9：59196-59210.

[3] HONG Z H，SUN P F，TONG X H，et al. Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map [J/OL].ISPRS International Journal of Geo-Information，2021，10（11）：[2022-08-20].https：//doi.org/10.3390/ijgi10110785.

[4] SUN Y H，FANG M，SU Y X. AGV Path Planning based on Improved Dijkstra Algorithm [C]//Journal of Physics：Conference Series.Bijing：IOP，2021，1746（1）：1-7.

[5] ZHAO H L，NIE Z，ZHOU F B，et al. A Compound Path Planning Algorithm for Mobile Robots [C]//2021 IEEE International Conference on Power Electronics，Computer Applications（ICPECA）.Shenyang：IEEE，2021：1-5.

[6] HUANG S K，WANG W J，SUN C H. A Path Planning Strategy for Multi-Robot Moving with Path-Priority Order Based on a Generalized Voronoi Diagram [J/OL].Applied Sciences，2021，11（20）：[2022-08-20].https：//doi.org/10.3390/app11209650.

[7] AL-DAHHAN M R H，SCHMIDT K W. Voronoi Boundary Visibility for Efficient Path Planning [J].IEEE Access，2020，8：134764-134781.

[8] CHI W Z，DING Z Y，WANG J K，et al. A Generalized Voronoi Diagram-Based Efficient Heuristic Path Planning Method for RRTs in Mobile Robots [J].IEEE Transactions on Industrial Electronics，2022，69（5）：4926-4937.

[9] DORIGO M，GAMBARDELLA L M. Ant colony system：a cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on evolutionary computation，1997，1（1）：53-66.

[10] KASHEF S，ELSHAER R. A Review of Implementing Ant System Algorithms on Scheduling Problems [J].The Egyptian Journal for Engineering Sciences and Technology，2021，36（2）：43-52.

[11] ABOLHOSEINI S，ALESHEIKH A A. Dynamic routing with ant system and memory-based decision-making process [J].Environment Systems and Decisions，2021，41（2）：198-211.

[12] POHAN M A R，TRILAKSONO B R，SANTOSA S P，et al. Path Planning Algorithm Using the Hybridization of the Rapidly-Exploring Random Tree and Ant Colony Systems [J].IEEE Access，2021，9：153599-153615.

[13] ZHANG S C，PU J X，SI Y N. An adaptive improved ant colony system based on population information entropy for path planning of mobile robot [J].IEEE Access，2021，9：24933-24945.

[14] LI C Q，XIAO J，LIU Y，et al. An Adaptive Immune Ant Colony Optimization for Reducing Energy Consumption of Automatic Inspection Path Planning in Industrial Wireless Sensor Networks [J/OL].Journal of Sensors，2021，2021：1-11[2022-08-16].https：//doi.org/10.1155/2021/9960043.

[15] SONG Q，ZHAO Q L，Dynamic Path Planning for Unmanned Vehicles Based on Fuzzy Logic and Improved Ant Colony Optimization [J].IEEE Access，2020，8：62107-62115.

[16] 約翰·H·霍兰.隐秩序：适应性造就复杂性 [M].周晓牧，译.上海：上海科技教育出版社，2019.

[17] WANG H J，FU Z J，ZHOU J J，et al. Cooperative collision avoidance for unmanned surface vehicles based on improved genetic algorithm [J/OL].Ocean Engineering，2021，222：[2022-08-16].108612.https：//doi.org/10.1016/j.oceaneng.2021.108612.

[18] XING X G，LIU Y，GARG A，et al. An improved genetic algorithm for determining modified water-retention model for biochar-amended soil [J].CATENA，2021，200：[2022-08-16].https：//doi.org/10.1016/j.catena.2021.105143.

[19] LI J L，LIU Z B，WANG X F. Public charging station location determination for electric ride-hailing vehicles based on an improved genetic algorithm [J/OL].Sustainable Cities and Society，2021，74：[2022-08-16].https：//doi.org/10.1016/j.scs.2021.103181.

[20] LI R H，CHANG Y L，WANG Z C. Study of optimal allocation of water resources in Dujiangyan irrigation district of China based on an improved genetic algorithm [J].Water Supply，2021，21（6）：2989-2999.

[21] 袁夢飞，阚秀，曹乐，等.自适应精英遗传算法的快递车路径规划 [J].导航定位学报，2021，9（6）：104-111.

[22] 王吉岱，王新栋，田群宏，等．基于改进模糊自适应遗传算法的移动机器人路径规划 [J]．机床与液压，2021，49（23）：18-23．

[23] YUAN Q N，YI J H，SUN R T，et al. Path Planning of a Mechanical Arm Based on an Improved Artificial Potential Field and a Rapid Expansion Random Tree Hybrid Algorithm [J/OL].Algorithms，2021，14（11）：[2022-08-16].https：//doi.org/10.3390/a14110321.

[24] YANG W L，WU P，ZHOU X Q，et al. Improved Artificial Potential Field and Dynamic Window Method for Amphibious Robot Fish Path Planning [J/OL].Applied Sciences，2021，11（5）：[2022-08-16].https：//doi.org/10.3390/app11052114.

[25] WANG Z，LI G F，REN J. Dynamic path planning for unmanned surface vehicle in complex offshore areas based on hybrid algorithm [J].Computer Communications，2021，166：49-56.

[26] YAO Q F，ZHENG Z Y，QI L，et al. Path planning method with improved artificial potential field—A reinforcement learning perspective [J].IEEE Access，2020，8：135513-135523.

[27] HE N F，SU Y F，GUO J L，et al. Dynamic path planning of mobile robot based on artificial potential field [C]//2020 International Conference on Intelligent Computing and Human-Computer Interaction（ICHCI）.Sanya：IEEE，2020：259-264.

[28] WANG M，ZENG B，WANG Q. Research on Motion Planning Based on Flocking Control and Reinforcement Learning for Multi-Robot Systems [J/OL].Machines，2021，9（4）：[2022-08-12].https：//doi.org/10.3390/machines9040077.

[29] ZHOU Y，ZHANG E D，GUO H L，et al. Lifting path planning of mobile cranes based on an improved RRT algorithm [J/OL].Advanced Engineering Informatics，2021，50：[2022-08-12].https：//doi.org/10.1016/j.aei.2021.101376.

[30] KANG J G，LIM D W，CHOI Y S，et al. Improved RRT-Connect Algorithm Based on Triangular Inequality for Robot Path Planning [J/OL].Sensors，2021，21（2）：[2022-08-12].https：//doi.org/10.3390/s21020333.

[31] CHEN J G，ZHAO Y，XU X. Improved RRT-Connect Based Path Planning Algorithm for Mobile Robots [J].IEEE Access，2021，9：145988-145999.

[32] CHEN G，LUO N，LIU D，et al. Path planning for manipulators based on an improved probabilistic roadmap method [J/OL].Robotics and Computer-Integrated Manufacturing，2021，72：[2022-08-12].https：//doi.org/10.1016/j.rcim.2021.102196.

[33] XU Z F，DENG D，SHIMADA K. Autonomous UAV Exploration of Dynamic Environments Via Incremental Sampling and Probabilistic Roadmap [J].IEEE Robotics and Automation Letters，2021，6（2）：2729-2736.

[34] RAVANKAR A A，RAVANKAR A，EMARU T，et al. HPPRM：Hybrid Potential Based Probabilistic Roadmap Algorithm for Improved Dynamic Path Planning of Mobile Robots [J].IEEE Access，2020，8：221743-221766.

[35] LOW E S，ONG P，CHEAH K C. Solving the optimal path planning of a mobile robot using improved Q-learning [J].Robotics and Autonomous Systems，2019，115：143-161.

[36] SUN F J，WANG X C，ZHANG R. Improved Q-Learning Algorithm Based on Approximate State Matching in Agricultural Plant Protection Environment [J/OL].Entropy，2021，23（6）：[2022-08-12].https：//doi.org/10.3390/e23060737.

[37] LI B，LIANG H B. Multi-Robot Path Planning Method Based on Prior Knowledge and Q-learning Algorithms [C]//Proceedings of 2020 2nd International Conference on Computer Modeling，Simulation and Algorithm（CMSA2020）.Beijing：IOP，2020，1624（4）：1-9.

[38] HAMDIA K M，ZHUANG X Y，RABCZUK T. An efficient optimization approach for designing machine learning models based on genetic algorithm [J].Neural Computing and Applications，2021，33（6）：1923-1933.

[39] ABDI A，ADHIKARI D，PARK J H. A Novel Hybrid Path Planning Method Based on Q-Learning and Neural Network for Robot Arm [J/OL].Applied Sciences，2021，11（15）：[2022-08-12].https：//doi.org/10.3390/app11156770.

[40] XIANG L D，LI X M，LIU H，et al. Parameter Fuzzy Self-Adaptive Dynamic Window Approach for Local Path Planning of Wheeled Robot [J].IEEE Open Journal of Intelligent Transportation Systems，2021，3：1-6.

[41] CHANG L，SHAN L，JIANG C，et al. Reinforcement based mobile robot path planning with improved dynamic window approach in unknown environment [J].Autonomous Robots，2021，45（1）：51-76.

[42] BALLESTEROS J，URDIALES C，VELASCO A B M，et al. A Biomimetical Dynamic Window Approach to Navigation for Collaborative Control [J].IEEE Transactions on Human-Machine Systems，2017，47（6）：1123-1133.

[43] WANG X Y，WANG A，WANG D Z，et al. Repetitive Control Scheme of Robotic Manipulators Based on Improved B-Spline Function [J/OL].Complexity，2021，2021：[2022-08-12].https：//doi.org/10.1155/2021/6651105.

[44] 古劲，吴泰羽，李传军，等. 基于改进三次B样条的灌木修剪运动轨迹光顺算法研究 [J].农业机械学报，2021，52（S1）：89-97.

[45] LUAN P G，THINH N T. C 2 Piecewise Cubic Bezier Curve Based Smoothing Path for Mobile Robot [J/OL].International Journal of Mechanical Engineering and Robotics Research，2021，10（9）：1-7[2022-08-12].http：//www.ijmerr.com/uploadfile/2021/0727/20210727113132943.pdf.

[46] ZENG X Y，LU H C，LYU H F，et al. Robot Path Planning Based on Improved RRT Algorithm [C]//LSMS 2021，ICSEE 2021：Intelligent Equipment，Robots，and Vehicles.Hangzhou：Springer，2021：361-369.

[47] CHEN J B，ZHOU Y L，GONG J，et al. An improved probabilistic roadmap algorithm with potential field function for path planning of quadrotor [C]//2019 Chinese Control Conference（CCC）.Guangzhou：IEEE，2019：3248-3253.

[48] LI Y B，DONG D G，GUO X N. Mobile Robot Path Planning based on Improved Genetic Algorithm With A-star Heuristic Method [C]//2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference（ITAIC）.Chongqing：IEEE，2020：1306-1311.

[49] CHEN Y L，BAI GQ，ZHAN Y，et al. Path Planning and Obstacle Avoiding of the USV Based on Improved ACO-APF Hybrid Algorithm With Adaptive Early-Warning [J].IEEE Access，2021，9：40728- 40742.

作者簡介：林梓健（1997—），男，汉族，广东江门人，硕士研究生在读，主要研究方向：智能装备；通讯作者：林群煦（1983—），男，汉族，广东江门人，副教授，博士，主要研究方向：智能化物流和移动机器人；刘凯（1999—），男，汉族，广东广州人，硕士研究生在读，主要研究方向：机器视觉、机器人导航。

收稿日期：2022-09-30