無人車怎麼規劃導航路線？用地圖啊
如今我們出行的方方面面都已經離不開地圖導航了。城市越來越大，工作強度越來越高，人們沒有時間和精力去了解城市的所有地圖和道路資訊。強大的地圖導航工具（像高德地圖、百度地圖等）為我們的出行提供了便利。隨著無人駕駛領域的發展，越來越多的人開始關心無人車是如何自動駕駛的。第一個關心的問題就是：無人車是如何進行導航的？它也用導航地圖嗎？
答案是肯定的，無人車也用導航地圖。不過，我們人有強大的大腦，可以根據導航地圖給出的粗略的路線，實時的根據路況進行判斷，並找到目標。而無人車的大腦還沒有人的大腦這麼強大，它必須知道自己該走那條車道，那條車道多長，何時轉彎，怎麼轉彎，轉彎半徑多大等等一系列的資訊。因此，無人車用的導航地圖跟我們人用的導航地圖不太一樣。
無人車用的導航地圖，通常稱為高精地圖。高精地圖的道路是一根根的電線，每一條電線代表了一條馬路的邊界或中心線。
（圖片來自網路）
（圖片來自網路）
高精地圖中的每一條線，實際上是由很多條線段連線而成，每條線段有起始點、終止點、方向角等資訊。如果是轉彎的曲線，則還包含了轉彎半徑、曲率、轉彎的弧線對應的角度、曲線圓心的位置座標、曲線的起始點、終止點等資訊。
圖片來自[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年出版