大範圍定位與建立地圖

摘要：近年來，自動駕駛成為最熱門的議題之一，在此篇文章我們從無人車實現的角度，對於大範圍定位與建立地圖技術解釋其重要性，並對其原理做說明，概述了幾種不同的實現方法，也對一些著名的大範圍定位實驗及業界發展狀態做介紹，討論其未來的挑戰和方向。
Abstract：In recent years, autonomous driving has become one of the hottest and popular topics. In this article, we explain the importance of large scale localization and mapping technology from the perspective of self-driving cars technology. It also explains principle and outlines several different methods for implementation. In this paper, we also introduce some well-known experiments of localization and mapping as well as the status of this industry development. We conclude by the discussion about their future challenges and directions.

關鍵詞：定位與導航、高精度地圖、自駕車
Keywords：Localization and mapping, High density map, Autonomous driving

前言
隨者近幾年的無人車蓬勃發展，越來越多的廠商投入，大量的資源投入相關研發，發展的速度超乎想像，而對於無人車的開發，如何在大範圍區域將車子精準的定位為關鍵的技術之一，在此篇文章，我們將對此部分技術做相關的介紹。
大範圍的定位應用中，全球定位系統(Global Positioning System, GPS)是最常被用來使用的技術，其擁有高達98%的全球覆蓋率[1]，並且在搭配地面基準站後解決了傳統GPS精度不足的問題的問題，可將定位精度提升到公分等級[2]，但即使如此，使用上還是存在許多問題，最常遇到就是環境物體的遮蔽或產生多路徑干擾，造成訊號的劣化，使得定位訊號精度降低或斷訊。這個問題在城市中很容易發生(例:高樓大廈，高架橋下，隧道等)，造成定位訊號的不穩定。而三十多年來,同步定位與地圖建構 (Simulation Localization and Mapping,SLAM [3])在移動機器人的領域已為關鍵的技術，透過建立的周圍環境地圖如圖1所示，使得機器人能知道其目前在所處的位置，可應用在已知空間的定位與未知空間的探索，可藉其解決GPS因遮蔽而定位失效的問題。

圖1 3D點雲地圖

另外也有一些研究基於當前現有的地圖資源來做到大規模範圍的定位，像是利用現有的影像圖資(例:google map)加入影像辨識定位或加入道路基礎設施（道路標記或道路檢測）來引導車子，類似目前高級的商用車中加入了車道標記檢測功能(例:車道偏移輔助系統[4])，這種方法主要限制車輛的橫向位置，對於一些簡單的道路環境（例:高速公路）來說足夠了。
在本文中，我們會先對SLAM對其原理做說明，敘述幾種不同的實現方法，及大範圍SLAM演算法及數據相關研發資源，最後對一些大範圍定位實驗及業界發展做介紹。
大範圍定位與建立地圖
SLAM是構建未知環境的地圖同時估測其位置的計算問題，最初是由Smith和Cheeseman提出的[5]。它將地圖構建與定位結合在一起進行考慮。機器人藉由建立地圖來校正里程計[6]誤差;使得移動距離增加時，位置和方向誤差不會增加，因此又可以創建更準確的地圖。但機器人定位過程依賴於精確的地圖，但精準的地圖程又依賴於定位位置的精確信息，這類似雞生蛋蛋生雞問題，解這個問題常用的近似求解方法包括，卡爾曼濾波器[7]、粒子濾波器[8]等。
SLAM問題通常以概率方式表示，整個目標是能夠同時估計車輛的狀態和正在建造的地圖。假設機器人的狀態表示為x(1:t) = x1, x2…, xt 控制輸入表示為u(1:t) = u1, u2…, ut  環境觀測表示為z(1:t) = z1, z2…, zt，m表示地圖，在給定所有控制輸入和所有測量值的情況下估計機器人的軌跡和地圖。整個過程可以用動態貝葉斯網絡(Dynamic Bayes Network, DBN)表示，如圖2所示。這個問題稱為FULL SLAM，根據整個傳感器數據計算所有姿勢和地圖。

圖2 以貝葉斯網絡表示FULL SLAM問題