理工酷

常用的路径规划算法可分为基于采样的路径规划算法以及基于地图的路径搜索算法两大类,每类路径规划算法又都包含一系列算法。

基于采样的路径规划算法很早便开始用于车辆路径规划,比较常见的基于采样的路径规划算法有概率图算 法 ( Probabilistic Road Map , PRM ) 和快速随机扩展树算法( Rapidly -exploring Random Tree , RRT )。

概率图算法使用局部规划算法建立随机状态之间的连接关系,从而抽象出概率图,对于确定的起始状态和目标状态,它只需要快速地搜索概率图便可获得路径。 快速随机扩展树算法由 LaValle 和 Kuffner 提出,它最初专用于解决运动学约束的路径规划问题。

基于地图的路径搜索算法通常采用单元分解法或者道路图法建立环境模型,它通过搜索环境信息的环境地图获得最终路径。在这类搜索方法中,比较有代表性的有深度优先算法( De p th-FirstSearch , DFS )、 Breadth-FirstSearch , BFS )、广度优先搜索算法( 迭代加深搜索算法( Iterative-Dee p enin g Search , IDS )、 Uniform-CostSearch , UCS ) 等代价搜索算法( 和 启发式搜索算法( HeuristicSearch , HS ) 等。深度优先搜索算法、广度优先搜索算法、迭代加深搜索算法和等代价搜索算法使用了回溯技术实施搜索,它从起始状态出发沿着树的深度遍历树的节点,尽可能深地搜索树的分支,直至要么到达目标状态,要么到达一个搜索终 止点。

如果发现了目标状态,它退出搜索并返回解路径;如果到达的是一个搜索终止点,那么它将回溯到路径上含有未搜索过的节点的临近节点,并沿着这个分支继续搜索下去。因此,这类算法比较适合于解决环境中节点数目较少情况下的路径搜索问题,当节点数目比较多时,算法搜索速度慢、效率低。而启发式搜索算法在决定节点扩展顺序的估价函数中引入了启发值,即当前节点状态到目标状态之间的估计消耗,从而引导搜索朝向目标状态的方向,避免了盲目搜索,有助于提高算法的搜索效率,因而启发式搜索算法越来越广泛地应用于路径规划。

本回答的主要内容来自图书《自动驾驶技术概论》，清华大学出版社