智能服務(wù)機(jī)器人正成為行業(yè)的風(fēng)口浪尖,,從清掃機(jī)器人開始,家庭陪伴機(jī)器人,、送餐機(jī)器人等陸續(xù)進(jìn)入公眾視線,。% f& ]8 C8 x0 o: T) x
' Z% f, Z* ]: [1 y) Z( ?
在討論這類機(jī)器人是否能解決實(shí)際問題時(shí),自主定位導(dǎo)航技術(shù)作為機(jī)器人智能化的第一步正不斷引起行業(yè)內(nèi)的重視,。同時(shí),,作為自主定位導(dǎo)航技術(shù)的重要突破口,SLAM 技術(shù)也成為關(guān)注焦點(diǎn),。
n8 d* v2 q* o. V* b- _, S
正如圖中所示,,機(jī)器人自主定位導(dǎo)航技術(shù)中包括定位、地圖創(chuàng)建與路徑規(guī)劃(運(yùn)動(dòng)控制),,而 SLAM 本身只是完成機(jī)器人的定位和地圖創(chuàng)建,,二者有所區(qū)別。
2 O7 d- p2 | ]3 x- ?4 p {, c% _) o% e
那么,,SLAM 技術(shù)究竟是如何實(shí)現(xiàn)的,?它有哪些難點(diǎn)?機(jī)器人如何實(shí)現(xiàn)自主移動(dòng)和路徑規(guī)劃,?到底什么樣的掃地機(jī)器人才算智能,? & P- q9 W& N. K* ^4 V% O" y" X
這些問題,小編將為你一一解答,,帶領(lǐng)大家了解機(jī)器人自主移動(dòng)的秘密,。 ; l% X6 ~. c; O0 ^ ?
今天,我們先從 SLAM 說起,。
) e3 Q& p3 \/ r' E
什么是SLAM技術(shù)? " E, R4 s' U7 |
SLAM 是同步定位與地圖構(gòu)建 (Simultaneous Localization And Mapping) 的縮寫,,最早由 Hugh Durrant-Whyte 和 John J.Leonard 提出。
7 c# m! Y! _% S
其實(shí),,SLAM 更像是一個(gè)概念而不是一個(gè)算法,,它本身包含許多步驟,其中的每一個(gè)步驟均可以使用不同的算法實(shí)現(xiàn),。主要用于解決移動(dòng)機(jī)器人在未知環(huán)境中運(yùn)行時(shí)即時(shí)定位與地圖構(gòu)建的問題,。
# e8 [3 ~% I4 b, Q$ Q7 C+ r# a5 C
當(dāng)你身處異地,怎么準(zhǔn)確找到想去的地方?在戶外迷路時(shí),,怎么找到回家的路,?沒錯(cuò),我們有導(dǎo)航軟件和戶外地圖,。 " u2 H2 y, k/ Y# o2 r; P! |, Q- e, g
和人類繪制地圖一樣,,機(jī)器人描述環(huán)境、認(rèn)識(shí)環(huán)境的過程主要就是依靠地圖,。它利用環(huán)境地圖來描述其當(dāng)前環(huán)境信息,,并隨著使用的算法與傳感器差異采用不同的地圖描述形式。
2 c9 Q, P9 j @3 U) R) }2 G
四種常見的地圖表示方法是什么,?
* O2 ~, u5 D `' ]' a# Z5 Y% {7 K3 W# a* W
機(jī)器人學(xué)中地圖的表示方法有四種:柵格地圖,、特征地圖、直接表征法以及拓?fù)涞貓D,。
6 g) h! |" Q4 k* p柵格地圖
4 p" i- o: ]# b. u5 ?
機(jī)器人對(duì)環(huán)境地圖的描述的方式最常見的為柵格地圖 (Grid map) 或者稱為 Occupancy Map,。柵格地圖就是把環(huán)境劃分成一系列柵格,其中每一柵格給定一個(gè)可能值,,表示該柵格被占據(jù)的概率,。 - K9 _9 n! O0 X
- W2 B1 W# |5 l. U) L
這種地圖看起來和人們所認(rèn)知的地圖沒什么區(qū)別,它最早由 NASA 的 Alberto Elfes 在 1989 年提出,,在火星探測車上就用到過,,其本質(zhì)是一張位圖圖片,但其中每個(gè)「像素」則表示了實(shí)際環(huán)境中存在障礙物的概率分布,。
) a/ P, H4 B. `" @4 z5 \
一般來說,采用激光雷達(dá),、深度攝像頭,、超聲波傳感器等可以直接測量距離數(shù)據(jù)的傳感器進(jìn)行 SLAM 時(shí),可以使用該地圖,。這種地圖也可以通過距離測量傳感器,、超聲波(早期)、激光雷達(dá)(現(xiàn)在)繪制出來,。 ) e0 R; u1 `9 O) h, Z
特征點(diǎn)地圖 % A; [' Y! W8 c: e p" N2 ]0 }1 z. H
特征點(diǎn)地圖,,是用有關(guān)的幾何特征(如點(diǎn)、直線,、面)表示環(huán)境,,常見于 vSLAM(視覺 SLAM)技術(shù)中。 / O; ~( X7 u; J; w" v9 d( S2 S
% o8 @( y" X/ [* ^7 l$ W
相比柵格地圖,,這種地圖看起來就不那么直觀了,。它一般通過如 GPS、UWB 以及攝像頭配合稀疏方式的 vSLAM 算法產(chǎn)生,優(yōu)點(diǎn)是相對(duì)數(shù)據(jù)存儲(chǔ)量和運(yùn)算量比較小,,多見于最早的 SLAM 算法中,。 6 j# {4 ?6 s. ~! R, X
直接表征法 + c* K/ q- \( C* p6 k! @* E
直接表征法中,省去了特征或柵格表示這一中間環(huán)節(jié),,直接用傳感器讀取的數(shù)據(jù)來構(gòu)造機(jī)器人的位姿空間,。
; Q* [* D$ C' G$ u
1 r4 K1 k$ J! q, k# J7 V1 n
上圖就是直接記錄了屋子內(nèi)天花板畫面的圖像地圖。這種方法就像衛(wèi)星地圖一樣,,直接將傳感器原始數(shù)據(jù)通過簡單處理拼接形成地圖,,相對(duì)來說更加直觀。
7 f" M- B2 Z( u* p+ n. }拓?fù)涞貓D 9 r+ J) E$ S8 b- O! C
拓?fù)涞貓D,,是一種相對(duì)更加抽象的地圖形式,,它把室內(nèi)環(huán)境表示為帶結(jié)點(diǎn)和相關(guān)連接線的拓?fù)浣Y(jié)構(gòu)圖,其中結(jié)點(diǎn)表示環(huán)境中的重要位置點(diǎn)(拐角,、門,、電梯、樓梯等),,邊表示結(jié)點(diǎn)間的連接關(guān)系,,如走廊等。這種方法只記錄所在環(huán)境拓?fù)滏溄雨P(guān)系,,這類地圖一般是由前幾類地圖通過相關(guān)算法提取得到,。
/ G7 S& F$ B7 K+ z# A9 r3 V& `
比如掃地機(jī)器人要進(jìn)行房間清掃的時(shí)候,就會(huì)建立這樣的拓?fù)涞貓D:
# u; b) x6 d6 V小結(jié)
# ~, h) I( R |, l
在機(jī)器人技術(shù)中,,SLAM 的地圖構(gòu)建通常指的是建立與環(huán)境幾何一致的地圖,。 7 U4 r* ]' x5 X0 u
一般算法中建立的拓?fù)涞貓D只反映了環(huán)境中的各點(diǎn)連接關(guān)系,并不能構(gòu)建幾何一致的地圖,,因此,,這些拓?fù)渌惴ú荒鼙挥糜?SLAM。 $ m9 L7 z* j$ i2 n1 b* ?# x% \
直接表征法類似衛(wèi)星地圖,,它是直接使用傳感器(一般是圖像傳感器)構(gòu)建得到,。這種方法的信息冗余度最大,對(duì)于數(shù)據(jù)存儲(chǔ)是很大的挑戰(zhàn),,同時(shí),,機(jī)器人要從中提取出有用的數(shù)據(jù)也要耗費(fèi)一番周折,因此在實(shí)際應(yīng)用中很少使用,。 . ]; n$ R a% B. w
特征點(diǎn)地圖又是另一個(gè)極端,,雖然數(shù)據(jù)量少,但是它往往不能反應(yīng)所在環(huán)境的一些必須的信息,,比如環(huán)境中障礙物的位置,。vSLAM 技術(shù)中,,多采用這種地圖來解決機(jī)器人定位問題。想讓機(jī)器人進(jìn)行自主避障和路徑規(guī)劃,,還需要額外配置距離傳感器,,如激光雷達(dá)、超聲波來完成,。
/ L8 m7 `4 H5 _- J" t L
柵格地圖,,或者 Occupancy Map(占據(jù)地圖)恰好介于其中,一方面它能表示空間環(huán)境中的很多特征,,機(jī)器人可以用它來進(jìn)行路徑規(guī)劃,,另一方面,它又不直接記錄傳感器的原始數(shù)據(jù),,相對(duì)實(shí)現(xiàn)了空間和時(shí)間消耗的最優(yōu),。因此,柵格地圖是目前機(jī)器人所廣泛應(yīng)用的地圖存儲(chǔ)方式,。
2 j+ [7 X: y: X `% [
思嵐科技的 SLAMWARE 系統(tǒng)內(nèi)部也采用這種地圖方式,。
' I! j. F4 @) R/ C, E6 d
1 ~1 U- n. Q& |0 u# X4 E: E5 R
當(dāng)你打開手機(jī)中的導(dǎo)航軟件,在選擇前往目的地的最佳路線之前,,首先要做的動(dòng)作是什么呢,?沒錯(cuò),就是定位,。我們要先知道自己在地圖中的位置,,才可以進(jìn)行后續(xù)的路徑規(guī)劃。 - ~/ O9 P: [0 m' h4 S5 f6 r
在機(jī)器人實(shí)時(shí)定位問題中,,由于通過機(jī)器人運(yùn)動(dòng)估計(jì)得到的機(jī)器人位置信息通常具有較大的誤差,,我們還需要使用測距單元得到的周圍環(huán)境信息更正機(jī)器人的位置。
. j! a2 h# U* g& Y5 ^+ D4 x
目前,,常見的測距單元包括激光測距,、超聲波測距以及圖像測距三種。其中,,憑借激光良好的指向性和高度聚焦性,激光雷達(dá)已經(jīng)成為移動(dòng)機(jī)器人的核心傳感器,,同時(shí)它也是目前最可靠,、最穩(wěn)定的定位技術(shù)。 , F1 l8 x" u9 d5 u1 {5 h9 ^3 d
自 1988 年被提出以來,,SLAM 的理論研究發(fā)展十分迅速,。在實(shí)際應(yīng)用時(shí),除配備激光雷達(dá)外,,還需要機(jī)器人具有 IMU(慣性測量單元),、里程計(jì)來為激光雷達(dá)提供輔助數(shù)據(jù),,這一過程的運(yùn)算消耗是巨大的,傳統(tǒng)上需要 PC 級(jí)別的處理器,,這也成為限制 SLAM 廣泛應(yīng)用的瓶頸之一,。 . c- F/ G: y, j) ^
那么,實(shí)現(xiàn) SLAM 的過程中,,都會(huì)遇到哪些坑呢,? $ S2 Q' }9 Q% I, t
SLAM 實(shí)現(xiàn)過程中的難點(diǎn)有哪些? * G4 ?8 x7 \' v* y6 I# t, D6 R
SLAM 主要解決機(jī)器人的實(shí)時(shí)定位與自動(dòng)建圖問題,,那么,,在實(shí)際應(yīng)用時(shí),SLAM 究竟是如何實(shí)現(xiàn)的呢,?在實(shí)現(xiàn)過程中有哪些難點(diǎn),?
! Z- B! z5 P/ j4 U/ T8 e G4 C
這是一個(gè)完整的 SLAM 和導(dǎo)航系統(tǒng)的主要架構(gòu)圖:
$ N; g M$ ^ D3 z( U
# Z. @3 k! M. D
其中,SLAM 核心過程包括 3 個(gè)步驟,,第一步稱為預(yù)處理,。我們知道,激光雷達(dá)和其他雷達(dá)設(shè)備一樣,,某一個(gè)時(shí)刻只能獲取它所在位置的環(huán)境信息,。 $ J2 t5 L; c7 g9 i! Q
這就是我們所說的點(diǎn)云,它只能反映機(jī)器人所在環(huán)境中的一個(gè)部分,。第一步預(yù)處理就是對(duì)激光雷達(dá)原始數(shù)據(jù)進(jìn)行優(yōu)化,,剔除一些有問題的數(shù)據(jù),或者進(jìn)行濾波,。 3 D W' V5 b, Z- r8 z
# u) s$ a8 {) d8 [* w+ X+ P
第二步是匹配,,也就是說把當(dāng)前這一個(gè)局部環(huán)境的點(diǎn)云數(shù)據(jù)在已經(jīng)建立地圖上尋找到對(duì)應(yīng)的位置,這個(gè)步驟非常關(guān)鍵,。 # G: }7 t' v/ x8 _$ H
這個(gè)是 ICP 的點(diǎn)云匹配算法,,用于實(shí)現(xiàn)匹配。說這個(gè)過程關(guān)鍵,,就是因?yàn)樗暮脡�,,直接影響�?SLAM 構(gòu)建地圖的精度。這個(gè)過程和我們玩拼圖游戲有點(diǎn)類似,,就是在已經(jīng)拼好的畫面中找到相似之處,,確定新的一個(gè)拼圖該放在哪里。 2 \9 v0 h* ], i
在 SLAM 過程中,,需要將激光雷達(dá)當(dāng)前采集的點(diǎn)云(紅色部分)匹配拼接到原有地圖中,。
9 k9 D! Q& E- L- \6 b/ R
# B2 {0 O# {8 [ t9 U; E
/ o: r2 b+ k6 x" J如果不進(jìn)行匹配過程,所構(gòu)建的地圖可能就亂成一團(tuán),,變成這樣,。
6 l$ A y8 l& @; ^' `; g n* _& Z: s
$ ~' C- P- B: K1 q0 f在這個(gè)部分完畢以后,,就進(jìn)行第三步,地圖融合,,也就是將這一輪來自激光雷達(dá)的新數(shù)據(jù)拼接到原始地圖當(dāng)中,,最終完成地圖的更新。
7 j: ^1 _' o. A7 F0 F4 r" h) A1 E
就像這個(gè)圖一樣,,這個(gè)過程是永遠(yuǎn)伴隨 SLAM 過程的,。 ; `4 `0 E9 k3 F; V& U
5 W9 l% V& i/ l$ a
數(shù)據(jù)融合和簡單的貼圖是有很大的差異的。因?yàn)閷?shí)際上傳感器描繪的世界存在一定的誤差,,或者正巧在這個(gè)時(shí)間環(huán)境有了變化,,例如機(jī)器人旁邊闖入了一只小貓。
5 A4 e3 v1 P. o8 n5 Y! H
因此,,實(shí)際要進(jìn)行的過程會(huì)更加復(fù)雜,,需要用很多概率算法,并采用濾波的方式進(jìn)行融合,。將上述這個(gè)過程逐次執(zhí)行,,就最終產(chǎn)生了我們看到的柵格地圖。 2 `/ |9 V$ u2 h& m7 P2 u+ q
( [* d" x& ?, ^6 V- Q( _& k+ s
這個(gè)過程聽起來其實(shí)并不復(fù)雜,,但是要處理好有很大難度,。這里舉幾個(gè)例子,比如叫做 Loop Closure(回環(huán))問題,。如果匹配算法不足夠優(yōu)秀,,或者環(huán)境中存在很不巧的干擾,當(dāng)機(jī)器人繞著環(huán)境一圈后,,就會(huì)發(fā)現(xiàn)原本是應(yīng)該閉合的一個(gè)環(huán)形走廊斷開了,。
4 ~0 f7 l+ e% r0 Z# n
比如正常地圖應(yīng)該這樣: 8 ^8 v6 t3 {& K: K
2 `7 {8 E+ T! @/ ~
如果處理不好,實(shí)際地圖就成這樣: : a3 ]/ U' n/ g0 a3 a
8 ^ @) Z' ]+ D. k對(duì)于環(huán)境比較大的場景,,回環(huán)問題是不得不面對(duì)的,,但現(xiàn)實(shí)總是不完美的,即使是激光雷達(dá)這種高精度傳感器,,也難免存在誤差,。而回環(huán)問題的難點(diǎn)恰恰在于在一開始出現(xiàn)少許誤差的時(shí)候,并不會(huì)被發(fā)覺,,直到機(jī)器人繞著環(huán)路一圈,,隨著誤差的累加,發(fā)現(xiàn)環(huán)路已經(jīng)無法閉合時(shí),,此時(shí)已經(jīng)釀成大錯(cuò),一般很難回天,。
) H ] B: g6 K# R; N+ J' S; k% A
當(dāng)然這個(gè)問題并不是無解,,一個(gè)好的商用化 SLAM 系統(tǒng),,回環(huán)問題是否能很好的解決,就成為評(píng)判這個(gè)系統(tǒng)實(shí)力的指標(biāo)了,。
, Z& M8 s2 y+ A& u# d1 u- y
這是前兩天在我們辦公室進(jìn)行的測試,,左邊的視頻是基于開源的 ROS 機(jī)器人操作系統(tǒng)進(jìn)行的地圖構(gòu)建,右邊的是基于 SLAMWARE 構(gòu)建的地圖,。
+ G- k% K" R. b X% ?- i2 R
: G# f# b6 s2 m3 d) X; y1 R" q! ? 9 _' H! S+ m$ V9 @4 W1 e
3 c- p. x! V2 V. A3 \
當(dāng)機(jī)器人已經(jīng)繞場一周后,,ROS 構(gòu)建的地圖出現(xiàn)了中斷,而 SLAMWARE 構(gòu)建的地圖是一個(gè)完美的閉環(huán),,它與我們辦公室的設(shè)計(jì)圖完美重合,。
% E! f. T6 e4 I3 o v. t5 Q
' [3 Y9 I4 t% P) q' ^& A1 \& o
除了算法層面的回環(huán)問題,SLAM 實(shí)際應(yīng)用中還有很多這種坑,,比如走廊問題與外界干擾問題,。
/ p3 y) @5 J! x W) D! l
以外界干擾問題來說,通常,,激光雷達(dá)作為機(jī)器人的眼睛,,一般是安裝在底盤上的,它能看到的視野很有限,。當(dāng)受到外界干擾(人類或者寵物等等)后,,機(jī)器人很容易丟失定位精度,無法正常完成后續(xù)的建圖工作,。 / R' Y4 s' x; M9 {& A
目前,,SLAM 的開源實(shí)現(xiàn)代表多為學(xué)術(shù)界,實(shí)際應(yīng)用有很多 Corner Case 要處理,,需要傳感器,、系統(tǒng)參數(shù)、其他輔助設(shè)備的聯(lián)合調(diào)優(yōu),。 ( q- m/ V ]1 B# M* k6 I& w8 K
一般來說,,上述的 SLAM 過程對(duì)于運(yùn)算消耗是巨大的,雖然并沒有達(dá)到像訓(xùn)練神經(jīng)網(wǎng)絡(luò)動(dòng)用服務(wù)器集群那種地步,,但傳統(tǒng)上需要 PC 級(jí)別的處理器,。 . A" o) m9 v) [9 T
除配備激光雷達(dá)外,還需要機(jī)器人具有 IMU(慣性測量單元),、里程計(jì)來為激光雷達(dá)提供輔助數(shù)據(jù),,否則 SLAM 系統(tǒng)也難以得到運(yùn)行�,?偟膩碚f,,SLAM 算法本身是一個(gè)對(duì)于外部系統(tǒng)有著多種依賴的算法,這是一個(gè)切實(shí)的工程問題,。 $ ^( u7 @! w% U3 \# b" q, C
很多機(jī)器人,,比如掃地機(jī)是不可能裝一個(gè) PC 進(jìn)去的,,為了讓 SLAM 能在這類設(shè)備里運(yùn)行,除了解決激光雷達(dá)成本外,,還要對(duì) SLAM 算法做出很好的優(yōu)化,。 0 I+ n' I8 ~ {. g
那么,機(jī)器人利用 SLAM 技術(shù)得到了有效的空間信息后,,它是怎樣實(shí)現(xiàn)路徑規(guī)劃的,?SLAM 和路徑規(guī)劃之間關(guān)系是怎樣的? + c2 v& Z$ j# {, c' }, K3 F& \- i
機(jī)器人如何實(shí)現(xiàn)自主移動(dòng)和路徑規(guī)劃,?
, Q. Q$ p+ O& F; A+ N" |# W6 ?: U
上面我們已經(jīng)知道了 SLAM 與路徑規(guī)劃的關(guān)系,。 5 A5 @6 O) [% w
實(shí)際上,SLAM 算法本身只是完成了機(jī)器人的定位和地圖構(gòu)建兩件事情,,與我們說的導(dǎo)航定位并不是完全等價(jià)的,。這里的導(dǎo)航,其實(shí)是 SLAM 算法做不了的,。它在業(yè)內(nèi)叫做運(yùn)動(dòng)規(guī)劃 (Motion Planning),。 ) ^8 T* b4 r ]! G7 O n
運(yùn)動(dòng)規(guī)劃是一個(gè)很大的概念,從機(jī)械臂的運(yùn)動(dòng),、到飛行器的飛行,,再到這里我們說的掃地機(jī)的清掃路徑規(guī)劃,都是運(yùn)動(dòng)規(guī)劃的范疇,。 : P7 p9 b9 K2 S2 S' r
我們先談?wù)勧槍?duì)掃地機(jī)這類輪式機(jī)器人的運(yùn)動(dòng)規(guī)劃,。這里所需的基礎(chǔ)能力就是路徑規(guī)劃,也就是一般在完成 SLAM 后,,要進(jìn)行一個(gè)叫做目標(biāo)點(diǎn)導(dǎo)航的能力,。通俗的說,就是規(guī)劃一條從 A 點(diǎn)到 B 點(diǎn)的路徑出來,,然后讓機(jī)器人移動(dòng)過去,。 ( q# G& p1 J0 d2 o( d4 w
要實(shí)現(xiàn)這個(gè)過程,運(yùn)動(dòng)規(guī)劃要實(shí)現(xiàn)至少兩個(gè)層次的模塊,,一個(gè)叫做全局規(guī)劃,,這個(gè)和我們車載導(dǎo)航儀有一點(diǎn)像,它需要在地圖上預(yù)先規(guī)劃一條線路,,也要有當(dāng)前機(jī)器人的位置,。這是由我們的 SLAM 系統(tǒng)提供出來的。行業(yè)內(nèi)一般會(huì)用叫做 A * 的算法來實(shí)現(xiàn)這個(gè)過程,,它是一種啟發(fā)式的搜索算法,,非常優(yōu)秀。它最多的應(yīng)用,是在游戲中,,比如像星際爭霸,、魔獸爭霸之類的即時(shí)戰(zhàn)略游戲,都是使用這個(gè)算法來計(jì)算單位的運(yùn)動(dòng)軌跡的,。 ! ?7 J3 i) R |7 {6 f
當(dāng)然,僅僅規(guī)劃了路徑還是不夠的,,現(xiàn)實(shí)中會(huì)有很多突發(fā)情況,,比如正巧有個(gè)小孩子擋道了,就需要調(diào)整原先的路徑,。當(dāng)然,,有時(shí)候這種調(diào)整并不需要重新計(jì)算一遍全局路徑,機(jī)器人可能稍微繞一個(gè)彎就可以,。此時(shí),,我們就需要另一個(gè)層次的規(guī)劃模塊,叫做局部規(guī)劃,。它可能并不知道機(jī)器人最終要去哪,,但是對(duì)于機(jī)器人怎么繞開眼前的障礙物特別在行。 6 h4 R* ^/ T9 d" g2 t
這兩個(gè)層次的規(guī)劃模塊協(xié)同工作,,機(jī)器人就可以很好的實(shí)現(xiàn)從 A 點(diǎn)到 B 點(diǎn)的行動(dòng)了,,不過實(shí)際工作環(huán)境下,上述配置還不夠,。比如 A*算法規(guī)劃的路徑是根據(jù)已知地圖,,預(yù)先規(guī)劃好的,一旦機(jī)器人前往目的地的過程中遇到了新的障礙物,,就只好完全停下來,,等待障礙物離開或者重新規(guī)劃路徑了。如果掃地機(jī)器人買回家,,必須先把屋子都走一遍以后才肯掃地,,那用戶體驗(yàn)就會(huì)很差。
( n/ ?2 J: d2 g/ g) D* [2 H4 _1 G
為此,,也會(huì)有針對(duì)這類算法的改進(jìn),,比如 SLAMWARE 內(nèi)我們采用改良的 D * 算法進(jìn)行路徑規(guī)劃,這也是美國火星探測器采用的核心尋路算法,。這是一種動(dòng)態(tài)啟發(fā)式路徑搜索算法,,它讓機(jī)器人在陌生環(huán)境中行動(dòng)自如,在瞬息萬變的環(huán)境中游刃有余,。
/ O- `; J/ H8 X5 o B, k/ `% |/ Y
D * 算法的最大優(yōu)點(diǎn)是不需要預(yù)先探明地圖,,機(jī)器人可以和人一樣,即使在未知環(huán)境中,也可以展開行動(dòng),,隨著機(jī)器人不斷探索,,路徑也會(huì)時(shí)刻調(diào)整。 + l( e: ?/ S+ A$ ]
0 A" v* \" {; M: c$ b3 h
以上是目前大部分移動(dòng)機(jī)器人都需要的路徑規(guī)劃算法,,而掃地機(jī)器人作為最早出現(xiàn)在消費(fèi)市場的服務(wù)機(jī)器人之一,,它需要的路徑規(guī)劃算法更為復(fù)雜。 , X+ k# p+ |! h' P4 W* W) e
一般來說,,掃地機(jī)需要這么幾個(gè)規(guī)劃能力:貼邊打掃,、折返的工字形清掃以及沒電時(shí)候自主充電。單單依靠前面介紹的 D * 這類算法,,無法滿足這些基礎(chǔ)需要,。
5 ~) n, ?$ i& V
掃地機(jī)器人還需要有額外的規(guī)劃算法,比如針對(duì)折返的工字形清掃,,有很多問題要處理,。掃地機(jī)如何最有效進(jìn)行清掃而不重復(fù)清掃?如何讓掃地機(jī)和人一樣,,理解房間,、門、走廊這種概念,? 針對(duì)這些問題,,學(xué)術(shù)界長久以來有一個(gè)專門的研究課題,叫做空間覆蓋(space coverage),,同時(shí)也提出了非常多的算法和理論,。其中,比較有名的是 Morse Decompositions,,掃地機(jī)通過它實(shí)現(xiàn)對(duì)空間進(jìn)行劃分,,隨后進(jìn)行清掃。 ( ?7 q; ?- D/ J! S& ?, W
20 世紀(jì) 70 年代,,卡內(nèi)基梅隴大學(xué)(CMU)完全依靠超聲波做到了現(xiàn)在我們掃地機(jī)的行為,,當(dāng)然造價(jià)也十分昂貴。
* Y; U ]3 @) V' {1 ^
前面介紹的從 A 點(diǎn)到 B 點(diǎn)移動(dòng)路徑規(guī)劃也是實(shí)現(xiàn)這類更高級(jí)路徑規(guī)劃的基礎(chǔ),。實(shí)際上,,要從 SLAM 實(shí)現(xiàn)到掃地機(jī)器人所需要的這些功能,還是有非常多的工作要做的,。 1 T8 g" { d0 ]+ D0 _$ U/ b% R
2 Z4 g* @. y/ o/ \. D8 J
; t. V4 a8 w4 x0 S7 e) | |