山西中北大學(xué)機電工程學(xué)院　閆鵬杰　張亞

一種移動機器人路徑規(guī)劃新方法

山西中北大學(xué)機電工程學(xué)院閆鵬杰張亞

路徑規(guī)劃是自主移動機器人導(dǎo)航的基本任務(wù)，其精度取決于地圖構(gòu)建和定位。一些路徑規(guī)劃算法已經(jīng)應(yīng)用于精確的路勁規(guī)劃過程，比如Dijkstra算法，A*算法等。如果機器人的體積大于柵格地圖的柵格單元，傳統(tǒng)A*算法路徑規(guī)劃就會不精確，在這種情況下移動機器人很難安全通過門和狹窄的通道。本文提出的新的路徑規(guī)劃方法在障礙物周圍虛擬增加障礙柵格單元，有效降低了發(fā)生碰撞的可能性。

路徑規(guī)劃；A*算法；自主移動機器人

1　引言

路徑規(guī)劃是自主導(dǎo)航移動機器人的關(guān)鍵技術(shù)之一。準確、最優(yōu)的路徑規(guī)劃一方面需要機器人通過傳感器獲取準確的環(huán)境信息和里程計信息；另一方面移動機器人必須避開障礙物安全到達目標點，并且路徑必須是最短的。最短路徑是節(jié)省時間方面的約束，最安全路徑是移動機器人安全方面的約束［1-2］。

Dijkstra算法是一種移動機器人最短路徑規(guī)劃算法。Peter E. Har等人在dijkstra算法基礎(chǔ)上提出了A*算法［3］，加快了搜索效率。但是A*一直存在一個問題：當機器人的外形尺寸大于柵格地圖中柵格的尺寸時，當機器人沿著規(guī)劃的最短路徑行走時存在撞到障礙物的可能性，這對機器人是不安全的。本文就是在傳統(tǒng)A*算法的基礎(chǔ)上，將機器人的外形尺寸因素引入到路徑搜索的過程中，從而尋找到最短路徑。

2　路徑規(guī)劃

2.1A*路徑規(guī)劃算法

A*算法應(yīng)用在柵格環(huán)境地圖中，是一種啟發(fā)式搜索算法，啟發(fā)函數(shù)h（n）是算法的核心，也是區(qū)別于Dijkstra算法的關(guān)鍵。啟發(fā)函數(shù)的作用是給出當前節(jié)點到目標節(jié)點的估計距離，這個距離不考慮路徑中的障礙物。啟發(fā)函數(shù)使算法可有效得到更多關(guān)于環(huán)境地圖的信息。A*算法從起始節(jié)點開始搜索，并把起始節(jié)點周圍的節(jié)點加入到一個列表中，我們稱之為Open列表。Open列表中的節(jié)點按f（n）值由小到大排列，啟發(fā)函數(shù)h（n）是f （n）的組成部分。Open列表中f（n）值最小的節(jié)點就是下一次的擴展節(jié)點，這個過程一直循環(huán)直到擴展到目標節(jié)點，這樣最終路徑就被搜索出來了。每個柵格節(jié)點的代價函數(shù)如下式：

f（n）=g（n）+h（n）（1）

上式中，假設(shè)當前的搜索節(jié)點為n（xn，yn），f（n）是從起始節(jié)點S經(jīng)過當前節(jié)點n到達目標節(jié)點G的最小代價估計值，g （n）是從起始節(jié)點S到達當前節(jié)點n的實際最小代價值，h（n）是從當前節(jié)點n到達目標點G的最小估計代價值。g（n）的值表示如式（2）：

當prev（n）=Sk時，即當前節(jié)點為Sk時：

式（4）中的h（n）值是從當前節(jié)點n到目標節(jié)點G的歐式距離。啟發(fā)函數(shù)h（n）的值也可以按Manhattan距離計算或是其他相對應(yīng)的距離計算方法。

通過以上計算方法和搜索策略就可以找到最短路徑。從目標點依次向前追蹤到起始點S就是所求最短路徑。傳統(tǒng)A*算法的路徑規(guī)劃仿真結(jié)果如圖1所示。

2.2缺陷

仿真實驗?zāi)M的是室內(nèi)的環(huán)境，包括一些虛擬的障礙物如門、墻、桌子等。占有柵格地圖是虛擬室內(nèi)環(huán)境的映射，障礙物柵格用‘1’表示，可行區(qū)域用‘0’表示。仿真實驗中起始節(jié)點和目標節(jié)點在柵格地圖中的位置是事先給定的。起始位置設(shè)置為‘-1’目標位置設(shè)置為‘-2’。按照公式（1）-（4）的計算方法，從起始點到目標點用傳統(tǒng)A*算法進行路徑搜索就會找到路徑。為了獲得更精確的最短路徑，必須增大柵格地圖的分辨率，即機器人的外形尺寸會大于柵格大小，這就會使傳統(tǒng)A*算法規(guī)劃出的路徑存在安全問題，如圖1所示，機器人行走路徑會很接近障礙物，這就會導(dǎo)致實際移動機器人在行走中會撞上墻等障礙物。另一方面，如果門等通道是很狹窄的，機器人可能被夾住。

同理，式（1）中的h（n）估計值如式（4）：

圖1　傳統(tǒng)A*算法

2.3改進方法

為了解決上述問題，本文對A*算法進行了改進。在新方法中，我們按照公式（5），在障礙物的周圍增加了虛擬的障礙柵格所有的障礙物柵格被定義為‘1’。虛擬障礙物的設(shè)置規(guī)則如下：

代價值被標記為‘1’和‘2’的所有柵格都放在關(guān)閉列表中。關(guān)閉列表是機器人下一次搜索不能選的單元列表。代價值為‘2’的柵格單元就被認定為虛擬障礙物?，F(xiàn)在傳統(tǒng)的A*算法按式（5）進行了改進。改進后的A*算法更適應(yīng)于機器人外型等于柵格大小的情況。

A*算法的過程：

A.生成可行節(jié)點和不可行節(jié)點的地圖。

B.創(chuàng)建“Open”和“Closed”列表，初始狀態(tài)都為空。

C.將所有的不可行節(jié)點放入“關(guān)閉”列表。

D.創(chuàng)建起始節(jié)點和目標節(jié)點。將起始節(jié)點放在開啟列表中

E.如果開啟列表不是空的并且沒有找到路徑，按如下步驟：

a）將開啟列表中f（n）值最小的節(jié)點移出，這個節(jié)點就作為當前節(jié)點。

b）將當前節(jié)點的狀態(tài)設(shè)置為關(guān)閉狀態(tài)。

c）對于當前節(jié)點周圍相鄰的8個節(jié)點做如下處理：

·如果該節(jié)點是地圖范圍內(nèi)可以行走的，并且不在關(guān)閉列表中，做如下處理：

·如果該節(jié)點不在Open列表中，把它放入Open列表中，并存儲其f、g、h值，同時將它的狀態(tài)設(shè)置為開啟狀態(tài)。

·如果該節(jié)點已經(jīng)在Open列表中（也就是說它的狀態(tài)為開啟狀態(tài)），重新計算它的g值，如果新的g值小于之前的g值，則將它的父輩節(jié)點改為當前節(jié)點，并且在Open列表中存儲新的f 和g值。

d）當目標節(jié)點的狀態(tài)被放到開啟列表中時，意味著找到了路徑。

F.當開啟列表為空時，意味著路徑搜索失敗。

以此類比，當機器人的外形尺寸是柵格尺寸的2～3倍時，從安全角度考慮，我們將虛擬障礙物再向外擴展一層，如圖3所示。

3　仿真實驗

本實驗假設(shè)環(huán)境地圖為已知的柵格地圖，地圖大小分為100×100格。柵格地圖的表示方法為：‘1’表示為障礙物（不可行節(jié)點），‘0’表示可通行區(qū)域（可行節(jié)點），起始位置都預(yù)先在地圖中設(shè)置。本文提出的改進策略也在算法中實現(xiàn)。

傳統(tǒng)A*算法的搜索結(jié)果見圖1，機器人在移動過程中會離障礙物很近。經(jīng)過公式（5）改進，從圖2中可以很明顯的看到，改進后的A*算法搜索出的路徑對機器人更安全。如果機器人外形尺寸變?yōu)闁鸥癯叽绲?～3倍時，繼續(xù)擴大虛擬障礙物范圍，此時的搜索結(jié)果如圖3所示。對比圖1與圖3可以發(fā)現(xiàn)，改進后的A*算法可以解決機器人在移動過程中碰到障礙物的問題。

圖2　改進A*算法：機器人尺寸等于柵格尺寸

圖3　改進A*算法：機器人外形尺寸等于2～3倍柵格尺寸

4　結(jié)論

為了避免機器人與障礙物發(fā)生碰撞，在傳統(tǒng)算法基礎(chǔ)上改進的A*算法通過添加虛擬障礙物來適應(yīng)不同外形尺寸的機器人，仿真實驗結(jié)果驗證了新方法的有效性。改進后的A*算法搜索出的路徑或許不是最短的，但是對于機器人來說會更加安全。

［1］王麗，徐德民.移動機器人路徑規(guī)劃方法研究［J］.西安：西北工業(yè)大學(xué)航海學(xué)院，2007.

［2］黎紅.自主移動機器人路徑規(guī)劃中的主要方法［J］.中國電力教育，2010（S1）：814-816.

［3］王殿君.基于改進A*算法的室內(nèi)移動機器人路徑規(guī)劃［J］.清華大學(xué)學(xué)報，2012，52（8）：1085-1089.

［4］譚寶成，王培.A＊路徑規(guī)劃算法的改進及實現(xiàn)［J］.西安工業(yè)大學(xué)學(xué)報，2012，32（04）：325-328.

閆鵬杰，1990出生，男，山西運城人，在讀碩士研究生，機械電子工程。