鄧旭 趙連軍 郇靜

摘要：針對復(fù)雜迷宮環(huán)境的目標(biāo)體具體位置與路徑規(guī)劃問題為對象，提出了一種基于隱馬爾可夫模型的粒子濾波算法。該方法通過隱馬爾可夫模型的概率計(jì)算、粒子濾波算法時(shí)間流逝、觀察、抽樣策略，推理出目標(biāo)體可能范圍，通過A·算法將目標(biāo)捕獲。仿真結(jié)果表明，與普通的概率計(jì)算目標(biāo)體位置，粒子濾波算法計(jì)算的目標(biāo)體位置，大大減少了總步數(shù)，形成了最短路徑。

關(guān)鍵詞：路徑規(guī)劃：隱馬爾可夫模型：粒子濾波

0引言

人工智能在越來越多的領(lǐng)域得到了應(yīng)用。近幾年人工智能的發(fā)展異常迅猛。Hinton等的卷積神級網(wǎng)絡(luò)在計(jì)算機(jī)視覺領(lǐng)域的圖形分類做出了重要貢獻(xiàn)，并且在2015優(yōu)化成深度學(xué)習(xí)。

Silver，D等在2016使用深度神經(jīng)網(wǎng)絡(luò)在有監(jiān)督算法下訓(xùn)練的AlphaGo戰(zhàn)勝韓國棋手李世石。AlphaGo Zero則實(shí)現(xiàn)了更進(jìn)一步的提升，在不使用人類知識的情況下學(xué)習(xí)到了一個(gè)超人水平的計(jì)算機(jī)圍棋程序。

人工智能在迷宮搜索方面有著廣泛的應(yīng)用。但是，自主移動(dòng)機(jī)器人如何在未知的、復(fù)雜的環(huán)境中自主規(guī)劃從起點(diǎn)到終點(diǎn)的路徑，并且躲避障礙，或者通過路徑規(guī)劃捕獲具體目標(biāo)始終是復(fù)雜的技術(shù)難題。因此，進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃算法的研究，具有一定的理論意義和工程應(yīng)用意義。迷宮機(jī)器人是移動(dòng)機(jī)器人的典型應(yīng)用，也是檢驗(yàn)路徑規(guī)劃算法較好的平臺

目前，在迷宮搜索方面，取得了很多有效的進(jìn)展。但是目前的Agent迷宮搜索都是靜態(tài)的單個(gè)目標(biāo)搜索。在多個(gè)動(dòng)態(tài)目標(biāo)搜索方面存在著明顯不足。

隱馬爾可夫模型是統(tǒng)計(jì)模型。用來描述含有隱含未知參數(shù)的馬爾可夫過程。其難點(diǎn)是從可觀察的參數(shù)中確定該過程的隱含參數(shù)。利用這些參數(shù)作進(jìn)一步的分析。其在語音技術(shù)和手寫字符識別應(yīng)用中廣泛使用，但在迷宮搜索領(lǐng)域用得較少。

通過隱馬爾可夫模型的應(yīng)用，可以有效地確認(rèn)多個(gè)動(dòng)態(tài)目標(biāo)位置，通過A*算法尋找和捕獲目標(biāo)。

1 研究現(xià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ī)器人的無碰最短路徑規(guī)劃。

溫如春等對傳統(tǒng)蟻群算法收斂性較慢的問題進(jìn)行了改進(jìn)。通過計(jì)算機(jī)仿真和電腦鼠機(jī)器人實(shí)際行走實(shí)驗(yàn)表明，在場地復(fù)雜的情況下，該算法可以有效地規(guī)劃出全局最優(yōu)路徑。

李道新等研究移動(dòng)機(jī)器人的歷史與現(xiàn)狀基礎(chǔ)上，重點(diǎn)在移動(dòng)機(jī)器人避障與路徑選擇規(guī)劃中常用的算法中選取柵格法、勢場法、遺傳算法等方法進(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)平臺，研究了機(jī)器人的定位模型、路徑規(guī)劃和走迷宮尋徑問題。根據(jù)所建立的圖像處理方法和定位模型得到了相應(yīng)的圖形信息，利用圖像處理技術(shù)，完成了位置特征和環(huán)境特征的識別?；贜AO機(jī)器人坐標(biāo)系，獲取環(huán)境特征的定位信息，通過定位實(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)通過隱馬爾可夫模型的粒子濾波算法和A*算法在復(fù)雜迷宮環(huán)境下找到動(dòng)態(tài)目標(biāo)。

2.1 馬爾科夫鏈

馬爾科夫鏈為狀態(tài)空間中。經(jīng)過從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)換的隨機(jī)過程。該過程要求具備“無記憶”的性質(zhì)：下一狀態(tài)的概率分布只能由當(dāng)前狀態(tài)決定，在時(shí)間序列中與前面的事件均無關(guān)。這種特定類型的“無記憶性”稱作馬爾可夫性質(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)的概率都是相同的（無論之前漫步的路徑如何）。

實(shí)驗(yàn)為了追蹤所考慮的粒子隨時(shí)間的變化。需要了解馬爾科夫鏈的含義。其是在時(shí)間t=0的初始分布，以及某種過渡模型，用于描述在時(shí)間步長之間從一種狀態(tài)遷移到另一種狀態(tài)的可能性。如圖l所示馬爾可夫模型的初始分布，由Pr（P₀）給出的概率，從狀態(tài)i到i+1的轉(zhuǎn)變模型由Pr（P_i+1|P_i）給出。此過渡模型暗示的值是有條件的，其僅取決于P_i的值。換句話說，在時(shí)間t=i+1時(shí)的粒子位置滿足馬爾可夫性質(zhì)或無記憶性，并且與除t=i以外的所有其它時(shí)間步長的粒子位置無關(guān)。如果用以下方法重建p₀，p₁，p₂之間的聯(lián)合，使用馬爾可夫模型鏈?zhǔn)揭?guī)則如下：

Pr（P₀，P₁，P₂）=Pr（P₀）Pr（P₁|P₀）Pr（P₂|P₁，P₀），（1）

假設(shè)Markov屬性為true，并且W0W2| W1成立，則聯(lián)合簡化為：

Pr（P₀，P₁，P₂）=Pr（P_n）Pr（P₁|P₀）Pr（P₂|P₁）。（2）

馬爾科夫模型中，通常做出的最后一個(gè)假設(shè)是過渡模型是固定的。換句話說，對于所有i值，Pr（P_i+1|P_i）是相同的。在此可以用兩個(gè)表來表示馬爾可夫模型：一個(gè)用于Pr（P_n），一個(gè)用于Pr（P_i+1|P_i）。

通過馬爾可夫模型，看到了如何通過一系列隨機(jī)變量，將隨著時(shí)間的變化納入其中。例如，若想知道第1步的位置，可以從初始分布Pr（P₀）開始，并在過渡模型中使用小前向算法計(jì)算Pr（P₁₀）。但在時(shí)間t=0和t=10之間，可能會收集新的位置信息，這些證據(jù)可能會影響對任何給定位置概率分布的看法。

2.2 隱馬爾可夫模型

與馬爾科夫鏈不同。隱馬爾可夫模型有兩種不同類型的節(jié)點(diǎn)。為了區(qū)別起見，將每個(gè)pi稱為狀態(tài)變量，并將每個(gè)E_i稱為證據(jù)變量。由于pi是第i步的位置概率分布，自然得出第i步的具體位置，有條件地依賴于這一概率。馬爾科夫鏈如圖1所示。正如馬爾可夫模型一樣。隱馬爾可夫模型假設(shè)過渡模型是平穩(wěn)的，具體模型如圖2所示。隱馬爾可夫模型對傳感器模型做出了Pr（P_i+1|P_i）額外的簡化，假設(shè)Pr（E_i+1|P_i）也是固定的。因此，任何隱馬爾可夫模型都可以用3個(gè)概率表來緊湊地表示：初始分布、過渡模型和傳感器模型。作為符號的最后一點(diǎn)，將定義時(shí)間i的概率分布，并給出所有證據(jù)E_i，…，E_i，且觀察至B（P_i）=Pr（P_i|E₁，…，E_i）。

同樣，將B₀（P_i）定義為在時(shí)間i處的概率分布，并觀察到證據(jù)E₁，…E_i，B（P_i）=Pr（P_i|E₁，…，E_i）將E_i定義為在時(shí)間步i觀察到的證據(jù)，有時(shí)會用以下形式重新表達(dá)時(shí)間步1≤i≤t的證據(jù)匯總：E_1：t=E₁，…E_t，在這種表示法下，Pr（P_i|E₁，…E_i）。經(jīng)過時(shí)間的更新，將新的證據(jù)迭代地納入粒子模型中。

2.3粒子濾波算法

對于貝葉斯網(wǎng)絡(luò)，使用一種采樣技術(shù)是有效估算所需概率分布的可行選擇。隱藏的馬爾可夫模型具有相同的缺點(diǎn)一運(yùn)行需要時(shí)間。貝葉斯凈采樣的過程稱為粒子濾波，其涉及模擬一組粒子的運(yùn)動(dòng)，通過狀態(tài)圖來近似表述隨機(jī)變量的概率（信度）分布。

粒子過濾模擬始于粒子初始化，可以隨機(jī)地、均勻地或從一些初始分布中采樣粒子。一旦對初始粒子列表進(jìn)行了采樣，在每個(gè)時(shí)間步進(jìn)行觀察更新，更新是根據(jù)過渡模型，更新每個(gè)粒子的值。處于狀態(tài)P_i的粒子，可從Pr（P_i+1|P_i）給出的概率分布中采樣，得到更新后的值。更新與使用貝葉斯網(wǎng)絡(luò)進(jìn)行采樣的相似性，因?yàn)槿魏谓o定的粒子的頻率反映了轉(zhuǎn)移概率。

使用傳感器模型Pr（E_i|P_i），根據(jù)觀察到的證據(jù)所指示的概率和粒子的狀態(tài)對每個(gè)粒子進(jìn)行加權(quán)。對于狀態(tài)為P_i且傳感器讀數(shù)為E_i顆粒，分配Pr（E_i| P_i）的權(quán)重。觀測更新的算法如下：

（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)重。具體過程如圖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è)不可見目標(biāo)點(diǎn)的7×7大小的原始環(huán)境地圖。

由于實(shí)驗(yàn)的目標(biāo)體是不可見的，通過粒子來代替一個(gè)具體個(gè)體，通過隱馬爾可夫模型的粒子濾波算法找到不可見點(diǎn)的具體位置，如圖5所示。

如圖6所示，當(dāng)粒子向不可見的點(diǎn)合攏時(shí)，智能體能找到具體目標(biāo)，通過A*算法直接找到最近不可見的點(diǎn)，再找到另外一個(gè)不可見的點(diǎn)。

3.2 實(shí)驗(yàn)結(jié)果

為了使實(shí)驗(yàn)結(jié)果具有更好的準(zhǔn)確性，將實(shí)驗(yàn)分成3組，分別在小迷宮、中迷宮、大迷宮的環(huán)境下尋找2個(gè)不可見目標(biāo)點(diǎn)，通過10次實(shí)驗(yàn)，取其均值，其結(jié)果見表1.

通過實(shí)驗(yàn)結(jié)果可見，基于粒子濾波算法的路徑規(guī)劃比概率計(jì)算的路徑規(guī)劃，效率大幅度提升。

4 結(jié)束語

通過對復(fù)雜迷宮環(huán)境下的Agent尋找不可見目標(biāo)的研究，提出了一種基于隱馬爾可夫模型的粒子濾波算法，Agent通過粒子濾波算法確認(rèn)不可見目標(biāo)，通過A*算法最短路徑找到最近目標(biāo)。本實(shí)驗(yàn)使用粒子濾波結(jié)合A*算法，比普通的概率計(jì)算結(jié)合A*算法效率更高。下一步將研究多個(gè)智能體協(xié)同合作，實(shí)現(xiàn)多智能體在復(fù)雜環(huán)境下合作路徑規(guī)劃。