APA(自动泊车辅助系统):路径规划算法(A*算法)
前言
A*算法在网上有许多讲解，各种各样的版本都有，包括“文档”或者“视频”的形式都能够找到，这些讲解中都是作者基于作者个人的理解进行的，其中对算法的理解难免有出入，这就导致了后来者往往学习后出现“稀里糊涂”的感觉，这其中就包含我自己，因此针对这种情况，本人基于对算法论文的学习，做了一个总结概括，并在这里做了一个记录，记录内容如下：
目录
0. A*算法简述
1. A* 算法原理分析
0 A*算法简述
A*算法最早于1964年在IEEE Transactions on Systems Science and Cybernetics中的论文《A Formal Basis for the Heuristic Determination of Minimum Cost Paths》中首次提出，论文如下链接Sci-Hub | A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107 | 10.1109/tssc.1968.300136，其属于一种经典的启发式搜索方法，所谓启发式搜索，就在于当前搜索节点往下选择下一步节点时，可以通过一个启发函数来进行选择，选择代价最少的节点作为下一步搜索节点而跳转其上。
论文中A*算法步骤如下：
图 1 A*算法原始论文中的设计步骤
上图中， � 为目标集合（这个目标集合的概念下文会有阐述）；
关于A*的阐述就不做过多介绍，这块网上都很多，主要对其原理在下文进行分析。
1 A* 算法原理分析
1.1 关键名词的理解
1.2 算法逻辑
（1）建图（即初始化全局地图，并划分栅格）
举一个自动泊车的例子：开始泊车之前，在一个非开放空间内，由“道路边界”“车位上边缘边界”“车位边界”组成了一个“可行驶区域”，如果采用A*算法，那第一步就是建立这么一个“地图”并对这个地图进行“栅格”划分（当然从泊车性能指标的角度考虑：这里的栅格大小也是有讲究的，这里先不做叙述，仅对算法先做总结），每个节点指的就是每个栅格的中心点，示例图如下：
图 2 A*算法初始化全局地图
（2）OpenList 与 CloseList 更新
基于图2，对OpenList 与 CloseList进行分析描述，去“车位上边缘边界”与“道路边界”之间的区域进行分析，如下图（实际泊车也很少会有障碍物出现在这里，这里仅用作分析算法原理使用）：
图 3 A*路径规划搜寻原理分析
**注：（1）**这里为什么说最多八个栅格，一方面根据A*的启发函数的计算方式来说，节点往下走的方向即指这八个方向，如图4所示；另一方面来说，地图中的节点包含障碍物节点（节点分为可走和不可走，障碍物节点不可走），如果节点周围包含障碍物，则栅格数小于八个，如图5所示，此时的节点数为六个，准确说是可走节点（放入OpenList中的均指可走节点）。
图 4 节点周围栅格表示法
图 5 节点周围包含障碍物节点的示意图
基于图4，将此区域单独拿出来讨论，初始时刻OpenList内的栅格应包含下图6中所标记的节点，即OpenList ={N1 N2 N3 N4 N5 N6 N7 N8}
图 6 节点周围栅格示意
基于图5，将此区域单独拿出来讨论，初始时刻OpenList内的栅格应包含下图7中所标记的节点，即OpenList ={N1 N2 N3 N6 N7 N8}
图 7 有障碍物节点时最优节点附近栅格表示
综上，是对OpenList 的一个说明， CloseList则比较好理解，它就是存放最优节点的一个集合，当算法从其实节点搜寻到最后的目标点时， 将CloseList中的节点连接起来就是规划的路径。
（3）基于初始节点开始往下搜寻计算
此处总结计算之前先介绍一下几个求解点到点距离的计算方法，这也是A算法中启发函数所采用的计算方式之一（ A* 采用的是曼哈顿距离（Manhattan distance）），分别如下：
（一）曼哈顿距离
标准的启发函数是曼哈顿距离（Manhattan distance），如下图所示
图 8 几种距离求解的几何描述
**曼哈顿距离为：**两点之间的横坐标之差的绝对值 + 两点之间纵坐标之差的绝对值
（二）欧几里得距离（欧氏距离）
这个就是我们物理中常说的两点之间的距离求解公式
（三）对角线距离
在后续混合A*中详细介绍；
搜索计算介绍：
下面开始对A*的搜索计算进行总结（这部分其实比较好理解），此处假设节点到节点横向或纵向移动一个节点的代价记为10**（或通俗理解：就是横向移动或纵向移动一个节点需要消耗多少能量），斜向移动记为14（** 102≈14 ，标记为10就是为了好计算或好表示，标记为任何都行），如下图所示：
图 9 移动一个节点的代价表示
图10 基于起始点的A*算法搜索原理分析
综上，选取评价函数值最小的点既是最优节点，但巧合的是此处有两个点的评价函数的值相等，一般遇到此种情况可以使用一些策略选择最优节点，常见的几种策略如下：
（1）首选最早生成的节点：如果两个节点具有相等的评价函数值，那么可以选择最早生成的节点作为最优节点。这意味着在搜索树中，先生成的节点将被优先探索。
（2）首选最靠近起始点的节点：在评价函数值相等的情况下，可以选择距离起始节点最近的节点作为最优节点。这样可以尽量减少路径的长度。
（3）使用先进先出 (FIFO) 队列：将相等的评价函数值节点按先进先出的顺序加入待搜索队列。这样可以保证搜索按照广度优先的方式进行，即先探索更接近起始节点的路径。
