機器人SLAM原理及應用

段航琪 張峰源 杜嘯宇 劉源 臧博

摘 要：機器人同時定位與建圖技術在移動機器人、無人駕駛中占有核心地位。按照傳感器不同大體分為激光SLAM和視覺SLAM兩種，按照算法的不同又可以分為基于濾波器的SLAM算法和基于圖優化的SLAM算法?，F有的SLAM開源算法有gmapping、cartographyer、ORB-SLAM等。在二位柵格地圖上，主要使用A*算法和DWA算法完成導航。

關鍵詞：機器人SLAM；自主導航；A*算法；DWA算法

一、SLAM的起源

移動機器人在進入一個陌生環境時，要解決“我在哪”以及“我周圍的環境是怎樣的”這兩個問題，才可以更好地進行移動和工作。而在位姿估計的同時建立環境地圖，就是機器人SLAM技術。

二、SLAM的原理

SLAM主要解決位姿估計和環境地圖建立這兩個問題，這兩個部分是相互依存的。

1.定位

機器人估計自身位姿有兩種方案。一是靠里程計信息進行估計，里程計信息來源主要有輪式編碼器、慣性測量單元（imu）、攝像頭（視覺里程計）這幾類傳感器；另一種是靠觀測路標點進行位姿估計，通過激光雷達掃描得到的深度信息或者攝像頭拍照，對機器人當前位置周圍的特征點進行提取，然后將提取到的特征點與之前的路標進行匹配，根據機器人對路標點的觀測量可以得出機器人當前相對于路標點的位姿。理論上，這兩種方法在沒有測量誤差的情況下都可以單獨估計機器人位姿。但由于數據測量噪聲的存在，單獨使用其中一種無法得到機器人準確的位姿，因此需要將兩種數據進行融合，得到效果更好的位姿估計量。融合的方法分為濾波器和圖優化兩種，經典的SLAM算法是基于濾波器的，而近年來的研究熱點為基于圖優化的視覺SLAM。

2.建圖

機器人在定位過程中同時建立環境地圖。最基本的，機器人在定位過程中，將自身位置周圍的landmark（地標）位置記錄下來，便構成一張記錄地標位置的地圖。機器人可以通過觀測路標并與路標地圖比較，從而實現兩種定位方法中的觀測路標法。

三、SLAM在機器人上的應用——自主導航

1.柵格地圖

SLAM在機器人上的應用主要為機器人自主導航。機器人通過環境地圖中的路標信息與傳感器觀測值來估計自身位置，并根據導航目標點和地圖來進行路徑規劃（path planning）和軌跡規劃（trajectory planning）。而前面介紹的SLAM原理中的建圖環節的地圖，只包含路標信息，而不包括路標之外的信息，這種地圖稱為“稀疏地圖”。顯然，稀疏地圖并不能體現各路標點之間的道路狀況，如果機器人使用稀疏地圖進行導航，比如直奔某個路標點，那么極有可能在中途碰到障礙物。因此，導航需要的是包含路標信息以及路標之間道路狀況的地圖，我們稱這種包含信息更多的地圖為“稠密地圖”。稠密地圖中應用較廣的一種是“占據柵格地圖”， 機器人對環境地圖的描述的方式最常見的為柵格地圖（Grid map）或者稱為Occupancy Map，如下圖所示。柵格地圖就是把環境劃分成一系列柵格，其中每一柵格給定一個可能值，表示該柵格被占據的概率。

下面以柵格地圖來介紹機器人導航算法。導航算法分為全局路徑規劃與局部路徑規劃兩部分。

2.全局路徑規劃——A*導航算法

A*導航算法，俗稱A星算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的算法。常用于游戲中的NPC的移動計算，或網絡游戲的BOT的移動計算上。如下圖，考慮具有許多障礙的方格，我們給出起始單元和目標單元。我們希望盡可能快地從起始單元到達目標單元。該算法綜合了最良優先搜索和Dijkstra算法的優點：在進行啟發式搜索提高算法效率的同時，可以保證找到一條最優路徑（基于評估函數）。

在此算法中，如果以 表示從起點到任意頂點 的實際距離， 表示任意頂點 到目標頂點的估算距離（根據所采用的評估函數的不同而變化），那么A*算法的估算函數為：

這個公式遵循以下特性：

如果 為0，即只計算任意頂點 到目標的評估函數 ，而不計算起點到頂點 的距離，則算法轉化為使用貪心策略的最良優先搜索，速度最快，但可能得不出最優解；

如果 不大于頂點 到目標頂點的實際距離，則一定可以求出最優解，而且 越小，需要計算的節點越多，算法效率越低，常見的評估函數有——歐幾里得距離、曼哈頓距離、切比雪夫距離；

如果 為0，即只需求出起點到任意頂點 的最短路徑 ，而不計算任何評估函數 ，則轉化為單源最短路徑問題，即Dijkstra算法，此時需要計算最多的頂點；

3.局部導航算法——DWA

機器人局部路徑規劃常用DWA算法，動態窗口法主要是在速度（v，w）空間中采樣多組速度，并模擬機器人在這些速度下一定時間（sim_period）內的軌跡。在得到多組軌跡后，對于這些軌跡進行評價，選取最優軌跡所對應的速度來驅動機器人運動。該算法突出點在與動態窗口這個名詞，它的含義是依據移動機器人的加減速性能限定速度采樣空間在一個可行的動態范圍內。該算法主要包含速度采樣和評價函數兩部分。

（1）速度采樣

建立機器人的軌跡運動模型后，根據速度就可以推算出軌跡。因此只需采樣很多速度，推算軌跡，然后評價這些軌跡優劣。速度采樣的過程為：在速度（v，w）的二維空間中，存在無窮多組速度。但是根據機器人本身的限制和環境限制可以將采樣速度控制在一定范圍內。

（2）評價函數

在采樣的速度組中，有若干組軌跡是可行的，因此采用評價函數的方式為每條軌跡進行評價。

參考文獻：

作者簡介：

段航琪（1999.04.23-） 男，漢族，河南省開封市，本科生，研究方向：自動化

張峰源（1998.10.26-） 男，漢族，河南省周口市，本科生，研究方向：機械工程

杜嘯宇（1998.10.8-）男 漢族 河南省信陽市淮濱縣 本科 研究方向：汽車工程

劉源 （1999.4.2-）男 ，漢族，河南省鄭州市，本科生，研究方向：自動化

臧博（1998.6.18-）男，漢族，山東省泰安市，本科生，研究方向：機械工程