一種基于改進(jìn)Theta*的機(jī)器人路徑規(guī)劃算法

肖國(guó)寶，嚴(yán)宣輝

(福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350007)

路徑規(guī)劃是智能交通、智能網(wǎng)絡(luò)、機(jī)器人等人工智能研究領(lǐng)域的重要分支，所謂移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)，就是機(jī)器人根據(jù)自身傳感器對(duì)環(huán)境的感知，在線規(guī)劃出一條安全、可靠的運(yùn)行路徑，同時(shí)高效完成作業(yè)任務(wù)［1-2］.它是一個(gè)比較復(fù)雜的帶約束條件的優(yōu)化問題，約束條件包括但不限于:不與障礙物碰撞、運(yùn)動(dòng)路徑最短、盡量遠(yuǎn)離障礙物、路徑盡量平滑等［3-4］.

未知環(huán)境下的機(jī)器人路徑規(guī)劃是智能體實(shí)現(xiàn)其在線規(guī)劃的前提，也是移動(dòng)機(jī)器人導(dǎo)航中一個(gè)重要的問題.目前，確定性環(huán)境的導(dǎo)航控制方法已取得了大量的研究和應(yīng)用成果［5-6］，在二維未知環(huán)境中的導(dǎo)航控制方面已展開了一些研究，并提出了若干方法［7-9］;但隨著人類活動(dòng)空間的擴(kuò)張，已有的二維路徑規(guī)劃技術(shù)越來越滿足不了許多領(lǐng)域的需求，人們迫切需要一套成熟可靠的三維空間路徑規(guī)劃技術(shù)［7］.

機(jī)器人路徑規(guī)劃需要考慮很多因素，其中主要包括環(huán)境的不確定性和動(dòng)態(tài)特性、規(guī)劃算法的優(yōu)越性、實(shí)時(shí)能力等.三維環(huán)境下的機(jī)器人路徑規(guī)劃問題由于運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)約束變得非常復(fù)雜，機(jī)器人的自由度也大幅度增加，這要求規(guī)劃算法的實(shí)時(shí)性要比較好，防止出現(xiàn)數(shù)據(jù)爆炸的情況.針對(duì)盲目搜索的效率較低，會(huì)耗費(fèi)過多的計(jì)算空間與時(shí)間，目前用于三維路徑規(guī)劃比較常見的算法有 A*［8］、Diskstra、D*-lite、貪婪搜索、四/八叉樹搜索［9］以及這些算法的改進(jìn)［10-11］.采用的搜索策略如寬度優(yōu)先、深度優(yōu)先、啟發(fā)式、非啟發(fā)式搜索等［7］.

經(jīng)典的啟發(fā)式搜索算法——A*算法是由P.E.Hart等在20世紀(jì)60年代提出的，該算法在各個(gè)領(lǐng)域得到了廣泛的應(yīng)用［12］.A*算法也是目前用來解決游戲地圖路徑搜索問題最優(yōu)的算法，但該算法只能用在格子環(huán)境中，這在一定程度上限制了其進(jìn)一步的推廣.Alex等在2007年提出了一種A*算法的變種——Theta*算法［13］，突破了格子的限制，允許以任意角度改變路徑的方向.

啟發(fā)函數(shù)是評(píng)定候選擴(kuò)展節(jié)點(diǎn)的方法，以便確定哪個(gè)節(jié)點(diǎn)最有可能在通向目標(biāo)的最佳路徑上，它將會(huì)影響到整個(gè)算法的性能和效果.在大部分啟發(fā)式搜索算法中的啟發(fā)函數(shù)只估算到起始點(diǎn)和目標(biāo)點(diǎn)的代價(jià)，沒有合理地利用障礙物信息，這會(huì)限制其用于解決機(jī)器人路徑規(guī)劃問題時(shí)的進(jìn)一步推廣.

本文將局部環(huán)境的障礙物對(duì)機(jī)器人產(chǎn)生的斥力作為懲罰函數(shù)引入到啟發(fā)函數(shù)中，為機(jī)器人提供了更加可靠的啟發(fā)信息.首先，利用仿真實(shí)驗(yàn)的數(shù)據(jù)統(tǒng)計(jì)合理地選擇懲罰函數(shù)權(quán)重，以確定啟發(fā)函數(shù);然后在此啟發(fā)策略的基礎(chǔ)上，改進(jìn)A*算法的變種——Theta*算法，用PS_Theta*算法對(duì)路徑進(jìn)行平滑處理，優(yōu)化路徑.

1 算法描述

1.1 三維環(huán)境模型

移動(dòng)機(jī)器人環(huán)境模型問題就是機(jī)器人根據(jù)傳感器的感知獲得環(huán)境的二維或三維空間模型.單元分解建模是典型的環(huán)境模型，其主要思想是將環(huán)境離散化為若干個(gè)規(guī)則的相同大小的基本單元——三維的立方格，通過二值信息便可以對(duì)障礙物和自由空間進(jìn)行標(biāo)識(shí)，因此使用簡(jiǎn)單的傳感器即可獲得創(chuàng)建地圖的信息.然而，立方格的大小直接影響著移動(dòng)機(jī)器人環(huán)境信息存儲(chǔ)量的大小和規(guī)劃時(shí)間的長(zhǎng)短，立方格選得小，環(huán)境分辨率高，但環(huán)境信息存儲(chǔ)量大，相應(yīng)的干擾信號(hào)相對(duì)增加，使得決策工作量加大，最終導(dǎo)致規(guī)劃速度變慢，降低系統(tǒng)的實(shí)時(shí)性;當(dāng)立方格變大時(shí)，雖然抗干擾能力增強(qiáng)，但環(huán)境分辨率下降，在密集障礙物環(huán)境中不利于規(guī)劃出有效的路徑［14］.

在Matlab 7.6中建立2種常見的模型:1)城市環(huán)境模型，如圖1;2)普通環(huán)境模型，如圖2.其中，將機(jī)器人看作質(zhì)點(diǎn)，不能碰到環(huán)境中的任何障礙物.

圖1 城市環(huán)境模型Fig.1 Urban environment model

圖2 普通環(huán)境模型Fig.2 Common environment model

任意時(shí)刻，在二維地圖中，機(jī)器人的運(yùn)動(dòng)方向有8個(gè)，如圖3所示，機(jī)器人可以到達(dá)相鄰柵格的各個(gè)頂點(diǎn);在三維地圖中，機(jī)器人的運(yùn)動(dòng)方向有26個(gè)，如圖4所示，機(jī)器人可以到達(dá)相鄰立方格的各個(gè)頂點(diǎn).

圖3 二維運(yùn)動(dòng)方向Fig.3 The direction of movement in 2-D environment

圖4 三維運(yùn)動(dòng)方向Fig.4 The direction of movement in 3-D environment

機(jī)器人路徑規(guī)劃問題就是在圖中尋找一個(gè)從起始點(diǎn)S到目標(biāo)點(diǎn)T之間點(diǎn)的集合，并要求相鄰點(diǎn)之間的線段連接沒有經(jīng)過障礙物.

1.2 改進(jìn)啟發(fā)函數(shù)

在啟發(fā)式搜索算法中，引入當(dāng)前節(jié)點(diǎn)x的啟發(fā)式估價(jià)函數(shù)f'(x)，其函數(shù)的定義式為

式中:f'(x)是從起點(diǎn)S出發(fā)到目標(biāo)點(diǎn)的最小代價(jià)值f(x)的估價(jià)函數(shù)，g(x)是從起點(diǎn)S到當(dāng)前節(jié)點(diǎn)x的實(shí)際代價(jià)值，h'(x)是從當(dāng)前節(jié)點(diǎn)x到目標(biāo)點(diǎn)估計(jì)的最小代價(jià)值，α、β是2個(gè)增益系數(shù).顯然，當(dāng)h'(x)=0時(shí)，啟發(fā)式搜索算法就變成了沒有任何啟發(fā)信息的盲目搜索算法，如普通Dijkstra算法.

在啟發(fā)式搜索算法中，找到最優(yōu)路徑的關(guān)鍵在于估價(jià)函數(shù)h(x)的選取，如可以取兩節(jié)點(diǎn)的歐幾里德距離作為估價(jià)值.由式(1)可知，啟發(fā)信息與環(huán)境中的障礙物無關(guān)，但對(duì)于機(jī)器人路徑規(guī)劃問題，障礙物的位置信息是規(guī)劃過程中需要考慮的重要信息之一.因此，啟發(fā)信息若能夠考慮障礙物的位置信息將更有前瞻性和可靠性，有利于機(jī)器人準(zhǔn)確地判斷下一步的動(dòng)作.在保證路徑長(zhǎng)度較短的前提下，盡可能地靠近目標(biāo)點(diǎn)及遠(yuǎn)離障礙物是路徑規(guī)劃最理想的狀態(tài)，此處引入人工勢(shì)場(chǎng)法(artificial potential field，APF)的思想［15-16］，讓機(jī)器人盡可能地避開障礙物.本文將一定范圍內(nèi)的障礙物對(duì)機(jī)器人產(chǎn)生的斥力作為一種懲罰函數(shù)添加至啟發(fā)函數(shù)中.在人工勢(shì)場(chǎng)法中斥力場(chǎng)公式為:

式中:η 是正增益系數(shù);X=(xr，yr)和 XG=(xG，yG)分別表示機(jī)器人位置向量和目標(biāo)點(diǎn)位置向量;ρ表示機(jī)器人到障礙物的歐式距離;ρ0表示單個(gè)障礙物影響的最大距離范圍.相應(yīng)的斥力為其負(fù)梯度，如式(2):

式中:

將式(2)作為懲罰函數(shù)可知，障礙物距離機(jī)器人越近，其產(chǎn)生的斥力就越大，進(jìn)而相應(yīng)的啟發(fā)函數(shù)值也會(huì)增大，即懲罰越嚴(yán)重.將其并入到式(1)，得到式(3):

式中:g(x)是從起點(diǎn)S到當(dāng)前節(jié)點(diǎn)x的實(shí)際代價(jià)值，h'(x)是從當(dāng)前節(jié)點(diǎn)x到目標(biāo)點(diǎn)估計(jì)的最小代價(jià)值(用與目標(biāo)點(diǎn)之間的歐式距離來衡量)，w(x)是當(dāng)前節(jié)點(diǎn)x在局部環(huán)境中所受到的斥力總和的模長(zhǎng)，α、β、θ是3個(gè)增益系數(shù).當(dāng) θ=0時(shí)，f'(x)為普通的啟發(fā)函數(shù)，即與式(1)等價(jià).

采用式(3)作為啟發(fā)函數(shù)，考慮到了機(jī)器人從傳感器得到的障礙物位置信息，可以根據(jù)局部環(huán)境信息的變化動(dòng)態(tài)地修改啟發(fā)函數(shù)，這將有利于規(guī)劃出更優(yōu)的軌跡.此外，經(jīng)過改進(jìn)的啟發(fā)函數(shù)仍然能夠滿足啟發(fā)式搜索算法的可歸納性［17］，即在一些問題的求解過程中，如果存在最短路徑，無論在什么情況之下，該搜索算法都能夠保證找到這條最短路徑.

啟發(fā)函數(shù)中的系數(shù)選擇將會(huì)影響到函數(shù)的最終結(jié)果，從實(shí)驗(yàn)的角度分析系數(shù)的選擇.選取α與β的最佳比例［18］為，β與θ最佳的比例從多個(gè)指標(biāo)(路徑長(zhǎng)度、方向轉(zhuǎn)換次數(shù)、擴(kuò)展的節(jié)點(diǎn)數(shù)和運(yùn)行時(shí)間)進(jìn)行分析.在500×500的柵格中，采用具有代表性的啟發(fā)式搜索算法——A*算法［12］作為測(cè)試算法，選擇不同的β與θ比例在500種隨機(jī)環(huán)境下進(jìn)行路徑規(guī)劃，有效的平均數(shù)據(jù)統(tǒng)計(jì)如表1所示.

表1 不同增益系數(shù)比例下規(guī)劃的數(shù)據(jù)統(tǒng)計(jì)結(jié)果Table 1 The calculation results of path planning in different gain factors

從表1的數(shù)據(jù)統(tǒng)計(jì)可以得出以下結(jié)論:1)采用同一比例的不同β與θ值規(guī)劃后的軌跡基本一致;2)合理地將障礙物信息引入到啟發(fā)函數(shù)后，可以得到更優(yōu)的路徑(當(dāng)θ=0時(shí)，A*算法采用的是普通的啟發(fā)策略);3)當(dāng)比例大于10時(shí)，各項(xiàng)數(shù)據(jù)指標(biāo)趨于穩(wěn)定;4)從多個(gè)指標(biāo)衡量，最佳的比例為(θ/β)=(1/7).同樣，采用其他啟發(fā)式搜索算法作為測(cè)試算法，其數(shù)據(jù)統(tǒng)計(jì)也能夠反應(yīng)出類似的趨勢(shì).

1.3 Basic Theta*算法及其改進(jìn)

Basic Theta*算法是一種柵格路徑規(guī)劃算法，也是A*算法的一種變種，其最大的改進(jìn)在于它不要求搜索樹節(jié)點(diǎn)的父節(jié)點(diǎn)必須是其相鄰的節(jié)點(diǎn)，因此所求解路徑的軌跡不限制在柵格的橫向與縱向，理論上允許以任意角度改變路徑的方向［13］.

在估價(jià)函數(shù)的選取上，Basic Theta*算法與A*算法是一致的，故在使用其解決路徑規(guī)劃問題時(shí)，式(3)作為其啟發(fā)函數(shù)能夠獲取更優(yōu)的路徑.該算法在搜索中設(shè)置了2個(gè)表:OPEN表和 CLOSE表.OPEN表保存了所有已擴(kuò)展而未被考察過的節(jié)點(diǎn)，CLOSE表記錄了已被考察過的節(jié)點(diǎn).

Basic Theta*算法的步驟如下［19］.

1)初始化OPEN、CLOSE表，并將起始點(diǎn)S放入到OPEN表中.

2)如果OPEN表為空，表示沒有找到路徑，退出.

3)從OPEN表中找出最佳節(jié)點(diǎn)，作為當(dāng)前節(jié)點(diǎn)x，并將其從OPEN表移到CLOSE表中.

4)判斷當(dāng)前節(jié)點(diǎn)x是否為目標(biāo)點(diǎn)，如果是，則通過節(jié)點(diǎn)x的父節(jié)點(diǎn)，一直遍歷到起點(diǎn)，找到路徑的節(jié)點(diǎn)集合，搜索結(jié)束;否則，轉(zhuǎn)至5).

5)開始擴(kuò)展當(dāng)前節(jié)點(diǎn)x，找到當(dāng)前節(jié)點(diǎn)的所有后續(xù)節(jié)點(diǎn)集合U并遍歷集合內(nèi)節(jié)點(diǎn).如果遍歷的節(jié)點(diǎn)yi不在OPEN或者CLOSE表中，將該節(jié)點(diǎn)yi加入OPEN表中，計(jì)算該節(jié)點(diǎn)yi的估計(jì)值，并記錄其父節(jié)點(diǎn)為x;否則，轉(zhuǎn)至6).

6)判斷當(dāng)前節(jié)點(diǎn)x的父節(jié)點(diǎn)x'與遍歷的節(jié)點(diǎn)yi是否相通(節(jié)點(diǎn)之間的線段沒有經(jīng)過障礙物):

①若相通，比較當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)x'的代價(jià)g(x')和OPEN表中的代價(jià)g(yi)，如果g(x')較小，則更新表中的代價(jià)，并將節(jié)點(diǎn)yi的父節(jié)點(diǎn)指向x';

②若不相通，直接比較當(dāng)前節(jié)點(diǎn)的代價(jià)g(x)和OPEN表中的代價(jià)g(yi)，如果g(x)較小，則更新表中的代價(jià)及父節(jié)點(diǎn).

7)按照估價(jià)值遞增順序，對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序，轉(zhuǎn)向2).

Basic Theta*算法能夠突破格子的限制，找到可行路徑，但該算法存在著一些缺陷，即最先找到的路徑并不能保證路徑最短.如圖5所示，最短路徑應(yīng)該是E1到B9的線段，但E1不會(huì)成為B9的父節(jié)點(diǎn)，路徑經(jīng)過了點(diǎn)C6.分析其原因在于Basic Theta*的擴(kuò)展方式［13］，即2個(gè)頂點(diǎn)之間并不會(huì)隨意形成父節(jié)點(diǎn)與子節(jié)點(diǎn)的關(guān)系.

圖5 Theta*算法規(guī)劃軌跡演示Fig.5 The path planning demo of Theta*algorithm

對(duì)路徑進(jìn)行平滑處理能夠有效地優(yōu)化路徑［20］，在經(jīng)過Basic Theta*算法搜索找到路徑后，中間經(jīng)過的點(diǎn)會(huì)大量減少，對(duì)其進(jìn)一步平滑可以在較短的時(shí)間內(nèi)完成.具體平滑步驟如下.

1)獲取Basic Theta*規(guī)劃后的路徑軌跡節(jié)點(diǎn)集合.

2)選擇集合中的起始點(diǎn)為平滑的基準(zhǔn)點(diǎn)x.

3)判斷節(jié)點(diǎn)x與節(jié)點(diǎn)z是否相通，其中，節(jié)點(diǎn)z為節(jié)點(diǎn)y的后續(xù)節(jié)點(diǎn)，節(jié)點(diǎn)y為節(jié)點(diǎn)x的后續(xù)節(jié)點(diǎn):

①若相通，去除中間節(jié)點(diǎn)y，即將節(jié)點(diǎn)x的后續(xù)節(jié)點(diǎn)修改為節(jié)點(diǎn)z，相應(yīng)地，節(jié)點(diǎn)z的父節(jié)點(diǎn)為節(jié)點(diǎn)x;

②否則，將基準(zhǔn)點(diǎn)更新為節(jié)點(diǎn)y.如此循環(huán)，直到節(jié)點(diǎn)y為目標(biāo)點(diǎn)時(shí)，循環(huán)結(jié)束，轉(zhuǎn)到4).

4)平滑完畢后，從目標(biāo)點(diǎn)回溯到起始點(diǎn)，重新組成最佳的節(jié)點(diǎn)集合.

由Basic Theta*算法與平滑步驟組成PS_Theta*算法，針對(duì)圖5中Basic Theta*算法規(guī)劃的軌跡，PS_Theta*算法能夠進(jìn)一步優(yōu)化路徑，如圖6所示.光滑度是路徑軌跡優(yōu)越性的重要指標(biāo)，光滑的軌跡能夠有效提高機(jī)器人到達(dá)目標(biāo)點(diǎn)的效率，可以盡可能地滿足非完整性約束的條件.

圖6 PS_Theta*算法規(guī)劃軌跡演示Fig.6 The path planning demo of PS_Theta*algorithm

2 仿真與結(jié)果分析

2.1 二維隨機(jī)環(huán)境下的路徑規(guī)劃問題

本文在Matlab 7.6環(huán)境下對(duì)算法進(jìn)行驗(yàn)證和比較.在二維環(huán)境下，采用本文提出的改進(jìn)啟發(fā)式搜索策略，對(duì) A*［12］、Basic Theta*［13］與 PS_Theta*算法進(jìn)行對(duì)比實(shí)驗(yàn).在柵格模型中，選擇2種規(guī)格進(jìn)行測(cè)試，分別為100×100與500×500，障礙物按不同比例隨機(jī)生成，并隨機(jī)初始化起始點(diǎn)與目標(biāo)點(diǎn)，統(tǒng)計(jì)500次仿真實(shí)驗(yàn)，平均數(shù)據(jù)如表2所示，圖7和8分別表示2種規(guī)格下3種算法規(guī)劃的平均路徑方向變化頻率曲線圖.

表2 二維隨機(jī)環(huán)境的仿真實(shí)驗(yàn)結(jié)果Table 2 The simulation experimental results in 2-D random environment

圖7 路徑方向變化頻率曲線(100×100)Fig.7 The graph of heading changes(100 ×100)

圖8 路徑方向變化頻率曲線(500×500)Fig.8 The graph of heading changes(500 ×500)

由表2的數(shù)據(jù)及圖7和8的曲線圖可以表明，使用Basic Theta*算法能夠規(guī)劃出較短的路徑，PS_Theta*算法利用較少的額外運(yùn)行時(shí)間代價(jià)使得路徑更優(yōu)，主要體現(xiàn)在2點(diǎn):1)路徑長(zhǎng)度更短;2)路徑方向變化大量降低.路徑方向變化頻率能夠體現(xiàn)路徑的光滑程度，是路徑優(yōu)越性的重要指標(biāo).

2.2 三維隨機(jī)環(huán)境下的路徑規(guī)劃問題

將采用啟發(fā)式搜索算法解決路徑規(guī)劃問題的環(huán)境規(guī)模擴(kuò)展至三維隨機(jī)環(huán)境中.在2種環(huán)境模型下采用不同啟發(fā)式搜索算法進(jìn)行路徑規(guī)劃，2種隨機(jī)的城市環(huán)境模型的規(guī)劃軌跡如圖9和10所示，從多個(gè)角度觀察普通環(huán)境模型的規(guī)劃軌跡如圖11和12所示.3種啟發(fā)式搜索算法均能夠快速地找到目標(biāo)點(diǎn)，從規(guī)劃后的對(duì)比效果可以表明，PS_Theta*算法規(guī)劃的路徑軌跡長(zhǎng)度最短.

圖9 城市環(huán)境模型規(guī)劃演示1Fig.9 Urban path 1

圖10 城市環(huán)境模型規(guī)劃演示2Fig.10 Urban path 2

圖11 普通環(huán)境模型規(guī)劃結(jié)果Fig.11 The path 1 in common environment

圖12 普通環(huán)境模型規(guī)劃結(jié)果Fig.12 The path 2 in common environment

最后，通過多次實(shí)驗(yàn)的統(tǒng)計(jì)數(shù)據(jù)對(duì)比算法的性能.在三維立方格模型中，選擇2種規(guī)格進(jìn)行測(cè)試，分別為50×50×50與100×100×100，按不同比例隨機(jī)生成障礙物，并隨機(jī)初始化起始點(diǎn)與目標(biāo)點(diǎn)的位置.統(tǒng)計(jì)500次仿真實(shí)驗(yàn)，平均數(shù)據(jù)如表3所示，圖13和14分別表示2種規(guī)格下3種算法規(guī)劃的平均路徑方向變化頻率曲線圖.

圖13 路徑方向變化頻率曲線(50×50×50)Fig.13 The graph of heading changes(50 ×50 ×50)

圖14 路徑方向變化頻率曲線(100×100×100)Fig.14 The graph of heading changes(100×100×100)

表3 三維隨機(jī)環(huán)境的仿真實(shí)驗(yàn)結(jié)果Table 3 The simulation experimental results in 3-D random environment

由表3的數(shù)據(jù)及圖13和14的曲線圖可以表明，在三維隨機(jī)復(fù)雜的環(huán)境下，3種啟發(fā)式搜索算法均能夠快速地找到路徑.相比其他2種算法，PS_Theta*算法利用較少的額外時(shí)間代價(jià)，大幅度降低了路徑方向改變的頻率，保證了軌跡的平滑性，并且能有效地縮短路徑長(zhǎng)度.相比二維環(huán)境，PS_Theta*算法的優(yōu)勢(shì)更加明顯，提高了路徑方向變化的區(qū)分度.

3 結(jié)束語

啟發(fā)式搜索是一種有序高效的搜索策略，其相對(duì)簡(jiǎn)單的時(shí)間復(fù)雜度能夠保證規(guī)劃的實(shí)時(shí)性，本文將障礙物對(duì)機(jī)器人產(chǎn)生的斥力作為懲罰函數(shù)加入到啟發(fā)函數(shù)中，合理性主要體現(xiàn)在以下3點(diǎn):1)提高啟發(fā)函數(shù)的前瞻性與可靠性;2)考慮到了障礙物對(duì)機(jī)器人的影響，能夠較好地選擇節(jié)點(diǎn)，減少擴(kuò)展的節(jié)點(diǎn)數(shù)量;3)有效地減少規(guī)劃時(shí)間，提高效率.而將Theta*算法應(yīng)用在三維隨機(jī)環(huán)境解決機(jī)器人路徑規(guī)劃問題，相比A*算法，體現(xiàn)出了其算法的優(yōu)越性，即有效縮短了路徑長(zhǎng)度.利用改進(jìn)算法PS_Theta*對(duì)路徑進(jìn)行平滑處理，能夠大幅度地降低路徑方向變化的頻率，提高軌跡的平滑性.

總之，將局部環(huán)境中的障礙物信息引入到啟發(fā)函數(shù)中，為機(jī)器人提供更加可靠的啟發(fā)信息，以提高其下一步動(dòng)作的準(zhǔn)確性，使用改進(jìn)算法大幅度降低了規(guī)劃的路徑方向變化，這在實(shí)際應(yīng)用中能夠提高機(jī)器人動(dòng)作連貫性，加快到達(dá)目的地.

［1］朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述［J］.控制與決策，2010，25(7):961-967.ZHU Daqi，YAN Mingzhong.Survey on technology of mobile robot path planning［J］.Control and Decision，2010，25(7):961-967.

［2］肖國(guó)寶，嚴(yán)宣輝.一種動(dòng)態(tài)不確定環(huán)境中機(jī)器人路徑規(guī)劃方法［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2012，21(4):92-98.XIAO Guobao，YAN Xuanhui.Path panning of mobile robot in dynamic nondeterministic environments［J］.Computer Systems and Applications，2012，21(4):92-98.

［3］張捍東，鄭睿，岑豫皖.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望［J］.系統(tǒng)仿真學(xué)報(bào)，2005，17(2):439-443.ZHANG Handong，ZHENG Rui，CEN Yuwan.Present situation and future development of mobile robot path planning technology［J］.Acta Simulata Systematica Sinica，2005，17(2):439-443.

［4］劉華軍，楊靜宇，陸建峰，等.移動(dòng)機(jī)器人運(yùn)動(dòng)規(guī)劃研究綜述［J］.中國(guó)工程科學(xué)，2006，8(1):85-94.LIU Huajun，YANG Jingyu，LU Jianfeng，et al.Research on mobile robots motion planning:a survey［J］.Engineering Science，2006，8(1):85-94.

［5］禹建麗，李曉燕，王躍明，等.一種基于神經(jīng)網(wǎng)絡(luò)的機(jī)器人路徑規(guī)劃算法［J］.洛陽工學(xué)院學(xué)報(bào)，2001，22(1):31-34.YU Jianli，LI Xiaoyan，WANG Yueming，et al.An algorithm of path planning for car-like robots based on neural network［J］.Journal of Luoyang Institute of Technology，2001，22(1):31-34.

［6］HU Yanrong，YANG S X.A knowledge based genetic algorithm for path planning of a mobile robot［C］//Proceedings of the 2004 IEEE International Conference on Robotics and Automation.New Orleans，USA，2004:4350-4355.

［7］陳洋，趙新剛，韓建達(dá).移動(dòng)機(jī)器人3維路徑規(guī)劃方法綜述［J］.機(jī)器人，2010，32(4):568-576.CHEN Yang，ZHAO Xin'gang，HAN Jianda.Review of 3D path planning methods for mobile robot［J］.Robot，2010，32(4):568-576.

［8］SATHYARAJ B M，JAIN L C，F(xiàn)INN A，et al.Multiple UAVs path planning algorithms:a comparative study［J］.Fuzzy Optimization and Decision Making，2008，7(3):257-267.

［9］WU X J，TANG J，LI Q，et al.Development of a configuration space motion planner for robot in dynamic environment［J］.Robotics and Computer-Integrated Manufacturing，2009，25(1):13-31.

［10］CARSTEN J，F(xiàn)ERGUSON D，STENTZ A.3D field D:improved path planning and replanning in three dimensions［C］//2006 IEEE/RSJ International Conference on Intelligent Robots and Systems.Beijing，China，2006:3381-3386.

［11］DOLGOV D，THRUN S，MONTEMERLO M，et al.Practical search techniques in path planning for autonomous driving［C］//Proceedings of the First International Symposium on Search Techniques in Artificial Intelligence and Robotics.Chicago，USA，2008:1-6.

［12］HART P E，NILSSON N J，RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths［J］.IEEE Transactions on Systems Science and Cybernetics，1968，4(2):100-107.

［13］NASH A，DANIEL K，KOENIG S，et al.Theta*:anyangle path planning on grids［C］//Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence.Vancouver，Canada:AAAI Press，2007:1177-1183.

［14］蔡自興，徐光祐.人工智能及其應(yīng)用［M］.3版.北京:清華大學(xué)出版社，2004.

［15］SABATTINI L，SECCHI C，F(xiàn)ANTUZZI C.Arbitrarily shaped formations of mobile robots:artificial potential fields and coordinate transformation［J］.Autonomous Robots，2011，30(4):385-397.

［16］SHENG Junwen，HE Gaoqi，GUO Weibin，et al.An improved artificial potential field algorithm for virtual human path planning［C］//Proceedings of the Entertainment for Education，and 5th International Conference on E-learning and Games.Berlin/Heidelberg，Germany:Springer-Verlag，2010:592-601.

［17］周小鏡.基于改進(jìn) A*算法的游戲地圖尋徑的研究［D］.重慶:西南大學(xué)，2011:22-23.ZHOU Xiaojing.Research of routing in the game map based on improved A*algorithm［D］.Chongqing:Southwest University，2011:22-23.

［18］De FILIPPIS L，GUGLIERI G，QUAGLIOTTI F.Path planning strategies for UAVS in 3D environments［J］.Journal of Intelligent＆ Robotic Systems，2011，65(1/2/3/4):247-264.

［19］NASH A，KOENIG S，LIKHACHEV M.Incremental Phi*:incremental any-angle path planning on grids［C］//Proceedings of the 21st International Joint Conference on Artificial Intelligence.San Francisco，USA:Morgan Kaufmann Publishers Inc.，2009:1824-1830.

［20］BOTEA A，MULLER M，SCHAEFFER J.Near optimal hierarchical path-finding［J］.Journal of Game Development，2004，1(1):7-28.