如今我们出行的方方面面都已经离不开地图导航了。城市越来越大，工作强度越来越高，人们没有时间和精力去了解城市的所有地图和道路信息。强大的地图导航工具（像高德地图、百度地图等）为我们的出行提供了便利。随着无人驾驶领域的发展，越来越多的人开始关心无人车是如何自动驾驶的。第一个关心的问题就是：无人车是如何进行导航的？它也用导航地图吗？
答案是肯定的，无人车也用导航地图。不过，我们人有强大的大脑，可以根据导航地图给出的粗略的路线，实时的根据路况进行判断，并找到目标。而无人车的大脑还没有人的大脑这么强大，它必须知道自己该走那条车道，那条车道多长，何时转弯，怎么转弯，转弯半径多大等等一系列的信息。因此，无人车用的导航地图跟我们人用的导航地图不太一样。
无人车用的导航地图，通常称为高精地图。高精地图的道路是一根根的电线，每一条电线代表了一条马路的边界或中心线。
高精地图中的每一条线，实际上是由很多条线段连接而成，每条线段有起始点、终止点、方向角等信息。如果是转弯的曲线，则还包含了转弯半径、曲率、转弯的弧线对应的角度、曲线圆心的位置坐标、曲线的起始点、终止点等信息。
图片来自[1][2]
如图所示，高精地图中的线路包含了无数条lane片段，每条lane在软件数据库中的定义包含编号（land ID）、类型（直行道、转弯、或者其他类型）、起始点坐标（经纬度）、圆弧信息（圆弧起始点、结束点、转弯半径、曲率、对应的夹角、圆心位置坐标等）、车道中心线信息（路宽、长度、起始点、结束点、航向等信息）。
无人车就是基于高精地图的lane数据库来进行导航路线规划的，在无人驾驶领域，称之为路由寻径（Routing）。路由寻径是无人车控制规划系统的最顶层的模块，它可以告诉系统该沿着哪条路的那条车道行驶，何时需要转弯，何时需要变道等信息。
路由寻径模块需要利用高精地图定义绘制的道路划分信息（lane片段信息），参考一定的优化策略（比如要求路线最短、行驶时间最短、主路优先、避开交通堵塞区等），结合无人车自身运动的约束（转弯半径等），借助优化求解算法解算出一个从起始点到目标点的最优道路行驶序列。路由寻径模块的输出，也是一个数据库或数据包，里面包含了连接起始点和目标点的一系列有序的lane片段，并且按照先后顺序进行了排序，序列信息如下：
{（lane-1, 进入点坐标，离开点坐标），（lane-2，进入点坐标，离开点坐标），……，（lane-n，进入点坐标，离开点坐标）}
得到了规划好的lane序列，下层的规划控制模块就会按照lane序列的顺序，依次跟踪每个lane序列的中心线，适时的改变形式策略（变道、超车、减速、加速等），直到无人车到达最后一个lane片段上的目标点为止。
路由寻径算法在具体实现的时候，并没有说起来这么简单。它根本上可以抽象为一个有向带权图的最短路径搜索问题。通过将高精地图中所有可能用到的lane序列覆盖的范围进行撒点抽样，并且根据安全风险的大小等因素给这些点与点之间的连接附加一个代价权重，风险大的连接代价权重大，这样，优化函数会根据优化目标尽量避开这些连接。
图片来自[1][2]
这样，无人车的路由寻径问题转化为有向带权图的最短路径搜索问题之后，就可以利用现有的成熟算法来求解最优路径了。无人驾驶领域，常用的路由寻径算法有：A*算法和Dijkstra算法。
[1] 刘少山, 唐洁, 吴双, 李力耕. 第一本无人驾驶技术书, 2017年出版
[2]
閱讀更多 原力源 的文章
