王 陳,朱衛(wèi)東

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

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

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

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

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

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

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

1 基于球員影響力的區(qū)域劃分

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

1.1 劃分原理

設(shè)防守球員f是對方防守球員集F中的一個元素,q為帶球球員,設(shè)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試圖帶球經(jīng)過H(f:q),容易被f截球.如圖1所示,點q表示正在帶球的球員,點a,b,c表示對方的防守球員.我們可以發(fā)現(xiàn)當對a、b同時運用TPL算法時會得到H(a:q)與H(b:q)的公共部分,即區(qū)域①、②.所以如果q在區(qū)域④將球踢入或帶球接近區(qū)域①、②時,將會承擔較高的風險.特別指出區(qū)域②比區(qū)域①的風險更高,因為區(qū)域②是H(a:q)、H(b:q)和H(c:q)的公共部分.同時我們也能夠發(fā)現(xiàn)區(qū)域④是安全的,因為位于此區(qū)域上的位置到q的距離是最近的.

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

圖1 TPL算法的圖解

1.2 具體方法

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

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

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

1.3 風險值的設(shè)置

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

圖2 TPL算法對球場的劃分

圖3 TPL算法計算區(qū)域風險等級

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

2 基于A*算法的路徑規(guī)劃

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

2.1 A*算法

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

2.2 搜索空間的優(yōu)化

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

圖5 規(guī)劃路徑示例

搜索空間的優(yōu)化算法如算法2.

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

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

2.3 改進的 A*算法

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

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

在本文中,計算路徑的長度是通過計算路徑經(jīng)過的柵格的長度實現(xiàn)的.路徑長度的計算公式如下所示:

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

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

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

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

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

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

(3)優(yōu)缺點分析

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

3 實驗分析

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

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

圖6 傳統(tǒng)A*算法規(guī)劃的最短路徑

圖7 風險值最低的路徑

圖8 改進后的A*算法規(guī)劃的最優(yōu)安全路徑

4 結(jié)束語

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

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

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

2 祁曉鈺.機器人足球路徑規(guī)劃的一種改進算法.計算機仿真,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 潘攀.足球機器人路徑規(guī)劃算法的研究及其仿真.計算機仿真,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 丁彪.基于改進遺傳算法的移動機器人路徑規(guī)劃.自動化應(yīng)用,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 林志雄,張莉.基于神經(jīng)模糊勢場法的足球機器人路徑規(guī)劃.計算機仿真,2014,31(1):416–420,437.

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

12 王紅衛(wèi),馬勇,謝勇,等.基于平滑A*算法的移動機器人路徑規(guī)劃.同濟大學學報(自然科學版),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.