北京伍强科技有限公司-尊龙凯时官网登录

        尊龙凯时官网登录的版权声明：本文为csdn博主「曼陀罗彼岸花」的原创文章，遵循 cc 4.0 by-sa 尊龙凯时官网登录的版权协议，转载请附上原文出处链接及本声明。

        原文链接：

        https://blog.csdn.net/tiandijun/article/details/62226163

        下面是路径规划最常用的a*算法的介绍。

        1、路径规划定义

        路径规划是指的是机器人的最优路径规划问题，即依据某个或某些优化准则（如工作代价最小、行走路径最短、行走时间最短等），在工作空间中找到一个从起始状态到目标状态能避开障碍物的最优路径。

        也就是说，应注意以下三点：

        ❖   明确起始位置及终点

        ❖   避开障碍物

        ❖   尽可能做到路径上的优化

        机器人的路径规划应用场景极丰富，最常见如游戏中npc及控制角色的位置移动，百度地图等导航问题，小到家庭扫地机器人、无人机，大到各公司正争相开拓的无人驾驶汽车等。

        这里介绍一下在游戏以及无人机航线规划上最常见的a*算法。

        2、a*算法详解

        在计算机科学中，a*算法作为dijkstra算法的扩展，因其高效性而被广泛应用于寻路及图的遍历，如星际争霸等游戏中就大量使用。

        在理解算法前，我们需要知道几个概念：

        搜索区域（the search area）：图中的搜索区域被划分为了简单的二维数组，数组每个元素对应一个小方格，当然我们也可以将区域等分成是五角星、矩形等，通常将一个单位的中心点称之为搜索区域节点（node），而非方格（squares）。

        开放列表(open list)：我们将路径规划过程中待检测的节点存放于open list中，而已检测过的格子则存放于close list中。

        父节点（parent）：在路径规划中用于回溯的节点，开发时可考虑为双向链表结构中的父节点指针。

        路径排序（path sorting）：具体往哪个节点移动由以下公式确定：f(n) = g(n) h(n)。g代表的是从初始位置a沿着已生成的路径到指定待检测格子的移动开销。h指定待测格子到目标节点b的估计移动开销。

        启发函数（heuristics function）：h为启发函数，也被认为是一种试探，由于在找到唯一路径前，我们不确定在前面会出现什么障碍物，因此用了一种计算h的算法，具体根据实际场景决定。在我们简化的模型中，h采用的是传统的曼哈顿距离（manhattan distance），也就是横纵向走的距离之和。

        如图中所示，绿色方块为机器人起始位置a，红色方块为目标位置b，蓝色为障碍物。

        现用a*算法寻找出一条自绿色a到红色b的最短路径，经简化，每个方格的边长为10，即垂直水平方向移动开销为10。节点对角线为10，因此斜对角移动开销约等于14。因此具体步骤如下：

        （1）将a点加入到open list中，图中所示，上下左右移动一格距离为10，斜对角移动距离为14。环绕绿色方块的就是待检测格子，左下角的值就是g值，右下角为h值，左上角对应的就是f值，找到f值最小的节点作为新的起始位置。

        （2）绿色格子右侧的节点f为40，选作当前处理节点，并将这个点从open list删除，增加到close list中，对这个节点周围的8个格子进行判断，若是不可通过或已经在close list中，则忽略之。否则执行以下步骤：

        若当前处理格子的相邻格子已经在open list中，那就计算临近节点经当前处理节点到起点的距离g是否比原g值小，若小，则把相邻节点的父节点（parent）设置为当前处理节点。

        若当前处理格子的相邻格子不在open list中，那么把它加入，并将它的父节点设置为该节点。

        （3）重复1、2步骤，直到终点b加入到了open list中，再沿着各节点的父节点回溯遍历，将遍历得到的节点坐标保存下来，所得的节点就是最短路径。

        最终效果如图所示：

        在github上找到了一个a-star的c 源码：https://github.com/booirror/data-structures-and-algorithm-in-c供参考。

        但也发现，在整个计算过程中，a*算法结合了启发式方法，利用估值函数f(h)来估计途中当前点与终点距离，并由此决定搜索方向，当这条路失败会重新尝试其他路径，但不理想的估值函数会导致整个算法运行很慢，而且这种算法虽说在时间上最优，但也存在空间增长是指数级别的缺点。因此在往高维状态空间进行运算时，速度会受到影响，基于a*算法迭代加深的ida*算法则有效解决了空间增长带来的问题。

        3、自动驾驶对路径规划的需求

        目前业内对自动驾驶的技术方案观点较为一致，主要可分为四个部分：

        因此首先要做的就是对外部环境的实时获取及车辆的动态路径规划。 传统机器人路径规划大致可分三种：

        ❖   静态结构化环境下的路径规划

        ❖   动态已知环境下的路径规划

        ❖   动态不确定环境下的路径规划

        将其与自动驾驶对应起来，静态的规划就是根据地理信息以及交通规则在已知的全局地图上进行道路循迹，但这个技术对于目前自动驾驶实现来说并没有什么实际应用价值。

        自动驾驶需要的是对预先已选择好的最优路径，甚至在未知的环境下，基于实时不确定的场景，进行动态调整的路径规划技术，而这对地图的需求、外部信息采集等就还是要依赖上一篇提及的如摄像头、激光雷达、传感器等硬件的支持。

        之前网上有在转载的一篇《从算法上解读自动驾驶是如何实现的》也有所总结，提到目前自动驾驶上应用较广的有dijkstra、lee、floyd、双向搜索算法以及蚁群算法，大家如果感兴趣可以自行搜索学习，这里不再赘述。

        现有传统机器人路径规划技术已经发展得较为成熟，而将该技术如何更为符合场景地应用到自动驾驶技术上还有很长的探索阶段，但现已存在的包括a*算法在内的一系列最优路径算法将会越来越由于图论、人工智能、机器人技术、自动驾驶等多学科的融合下得到更大的发展。