孟磊,吳芝亮,王軼強

(天津大學 機械工程學院,天津 300354)

隨著機器人技術的快速發(fā)展,移動機器人現(xiàn)已廣泛應用在民用和軍事領域,比如航天、醫(yī)療、制造業(yè)、服務業(yè)等。機器人不僅能為人類帶來生活上的便利,更重要的是能夠代替人類工作于惡劣和危險的環(huán)境[1-2]。由多個移動機器人組成的多機器人系統(tǒng)與單個機器人相比具有魯棒性強、效率高的優(yōu)點[3]。通過多個機器人數據共享協(xié)同合作,可以極大地提高完成任務的效率,甚至能夠完成單機器人無法完成的任務。

多機器人系統(tǒng)探測未知環(huán)境是移動機器人技術的基礎問題和研究熱點[4]。利用多機器人系統(tǒng)進行環(huán)境探測,目標在于有效控制機器人的協(xié)同行為,最大化對外部世界的認識?？蓱糜诤Ｑ蟓h(huán)境和太空探索,對提高人類對未知領域的認知程度具有重要意義;也可應用于災難搜索救援、物理場重構以及動態(tài)環(huán)境監(jiān)測,為保障公共安全提供支撐作用。在這些場合中,通常對所探測環(huán)境的先驗知識較為欠缺,因此采用局部路徑規(guī)劃更有優(yōu)勢[5],要求多機器人系統(tǒng)能夠實現(xiàn)自主在線協(xié)同路徑規(guī)劃。通過信息感知與數據共享,每個機器人以提高整體探測質量與探測效率為目標,自主在線規(guī)劃各自的最優(yōu)路徑。

多機器人環(huán)境探測就是機器人使用路徑規(guī)劃的方法規(guī)劃出一條行進的最優(yōu)路徑,完成對未知環(huán)境探測的任務。目前已經有很多用于路徑規(guī)劃的智能算法,如迭代優(yōu)化算法[6]、A*算法[7-8]、遺傳算法[9-10],人工勢場法[11-12],水平集算法[13],快速擴展隨機樹(RRT)算法[14-15],蟻群算法[16],粒子群優(yōu)化算法[17]。這些算法應用在多機器人的路徑規(guī)劃中都有著各自的優(yōu)勢。段勇等[9]針對多機器人環(huán)境探測中的路徑規(guī)劃問題,提出了一種免疫遺傳算法將每個待探索的任務點根據距離合理地分配給各個機器人,提高了多機器人路徑規(guī)劃的效率,有效地實現(xiàn)了多機器人多任務點環(huán)境探索問題。Nazarahari等[10]開發(fā)了一種改進遺傳算法(EGA),將其用于連續(xù)環(huán)境中多機器人路徑規(guī)劃中,改善了連續(xù)空間中的初始路徑并找到了最佳路徑。Zhang等[14]提出了一種擴展的快速搜索隨機數的方法,為多機器人探索和構建地圖環(huán)境提出了一種基于最優(yōu)化的地圖探索策略,采用了基于市場的任務分配策略,優(yōu)化了前沿點,定義了新的任務分配策略,提高了多機器主動探索和構建環(huán)境地圖的效率。蔡標等[16]運用蟻群算法解決了多機器人環(huán)境探測中的目標分配和環(huán)境區(qū)域覆蓋的問題,將蟻群算法很好的應用到了環(huán)境探索中的任務分配中。Das等[17]在改進的粒子群優(yōu)化算法(IPSO)中運用了進化算子(EOPs)來解決多機器人路徑規(guī)劃中每個機器人計算最佳的無碰撞軌跡路徑的問題,通過和改進的粒子群優(yōu)化算法、差分進化算法比較,顯示了更優(yōu)的魯棒性和實用性,在效率和行駛的能量消耗方面有了很大的提升。

以上的方法用不同的算法對路徑規(guī)劃問題進行了表述和求解,取得了較為不錯的結果,但是上述算法都沒有考慮到傳感器的局限性。在環(huán)境探測時,傳感器不可避免有測量誤差,因而測量信息和環(huán)境實際之間存在偏差,這個偏差對路徑規(guī)劃效果有很重要的影響。另外,在環(huán)境探測時,機器人對未知環(huán)境沒有先驗知識,需要其對得到的信息進行一個實時自主在線的路徑規(guī)劃。為了解決上述問題,本文引入POMDP模型,該模型是一種動態(tài)規(guī)劃模型,將傳感器感知的不確定性考慮到路徑規(guī)劃策略中。而且本文將機器人對環(huán)境的信念用非參數的形式表示,這樣可以表示更廣泛的狀態(tài)空間。采用貝葉斯濾波來更新機器人對環(huán)境的信念,并將信息熵作為報酬函數。同時采用POMDP的貪婪狀況,可以最大化機器人觀察到的信息量。POMDP可以在信息部分已知的情況下來得到最優(yōu)的決策,完成實時的動態(tài)規(guī)劃,很大程度提高了多機器人環(huán)境探測的效率。

1 基于POMDP模型的路徑規(guī)劃方法

本文研究了一種基于POMDP決策模型的路徑規(guī)劃方法用于多機器人環(huán)境探測。建立POMDP模型,提出一種循環(huán)的方法:1) 機器人通過傳感器獲得觀察數據并與其他機器人信息交流得到多機器人系統(tǒng)的全部數據。2) 收到數據后,采用貝葉斯濾波來更新機器人對環(huán)境狀態(tài)的信念。3) 將信息熵作為報酬,運用POMDP的貪婪狀況做出行為決策,讓機器人往信息熵最大的方向移動,可以最大化下一次觀察到的信息量。通過此3步循環(huán)的方法機器人逐漸完成環(huán)境探測的任務。

1.1 POMDP概述

部分可觀測馬爾可夫決策過程是一種動態(tài)規(guī)劃模型,根據所構建的優(yōu)化目標來獲得最優(yōu)決策。馬爾可夫決策過程(MDP)假設未來的狀態(tài)只取決于當前的狀態(tài),而與過去的狀態(tài)無關、環(huán)境狀態(tài)能隨時完全感知。換句話說,感知模型是確定性的和雙射的。而在環(huán)境探測中,機器人是不能掌握全部信息的,因此我們采用POMDP來解決環(huán)境探測時的決策問題。本文中POMDP模型包括:

1) 位置集合S,表示機器人在環(huán)境中位置的集合。

2) 測量C,表示機器人對環(huán)境狀態(tài)的所有測量值的集合。

3) 動作集合U,機器人可以選擇的行動集合,在本文中,機器人步長一定,因此動作取決于機器人行進的方向。

4) 狀態(tài)轉移概率T(s′|s,u),表示機器人在位置s時執(zhí)行行動u后狀態(tài)變?yōu)閟′的概率。在本文中不考慮機器人的運動誤差,因此機器人的狀態(tài)轉移是確定的。

5) 測量概率P(c|z),其中z為環(huán)境狀態(tài)真值。測量概率表示機器人在某個位置時,環(huán)境狀態(tài)為z時機器人的測量為c的概率,體現(xiàn)出傳感器的不確定性。一般傳感器的測量概率是一個以真值為均值的高斯分布,而這個高斯分布的標準差σ可以通過標定試驗確定。

6) 報酬函數R(s,u),表示在位置為s時,采取行動u后所得到的立即報酬。

POMDP模型可以用M=表示。

1.2 POMDP數學模型

1.2.1 信念分布表示

信念分布是機器人對環(huán)境狀態(tài)認知的一種表達方式,體現(xiàn)為環(huán)境狀態(tài)值的概率分布。對環(huán)境狀態(tài)的認識,通常都是建立在一個環(huán)境模型基礎上的。高斯分布是一種較常用的環(huán)境模型。可以精確地表示和簡化系統(tǒng),但是,對于較復雜的環(huán)境,高斯分布往往不能充分地表示環(huán)境的特性,從而引入一定的誤差。本文采用非參數的、基于樣本的方法來表示系統(tǒng)中信念的概率分布。本文使用帶權重的樣本集來近似機器人的信念,對于每一處區(qū)域的認識都使用基于樣本的表示方法來表示。

機器人已經探測過的點我們稱為路徑點。對于每個路徑點,采用nz個樣本值及其相應的權重來表示機器人對此點的信念,即

Z={(zj,wj):j∈{1,…,nz}}

(1)

式中:nz為樣本值的個數;zj為樣本值;wj為樣本值所對應的權重,wj∈(0,1)。樣本和它所對應的權值代表了機器人對環(huán)境狀態(tài)信念的非參數的表示。這種非參數的樣本表示方法可以用來表示更廣泛的分布空間,它的另外一個優(yōu)點就是其建模隨機變量的非線性變換的能力。

1.2.2 信念分布的轉移

本文使貝葉斯濾波來實現(xiàn)對環(huán)境信念的更新。對環(huán)境的信念更新是通過兩步來完成的。在第一步中,根據已有測量數據獲得對目標待測點的預測,建立一個加權環(huán)境樣本集:預測樣本集。根據預測樣本集,驅動機器人運動,到達目標探測點并進行測量。在第二步中,融合上一步對新位置的預測和機器人在新位置的測量來更新加權環(huán)境樣本集,從而建立機器人對環(huán)境的新信念,這就是貝葉斯濾波的預測和更新兩大步驟。

(2)

式中:η為歸一化因子;P(z)為先驗概率,是預測樣本集中的概率;P(c|z)為測量概率。此步更新了樣本的概率,是貝葉斯濾波的更新過程。將機器人路徑點及其相應的加權樣本集記為

path={(xk,yk,Zk):k∈{1,.,npath}}

(3)

式中:Zk為加權環(huán)境樣本集;npath為機器人路徑點個數。貝葉斯濾波的偽代碼如下:

Pseudocode: 貝葉斯濾波算法

2) 更新:根據貝葉斯公式更新樣本的概率,得到加權環(huán)境樣本集Zm2={(zj,wj):j∈{1,…,nz}}

輸出:目標探測點的加權環(huán)境樣本集Zm2。

1.2.3 報酬函數和值函數

首先建立報酬函數R(s,u),表示在位置為s時,采取行動u后所得到的立即報酬。報酬函數可以驅動多機器人系統(tǒng)完成探測任務。引入值函數VT(x)來表示當前動作對未來的影響，即

(4)

式中r為折扣因子,是一個問題特定參數,且r∈[0,1]。通過值函數,可以得到最優(yōu)策略為

(5)

本文只考慮未來一步對當前的影響,也就是T=1。因此最優(yōu)策略為

(6)

H(z)=E[log2p(z)]

(7)

式中z為預測樣本集中的樣本。

1.2.4 目標探測點的選擇

圖1 機器人下一步探測點選擇

將脫離環(huán)境邊界的待選點刪掉后,對于每一個機器人,有nsample個可選待測點的集合，即

(8)

(9)

2 多機器人環(huán)境探測任務

多機器人環(huán)境探測,目的是控制機器人最大化對外界的認識,本節(jié)將我們的基于POMDP模型的路徑規(guī)劃方法應用于環(huán)境探測中。

2.1 機器人的協(xié)同體系結構

協(xié)同體系結構直接決定了多機器人的行為能力。因此,多機器人的協(xié)同系統(tǒng)的正常運行需要建立合適的協(xié)同體系結構。系統(tǒng)中的機器人通過信息交流來保證他們的協(xié)調同步以完成給定的任務。

對多機器人環(huán)境探測任務,本文設置了3個機器人,對未知環(huán)境進行探測。設定機器人具有理想網絡的分布式多機器人系統(tǒng),如圖2所示。

圖2 分布式控制體系結構多機器人系統(tǒng)

假設機器人具有理想集中網絡,機器人可以通過與其他機器人的信息交流獲取多機器人系統(tǒng)的所有信息。分布式體系結構中的機器人根據信息獨立地采取行動,應對單個機器人失效的魯棒性較高,而且更加靈活。

2.2 環(huán)境探測

在環(huán)境探測時,機器人對環(huán)境狀態(tài)信念的表示用一組樣本和它所對應的權值來表示,同時又能體現(xiàn)出信息熵,即可以表示對每一處環(huán)境的信息。具體探測步驟如下:

1) 首先,建立POMDP模型。令nz=10,n=4,因此預測的加權環(huán)境樣本集包含10 000組數據。

2) 開始探測時,在環(huán)境中在比較靠近的位置放置3個機器人,讓它們隨機先探測幾個位置并通過信息交流得到一個初始的測量數據。

3) 有了基本的初始數據以后,機器人可以遵從POMDP行為決策,根據可選待測點的信息量也就是信息熵來決定自己的探測路徑,行進至信息量最大的一點進行探測,在傳感器的測量數據中得到數據并與其他機器人進行交流得到系統(tǒng)的全部數據。將得到的數據運用貝葉斯濾波來更新對環(huán)境的信念,然后再根據當前的信息來預測可選待測點的信息,繼續(xù)選擇信息熵最大的一點作為目標點,最大化下一步觀察的信息量,這樣周而復始直至達到我們的設定的探測目標。本文分別采用均方根誤差和探測時間作為多機器人環(huán)境探測精度和效率的定量評價指標。

多機器人根據傳感器的數據實時的進行路徑規(guī)劃,因此這也是一種在線的路徑規(guī)劃,完成對環(huán)境的探測任務。圖3為基于POMDP模型算法的多機器人環(huán)境探測的流程圖。

圖3 多機器人環(huán)境探測流程圖

3 仿真結果和分析

為了驗證本文基于POMDP模型的路徑規(guī)劃方法在多機器人探測環(huán)境時的有效性,在MATLAB環(huán)境下對本文中的方法和傳統(tǒng)的全覆蓋路徑規(guī)劃方法[18-19]進行仿真試驗,并將結果進行對比分析。

3.1 擬合結果分析

為了驗證本文方法的普適性,選取了兩種大小不同的環(huán)境,選取3個裝有傳感器的機器人利用上述方法協(xié)同合作對虛擬環(huán)境中的一氧化碳(CO)的濃度進行探測。在本例中,機器人得到的環(huán)境CO濃度的概率分布就是機器人的信念。機器人信念Z中的zj表示CO濃度的值,wj是相應的權重。

首先令機器人探測環(huán)境大小為90 m×120 m的環(huán)境,CO濃度范圍為20 ppm到30 ppm,待測的標量場如圖4所示。3個機器人探測201個位置,最終得到的機器人路徑如圖5。將最終的測量數據代入高斯過程回歸模型,采用樣本點對模型進行訓練,得到如圖6所示的測量場圖,圖7為誤差場,可以體現(xiàn)虛擬環(huán)境每個位置真實場與測量場的CO濃度差。

圖4 待探測90 m×120 m真實場

圖5 多機器人探測路徑(90 m×120 m)

圖6 90 m×120 m測量場

圖7 90 m×120 m誤差場

通過對比測量場圖和真實場,測量場很好的重建了真實場的CO濃度的信息,環(huán)境中CO濃度的峰值和谷值的位置很相近。在誤差場圖中可以看出最大的誤差只有0.15 ppm。計算整場的均方根誤差,最終的均方根誤差為0.020 5,有很高的重建質量,仿真效果很理想。

對大小為60 m×70 m的環(huán)境,同樣是放3個機器人來探測,環(huán)境地圖如圖8所示,令3個機器人探測93個位置點,CO濃度范圍在22～30 ppm。機器人的路徑圖如圖9所示。將真實場和測量場的CO濃度作差得到圖10的誤差場。

圖8 待探測60 m×70 m真實場

圖9 多機器人探測路徑(60 m×70 m)

圖10 60 m×70 m誤差場

60 m×70 m的CO濃度場只有一個波峰和一個波谷,場的面積較小,機器人可以用更少的步數來完成對環(huán)境的探測,3個機器人合作完成標量場的探測任務,路徑都是朝著可以獲得信息量最大的方向,最大的誤差只有0.15 ppm。計算均方根誤差時,以0.1 m×0.1 m為間隔進行采樣。最終的均方根誤差為0.023 7。

通過對兩個場的仿真試驗,可以看出基于POMDP的路徑規(guī)劃方法在探測環(huán)境時有較高的精準度,無論是局部的每一點的誤差還是全局的均方根誤差都達到很小的數值,得到很好的觀測區(qū)域測量場。

3.2 與全覆蓋路徑規(guī)劃方法的對比分析

上文驗證了本文提出的方法在探測環(huán)境時的準確度,本節(jié)將傳統(tǒng)的全覆蓋路徑規(guī)劃方法和該方法做一個對比,通過兩者之間的對比,更能說明基于POMDP的路徑規(guī)劃方法在準確度還有效率上的優(yōu)勢。對比大小為60 m×70 m的環(huán)境場,令3個機器人按照全覆蓋的路徑來對環(huán)境進行探測,與3.1節(jié)中機器人移動同樣的步數,對結果進行對比。

圖11就是傳統(tǒng)的全覆蓋路徑規(guī)劃方法的機器人路徑圖。機器人按照全覆蓋式的路徑進行地毯式的搜索,其誤差場如圖12所示。

圖11 多機器人全覆蓋式路徑

圖12 60 m×70 m全覆蓋路徑規(guī)劃誤差場

可以看出這種方法也是可以將CO濃度場的大體結構特征預測出來,但是跟基于POMDP的方法對比可以看出:局部上,運行同樣的步數,基于POMDP路徑規(guī)劃方法的最大誤差只有0.15 ppm,而全覆蓋路徑規(guī)劃方法的最大誤差是0.4 ppm。總體來看,基于POMDP的方法的全場均方根誤差只有0.023 7,而全覆蓋路徑規(guī)劃方法的均方根誤差有0.051 3。無論是在局部角度還是在全場角度,基于POMDP的路徑規(guī)劃方法用于預測都有更高的精度。

兩種算法的均方根誤差的對比如圖13所示。從該圖中可以看出,全覆蓋路徑規(guī)劃方法的路徑圖需要機器人遍歷全場,這對時間和資源產生了太大的浪費,效率會很低。在路徑點數量小于48個時,均方根誤差都比較大,所以取了48以后的均方根誤差來對比。對比結果可以看出,基于POMDP的路徑規(guī)劃方法的均方根誤差很快就能達到很小的數量級;在70個路徑點時就可以達到0.02左右,而全覆蓋路徑規(guī)劃方法的均方根誤差需要144個路徑點才能達到0.02,需要更長的探測時間。因此在效率上POMDP方法優(yōu)于全覆蓋方法。

圖13 60 m×70 m場均方根誤差曲線

4 結論

本文提出了一種基于POMDP的路徑規(guī)劃方法來控制多個裝有傳感器的機器人來探測環(huán)境,建立部分可觀馬爾可夫決策模型,完成環(huán)境探測的任務。用信息熵驅動可以最大化機器人探測的信息量,規(guī)劃出最優(yōu)路徑,采用非參數的表示可以表示更廣泛的分布空間并通過貝葉斯濾波來更新機器人對環(huán)境的信念。仿真結果表明對不同的場,測量場都非常的精確。與傳統(tǒng)的全覆蓋路徑規(guī)劃方法對比分析,在精度和效率上有了很大的優(yōu)化。然而本文在驅動這一步只考慮了單步的信息量,未來重點將考慮多步的信息來進行機器人驅動,來規(guī)劃最優(yōu)路徑。