以下是本⼈在学习路径规划过程中的⼀些总结，借着机会写了⼀下，有不妥之处欢迎批评指正，谢谢。
路径规划部分在⽆⼈车架构体系当中分属控制或决策部分，如图1，是实现⽆⼈化驾驶的关键技术之⼀。路径规划模块性能的⾼低直接关系车辆⾏驶路径选择的优劣和⾏驶的流畅度，⽽路径规划算法的性能优劣很⼤程度上取决于规划算法的优劣，如何在各种场景下迅速、准确的规划出⼀条⾼效路径且使其具备应对场景动态变化的能⼒是路径规划算法应当解决的问题。
图 0.1
根据对环境信息的把握程度可把路径规划划分为基于先验完全信息的全局路径规划和基于传感器信息的局部路径规划。其中，从获取障碍物信息是静态或是动态的⾓度看，全局路径规划属于静态规划，局部路径规划属于动态规划。全局路径规划需要掌握所有的环境信息，根据环境地图的所有信息进⾏路径规划；局部路径规划只需要由传感器实时采集环境信息，了解环境地图信息，然后确定出所在地图的位置及其局部的障碍物分布情况，从⽽可以选出从当前结点到某⼀⼦⽬标结点的最优路径。
在全局路径规划算法中，⼤致可分为三类：传统算法（Dijkstra算法、A*算法等）、智能算法（PSO算法、遗传算法、强化学习等）、传统与智能相结合的算法。智能算法种类繁多，但传统算法更为基础，故本着由浅⼊深的原则，⾸先对传统算法展开学习。科学家发现人类新器官
1 算法综述
在传统路径规划算法中，各种算法的实现原理和应⽤范围差异很⼤，但可以将以下五种算法看作⼀类（Dijkstra、A*、D*、LPA*、D* lite），以下对各算法的基本原理进⾏阐述，并在搜索原理和应⽤场景等⽅⾯进⾏了对⽐区分。 1.1 算法简述
1.1.1 Dijkstra算法
Dijkstra算法是由E.W.Dijkstra于1959年提出，⼜叫迪杰斯特拉算法。该算法采⽤了⼀种贪⼼模式，其解决的是有向图中单个节点到另⼀节点的最短路径问题，其主要特点是每次迭代时选择的下⼀个节点是当前节点最近的⼦节点，也就是说每⼀次迭代⾏进的路程是最短的。⽽为了保证最终搜寻到的路径最短，在每⼀次迭代过程中，都要对起始节点到所有遍历到的点之间的 最短路径 进⾏更新，具体看⼀下过程。
百位老人积蓄被骗
图 1.1 节点有向图
初始化：
建⽴distance[](起点到其他所有点的距离信息)、Top_node[]（最短路径信息）两个列表存放信息。其
中，distance[]的维度为节点的个数，每⼀个数值为到达对应索引节点的最短路径距离，⽐如distance[2]的值代表当前迭代时刻到达3号节点的最短距离。初始状态distance[0 inf 10 inf 30 100]，其中0代表⾃⾝，inf代表⽆法到达；Top_node[num1]，其中num1代表⼀号节点并以此类推。
搜索最⼩点：
到当前节点到下⼀点的最⼩值，即从num1开始搜索到1->5/1->3/1->6三条路，并到距离最⼩的路1->3。则此时到达num3点的最短路径确定为10，将num3存⼊Top_node[]。
松弛：
确定num3到最短路径，然后num3开始搜寻其弧尾，到3->4路径，此时1->3->4路径距离为10+50=60，⼩于inf，故将列表更新为distance[0 inf 10 60 30 100]。注意这⾥通过3->4这条路径缩短1->4这条路径的过程叫做“松弛”，该算法证实通过这样的⽅法进⾏路径寻优。
重复迭代：
除去num1和num3，从剩余点搜寻距离最⼩，到num5，故将num5加⼊Top_node[]。到弧尾路径5->4/5->6，进⾏松弛，其中1->5->4距离为30+20=50<60，1->5->6距离为30+60=90<100，所以列表更新为distance[0 inf 10 50 30 90]。
弗朗西斯卡
重复迭代：
除去num1、num3和num5，其余点寻最⼩，到num4，将其加⼊Top_node[]。然后到弧尾4->6，进⾏松弛，1->5->4->6距离
30+20+10=60<90，1->3->4->6距离10+50+10=70>60，进⾏列表更新distance[0 inf 10 50 30 60]。
重复迭代：
除去num1、num3、num4和num5，其余点寻最⼩，到num6，将其加⼊Top_node[]，然后没有到弧尾，则此时到达num6的最优路径到。
以上就是Dijkstra算法的简单实例，可见其主要是通过贪⼼原则逐个遍历最⼩⼦节点，然后利⽤松弛⽅法去优化路径选择，最终将最优路径存放到可读列表当中，以此来解决最优路径规划问题。
1.1.2 A*算法
A*算法是启发式搜索算法，启发式搜索即在搜索过程中建⽴启发式搜索规则，以此来衡量实时搜索位置和⽬标位置的距离关系，使搜索⽅向优先朝向⽬标点所处位置的⽅向，最终达到提⾼搜索效率的效果。
A*算法的基本思想如下：引⼊当前节点x的估计函数f(x)，当前节点x的估计函数定义为：
f (x)= g(x)+h(x)
其中g(x)是从起点到当前节点x的实际距离量度（代码中可以⽤两点之间距离代替）；h(x)是从节点x到终点的最⼩距离估计，h(x)的形式可以从欧⼏⾥得距离（）或者曼哈顿距离中选取。
算法基本实现过程为：从起始点开始计算其每⼀个⼦节点的f值，从中选择f值最⼩的⼦节点作为搜索的下⼀点，往复迭代，直到下⼀⼦节点为⽬标点。
1.1.3 D*算法
基于A*算法，Anthony Stentz在1994年提出了Dynamic A*算法，也就是D*算法。D*算法是⼀种反向增量式搜索算法，反向即算法从⽬标点开始向起点逐步搜索；增量式搜索，即算法在搜索过程中会计算每⼀个节点的距离度量信息H(x)，在动态环境中若出现障碍物⽆法继续沿预先路径搜索，算法会根据原先已经得到的每个点的距离度量信息在当前状态点进⾏路径再规划，⽆需从⽬标点进⾏重新规划。
其中，距离度量信息H(x)=H(y)+C(y, x)，H(y)代表x点到⽬标点的距离度量，C(y，x)代表y点到x点的距离度量，在算法中均可⽤两点间实际距离代替。
1.1.4 LPA*算法
绍兴县鉴湖小学2001年，由斯⽂·柯尼格(Sven Koenig)和马克西姆·利卡切夫(Maxim Likhachev)共同提出的Life Planning A*算法是⼀种基于A*算法的增量启发式搜索算法。
LPA*算法实现原理：
搜索起始点为所设起点（正向搜索），按照Key值的⼤⼩作为搜索前进的原则，迭代到⽬标点为下⼀搜索点时完成规划；Key值中包含启发式函数h项作为启发原则来影响搜索⽅向；处于动态环境时，LPA*可以适应环境中障碍物的变化⽽⽆需重新计算整个环境，⽅法是在当前搜索期间⼆次利⽤先前搜索得到的g值，以便重新规划路径。
其中，Key[]为⼀个⼆维数组：
g(n)代表起点到当前点的距离度量。rhs(n)为min(g(n’)+c(n’, n))，n’为n的⽗节点，h(n, goal)为启发项；搜索原则为：优先判断k1⼤⼩，若k1⼩则优先遍历，若k1=k2，则选择k2较⼩的点。
1.1.5 D* lite算法
中国生物工程杂志
护理研究D* lite算法是Koenig S和Likhachev M基于LPA_star 算法基础上提出的路径规划算法。D* lite与LPA*的主要区别在于搜索⽅向的不同，这就将Key[]定义中涉及到的⽬标点goal替换为起始点start的相应信息。
D*_lite算法是先在给定的地图集中逆向搜索并到⼀条最优路径。在其接近⽬标点的过程中，通过在局部范围的搜索去应对动态障碍点的出现。增量式算法的优势在于，各个点的路径搜索已经完成，在遇到障碍点⽆法继续按照原路径进⾏逼近时，通过增量搜索的数据再利⽤直接在受阻碍的当前位置重新规划出⼀条最优路径，然后继续前进。
1.2 算法对⽐
1.2.1 性能和应⽤对⽐
表 1.1中给出了五种算法分别在搜索⽅向、启发式、增量式、适⽤范围和现实应⽤五个⽅⾯的对⽐。以上五种算法的效能和适⽤范围各不相同，效能⾼且解决问题范围⼴并不⼀定代表应⽤⼴泛，⽬前实际应⽤的算法应偏向竭⼒发挥某⼀算法的专长，在基础功能之上不断优化算法性能。
1.2.2 理解浅见对⽐
搜索⽅向的正反：
在静态环境中全局地图信息已知，则⽆论正向搜索还是反向搜索都可以发挥效能。但是在动态环境中，⾯对未知地图，要想获得最短路径则需要不断的尝试，正向搜索很容易产⽣与最优路径背道⽽驰的现象，⽽此时反向搜索算法能够很好的处理这种情况。反向搜索配合增量式搜索使得D* lite算法在动态障碍图中，可以利⽤先前迭代中产⽣的节点距离信息，不断更新当前点到⽬标点的最优路径。⽽在正向搜索中，增量式算法只能提供当前点到起始点的距离信息和到⽬标点的启发估计信息，并不能保证未搜索区域的可通⾏性。
启发式与⾮启发式：
启发式算法能够在每次搜索时将搜索⽅向导向⽬标点，替代了⾮启发式算法向四周⽆规则遍历的局限，正常情况下能够⼤⼤提⾼搜索效率。但是在启发式路径受阻的情况下，搜索效果将适得其反。如图1.
图 1.2
启发式与增量式：
启发式搜索是利⽤启发函数来对搜索进⾏指导，从⽽实现⾼效的搜索，启发式搜索是⼀种“智能”搜索，典型的算法例如A*算法、遗传算法等。增量搜索是对以前的搜索结果信息进⾏再利⽤来实现⾼效搜索，⼤⼤减少搜索范围和时间，典型的例如LPA*、D* Lite算法等。
搜索⽅向的正反多与是否能处理动态规划有关；启发式搜索带来的时效能的提⾼，避免全局盲⽬搜寻；增量式搜索则代表着迭代信息的⼆次利⽤，多⽤于提⾼算法效率。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议