同時定位與及地圖構建

同時定位與及地圖構建（英文：Simultaneous localization and mapping，SLAM）係計算幾何學同埋機械人學當中嘅一種運算問題，志在構造抑或係更新未知環境嘅地圖嗰陣、同時跟踪埋個智能體喺地圖入邊嘅位置。雖然呢個問題初初睇落似係雞先定蛋先問題，但對於某啲環境，都有返幾種演算法係喺可控時間內勉強搞得扂佢嘅。啲近似嘅解決方案流行嘅包括有粒子濾波器、擴展卡曼濾波器、協方差交點同埋GraphSLAM。SLAM算法使喺導航、機械人地圖構建當中，亦使喺虛擬實境抑或係擴張實境嘅里程計當中。

2005年DARPA大挑戰賽冠軍STANLEY，上高運行有SLAM作為佢自動駕駛系統嘅一部分

SLAM機械人生成嘅地圖

SLAM算法係基於啲手頭上嘅資源量身做嘅，所以唔志在完美、衹志在操作啱搭性（operational compliance）。公佈有嘅方法得使喺自動駕駛汽車、無人駕駛飛行器、自主水下航行器、行星漫遊車、新式家用機械人甚至人體內部探察啲領域之中。

數學描述

根據貝葉斯規則、特別係貝葉斯推論有：

$P(H\mid E)={\frac {P(E\mid H)\cdot P(H)}{P(E)}}$

裏頭啲字母表示：

證據$\textstyle E$（譬如睇到路邊有隻鴨$\textstyle E$）同埋佢嘅概率$\textstyle P(E)$；

假說$\textstyle H$（譬如位置到唨某個圩市$\textstyle H$度）同埋嘅概率$\textstyle P(H)$（先驗概率）；

假說$\textstyle H$啱嘅話睇到證據$\textstyle E$條件概率$\textstyle P(E\mid H)$（到唨個圩市$\textstyle H$會睇到路邊有隻鴨$\textstyle E$嘅概率）；

持有證據$\textstyle E$嗰陣證實假說$\textstyle H$係啱嘅條件概率$\textstyle P(H\mid E)$（睇到路邊有隻鴨$\textstyle E$證實到唨個圩市$\textstyle H$嘅概率）（後驗概率，posteriors）。

基於呢種貝葉斯框架，SLAM問題入便嘅定位部分可以表述爲畀有一系列嘅控制量$u_{k}$同埋傳感器觀察量$o_{k}$，喺離散步$k$上，要得到智能機狀態（位置同姿態等等）嘅一個估計值$x_{k}$。所有啲數量好多時都係概率性嘅。係噉，就可以表示成：

$P(x_{k}|o_{1:k},u_{0:k-1})$

$=\eta (k)P(o_{k}|x_{k})\sum _{x_{k-1}}P(x_{k}|x_{k-1},u_{k-1})P(x_{k-1}|o_{1:k-1},u_{0:k-2})$

其中

$P(o_{k}|x_{k})$：喺某笪埞睇到嘢嘅概率（代表傳感器模型）；

$P(x_{k}|x_{k-1},u_{k-1})$：喺先前一笪埞$x_{k-1}$得到命令$u_{k-1}$之後到新埞嘅概率（代表運動模型），又叫轉換函數；

$P(x_{k}|x_{k-1},u_{k-1})P(x_{k-1}|o_{1:k-1},u_{0:k-2})$：早先狀態$x_{k-1}$轉到噉時狀態$x_{k}$；

$\eta (k)=\left[\sum _{x_{k}}P(y_{k}|x_{k})P(x_{k}|o_{1:k-1},u_{0:k-1})\right]^{-1}$：觀察值概率嘅倒數，對應貝葉斯推論式嘅分母。

推廣到離散時間$t$，考慮埋地圖$m_{t}$嘅構建嘅情況下，SLAM問題目標係計出：

$P(m_{t+1},x_{t+1}|o_{1:t+1},u_{1:t})$

透過呢種框架，可以根據一幅地圖同埋相應嘅轉換函數$P(x_{t}|x_{t-1})$ 嚟按順序更新啲位置嘅後驗概率：

$P(x_{t}|o_{1:t},u_{1:t},m_{t})=\sum _{m_{t-1}}P(o_{t}|x_{t},m_{t},u_{1:t})\sum _{x_{t-1}}P(x_{t}|x_{t-1})P(x_{t-1}|m_{t},o_{1:t-1},u_{1:t})/Z$

同樣個地圖可以按順序進行更新：

$P(m_{t}|x_{t},o_{1:t},u_{1:t})=\sum _{x_{t}}\sum _{m_{t}}P(m_{t}|x_{t},m_{t-1},o_{t},u_{1:t})P(m_{t-1},x_{t}|o_{1:t-1},m_{t-1},u_{1:t})$

似好多推斷問題（inference problems）噉，要得出考慮埋兩隻變數嘅嗰啲解以及一個局部最優解，可以透過用期望最大化算法嘅形式交替更新嗰兩個信念（beliefs）嚟做到。

演算法

用於比照接近前述方程式嘅統計學技術包括卡曼濾波器同埋粒子濾波器（即蒙地卡羅方法）。針對機械人嘅姿勢同埋地圖參數，啲技術可以估計返後驗概率函數。啲使協方差交叉嚟保守近似前述模型嘅方法可以避免得到依賴統計獨立性假設，來到減少大規模應用陣時嘅算法複雜性。其他啲近似方法、之用到簡單有界區域表述畀唔確定性嘅，都有提高到計算效率。

至於集合成員技巧就主要基於區間約束傳播。啲技巧提供唨一個包埋機械人姿勢嘅集合同埋地圖近似值嘅集合。捆綁調整（又喊做「光束法平差」），廣泛來講又係最大後驗估計（MAP），係SLAM嘅另一種流行技巧使到圖像數據嘅，佢可以將姿勢同埋地標位置佮埋起身估計，可以提高地圖保真度，並且經已用於啲商業化嘅SLAM系統當中（譬如Google嘅ARCore，之替走唨佢哋之前整開嘅擴張實境項目「 Tango 」）。喺畀定傳感器數據嘅情況下，最大後驗估計個估計器會計出一個最可能解釋畀機械人姿勢與及地圖，而唔係嘗試去估計成個後驗概率。

新嘅SLAM算法仲係一個活躍嘅研究領域， 而且經常係旨在處理類似下低提到嘅唔同要求同埋假設，啲針對唔同地圖、傳感器同埋模型嘅。好多SLAM系統都可以睇作係考慮埋呢啲唔同方面之後而經過揀選鬭出嘅結合體。

任務

繪圖

拓撲地圖係一種環境表示方法：比起創建幾何上精確嘅圖，反而志在捕獲個環境嘅連通性（即拓撲）。喺度量SLAM算法入便，經已使開拓撲SLAM方法嚟強制實現全局一致性。

反之，柵格地圖使用離散單元數組（通常為正方形抑係六邊形）嚟表示一個拓撲世界，藉此推斷出邊啲單元格捱厏住。好多時就假定啲單元格喺統計上係獨立嘅，嚟幫助簡化計算。喺噉嘅假設下，若果喺位置$x_{t}$新地圖嘅單元格同觀測值 $o_{t}$一致，個值$P(m_{t}|x_{t},m_{t-1},o_{t})$就設為1；若果唔係就設0。

藉由廣泛使用啲預早收集好嘅、高度詳細嘅地圖數據，入邊啲圖註詳細到包埋道路上各個白線段同埋路緣啲標記位置嘅，現代自動駕駛汽車上個製圖問題幾乎可以簡化到直程冇咁嚌。標有位置嘅視覺數據（例如Google嘅StreetView）亦都可以當作地圖嘅一部分。實質上，噉嘅系統直程捉SLAM問題簡化成一個愈發簡單嘅純定位任務（localisation only task），之可能衹需要到更新啲運行陣時出現喺地圖上嘅嗰啲喐緊嘅嘢（似汽車同人）。

感測

嚟自光達SLAM嘅累積註冊點雲。

SLAM使開幾種唔同類型嘅傳感器，而且各種傳感器類型嘅功能同埋極限一直係推動新算法產生嘅主要動力。統計獨立性係應對度量偏差同埋測量噪聲嘅強制性要求。唔同類型嘅傳感器催生唨唔同嘅SLAM算法，相應算法啲假設又最啱返啲傳感器。極端情況下，激光深度傳感器得出嘅激光掃描結果抑或係視覺傳感器攞到嘅視覺特徵可以畀足區域內好多點嘅細節，令到有時毋需再進行SLAM推斷，因為啲點雲入便嘅形狀可以透過圖像配準嘅每個步驟輕鬆、明確噉對齊錔返。相反，觸覺傳感器非常之稀疏（sparse），因為僅衹得到十分之臨近個智能機啲點嘅信息，所以要到好強大嘅先驗模型嚟補償啲純觸覺嘅SLAM方案。大多數實際嘅SLAM任務介於嗰視覺、触覺兩種極限之間。另外，仲有依靠聽覺傳感器嘅聽覺SLAM。

傳感器模型可以大致噉分為基於地標嘅方法同埋基於原始數據嘅方法。地標係世界上啲可以唯一標識得嘅對象，個位置可以藉由傳感器估算出嚟，譬如wifi接入點抑或係無線電信標。原始數據方法唔假定啲地標可以識別得，而係幫$P(o_{t}|x_{t})$建模並直接攞嚟作為位置嘅函數。

光學傳感器可以係一維（單光束）抑或係二維（掃描）嘅激光測距儀、3D高解析度光達、3D閃光光達、2D/3D聲納傳感器與及一/多台2D攝像頭。自2005年以嚟，由於喺移動設備中使用攝像頭係越嚟越普及，主要使用視覺（攝像頭）傳感器嘅VSLAM（可視SLAM）方案就得到唨深入研究。視覺同埋LIDAR傳感器啲信息豐富到可以喺好多情況下提取出啲地標。同時，SLAM嘅其他最新形式都包括有觸覺式SLAM （僅衹透過本地觸摸感測）、雷達SLAM、聲學SLAM、同埋Wifi-SLAM（透過附近Wifi接入點嘅強度進行感測）。近排有方法將SLAM佮埋用於多邊（譬如喺Real-time locating system，RTLS）抑或係多角度測量嘅準光學（quasi-optical）無線測距當中，以應對無線測量嘅唔穩定。一種用於行人室內定位系統嘅SLAM，衹使安裝喺鞋度嘅慣性測量單元作為主要傳感器，單純依賴啲行人識避開啲牆嚟自動繪出建築物嘅室內平面圖。

對於某啲戶外應用，鑑於高精度差分GPS傳感器嘅應用，SLAM嘅需求幾乎已經冇唨。從SLAM嘅角度嚟睇，考慮到啲似然值（likelihoods）之高，啲可以睇作係位置傳感器嘅裝置已經完全滿足SLAM嘅推斷任務。但係，GPS傳感器有時可能性能會下降抑係完全失效，特別係喺軍事衝突期間，啲都係某啲機械人應用十分關注到嘅場合。

運動學建模

$P(x_{t}|x_{t-1})$個式表示模型嘅運動學信息，通常包含有啲畀到機械人嘅動作命令嘅信息。機械人嘅運動學信息作為模型嘅一部分亦都包含喺模型裏便，嚟到改善喺固有噪聲同埋環境噪聲條件下嘅感知估計。個動態模型識平衡到嚟自各種傳感器、各種局部誤差模型嘅貢獻，並最終以一幅地圖嘅形式喺清晰、虛擬嘅描述結果當中整合嗮啲信息，之機械人嘅位置同埋前進方向就表現爲某啲機率雲。地圖構建係此類模型嘅最屘一個描繪過程，地圖本身就係噉樣嘅描繪結果抑或係個模型嘅抽象表述。

對於2D機械人，運動學信息一般由旋轉信息佮埋「前進」命令畀出，同時考慮埋啲電機噪聲而實現到。雖然互相獨立嘅噪聲喺角度同埋線性方向上形成嘅分佈並非高斯分佈，但經常藉由高斯分佈嚟做近似。另一種方法係忽略丟運動學信息，並且喺每個命令之後從機械人車輪度讀取啲里程計數據，之可以着睇作係一種傳感器信息而唔係運動學信息。

SLAM細分領域

聽覺SLAM

常見嘅SLAM問題經已擴展並應用到聲音領域，其中啲環境由聲源嘅三維位置表示。呢種技術亦即係聽覺SLAM（Acoustic SLAM），佢個早期實現經已利用到到達方向（Direction-of-Arrival，DoA）嚟估計聲源位置，並且依靠聲音定位嘅原理嚟確定啲聲源嘅位置。觀察者，也即係機械人必須配備咪高風陣列先用得到聽覺SLAM，噉樣先正確噉估計得到啲DoA特徵。聽覺SLAM為聲音場景地圖構建嘅進一步研究奠定基礎，同時亦都可以透過語音喺人機交互中發揮到重要作用。為唨幫多個、間中會斷續嘅聲源嚟做地圖構建，聽覺SLAM系統利用隨機有限集理論（Random Finite Set theory）入便嘅基礎原理嚟處理聲音地標嘅嗰啲變化。但係，聲音特徵嘅本身性質令到聽覺SLAM易受環境中混響、聲源靜默情況同埋噪聲問題嘅影響。

視聽SLAM

初初係為人機交互設計嘅視聽SLAM係一個框架，佢可以融合環境入便嘅聽覺形態同埋視覺形態嚟獲得地標特徵。人類互動嘅特徵唔單止限於視覺形態，仲包括埋聽覺形態。因此，以人作為中心嘅機器同埋機械人嘅SLAM算法必須兼顧呢兩組功能。透過使用諸如人嘅姿勢之類嘅視覺特徵同埋諸如人嘅言語之類嘅聽覺特徵，視聽框架可以估計到並繪製出人類地標嘅位置，並融合嗰啲信念嚟整出一幅仲要頑健尐嘅環境地圖。對於移動機械人（例如無人機、服務機械人）當中嘅應用，使返低功率、輕便尐嘅設備（例如單目相機抑或微電子咪高風陣列）十分之有價值。視聽SLAM仲可以實現啲傳感器之間嘅互補功能，藉由音頻傳感器嘅全感測範圍同埋無障礙表示環境嘅特性可以補償返光學傳感器啲諸如視場逼窄、特徵遮擋、仲有輕量級光學傳感器常見嘅光學衰減（optical degradations）等問題。音頻傳感器對混響、聲源靜默同埋噪聲等等問題嘅易感性亦都可以透過融合返由視覺方式獲取嘅地標信念而得到相應嘅補償。對於創造啲佮人類語音同埋人類動作完全交互得嘅機械人同埋機器嚟講，環境入便聽覺同埋視覺感知途徑之間嘅互補能力非常之有價值。

協作SLAM

協作式SLAM可以組合嚟自多個機械人抑係用戶嘅圖像，嚟生成3D地圖。

動態環境

非靜態環境（例如包含其他車輛抑係行人嘅環境）照舊有好多挑戰值得研究。用DATMO嘅SLAM係一種模型，之可以用返戥跟蹤智能機本體類似嘅方式嚟跟蹤埋環境入邊啲移動對象。

閉環問題

閉環問題係識別先前到達過嘅位置並相應噉更新信念嘅問題。呢個點解成爲一個問題係因為模型抑係算法嘅錯誤會令到系統分配到低先驗值畀個位置。典型嘅閉環方法使到第二種算法嚟計出某種類型嘅、傳感器測量嘅相似度，並喺檢測到匹配嗰陣，設置過啲位置嘅先驗值。呢個可以透過譬如話存儲同埋比較啲嚟自每個先前訪問過嘅位置個SIFT特徵嘅詞袋矢量嚟做到。

主動勘察

「主動SLAM」研究SLAM個綜合問題，即決定下一步移動邊度先可以最高效噉構建返幅地圖。呢種主動勘察喺觸覺SLAM之類啲稀疏傳感方案中特別要用到。主動SLAM經常係透過喺假設動作下逼近地圖嘅熵嚟做到。「多重智能機SLAM」仲將呢個問題擴展到多個機械人協調佮夥嚟進行最佳探索嘅情況。

仿生SLAM

喺神經科學中，海馬體似乎參與唨SLAM嘅運算， 並促使位置細胞嘅形成，幫由生物啟發嘅SLAM系統（譬如RatSLAM）奠定唨基礎。

實現

各種SLAM算法都喺開源機械人作業系統（ROS）啲庫度實現到，經常佮埋點雲庫（對於3D地圖）抑或係OpenCV（對於視覺特徵）一齊用。

歷史

SLAM嘅其中一項開創性工作係RC Smith同埋P. Cheeseman喺1986年關於空間唔確定性嘅表示同埋估計嘅研究。其他開拓性工作由休·杜蘭特·懷特（ Hugh F. Durrant-Whyte）個研究小組喺1990年代初做出，個研究表明SLAM嘅解決方案衹存在於無窮數據極限當中。呢個發現令到啲人尋找喺計算上易處理並接近個解嘅算法。

由塞巴斯蒂安·特倫（ Sebastian Thrun）領導嘅自動駕駛車STANLEY同埋JUNIOR贏得唨DARPA大挑戰賽，又喺2000年代嘅DARPA城市挑戰賽入便獲得第二名。佢啲車上高搭載有SLAM系統，令到SLAM引起唨全世界嘅關注。而家可以喺消費級機械人吸塵器入便搵到大眾市場嘅SLAM實現。

睇埋

• 計算攝影
• 視覺里程計
• 卡曼濾波器
• 逆深度表示法
• SLAM方法一覽
• 移動機械人編程工具包（MRPT）項目：一組開放源代碼、跨平台嘅庫，涵蓋唨透過粒子濾波同埋卡曼濾波嘅SLAM。
• 蒙特卡洛定位
• 多輛自主地面機械人國際挑戰賽（MAGIC）：一項耗資160萬美元嘅國際挑戰賽，需要多輛車共同繪製大面積地圖
• Neato Robotics
• 粒子濾波器
• 探戈計劃
• 機械人地圖構建
• Stanley，使用SLAM技術嘅DARPA大挑戰載具冠軍
• 立體攝影測量
• 運動推斷結構

連出去

• Probabilistic Robotics，由Sebastian Thrun、Wolfram Burgard同埋Dieter Fox整嘅，有清晰嘅概述畀SLAM。
• SLAM for Dummies（同時定位與及地圖構建教程）
• Andrew Davison，倫敦帝國學院計算機系嘅研究頁面畀視覺SLAM。
• openslam.org收集有開源代碼同埋說明畀SLAM。
• 卡曼濾波嘅Matlab工具箱應用於同時定位與及地圖構建畀運行喺1D、2D、3D環境嘅載具。
• DLR嘅FootSLAM研究頁面，包括相關嘅Wifi SLAM同埋PlaceSLAM方法。
• SLAM講座online基於Python嘅SLAM講座。