基于隱馬爾可夫模型路徑規(guī)劃方法

鄧旭 趙連軍 郇靜

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

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

0引言

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

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

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

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

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

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

1 研究現(xiàn)狀

李慶中等提出的基于遺傳算法，簡單、有效的移動機器人實時動態(tài)避障路徑規(guī)劃方法，利用遺傳算法實時、穩(wěn)定地進行動態(tài)路徑規(guī)劃。仿真實驗表明：動態(tài)路徑規(guī)劃方法可實時、穩(wěn)定地產(chǎn)生移動機器人運動的最佳局部規(guī)劃路徑，且具有良好的動態(tài)避障性能。

顧新艷等研究移動機器人利用柵格法創(chuàng)建環(huán)境地圖時，在其計算資源有限的情況下，比較利用迷宮八方向搜索思想，實現(xiàn)最短路徑規(guī)劃的Dijkstra算法，提出采用基于柵格劃歸地圖的A*算法，能更快實現(xiàn)移動機器人的無碰最短路徑規(guī)劃。

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

李道新等研究移動機器人的歷史與現(xiàn)狀基礎(chǔ)上，重點在移動機器人避障與路徑選擇規(guī)劃中常用的算法中選取柵格法、勢場法、遺傳算法等方法進行分析比較：并以自行設(shè)計的一款微型機器人為例，探討了基于紅外感知的未知環(huán)境特征提取方法和安全避障距離選取的原則，給出了一種深廣結(jié)合算法的移動機器人避障策略：描述了深廣結(jié)合算法在機器人迷宮地圖中最優(yōu)路徑規(guī)劃實現(xiàn)中的應(yīng)用。

Shazhaev Ilman（伊勒曼）基于多NAO機器人搭建實驗平臺，研究了機器人的定位模型、路徑規(guī)劃和走迷宮尋徑問題。根據(jù)所建立的圖像處理方法和定位模型得到了相應(yīng)的圖形信息，利用圖像處理技術(shù)，完成了位置特征和環(huán)境特征的識別?；贜AO機器人坐標(biāo)系，獲取環(huán)境特征的定位信息，通過定位實驗，驗證了定位模型和路徑規(guī)劃的可行性?；诮⒌牡湫兔詫m結(jié)構(gòu)圖，進行了多機器人協(xié)同迷宮尋徑的研究。實驗完成了多機器人之間的信息交換，并可實時分享周圍的環(huán)境信息。建立了相應(yīng)的算法，根據(jù)編制的程序，利用分享的信息，機器人可以決定如何在迷宮中進行下一步行動。由于決策信息的實時共享，多個機器人比單個機器人更高效快捷地走出迷宮。

2 實驗方法

本實驗通過隱馬爾可夫模型的粒子濾波算法和A*算法在復(fù)雜迷宮環(huán)境下找到動態(tài)目標(biāo)。

2.1 馬爾科夫鏈

馬爾科夫鏈為狀態(tài)空間中。經(jīng)過從一個狀態(tài)到另一個狀態(tài)的轉(zhuǎn)換的隨機過程。該過程要求具備“無記憶”的性質(zhì)：下一狀態(tài)的概率分布只能由當(dāng)前狀態(tài)決定，在時間序列中與前面的事件均無關(guān)。這種特定類型的“無記憶性”稱作馬爾可夫性質(zhì)。在馬爾可夫鏈的每一步，系統(tǒng)根據(jù)概率分布，可以從一個狀態(tài)變到另一個狀態(tài)，也可以保持當(dāng)前狀態(tài)。狀態(tài)的改變叫做轉(zhuǎn)移，與不同的狀態(tài)改變相關(guān)的概率叫做轉(zhuǎn)移概率，如隨機漫步就是馬爾可夫鏈的例子。隨機漫步中每一步的狀態(tài)是在圖形中的點?？梢砸苿拥饺魏我粋€相鄰的點。在這里移動到每一個點的概率都是相同的（無論之前漫步的路徑如何）。

實驗為了追蹤所考慮的粒子隨時間的變化。需要了解馬爾科夫鏈的含義。其是在時間t=0的初始分布，以及某種過渡模型，用于描述在時間步長之間從一種狀態(tài)遷移到另一種狀態(tài)的可能性。如圖l所示馬爾可夫模型的初始分布，由Pr（P₀）給出的概率，從狀態(tài)i到i+1的轉(zhuǎn)變模型由Pr（P_i+1|P_i）給出。此過渡模型暗示的值是有條件的，其僅取決于P_i的值。換句話說，在時間t=i+1時的粒子位置滿足馬爾可夫性質(zhì)或無記憶性，并且與除t=i以外的所有其它時間步長的粒子位置無關(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）

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

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

2.2 隱馬爾可夫模型

與馬爾科夫鏈不同。隱馬爾可夫模型有兩種不同類型的節(jié)點。為了區(qū)別起見，將每個pi稱為狀態(tài)變量，并將每個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個概率表來緊湊地表示：初始分布、過渡模型和傳感器模型。作為符號的最后一點，將定義時間i的概率分布，并給出所有證據(jù)E_i，…，E_i，且觀察至B（P_i）=Pr（P_i|E₁，…，E_i）。

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

2.3粒子濾波算法

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

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

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

（1）如上所述計算所有顆粒的權(quán)重。

（2）計算每種狀態(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 實驗結(jié)果與分析

3.1實驗設(shè)置

為了驗證實驗的有效性，文本為Agent的路徑規(guī)劃設(shè)置了虛擬環(huán)境。本文制造了不同大小阻礙環(huán)境，其中障礙物和目標(biāo)點都是隨機生成的。如圖4所示，實驗設(shè)置了7個障礙，1個Agent，2個不可見目標(biāo)點的7×7大小的原始環(huán)境地圖。

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

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

3.2 實驗結(jié)果

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

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

4 結(jié)束語

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