在前一节（自动驾驶环运动规划的相关术语和定义）的状态空间包括车辆位置、方向、线性或角速度的每个表示，以及任何其他感兴趣的度量，自动驾驶其他感兴趣的度量就是本文需要介绍的空间。
规划自动驾驶车辆在道路上的行程时，需要以能够查询路径的方式来表示环境。这意味着必须将物理空间转换为配置或状态空间。当车辆在道路上行驶时，传感器的数据和从高精地图（什么是高精地图查看我们之前文章2020年自动驾驶汽车技术报告 - 自动驾驶汽车硬件和软件最新技术的指南之感知与定位）中获得的信息被用于将环境的连续性转换为道路网络的数字表示，这是就是自动驾驶规划的基本空间。
这种离散化的自动驾驶空间搜寻必须在效率、密度和表现力方面得到有效处理，因为高密度网络可能导致高计算成本和高功率。虽然不充分的空间表示虽然可以提高计算速度，但可能会导致自动驾驶空间里面不准确，那么就会有碰撞安全风险，所以空间搜寻是自动驾驶非常重要的一步。
当然空间搜寻方法有仅仅使用道路边界和障碍物的位置在连续坐标系中启动搜索，例如，Driving Corridors。有分解（或镶嵌）技术以更高的分辨率分析空间，包括Voronoi Diagram，occupancy grids，cost maps，lattices。本文将大概介绍以上几种方法。
a,Voronoi Diagram
Voronoi图描述了彼此接近的点，或他们的最近的邻居之间的空间关系。它是从点或位置派生的一组连接面。Voronoi“区域”的每一条线都位于两点之间。
在这里，您可以看到每条线恰好位于两点之间的中间，并且它们都在中间汇合。让我们向场景中添加更多点，看看会发生什么：
现在，这变得越来越有趣！我们开始获取实际区域,那么每个地区告诉我们什么？我们知道，在区域内时，我们保证最接近也在该区域内的单点。这告诉我们很多有关我们附近的东西的信息，这是Voronoi图中基本的空间关系。
通过这种空间关系我们就可以找出从A到B的路径，当然你可以赋予不同的权重可以寻找最快和最安全的路径。
Voronoi Digrams生成使车辆和周围障碍物之间的距离最大化的路径。用于搜索Voronoi图的算法是完整的，如果自由空间中存在路径，它也会出现在Voronoi Digrams 如图a所示，灰线代表Voronoi边缘（即与检测到的障碍物有最大距离的边缘），并产生一个车辆可以执行其行程的空间。2010年Dolgov等人通过将Voronoi Digrams与潜在的场景相结合，将Voronoi Digrams用于停车场中自动驾驶路径规划；这是一种源自移动机器人技术的避障算法。这种被称为Voronoi digrams的组合方法是为了克服传统的势场方法在狭窄通道（产生高潜在性）中的问题而开发的，这种方法使这些通道实际上不可穿越。Voronoi图通常用于静态环境中的规划，例如停车场。此外，Voronoi digrams本身并不适用于道路路径规划，因为车辆沿其行驶的Voronoi边可能是不连续的，不适合非完整约束车辆（什么是不完整约束可以查看我们之前文章自动驾驶环运动规划的相关术语和定义）。
b, Occupancy Grid c, Cost maps**
占用网格和成本图以类似的方式工作；它们都将状态空间离散成一个网格，并且网格的每个单元都与单元被障碍物占用的概率相关，或者与穿越的可行性或风险成比例的成本相关。风险或可行性主要通过考虑障碍物、车道和道路边界的存在来计算。基于网格的方法可以快速找到计算能力较低的解决方案，但难以以稳健的方式解释非线性动力学，并且在存在障碍物的情况下。如图1b和c所示，占用网格由一个网格组成，其中包含障碍物的位置和（有时）显示其预期运动的附加速度；而在成本图中，某个单元的成本越高，其在地图上的表现就越强烈。
d,State Lattice
状态格可以看作是网格的泛化。正如grids是通过重复矩形或正方形来离散连续空间一样，lattices是通过有规律地重复原始路径来构建的，这些路径连接了车辆的可能状态，如图1d所示。然后规划问题就减少到了一个边界值将原始状态与所需最终状态相连接的问题。状态格克服了基于grids的技术在效率上的局限性，而不增加计算能力。
e,Driving Corridors
Driving Corridors代表一个连续的无碰撞空间，以道路和车道边界以及其他障碍物为边界，车辆将在此处移动。驾驶走廊基于详细数字地图（高精地图）上给出的车道边界信息，或使用同步定位和制图（SLAM）技术构建的地图。车道边界形成了驾驶走廊的外部边界，在存在障碍物时受到限制。在图1e中，根据选择的操纵为每辆车建造一个驾驶走廊。确定走廊的中心线形成了一条路径，在该路径上，自动驾驶车辆将沿着该路径行驶。连续规划的主要缺点是，由于规划道路网络的整个坐标范围需要密集的计算能力，道路或车道的表示可能会限制车辆的运动。
需要注意的是，上述用于规划的搜索空间表示技术并不总是独立使用的。例如，Voronoi图和势场被dolgovi et al。（2010a）生成安全轨迹。在大多数情况下，它们结合在一起，不仅是为了为单一的规划层次提供更好的结果，而且为了提供所有三个层次的规划能力（即路径、机动和轨迹规划）。表1总结了它们的优缺点。
以上为本文大概介绍空间搜寻的几种方法，当空间搜寻结束之后，就需要进行路径搜寻了，关注我们下一集将介绍路径搜寻。
参考文献：
1，Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research directions -Christos Katrakazas a , Mohammed Quddus a,⇑ , Wen-Hua Chen b,1 , Lipika Deka a
2，Robust Calculation of Ego-Vehicle Corridors
3，Multi-layer occupancy grid mapping for autonomous vehicles navigation
文中部分图片版权归其所有
*未经准许严禁转载和摘录
作者：Pirate Jack
来源：https://mp.weixin.qq.com/s/YX53OqY94t-yg7Vsub2VKw
Vehicle微信公众号
相关文章推荐
•自动驾驶 - 只需要一个聪明的人工智能取代人类驾驶
•自动驾驶的三种解决方案
更多汽车行业干货请关注Vehicle专栏。
