自动驾驶-规划-现代导航工程实现要点

说明

这篇博客主要讨论交通网络中的路径规划问题，学术上和工程上找到比dijkstra algorithm更快、更实用的算法。

介绍

这里的路径规划定义为：已知路网，给定起点和终点，选择最合适的一条路径。

假设路网、任意两个节点的cost都是静态不变的，对于一个有向图： $G = (V, E)$
有n个节点（node），m条边（edge），一条边 $edge(u, v)$ 的非负权重是 $weight(u, v)$ 现在我们要检索从起点s到终点t的最短的一条路径，使得权重之和 $d(u, v)$ 最小

在静态地图中，我们可以事先计算好很多信息来加速检索。该领域就是在实时检索所需时间、预计算所需时间、预计算所需空间三者之间的权衡做研究，因为当地图过大，我们不可能把所有任意两点之间的信息都预计算好并存储下来。

dijkstra algorithm是解决这类问题的最优算法，通常会使用Priority Queues来实现；

当所有的weight一样的时候，dijkstra algorithm就蜕化成了Breadth-first search。

双边搜索（Bidirectional Search）是实际工程中经常使用的策略，因为它可以很方便地结合其他加速技术，我们可以分别从起点和终点执行dijkstra algorithm，一旦两边都访问过同一节点，使用已经计算好的信息就可以得到最短路径。

启发式（Heuristics）商业导航软件不得不面对更复杂的道路网络，不得不解决低端手机上做检索的问题，因此不保证一定可以有结果的启发式依然在使用，比方说，直接忽略不重要的街道，除非这条街道跟起点或终点很近。虽然这要求导航软件必须小心对街道进行分类，但这种启发式确实有很大的加速效果。

目标导向的算法

动机：dijkstra algorithm会访问大量无关节点，搜索空间过大；
分类：
- 基于A* algorithm
- 基于剪枝

A*

A*背后的动机很简单，最短路径应该大约指向终点，如果用g(n)表示从起点到任意节点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离，那么A*算法的估计函数为：f(n) = g(n) + h(n)。当h(n)=0的时候，A* algorithm蜕化成dijkstra algorithm。h(n)就是之前提到的启发式（Heuristics）。

ALT算法

思想：基于A*, 利用地标（Landmark）和三角不等式（Triangle inequality）计算下界估计
核心：如何选取地标，可以使用贪心算法选取
优点：预处理速度快，加速客观
缺点：预处理空间开销大

inequation

reach剪枝算法（Reach-Based Routing）

定义：给定s-t最短路径P以及P上的一点v，定义顶点v关于路径P的reach值r(v, P) := min(d(s,v), d(v,t))。整个图G中，v的定义为 $r(v,G):=max_{P}\{r(v,P)\}$
剪枝：如果v的reach值满足不等式 $r(v,G) < min(\underline{d}(s,v), \underline{d}(v,t))$ 则v不进入优先级队列，其中 $\underline{d}(s,v)$ 表示s到v的距离下界估计。
缺点：预处理的计算复杂度过高

几何容器法

思想：通过边上的预存信息排除不可能位于最短路径上的边
实现：对图中的每条边e，用集合S(e)表示为以e为起始边的最短路径所能到达的顶点集合
松弛：用几何形状代替集合S(e)
缺点：预处理代价过于高，以至于没法用到实际工程上

边标记（Edge Labels）

思想：类似对二维连续空间画网格离散化，落在同一个网格的节点都使用同一个区域标签
实现：网格、四叉树、k-d树和 METIS等不同的划分方法
优点：查询简洁，提升明显，对内存要求不高
缺点：预处理慢；对动态场景适应性差；对距离中等的起点和终点效果较差（划分区域的效果不明显）

分层探索（Exploiting Hierarchy）

动机：目标导向方法减少搜索空间，但是搜索空间的下界是最短路径的顶点个数，对大规模路网来说，依然很难快速检索；
思想：分而治之
分类：
- 分割法：利用道路网的平面特性进行分割，计算分块边界之间的距离，构建高层网络（感觉有点像边标记（Edge Labels））
- 重要节点法：对节点分类，选出重要节点，对节点和边进行剪枝

hierarchy

分割法

分割法的理论基础是Planar separator theorem，不过该理论很难用于实践，因此有了更好用的变种。

分：递归地使用small separators将道路网分割成尽可能均匀的子区域，块之间的edge尽可能少，总边界node尽可能少；
治：计算每个子区域的边界点之间的距离，当搜索经过该块时可以直接在边界点上跳跃，而不需要搜索内部顶点；

基于分割的多层算法

定义：对于给定图 $G = (V, E)$ 和一系列node子集 $V := V_{0} \supseteq V_{1} \supseteq V_{2} ... \supseteq V_{L}$
定义多层覆盖图为： $g := (G_{0}, G_{1}, ... , G_{L})$
其中 $G_{0} := G$
对于 $l > 0$ 有 $G_{l} := (V_{l}, E_{l}), E_{l} := \{(s, t) \in V_{l} \times V_{l} |\ in\ G_{l-1}, exists\ a\ shortest\ path\ P = <s, u_{1}, u_{2}, ..., u_{k}, t>, \forall i, u_{i} \in V_{l}\}$
优点：加速效果明显，可以handle大规模路网
评价：看得不是很懂

层次公路（Highway Hierarchies，或HH）

局部区域：定义顶点u的局部区域N(u)为包含距离u最近的H个顶点的集合，H是调优参数；
公路网：edge(u, v)属于公路网，当且仅当v不在s的局部区域N(s)，u不在t的局部区域N(t)；简单点来说，就是不在s和t附近的公路边；
剪枝：删除非公路边，删除度数较低的节点（引入捷径保证其他顶点间的最小间距不变）
双边搜索：双边都搜索结束后，再从交汇点中找到最短路径
优点：毫秒级处理美国道路网级别的大规模图；道路网几何级别收缩，并保持稀疏性和平面性；局部搜索虽然较慢，但是搜索有限；

公路节点规划算法（Highway Node Routing，或HNR）

简介：基于分割的多层算法的更一般形式
核心：覆盖顶点集；选取重要节点；
优点：比HH预处理时间长，但是内存需求更小；比HH预处理简单；可以处理动态路网（因为节点的重要性一般是不怎么变的）；
评价：依然看得不是很懂

层次收缩算法 (Contraction Hierarchies，或CH)

简介：CH是HNR的特例
步骤：1.将节点按重要性升序排序；2.按此顺序收缩节点，同时添加捷径保证最短路径长度不变；
优点：层次结构清晰，易于实现，空间开销小于原图大小；

节点转移算法（Transit-Node Routing，或TNR）

假设：1.较远的起点和终点一定经过某些重要节点；2.首个重要节点组成的集合很小；

TNR

结语

该博客简单总结了针对真实路网的工程中的路径规划算法，具体的加速效果可以见参考文献。

参考文献[3]实际上是[1-2]的汉化整理版。