基于柵格化視覺的機器人路徑優化研究

劉 梅

（河南牧業經濟學院自動化學院 鄭州 450011）

1 引言

路徑最優規劃是移動機器人系統中最重要的組成部分之一，分為點到點的路徑規劃和全覆蓋路徑規劃［1］。點到點的路徑規劃是按照一定的評價標準，如工作代價最小、行走路線最短、行走時間最短等［2］，在其工作空間中找到一條從起始點到目標點的能避開障礙物的最優路徑。主要包括全局路徑規劃和局部路徑規劃。在進行全局路徑規劃過程中，要找到一條從起點到終點的最優路徑，首先進行整體環境建模，在此基礎上通過搜索算法進行最短路徑規劃。環境建模方法通常有柵格法［3］、機器視覺法［4］和拓撲圖法［5］等，在進行環境建模時通常采用其中一種或多種方法結合的建模方法。其中柵格法是最常見的建模方法，通過環境的柵格量化，機器人和障礙物位置可以用柵格的坐標來描述，編程易實現［6］。機器視覺法常用在點到點的路徑規劃中，通過標記障礙物頂點進行避障。A*搜索算法適合于全局路徑規劃和局部路徑規劃，是最常用的一種路徑搜索算法［7］，通過計算代價值來進行路徑搜索。本文針對點到點的全局路徑進行算法設計和仿真，結合柵格法和機器視覺對環境進行建模，在柵格的基礎上得到可視線形成可視覺化，通過減少有效可視點個數對視覺化進行改進，利用A*算法對所有可視線形成的路徑進行代價計算，選擇一條代價值最小的路徑作為全局路徑規劃的最優路徑。

2 環境建模

建立合適的環境模型是尋找最優路徑的前提，這里在柵格化環境地圖的基礎上，機器人和障礙物可以量化在等大的單元格中，如果障礙物形狀復雜，那么可以將障礙物量化在多個相鄰單元格中，量化的障礙物和機器人用柵格頂點坐標分別表示出來。機器人初始位置置于起點處，以機器人為中心形成上、下、左、右、左上、左下、右上、右下的八連通柵格。連接機器人柵格頂點到障礙物外可視頂點形成可視線，這樣從起點到目標點就有多條可搜索路徑，然后結A*算法對這些連通的路徑進行搜索，從而找到一條從起點到目標點的最短路徑。

2.1 柵格化環境

將工作的環境區域進行柵格量化，得到一個m×m大小的環境區域，m為柵格區域邊長。環境地圖的每個柵格具有坐標屬性cell(x。y)，用柵格的障礙物屬性值來區分量化后的障礙物柵格和自由柵格。對自由柵格設置關聯屬性和搜索屬性，自由柵格的八連通方向上的柵格關聯屬性值大的被搜索的概率大［8］。機器人初始位置設置在起點S用○表示，目標點G用◇表示，黑色是障礙物。圖1所示是量化后的柵格模型。

柵格障礙物屬性值設置：

其中，若為0時表示該柵格是自由的，判斷該自由柵格八連通方向的柵格關聯屬性值，屬性值大的可以被搜索；若為1時表示該柵格是障礙物柵格，不可以被搜索。自由柵格的關聯屬性值為大于0的正整數，關聯值越大則搜索概率越大［9］，柵格搜索屬性值初始值設置為

被搜索的柵格的搜索屬性值：

該柵格的關聯屬性值：

如果關聯屬性值大小一樣，則機器人按照S→G方向覆蓋上方、右上或者右邊的柵格。

2.2 改進的視覺化

視覺化就是將所有量化在柵格中的起始點S(xs。ys)、障礙物頂點和目標點 G(xg。yg)用直線組合相連，同時要求三者之間的連線不能穿越障礙物，即直線是“可視的”［10］。給圖中的邊賦權值，構造圖 G(V。E)，節點集V=V0∪(S。G)，E 為所有弧段(Pi。Pj)即邊的集合，其中連接G中第i個和第 j個節點對接線端與任何障礙物均不相交，G(V。E)稱作為可視圖。節點V的選擇可以決定構成的E的多少，從而決定算法所要搜索的路徑。柵格化后的每個障礙物最多有三個可視點，可視點有外可視點和內可視點兩種，能形成可視線的只有外可視點，連接圖1中所有外可視點得到如圖2所示，形成的可視線非常多。

圖2 改進前所有可視點

為使起點到目標點的搜索路徑減少，提高搜索效率，在這里提出一種基于柵格地圖的改進的視覺化，可以大大減少可視線的數量，步驟如下：

Step1：以起點和目標點的橫坐標和縱坐標所在直線相交，形成一個矩形區域，將包圍在這個矩形區域內的障礙物作為形成可視線的目標，落在區域以外的障礙物不做考慮，如圖3所示的矩形區域為機器人進行路徑搜索的范圍；

圖3 改進后有效可視點

Step2：起點到終點的連線可以看做是一條有向的線段，這條線段所在直線可以表示為

將直線方程標準化得到：

其中，A=yg-ys，B=xs-xg，C=xgys-xsyg。以這條直線為標準，無論連線是否穿越障礙物，計算矩形區域內所有從起點到終點方向的具有獨立頂點的障礙物的外可視點 (xi。yi)，i=1。2。…到直線的垂直距離為

Step3：按照距離di從小到大的順序將每個障礙物外可視點坐標分別進行排列，距離分界線越近的可視點期望值越大，每個障礙物的外可視點中選擇一個距離最短的作為有效可視點；

Step4：將所有有效可視點進行連線，形成可視線，如圖4所示。形成的可視線即為搜索范圍。

圖4 可視線連通圖

通過對可視圖的改進，有效的可視點減少，按照已確定起點與目標點連線方向上，雖然障礙物類型繁多，分布區域雜亂，但是從起點到目標點的方向是一定的，如此就確定了有效可視點。距離起點終點方向連線距離遠的障礙物頂點通過上述計算可知，距離代價值大，排除這些無效可視點后，大大減少了搜索的盲目性［11］。圖2中改進前的可視點為48個，而改進后的可視點有15個，因此大大降低了搜索難度，提高了搜索效率。

可視點和可視線連接成有向圖，組成了G=(V。E)，從起點S到目標點G，計算所有路徑的長度并進行比較，最終選擇一條最短的路徑作為最優路徑。這里利用A*算法進行搜索，確定最終的期望路徑。

3 A*算法設計

3.1 基本思路

A*算法是在A算法基礎上，對估價函數加上一些限制后得到的一種啟發式搜索方法［12］。A*算法每次擴展所有可擴展節點中代價最小的節點。A*算法的關鍵是節點的代價 f(n)。設g(n)表示從搜索樹樹根擴展到達節點n的精確代價；h*(n)表示從節點n到達目標節點的最小代價，h*(n)是未知的。因此，從樹根出發經節點n到達目標節點的最小代價為

估價函數 f(n)與 f*(n)相比，g(n)是對 g*(n)的一個估計，h(n)是對h*(n)的一個估計。其中，g(n)≥g*(n)。 h(n)代替 h*(n)，但 h(n)≤h*(n)。綜上，可以證明應用這樣的估價函數是可以找到最短路徑的。

在全局路徑規劃中，機器人從起點開始到節點再從節點到目標點的代價值用遍歷的柵格總和來表示［13］，也就是機器人每覆蓋一個柵格，成本代價就是從起點到節點的覆蓋柵格數的累加，估計代價就是從當前節點到目標點的柵格數累加［14］。機器人在覆蓋柵格的時候首先要判斷目標柵格是否是自由柵格，然后判斷這個自由柵格是否是關聯性最大的柵格，與相關柵格比較如果關聯值最大即作為覆蓋柵格［15］。如果關聯屬性值大小一樣，在機器人的八連通方向上則按照S→G方向覆蓋上、右上或者右邊柵格。

3.2 算法流程

具體的算法實現如下：

Step1：初始化所有節點S(N)放在OPEN表中，起點為S，目標點為G，估計代價取當前節點到目標節點的距離，即h(n)=dis(n。G)，搜索方向為起點到目標點方向；

Step2：判斷OPEN表是否為空，是則轉移到Step7，否則繼續執行；

Step3：判斷N是否是目標節點，是則轉移到Step5，否則繼續執行；

Step4：移出OPEN表中已搜索的節點N放入CLOSED表中，冠以編號n，且

Step5：機器人沿著起點到目標點方向繼續搜索下一個節點，判斷目標節點cell(x。y).related值是否最大，是則利用式（3）、（4）轉移到Step4，否則繼續執行；

Step6：按照柵格八連通的方向和S→G方向覆蓋上、右上或右邊自由柵格。利用公式（3）（4）到下一個節點N，轉移到Step3；

Step7：算法結束，退出程序。

4 算法仿真

基于柵格的改進的視覺化建模減少了可視點數量，結合A*搜索算法［16］，高效率的找到最短路徑。通過基于柵格的改進視覺化的A*算法得到的最短路徑，地圖區域大小為20×20，其中○表示起點，也就是機器人初始位置，◇表示目標點，黑色表示障礙物，灰色表示搜索得到的最優路徑，仿真結果如圖5所示。

圖5 仿真結果

從Matlab仿真結果可以看出，圖中灰色路徑表示規劃的點到點的最短路徑。基于柵格的A*算法需要擴展的點至少有兩個，每一個點都要進行搜索，而且每一步都要進行路徑代價估計比較然后選擇一個節點繼續進行擴展，如此反復，當障礙物可視點數量過多時，擴展點增多，相應的可搜索的路徑增多，增加了搜索負擔。在柵格表示法基礎上采用改進的視覺化建立環境地圖，減少了可視點個數，結合A*算法進行點到點的路徑搜索，得到最后的最短路徑，而且實際代價較低，提高了機器人的搜索效率。

5 結語

基于柵格表示的改進后的視覺化全局路徑搜索是針對點到點的全局路徑規劃提出的算法，該方法通過對環境地圖柵格化、點到點的可視線連通設計、點到點的路徑搜索算法設計，實現了移動機器人從起點到目標點的最短路徑規劃，通過高效的環境建模方法，提高了算法的搜索效率。與一般的視覺化建模方法相比，基于柵格的改進的視覺化建模通過對障礙物所有可視點到起終點連線所在直線的垂直距離選擇最短的可視點作為有效可視點，以此減少可視點個數，相應可供選擇搜索的可視線減少，再結合A*搜索算法對所有路徑進行判斷，最終得到一條代價最小的路徑作為全局路徑規劃的最短路徑。仿真實驗結果表明該方法具有可行性和有效性。