鄧旭 趙連軍 郇靜
摘要:針對(duì)復(fù)雜迷宮環(huán)境的目標(biāo)體具體位置與路徑規(guī)劃問(wèn)題為對(duì)象,提出了一種基于隱馬爾可夫模型的粒子濾波算法。該方法通過(guò)隱馬爾可夫模型的概率計(jì)算、粒子濾波算法時(shí)間流逝、觀察、抽樣策略,推理出目標(biāo)體可能范圍,通過(guò)A·算法將目標(biāo)捕獲。仿真結(jié)果表明,與普通的概率計(jì)算目標(biāo)體位置,粒子濾波算法計(jì)算的目標(biāo)體位置,大大減少了總步數(shù),形成了最短路徑。
關(guān)鍵詞:路徑規(guī)劃:隱馬爾可夫模型:粒子濾波
0引言
人工智能在越來(lái)越多的領(lǐng)域得到了應(yīng)用。近幾年人工智能的發(fā)展異常迅猛。Hinton等的卷積神級(jí)網(wǎng)絡(luò)在計(jì)算機(jī)視覺(jué)領(lǐng)域的圖形分類做出了重要貢獻(xiàn),并且在2015優(yōu)化成深度學(xué)習(xí)。
Silver,D等在2016使用深度神經(jīng)網(wǎng)絡(luò)在有監(jiān)督算法下訓(xùn)練的AlphaGo戰(zhàn)勝韓國(guó)棋手李世石。AlphaGo Zero則實(shí)現(xiàn)了更進(jìn)一步的提升,在不使用人類知識(shí)的情況下學(xué)習(xí)到了一個(gè)超人水平的計(jì)算機(jī)圍棋程序。
人工智能在迷宮搜索方面有著廣泛的應(yīng)用。但是,自主移動(dòng)機(jī)器人如何在未知的、復(fù)雜的環(huán)境中自主規(guī)劃從起點(diǎn)到終點(diǎn)的路徑,并且躲避障礙,或者通過(guò)路徑規(guī)劃捕獲具體目標(biāo)始終是復(fù)雜的技術(shù)難題。因此,進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃算法的研究,具有一定的理論意義和工程應(yīng)用意義。迷宮機(jī)器人是移動(dòng)機(jī)器人的典型應(yīng)用,也是檢驗(yàn)路徑規(guī)劃算法較好的平臺(tái)
目前,在迷宮搜索方面,取得了很多有效的進(jìn)展。但是目前的Agent迷宮搜索都是靜態(tài)的單個(gè)目標(biāo)搜索。在多個(gè)動(dòng)態(tài)目標(biāo)搜索方面存在著明顯不足。
隱馬爾可夫模型是統(tǒng)計(jì)模型。用來(lái)描述含有隱含未知參數(shù)的馬爾可夫過(guò)程。其難點(diǎn)是從可觀察的參數(shù)中確定該過(guò)程的隱含參數(shù)。利用這些參數(shù)作進(jìn)一步的分析。其在語(yǔ)音技術(shù)和手寫(xiě)字符識(shí)別應(yīng)用中廣泛使用,但在迷宮搜索領(lǐng)域用得較少。
通過(guò)隱馬爾可夫模型的應(yīng)用,可以有效地確認(rèn)多個(gè)動(dòng)態(tài)目標(biāo)位置,通過(guò)A*算法尋找和捕獲目標(biāo)。
1 研究現(xiàn)狀
李慶中等提出的基于遺傳算法,簡(jiǎn)單、有效的移動(dòng)機(jī)器人實(shí)時(shí)動(dòng)態(tài)避障路徑規(guī)劃方法,利用遺傳算法實(shí)時(shí)、穩(wěn)定地進(jìn)行動(dòng)態(tài)路徑規(guī)劃。仿真實(shí)驗(yàn)表明:動(dòng)態(tài)路徑規(guī)劃方法可實(shí)時(shí)、穩(wěn)定地產(chǎn)生移動(dòng)機(jī)器人運(yùn)動(dòng)的最佳局部規(guī)劃路徑,且具有良好的動(dòng)態(tài)避障性能。
顧新艷等研究移動(dòng)機(jī)器人利用柵格法創(chuàng)建環(huán)境地圖時(shí),在其計(jì)算資源有限的情況下,比較利用迷宮八方向搜索思想,實(shí)現(xiàn)最短路徑規(guī)劃的Dijkstra算法,提出采用基于柵格劃歸地圖的A*算法,能更快實(shí)現(xiàn)移動(dòng)機(jī)器人的無(wú)碰最短路徑規(guī)劃。
溫如春等對(duì)傳統(tǒng)蟻群算法收斂性較慢的問(wèn)題進(jìn)行了改進(jìn)。通過(guò)計(jì)算機(jī)仿真和電腦鼠機(jī)器人實(shí)際行走實(shí)驗(yàn)表明,在場(chǎng)地復(fù)雜的情況下,該算法可以有效地規(guī)劃出全局最優(yōu)路徑。
李道新等研究移動(dòng)機(jī)器人的歷史與現(xiàn)狀基礎(chǔ)上,重點(diǎn)在移動(dòng)機(jī)器人避障與路徑選擇規(guī)劃中常用的算法中選取柵格法、勢(shì)場(chǎng)法、遺傳算法等方法進(jìn)行分析比較:并以自行設(shè)計(jì)的一款微型機(jī)器人為例,探討了基于紅外感知的未知環(huán)境特征提取方法和安全避障距離選取的原則,給出了一種深廣結(jié)合算法的移動(dòng)機(jī)器人避障策略:描述了深廣結(jié)合算法在機(jī)器人迷宮地圖中最優(yōu)路徑規(guī)劃實(shí)現(xiàn)中的應(yīng)用。
Shazhaev Ilman(伊勒曼)基于多NAO機(jī)器人搭建實(shí)驗(yàn)平臺(tái),研究了機(jī)器人的定位模型、路徑規(guī)劃和走迷宮尋徑問(wèn)題。根據(jù)所建立的圖像處理方法和定位模型得到了相應(yīng)的圖形信息,利用圖像處理技術(shù),完成了位置特征和環(huán)境特征的識(shí)別?;贜AO機(jī)器人坐標(biāo)系,獲取環(huán)境特征的定位信息,通過(guò)定位實(shí)驗(yàn),驗(yàn)證了定位模型和路徑規(guī)劃的可行性?;诮⒌牡湫兔詫m結(jié)構(gòu)圖,進(jìn)行了多機(jī)器人協(xié)同迷宮尋徑的研究。實(shí)驗(yàn)完成了多機(jī)器人之間的信息交換,并可實(shí)時(shí)分享周圍的環(huán)境信息。建立了相應(yīng)的算法,根據(jù)編制的程序,利用分享的信息,機(jī)器人可以決定如何在迷宮中進(jìn)行下一步行動(dòng)。由于決策信息的實(shí)時(shí)共享,多個(gè)機(jī)器人比單個(gè)機(jī)器人更高效快捷地走出迷宮。
2 實(shí)驗(yàn)方法
本實(shí)驗(yàn)通過(guò)隱馬爾可夫模型的粒子濾波算法和A*算法在復(fù)雜迷宮環(huán)境下找到動(dòng)態(tài)目標(biāo)。
2.1 馬爾科夫鏈
馬爾科夫鏈為狀態(tài)空間中。經(jīng)過(guò)從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)換的隨機(jī)過(guò)程。該過(guò)程要求具備“無(wú)記憶”的性質(zhì):下一狀態(tài)的概率分布只能由當(dāng)前狀態(tài)決定,在時(shí)間序列中與前面的事件均無(wú)關(guān)。這種特定類型的“無(wú)記憶性”稱作馬爾可夫性質(zhì)。在馬爾可夫鏈的每一步,系統(tǒng)根據(jù)概率分布,可以從一個(gè)狀態(tài)變到另一個(gè)狀態(tài),也可以保持當(dāng)前狀態(tài)。狀態(tài)的改變叫做轉(zhuǎn)移,與不同的狀態(tài)改變相關(guān)的概率叫做轉(zhuǎn)移概率,如隨機(jī)漫步就是馬爾可夫鏈的例子。隨機(jī)漫步中每一步的狀態(tài)是在圖形中的點(diǎn)??梢砸苿?dòng)到任何一個(gè)相鄰的點(diǎn)。在這里移動(dòng)到每一個(gè)點(diǎn)的概率都是相同的(無(wú)論之前漫步的路徑如何)。
實(shí)驗(yàn)為了追蹤所考慮的粒子隨時(shí)間的變化。需要了解馬爾科夫鏈的含義。其是在時(shí)間t=0的初始分布,以及某種過(guò)渡模型,用于描述在時(shí)間步長(zhǎng)之間從一種狀態(tài)遷移到另一種狀態(tài)的可能性。如圖l所示馬爾可夫模型的初始分布,由Pr(P0)給出的概率,從狀態(tài)i到i+1的轉(zhuǎn)變模型由Pr(Pi+1|Pi)給出。此過(guò)渡模型暗示的值是有條件的,其僅取決于Pi的值。換句話說(shuō),在時(shí)間t=i+1時(shí)的粒子位置滿足馬爾可夫性質(zhì)或無(wú)記憶性,并且與除t=i以外的所有其它時(shí)間步長(zhǎng)的粒子位置無(wú)關(guān)。如果用以下方法重建p0,p1,p2之間的聯(lián)合,使用馬爾可夫模型鏈?zhǔn)揭?guī)則如下:
Pr(P0,P1,P2)=Pr(P0)Pr(P1|P0)Pr(P2|P1,P0),(1)
假設(shè)Markov屬性為true,并且W0W2| W1成立,則聯(lián)合簡(jiǎn)化為:
Pr(P0,P1,P2)=Pr(Pn)Pr(P1|P0)Pr(P2|P1)。(2)
馬爾科夫模型中,通常做出的最后一個(gè)假設(shè)是過(guò)渡模型是固定的。換句話說(shuō),對(duì)于所有i值,Pr(Pi+1|Pi)是相同的。在此可以用兩個(gè)表來(lái)表示馬爾可夫模型:一個(gè)用于Pr(Pn),一個(gè)用于Pr(Pi+1|Pi)。
通過(guò)馬爾可夫模型,看到了如何通過(guò)一系列隨機(jī)變量,將隨著時(shí)間的變化納入其中。例如,若想知道第1步的位置,可以從初始分布Pr(P0)開(kāi)始,并在過(guò)渡模型中使用小前向算法計(jì)算Pr(P10)。但在時(shí)間t=0和t=10之間,可能會(huì)收集新的位置信息,這些證據(jù)可能會(huì)影響對(duì)任何給定位置概率分布的看法。
2.2 隱馬爾可夫模型
與馬爾科夫鏈不同。隱馬爾可夫模型有兩種不同類型的節(jié)點(diǎn)。為了區(qū)別起見(jiàn),將每個(gè)pi稱為狀態(tài)變量,并將每個(gè)Ei稱為證據(jù)變量。由于pi是第i步的位置概率分布,自然得出第i步的具體位置,有條件地依賴于這一概率。馬爾科夫鏈如圖1所示。正如馬爾可夫模型一樣。隱馬爾可夫模型假設(shè)過(guò)渡模型是平穩(wěn)的,具體模型如圖2所示。隱馬爾可夫模型對(duì)傳感器模型做出了Pr(Pi+1|Pi)額外的簡(jiǎn)化,假設(shè)Pr(Ei+1|Pi)也是固定的。因此,任何隱馬爾可夫模型都可以用3個(gè)概率表來(lái)緊湊地表示:初始分布、過(guò)渡模型和傳感器模型。作為符號(hào)的最后一點(diǎn),將定義時(shí)間i的概率分布,并給出所有證據(jù)Ei,…,Ei,且觀察至B(Pi)=Pr(Pi|E1,…,Ei)。
同樣,將B0(Pi)定義為在時(shí)間i處的概率分布,并觀察到證據(jù)E1,…Ei,B(Pi)=Pr(Pi|E1,…,Ei)將Ei定義為在時(shí)間步i觀察到的證據(jù),有時(shí)會(huì)用以下形式重新表達(dá)時(shí)間步1≤i≤t的證據(jù)匯總:E1:t=E1,…Et,在這種表示法下,Pr(Pi|E1,…Ei)。經(jīng)過(guò)時(shí)間的更新,將新的證據(jù)迭代地納入粒子模型中。
2.3粒子濾波算法
對(duì)于貝葉斯網(wǎng)絡(luò),使用一種采樣技術(shù)是有效估算所需概率分布的可行選擇。隱藏的馬爾可夫模型具有相同的缺點(diǎn)一運(yùn)行需要時(shí)間。貝葉斯凈采樣的過(guò)程稱為粒子濾波,其涉及模擬一組粒子的運(yùn)動(dòng),通過(guò)狀態(tài)圖來(lái)近似表述隨機(jī)變量的概率(信度)分布。
粒子過(guò)濾模擬始于粒子初始化,可以隨機(jī)地、均勻地或從一些初始分布中采樣粒子。一旦對(duì)初始粒子列表進(jìn)行了采樣,在每個(gè)時(shí)間步進(jìn)行觀察更新,更新是根據(jù)過(guò)渡模型,更新每個(gè)粒子的值。處于狀態(tài)Pi的粒子,可從Pr(Pi+1|Pi)給出的概率分布中采樣,得到更新后的值。更新與使用貝葉斯網(wǎng)絡(luò)進(jìn)行采樣的相似性,因?yàn)槿魏谓o定的粒子的頻率反映了轉(zhuǎn)移概率。
使用傳感器模型Pr(Ei|Pi),根據(jù)觀察到的證據(jù)所指示的概率和粒子的狀態(tài)對(duì)每個(gè)粒子進(jìn)行加權(quán)。對(duì)于狀態(tài)為Pi且傳感器讀數(shù)為Ei顆粒,分配Pr(Ei| Pi)的權(quán)重。觀測(cè)更新的算法如下:
(1)如上所述計(jì)算所有顆粒的權(quán)重。
(2)計(jì)算每種狀態(tài)的總權(quán)重。
(3)如果所有狀態(tài)的所有權(quán)重之和為0,重新初始化所有粒子。
(4)否則,標(biāo)準(zhǔn)化總權(quán)重分布,并從該分布重新采樣粒子列表。注意觀察更新與似然加權(quán)的相似性,在此根據(jù)證據(jù)再次降低樣本的權(quán)重。具體過(guò)程如圖3所示。
3 實(shí)驗(yàn)結(jié)果與分析
3.1實(shí)驗(yàn)設(shè)置
為了驗(yàn)證實(shí)驗(yàn)的有效性,文本為Agent的路徑規(guī)劃設(shè)置了虛擬環(huán)境。本文制造了不同大小阻礙環(huán)境,其中障礙物和目標(biāo)點(diǎn)都是隨機(jī)生成的。如圖4所示,實(shí)驗(yàn)設(shè)置了7個(gè)障礙,1個(gè)Agent,2個(gè)不可見(jiàn)目標(biāo)點(diǎn)的7×7大小的原始環(huán)境地圖。
由于實(shí)驗(yàn)的目標(biāo)體是不可見(jiàn)的,通過(guò)粒子來(lái)代替一個(gè)具體個(gè)體,通過(guò)隱馬爾可夫模型的粒子濾波算法找到不可見(jiàn)點(diǎn)的具體位置,如圖5所示。
如圖6所示,當(dāng)粒子向不可見(jiàn)的點(diǎn)合攏時(shí),智能體能找到具體目標(biāo),通過(guò)A*算法直接找到最近不可見(jiàn)的點(diǎn),再找到另外一個(gè)不可見(jiàn)的點(diǎn)。
3.2 實(shí)驗(yàn)結(jié)果
為了使實(shí)驗(yàn)結(jié)果具有更好的準(zhǔn)確性,將實(shí)驗(yàn)分成3組,分別在小迷宮、中迷宮、大迷宮的環(huán)境下尋找2個(gè)不可見(jiàn)目標(biāo)點(diǎn),通過(guò)10次實(shí)驗(yàn),取其均值,其結(jié)果見(jiàn)表1.
通過(guò)實(shí)驗(yàn)結(jié)果可見(jiàn),基于粒子濾波算法的路徑規(guī)劃比概率計(jì)算的路徑規(guī)劃,效率大幅度提升。
4 結(jié)束語(yǔ)
通過(guò)對(duì)復(fù)雜迷宮環(huán)境下的Agent尋找不可見(jiàn)目標(biāo)的研究,提出了一種基于隱馬爾可夫模型的粒子濾波算法,Agent通過(guò)粒子濾波算法確認(rèn)不可見(jiàn)目標(biāo),通過(guò)A*算法最短路徑找到最近目標(biāo)。本實(shí)驗(yàn)使用粒子濾波結(jié)合A*算法,比普通的概率計(jì)算結(jié)合A*算法效率更高。下一步將研究多個(gè)智能體協(xié)同合作,實(shí)現(xiàn)多智能體在復(fù)雜環(huán)境下合作路徑規(guī)劃。