环境地图表示方法

根据不同的表示形式，环境地图表示方法主要分为度量地图表示法，拓扑地图表示法等。

1、度量地图表示法

度量地图表示法采用坐标系中的格栅是否被障碍物占据的方式来描述环境特征，分为几何表示法和空间分解法。

几何表示法利用包括点、线、多边形在内的几何元素来表示环境信息。相比于其他环境地图表示方式，几何特征地图更为紧凑，有利于位置估计和目标识别；缺点是环境几何特征提取困难。几何特征地图适合于在环境已知的室内环境提取一些简单的几何特征，而室外环境下的几何特征较难提取。常用的几何地图有Voronoi图、概率路图等。

几何表示法

停车场Voronoi图

空间分解法是把环境分解为类似于格栅的局部单元，根据他们是否被障碍物占据来进行状态描述。如果格栅单元被障碍物占据，则为障碍格栅；反之，则为自由格栅。空间分解法通常采用基于格栅大小的均匀分解法和递阶分解法。均匀分解法中的格栅大小均匀分布，占据格栅用数值表示。均匀分解法能够快速直观地融合传感器信息；但是，均匀分解法采用相同大小格栅会导致存储空间巨大，大规模环境下路径规划计算复杂度高。为了克服均匀分解法中存储空间巨大的问题，递阶分解法把环境空间分解为大小不同的矩形区域，从而减少模型所占用的内存空间。

均匀格栅地图是度量地图路径规划中最常用的。它把环境分解为一系列离散的格栅节点。所有格栅节点大小统一，均匀分布。格栅用值占据方式来表示障碍物信息。例如使用最简单的二值表示方法，1表示障碍格栅，不可通行；0表示自由格栅。

当用均匀格栅地图表示环境信息后，格栅节点之间只有建立一定的连接关系才能保证能从起点搜索到目标点的有效路径。

2、拓扑地图表示法

拓扑地图模型选用节点表示道路上的特定位置，并用节点与节点间的关系来表示道路间联系。这种地图表示方法具有结构简单、存储方便、全局连贯性好、规划效率高、鲁棒性强等特点，适合于大规模环境下的道路规划，但它包含信息量少，需借助其他传感器来对道路环境做进一步描述。

路径规划算法

目前路径规划方法分类大致如下：

比较常用的路径规划算法为基于采样的路径规划算法以及基于搜索路径规划算法。

1、基于采样的路径规划算法

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

概率图算法是在规划空间内随机选取N个节点，之后连接各节点，并去除于障碍物接触的连线，由此得到一个可行路径。显然，当采样点太少，或者分布不合理时，PRM算法是不完备的，但可以增加采样点使该算法达到完备，所以PRM是概率完备但不是最优的。

PRM算法

快速随机扩展树最初主要用于解决含有运动学约束的路径规划问题。由于RRT在状态空间中采用随机采样确定扩展节点，不需要预处理，搜索速度快。因此这种算法作为一种快速搜索算法在路径规划问题中获得广泛应用。

RRT算法

2、基于搜索的路径规划算法

基于搜索的路径规划算法通过搜索表示环境信息的环境地图来获得最终的路径。比较有代表性的算法有Dijkstra算法和A算法。

Dijkstra算法是典型的广度优先搜索算法。它是一个按路径长度递增的次序产生的最短路径的方法，是求解最短路径的经典算法之一。Dijkstra算法是一种贪心算法，它在每一步都选择局部最优解，以产生一个最优解。这也会导致该算法的时间复杂度较高，在图规模较大时，该算法的计算速度慢，很难满足路径规划实时性的要求。

A*算法是经典的启发式搜索算法，它是由Dijkstra算法改进而来的。其最显著的特点就是在搜索过程中增加了启发函数，通过给定启发函数来减少搜索节点，从而提高路径搜索效率。研究表明，A*算法搜索得到的路径能够同时满足实时性和最优性要求。

3、结语

现实环境远比这要复杂，良好的规划必须建立对周边环境的深刻理解，另外还需要建立大量的数学方程，以及需要考虑障碍物、车道线、路径曲率、曲率变化率以及车辆速度、加速度等多种因素的影响。