路径规划算法综述

路径规划算法综述

路径规划算法主要问题

路径规划算法是机器人导航中的重要环节，主要是指机器人在相应区域内自动规划一条从起始点至目标点的路径，在这个过程中，需要保证不发生碰撞，并且寻路代价较低。目前路径规划存在的问题主要为环境建模困难、算法收敛素速度慢、容易陷入局部最优解，此外传统的路径规划算法需要在建立全局地图的基础上进行路径规划，即在已知地图中进行，这种算法导致了感知和决策分离，难以应用到位置环境中，因此后来相关研究者将兴趣放到了智能算法的研究上。

提示：以下是本篇文章正文内容

一、主要问题及现有解决方案

1.环境建模问题

• 在环境建模中，从维度上可划分为二维地图和三维地图，其中三维地图无论从计算量还是存储量上都要比二维地图复杂，并且目前多数路径规划算法都是针对二维平面进行规划的，当面对三维地图时，其算法复杂度以及计算量将要增加很多。
• 对于二维地图，主要采用栅格法进行构建，栅格法对机器人环境描述更加简便，处理时也比较方便，可以简化路径规划过程。
• 对于三维环境，我们则是将多个二维平面在高度上进行叠加得来，并且处理的时候也将其映射到二维上。

2.收敛速度和局部最优解

• 对于路径规划算法收敛速度以及局部最优解问题，通常的解决方法是对算法进行结构上的改进，增加算法参数的自适应能力，可降低算法陷入局部最优解的概率。此外也可以将算法进行结合来优化算法性能。

二、路径规划算法分类及简介

2.1传统算法

2.1.1全局路径规划算法

全局规划算法是适用于静态环境中的算法针对动态环境并不适用

2.1.1.1 A*算法

• A*算法是应用较为广泛的路径规划算法，其收敛速度比较快，稳定性较高。
• 算法最早追溯到1968年在论文《A Formal Basis for the Heuristic Determination of Minimum Cost Paths》中被提出
• A*算法是一种启发式搜索算法，将广度优先搜索（BFS）和常规路径规划算法Dijkstra算法相结合。通过利用一个启发函数来改变其搜索性能，从而可以更快的找到路径，并且找到的一定是最短路径。
• 针对A *算法计算量较大，运行时间较长等问题，后续学者又提出了很多改进的A *算法。

2.1.1.2 禁忌搜索算法

• 禁忌搜索算法是在贪婪思想的基础上发展的。贪婪算法最大的问题在于容易陷入局部最优，为了解决这个问题，研究人员引入了禁忌表，使其具有较强的全局搜索能力，禁忌表主要用于记录已经经过的点，其中内容是动态更新的，在这里的点在以后的搜索中将会直接跳过。
• 禁忌搜索算法要优于爬山启发式算法，爬山式启发算法局部搜索能力较强，收敛速度快但是容易陷入局部最优解，禁忌搜索算法在此基础上引入禁忌表后便可跳出局部最优解，转向寻找其他局部最优解，因此具备全局搜索能力。

2.1.1.3 RRT算法

• RRT算法是一种基于采样的路径规划算法，搜索效率较高，并且该算法适用于高维空间。该算法是随机树在空间扩展过程中进行碰撞检测，在样点足够情况下能够得出较优路径，但是不适用于狭长和动态空间中。

2.1.2局部路径规划算法

2.1.2.1 人工势场法

• 人工势场法是将运动物体在规定区域内的运动类比于在虚拟力场中的合力运动，障碍物对机器人产生斥力，目标点对运动物体产生引力，运动物体在虚拟力场的合力作用下逼近目标位置。
• 人工势场法生成的路径较为平滑，但是算法也存在一些问题，当引力与斥力相同情况下并且速度为0时将会导致运动物体无法运动陷入局部最优，规划路径也不是最优路径，因此针对人工势场算法，后续也提出了很多改进的算法。

2.1.2.2 D*算法

• 在A算法基础上又提出了D算法，这是一种适用于动态环境下的路径规划算法，在距离较短情况下可以快速找到合适的路径，虽然其可以进行全局规划，但是当空间较大时其收敛速度较慢，因此D*算法通常结合其他算法进行路径规划。

2.2智能算法

2.2.1 遗传算法

• 遗传算法是一种搜索最优解的优化算法，通过模拟基因的选择、交叉、变异来进行仿真，在搜索过程中具备自我学习能力，能够自适应控制搜索过程来获取最优解。
• 选择是将父代个体的信息不做改变地复制传递给子代。每个个体对当前环境的适应度存在差异，在复制过程中，适应度高的个体被选中复制的概率大，经过不断迭代，群体中优秀个体比重越来越多，相应的路径也被不断优化。
• 交叉是将同一代不同个体间部分基因进行交换，产生新个体，产生的新个体将有可能生成更加优良的个体，相应的也会产生新的路径，从而提供更多选择。
• 变异是使个体基因发生突变，提供更多的基因组合，在小范围内寻找最优解，变异增加了基因种类，使得组合的时候有更多可能，算法寻优范围进一步扩大，变异操作对应于路径上可能是增删某个路径点或者移动路径点，这种操作具有不确定性，路径的适应值有提高或者降低的可能。
• 遗传算法具备较好地收敛性和全局搜索能力，但是局部搜索能力较差，并且容易陷入局部最优。遗传算法也具有很多的改进算法。

2.2.2 粒子群算法

• 粒子群算法是一种集群优化算法，其算法通过模拟群觅食行为相互合作机制寻求最优解。算法首先在空间中初始化粒子，然后粒子经过迭代寻找全局最优解。
• 粒子群算法结构简单、容易实现，但是算法比较容易陷入局部最优解，算法的收敛速度随着迭代次数和搜索范围增加不断变慢，甚至最终停滞，算法开始时参数设定比较依赖经验。

2.2.3 蚁群算法

• 蚁群算法是一种模拟蚂蚁觅食行为数学模型的一种正反馈算法，具有启发式思想，算法主要利用蚂蚁在觅食过程中释放信息素的原理，信息素浓度高的地方对蚂蚁有较大吸引力，最短路径上的蚂蚁信息素浓度最高，据此可以找到最优路径。
• 面对较为复杂的状态空间时，蚁群算法容易陷入局部最优，并且实时性难以保证，因此后来出现了很多蚁群算法与其他算法相结合的算法。

2.2.4 基于强化学习的路径规划算法

• 强化学习是机器学习中一种重要的学习方法，是系统从环境到行为映射的学习，目的是是奖励信号函数值最大，即是一种学习如何从状态映射到行为以使得获取的奖励最大的学习机制，一个动作需要不断在环境中进行实验，环境对动作做出奖励，系统通过环境的奖励不断优化行为。
• 强化学习不存在监督学习中的正确标签，而是从自身的经验中去学习，强化学习的目标也不是寻找隐藏的结构，而是最大化奖励。

总结

• 本文介绍了路径规划算法，包括传统路径规划算法和智能算法，传统算法与智能算法目前都有一定的优缺点和应用场景。目前来看，算法主要问题仍然在于算法收敛速度和容易陷入局部最优化等问题，针对各种算法， 许多学者也都进行了改进，以扩大算法的应用面。相信随着研究的深入，将会有越来越多的算法被提出以及现有算法将会得到更好的改善。

参考文献

[1]王鹤静,王丽娜.机器人路径规划算法综述[J/OL].桂林理工大学学报:1-15[2022-12-21].http://kns.cnki.net/kcms/detail/45.1375.N.20221213.1104.001.html
[2]杨思明,单征,曹江,郭佳郁,高原,郭洋,王平,王景,王晓楠.基于模型的强化学习在无人机路径规划中的应用[J].计算机工程,2022,48(12):255-260+269.DOI:10.19678/j.issn.1000-3428.0063156.
[3]于效民. 基于深度强化学习的移动机器人路径规划研究[D].大连理工大学,2022.DOI:10.26991/d.cnki.gdllu.2022.002364.
[4]基于强化学习的智能机器人路径规划算法研究，https://blog.csdn.net/qq_53162179/article/details/128356575