基于A*算法的足球機(jī)器人路徑規(guī)劃①

王 陳,朱衛(wèi)東

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

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

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

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

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

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

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

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

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

1.1 劃分原理

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

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

圖1 TPL算法的圖解

1.2 具體方法

在每一個(gè)周期,帶球球員收集到球場(chǎng)上的信息后,都要運(yùn)用TPL算法對(duì)球場(chǎng)進(jìn)行分割,評(píng)估區(qū)域的風(fēng)險(xiǎn)性,受影響的程度越大,風(fēng)險(xiǎn)性越大.區(qū)域由區(qū)域的邊界線表示,邊界線的信息包括邊界線的方程、邊界線的端點(diǎn)信息.TPL算法對(duì)球場(chǎng)進(jìn)行劃分的過(guò)程如下.

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

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

1.3 風(fēng)險(xiǎn)值的設(shè)置

對(duì)柵格的風(fēng)險(xiǎn)值的設(shè)置要考慮的因素有兩個(gè),一是對(duì)方防守球員的位置,二是安全區(qū)域的風(fēng)險(xiǎn)等級(jí).對(duì)于防守球員所在的柵格要賦一個(gè)風(fēng)險(xiǎn)值,防守球員周?chē)臇鸥竦娘L(fēng)險(xiǎn)值以遞減的方式對(duì)其賦值,其他柵格按其所在區(qū)域的風(fēng)險(xiǎn)等級(jí)賦值,防守球員附近的柵格的風(fēng)險(xiǎn)值要高于其他柵格的風(fēng)險(xiǎn)值.受多種因素影響的柵格,其風(fēng)險(xiǎn)值是多種風(fēng)險(xiǎn)值的疊加.如圖4所示,對(duì)方防守球員所在的柵格的風(fēng)險(xiǎn)值為100,周?chē)鷸鸥竦娘L(fēng)險(xiǎn)值逐漸減小.其他區(qū)域柵格的風(fēng)險(xiǎn)值根據(jù)該柵格的風(fēng)險(xiǎn)等級(jí)對(duì)其賦值,風(fēng)險(xiǎn)等級(jí)越高風(fēng)險(xiǎn)值越大.

圖2 TPL算法對(duì)球場(chǎng)的劃分

圖3 TPL算法計(jì)算區(qū)域風(fēng)險(xiǎn)等級(jí)

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

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

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

2.1 A*算法

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

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

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

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

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

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

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

2.3 改進(jìn)的 A*算法

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

(1)實(shí)際代價(jià)g(n)的計(jì)算

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

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

路徑的安全性指路徑經(jīng)過(guò)的柵格的風(fēng)險(xiǎn)值的和.路徑的安全性計(jì)算公式如下:

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

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

(2)估計(jì)代價(jià)h(n)的計(jì)算

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

(3)優(yōu)缺點(diǎn)分析

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

3 實(shí)驗(yàn)分析

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

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

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

圖7 風(fēng)險(xiǎn)值最低的路徑

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

4 結(jié)束語(yǔ)

本文首次全面的對(duì)球員影響區(qū)域進(jìn)行了分析,通過(guò)對(duì)球場(chǎng)進(jìn)行區(qū)域劃分并設(shè)置風(fēng)險(xiǎn)值,再進(jìn)行路徑規(guī)劃,模擬了人類(lèi)足球運(yùn)動(dòng)員的突破行為,這是以往的路徑規(guī)劃方法都沒(méi)有考慮到的.

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

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

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

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

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

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

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