基于A*算法的足球機器人路徑規劃①

王 陳,朱衛東

1(北京交通大學 計算機與信息技術學院,北京 100044)2(北京交通大學信息中心,北京 100044)

機器人足球世界杯Robot Soccer World Cup,簡稱RoboCup,是當前國際上級別最高、規模最大、影響最廣泛的機器人賽事.RoboCup機器人足球比賽分為仿真組、小型組、中型組、標準平臺組,類人組,其中仿真組又分為2D和3D[1].本文的研究正是以機器人足球仿真2D為平臺.足球機器人路徑規劃是指正在帶球的足球機器人根據球場信息計算出一條以球為起點,以對方球門為終點的路徑,同時這條路徑還應該滿足不與對方防守球員發生碰撞、盡量遠離對方防守球員、路徑距離盡可能短、耗費時間盡可能少等條件.對于路徑規劃問題,目前已經有多種解決方案,例如柵格法[2]、人工勢場法[3,4]、蟻群算法[5,6]、遺傳算法[7,8]等.

柵格法是地圖建模的一種方法.采用柵格法進行路徑規劃的過程是用大小相等的正方形方塊分割球場,并假設對方防守球員所在的柵格是危險區域,其他柵格為安全區域,然后計算出一條從球所處的柵格到球門所處的柵格的最優安全路徑.對于柵格大小的選取是非常重要的.如果柵格較小,球場會被劃分的非常精確,這會導致要存儲的信息將會增多,且計算量也會變大.反之柵格較大將導致球場劃分的不夠精確,路徑規劃不嚴謹,不利于有效路徑的規劃.

人工勢場法將機器人在周圍環境中的運動,設計成一種抽象的人造引力場中的運動,目標點對移動機器人產生“引力”,障礙物對移動機器人產生“斥力”,最后通過求合力來控制移動機器人的運動.傳統的人工勢場法是從靜態避障研究中得出,適應能力較差,不能夠滿足足球機器人動態環境中實時規劃路徑的要求.此外其內在的局限性主要表現在,當目標附近有障礙物時,移動機器人將永遠到達不了目的地.

蟻群算法是通過模擬自然界螞蟻覓食行為提出的一種仿生進化算法.由于螞蟻覓食過程中會在所經過路徑上釋放一種被稱為信息素的物質,因而其他經過該路徑的螞蟻可以通過感知這種物質,并根據其殘留量確定行進的方向.這樣,螞蟻選擇越多的路徑上所留下的信息素濃度會越大,而濃度大的路徑會吸引更多的螞蟻,這樣就形成一種正反饋.在這種正反饋機制作用下,蟻群最終可以找到一條巢穴到食物源之間的最短路徑.該算法需要設置參數,如果設置不當,就會導致求解速度慢且所得解的質量特別差.此外該算法計算量大、收斂速度慢、求解所需時間較長,不適合實時規劃,易陷入局部最優.

遺傳算法使用種群進行尋優,在每一代的進化過程中,執行同樣的復制、交叉、變異、操作,利用適應度函數進行進化.遺傳算法的缺點是隨著種群的增加,計算量很大,很難滿足實時規劃的要求.而且遺傳算法只適合靜態環境下復雜障礙物環境的路徑規劃,不能滿足動態環境的要求.

盡管以上算法都有著各自的缺點,但它們以及其它的路徑規劃算法都很少考慮到障礙物是移動的的特點,也沒有考慮到障礙物移動性對其周圍區域的影響,因此規劃出的路徑的安全性較低.參考文獻[9]介紹了反向K鄰近(RkNN)的概念,并通過實驗對多種解決RkNN問題的算法的性能進行了比較.本文受到RkNN的概念以及其中一個解決RkNN問題的TPL算法的啟發,提出了一種基于A*算法的足球機器人路徑規劃方法.實驗證明,本文提出的方法考慮了障礙物的移動對其周圍區域的影響,規劃出的路徑更加安全可靠.

1 基于球員影響力的區域劃分

在人類的足球比賽中,帶球球員為了在帶球過程中防止對方防守球員截球,在帶球時總是會往對方防守球員比較少的區域跑,這樣能夠減少被包圍的概率.為了實現上述人類的這種行為,需要分析對方防守球員的影響區域.如果規劃出的路徑受影響的程度越小,路徑越安全.然而目前的路徑規劃算法并沒有考慮上述人類的這種行為,這些算法要么不考慮障礙物的影響區域[5,10,11],要么以障礙物為中心,以r為半徑的圓作為該障礙物的影響區域[2].這樣,圓以外的區域的影響程度就被忽略了,考慮得不夠全面,這就導致規劃出的路徑不夠安全.鑒于此,本文借鑒了TPL算法的思想,設計了一種劃分球員影響區域并根據區域受到的影響程度為其賦上風險值的方法,關于TPL算法的具體介紹請參考文獻[9].

1.1 劃分原理

設防守球員f是對方防守球員集F中的一個元素,q為帶球球員,設B(f:q)是f和q的中垂線,那么這個中垂線將球場分成了兩部分.H(f:q)表示包含了f的半平面,H(q:f)表示包含了q的半平面.任意位于H(q:f)的點p都滿足dist(p,f)＞dist(p,q),其中dist(p,q)表示p到q的距離.這表明如果q直接將球踢入H(f:q),球有很大的可能性會被f搶走.這也表明如果f在H(f:q)上的影響比在H(q:f)上的影響大,若q試圖帶球經過H(f:q),容易被f截球.如圖1所示,點q表示正在帶球的球員,點a,b,c表示對方的防守球員.我們可以發現當對a、b同時運用TPL算法時會得到H(a:q)與H(b:q)的公共部分,即區域①、②.所以如果q在區域④將球踢入或帶球接近區域①、②時,將會承擔較高的風險.特別指出區域②比區域①的風險更高,因為區域②是H(a:q)、H(b:q)和H(c:q)的公共部分.同時我們也能夠發現區域④是安全的,因為位于此區域上的位置到q的距離是最近的.

由此可見,當帶球球員對多個對方防守球員運用TPL算法進行區域劃分時,球場將會被分成多個區域.劃分出的區域分為安全區域和受影響的區域.包含帶球球員的區域即為安全區域,帶球球員到該區域上的任意位置的距離比對方防守球員到該位置的距離更近,因此球在此區域內是安全的.其他區域為受影響的區域.若某個區域是k個不同的H(fi:q)的一部分,則該區域的風險等級為k,風險值為k*δ,其中fi為對方防守球員,q為帶球球員,0＜k≤N,N為對方防守球員個數,δ為風險系數.因此當對球場進行區域劃分后,我們可以根據區域受到的影響程度為其賦上風險值,從而規劃路徑.

圖1 TPL算法的圖解

1.2 具體方法

在每一個周期,帶球球員收集到球場上的信息后,都要運用TPL算法對球場進行分割,評估區域的風險性,受影響的程度越大,風險性越大.區域由區域的邊界線表示,邊界線的信息包括邊界線的方程、邊界線的端點信息.TPL算法對球場進行劃分的過程如下.

算法1.區域劃分算法1)設球場左下角為原點,球場左邊界為Y軸,正方向向上.下邊界為X軸,正方向向右.初始安全區域為整個球場.設N為對方防守球員的數量,令i=0;2)若i＜N,則計算第i個對方防守球員P[i]和帶球球員q的垂直平分線Mi并執行3),否則算法結束;3)對Mi穿過的區域進行分割,并更新分割后的區域的相關信息.執行2).

如圖2所示,假設B4在收集到當前周期的信息后,通過計算與分析,此時最佳的決策是帶球.通過對A2、A3、A4、A7和A8這幾個對B4有較大影響的防守球員運用TPL算法可以將球場劃分成多個區域,并求出每個區域受到的影響程度,即風險等級,如圖3所示.當確定了球場上每個柵格的風險等級之后,B4可以再結合柵格法或其他路徑規劃算法規劃出最優安全路徑.

1.3 風險值的設置

對柵格的風險值的設置要考慮的因素有兩個,一是對方防守球員的位置,二是安全區域的風險等級.對于防守球員所在的柵格要賦一個風險值,防守球員周圍的柵格的風險值以遞減的方式對其賦值,其他柵格按其所在區域的風險等級賦值,防守球員附近的柵格的風險值要高于其他柵格的風險值.受多種因素影響的柵格,其風險值是多種風險值的疊加.如圖4所示,對方防守球員所在的柵格的風險值為100,周圍柵格的風險值逐漸減小.其他區域柵格的風險值根據該柵格的風險等級對其賦值,風險等級越高風險值越大.

圖2 TPL算法對球場的劃分

圖3 TPL算法計算區域風險等級

圖4 防守球員所在柵格的風險值設置方法示例

2 基于A*算法的路徑規劃

傳統的A*算法[12-14]通常僅僅考慮路徑的長度,很少考慮路徑經過的結點的權重.這導致在某些情況下規劃出的路徑效果不夠好.通過之前對各個柵格的風險值的設置,此處將探討在路徑結點具有權重的情況下的基于A*算法的路徑規劃.

2.1 A*算法

A*算法是一種靜態路網中求解最短路徑最有效的直接搜索方法.A*方法對狀態空間中的每一個搜索位置進行評估,得到最好的位置,再從這個位置進行搜索直到搜索到目標位置.這樣可以避免大量無謂的路徑搜索,提高了效率.該方法對位置的評估是十分重要的,路徑的代價估計函數為f(n)=g(n)+h(n),其中f(n)是從初始狀態經由狀態n到目標狀態的代價估計,g(n)是在狀態空間中從初始狀態到狀態n的實際代價,h(n)是從狀態n到目標狀態的最佳路徑的估計代價.

2.2 搜索空間的優化

為了提高計算的效率,可以對搜索空間進行優化,避免不必要的計算,此外在估計路徑代價時,需要考慮搜索空間的大小.通常最優的安全路徑存在于以起點柵格和目的柵格為對角頂點的矩形中.因此,對于該矩形以外的柵格可以不用考慮.但是在有些情況下,帶球球員會受到安全性因素的影響,選擇一條較長的路徑,從而走出了矩形區域.如圖5所示,帶球球員位于點S處,D為目的地.如果路徑被包含在矩形中,該路徑將是危險的.例如,如果帶球球員沿路徑path1走,將被防對方守球員A、B包圍;如果從A的上方通過將會被A、B、C包圍.如果沿path2走,路徑相對安全.因此需要設計一個合適的方法來解決這個問題優化搜索空間.

圖5 規劃路徑示例

搜索空間的優化算法如算法2.

算法2.搜索空間的優化算法1)設D為目的柵格,S為帶球球員所在柵格.初始搜索空間為以D和S為對角頂點的矩形R.獲取矩形R中的對方防守球員的信息,將該球員加入球員數組PlayerTemp[]中;2)如果PlayerTemp[]為空,則算法結束.否則依次遍歷PlayerTemp

[]中的球員,計算對方防守球員影響的柵格是否在垂直方向超出矩形R,若超出,則將矩形向垂直方向擴大至將該柵格包括在內,并滿足該柵格與R的上邊界或下邊界相隔兩個柵格,若矩形的上(下)邊界到達了球場的上(下)邊界,則矩形的上(下)邊界即為球場的上(下)邊界;3)獲取矩形外的對方防守球員的信息,如果矩形外沒有對方防守球員則搜空空間為矩形R,算法結束.否則依次遍歷矩形外的對方防守球員.如果對方防守球員影響的柵格位于矩形R內,則將該球員加入球員數組PlayerTemp[]中.遍歷結束后執行2).

2.3 改進的 A*算法

A*算法最關鍵的是確定路徑的代價估計函數f(n),代價估計函數f(n)又包括實際代價g(n)和估計代價h(n).由于實際代價g(n)是對確定路徑的代價計算,可以得出準確的值,而估計代價h(n)是對不確定路徑的代價估計,只能得到估計值.因此兩者的計算是不同的.本文從兩個方面進行對路徑代價進行了考慮,一是路徑的長度,二是路徑的安全性.

(1)實際代價g(n)的計算

在本文中,計算路徑的長度是通過計算路徑經過的柵格的長度實現的.路徑長度的計算公式如下所示:

其中L(S,n)表示從起點柵格S到柵格n的長度,n1表示該路徑的柵格總數,n2表示該路徑中位置是對角關系的柵格對數,dis表示相鄰柵格的中心點的距離.

路徑的安全性指路徑經過的柵格的風險值的和.路徑的安全性計算公式如下:

其中W(S,n)表示從起點柵格S到柵格n的風險值,n1表示該路徑的柵格總數,wj表示該路徑的第j個柵格的風險值.因此實際代價g(n)為:

其中a、b分別表示路徑長度和路徑風險等級所占的比重,具體大小根據實際情況設置.

(2)估計代價h(n)的計算

對于估計代價的計算通常有兩種方法,第一種為曼哈頓預估方法,第二種為歐幾里得預估方法.但是這兩種方法通常僅僅是路徑長度的計算,沒有考慮到路徑各結點的權重.為了提高計算效率,本文的估計代價計算均值.設搜索空間的風險值有k種,分別為w1,w2,…wk,風險值為wi的個數為ni,L為柵格n到目標柵格D的曼哈頓距離,N為搜索空間包含的柵格數,a、b為路徑長度和路徑風險等級所占的比重,則估計代價為:

(3)優缺點分析

A*算法是常用的啟發式算法,它通過代價估計函數f(n)引導算法的搜索方向,不用將所有可能的路徑都遍歷一遍,大大減少了計算量,提高了計算效率.以往的基于A*算法的足球機器人路徑規劃幾乎都沒有考慮所經過的柵格的權重,而本文改進的A*算法是在對柵格合理賦予風險值并對搜索空間優化了的基礎上進行路徑規劃的,不僅具備了傳統的A*算法的優點,還對路徑的長度和安全性綜合考慮,使規劃出的路徑在動態障礙物環境下更加安全.然而,改進后的A*算法同樣繼承了傳統A*算法的不足,即估計代價h(n)與實際值存在差異,不能保證得到最優解.

3 實驗分析

為了驗證本文所提出的算法的有效性以及優越性,進行了仿真實驗.球場被分成了61*36個柵格,試驗中球員和球的位置由實際比賽中隨機選取的某個時刻球員和球所在的位置確定.設dis為30,柵格的風險值為r*5,其中r為該柵格的風險等級.對方防守球員所在的柵格及其周圍的柵格的風險值的設置如圖4所示.為了確定a,b的值,設a=0,b=1-a,進行路徑規劃試驗.試驗結束后令a=a+0.1,再次進行試驗;直至a＞1時本輪實驗結束.本輪試驗結束后,更新球場球員及球的位置信息,重新進行確定a、b的試驗.試驗結果表明當a=0.4,b=0.6時,有最大的可能性得到最好的路徑.

可以發現當a、b分別設置為1和0時,即可得到傳統A*算法規劃出的最短路徑.如圖6所示,該路徑的長度雖然是最短的,但沒有考慮路徑結點的風險值,安全性非常低.當a、b分別設置為0和1時,得到的是風險值最低的安全路徑.如圖7所示,該路徑僅考慮了安全性,沒有考慮路徑長度,考慮的不夠全面.當a、b分別設置為0.4和0.6時,效果最好,得到的是改進后的A*算法規劃的安全路徑.如圖8所示,該路徑既考慮了安全性,又考慮了路徑長度.對比傳統的A*算法,改進后的A*算法規劃出的路徑更好.

圖6 傳統A*算法規劃的最短路徑

圖7 風險值最低的路徑

圖8 改進后的A*算法規劃的最優安全路徑

4 結束語

本文首次全面的對球員影響區域進行了分析,通過對球場進行區域劃分并設置風險值,再進行路徑規劃,模擬了人類足球運動員的突破行為,這是以往的路徑規劃方法都沒有考慮到的.

此外,傳統的A*算法都只是求解最短路徑,對于移動障礙物的避障路徑規劃效果不佳.而本文的A*算法不僅考慮了路徑的長度,還考慮了路徑上每個結點的權重,仿真對比結果表明改進后的A*算法計算出的路徑更加安全可靠.

1 方寶富,王浩.機器人足球仿真.合肥:合肥工業大學出版社,2011.

2 祁曉鈺.機器人足球路徑規劃的一種改進算法.計算機仿真,2014,31(5):373–377.

3 Mabrouk MH,Mcinnes CR.Solving the potential field local minimum problem using internal agent states.Robotics and Autonomous Systems,2008,56(12):1050–1060.[doi:10.1016/j.robot.2008.09.006]

4 Masoud AA.Managing the dynamics of a harmonic potential field-guided robot in a cluttered environment.IEEE Transactions on Industrial Electronics,2009,56(2):488–496.[doi:10.1109/TIE.2008.2002720]

5 潘攀.足球機器人路徑規劃算法的研究及其仿真.計算機仿真,2012,29(4):181–184.

6 Garcia MAP,Montiel O,Castillo O,et al.Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation.Applied Soft Computing,2009,9(3):1102–1110.[doi:10.1016/j.asoc.2009.02.014]

7 丁彪.基于改進遺傳算法的移動機器人路徑規劃.自動化應用,2014,(1):1–3.

8 Kala R.Multi-robot path planning using co-evolutionary genetic programming.Expert Systems with Applications,2012,39(3):3817–3831.[doi:10.1016/j.eswa.2011.09.090]

9 Yang SY,Cheema MA,Lin XM,et al.Reverse k nearest neighbors query processing:Experiments and analysis.Proceedings of the VLDB Endowment,2015,8(5):605–616.[doi:10.14778/2735479]

10 林志雄,張莉.基于神經模糊勢場法的足球機器人路徑規劃.計算機仿真,2014,31(1):416–420,437.

11 劉成菊,韓俊強,安康.基于改進RRT算法的RoboCup機器人動態路徑規劃.機器人,2017,39(1):8–15.

12 王紅衛,馬勇,謝勇,等.基于平滑A*算法的移動機器人路徑規劃.同濟大學學報(自然科學版),2010,38(11):1647–1650,1655.[doi:10.3969/j.issn.0253-374x.2010.11.016]

13 辛煜,梁華為,杜明博,等.一種可搜索無限個鄰域的改進A*算法.機器人,2014,36(5):627–633.

14 趙奇,趙阿群.一種基于A*算法的多徑尋由算法.電子與信息學報,2013,35(4):952–957.