(西安工業(yè)大學(xué) 電子信息工程學(xué)院，西安 710021)

0 引言

路徑規(guī)劃是機器人研究的核心內(nèi)容之一，近年來在很多領(lǐng)域都具有廣泛的應(yīng)用，如室內(nèi)服務(wù)機器人的自主運動[1]；無人機的避障突防飛行[2]；物流管理中的車輛問題[3]及類似的資源管理、資源配置問題。機器人的路徑規(guī)劃按照“感知-建模-規(guī)劃-執(zhí)行”的過程依次進行。首先機器人用自身攜帶的傳感器感知環(huán)境，對環(huán)境形成兩類信息，一類是靜態(tài)的長期信息反映環(huán)境中靜態(tài)障礙物的分布，另一類是動態(tài)的短期信息反映環(huán)境中動態(tài)障礙物的分布。然后選擇合適的建模方法對整個工作空間建立一個便于計算機進行路徑規(guī)劃的環(huán)境模型，即將實際的物理空間抽象成算法能夠處理的抽象空間[4]。接下來根據(jù)已有的長期信息和在運動過程中感知到的動態(tài)障礙物，依據(jù)最低耗損原則規(guī)劃出最優(yōu)化路線，使預(yù)定的性能函數(shù)獲得最優(yōu)值。最后執(zhí)行系統(tǒng)執(zhí)行該條線路，使得機器人無碰撞的安全到達目標(biāo)點[5-9]。

本文重點對全局路徑規(guī)劃和局部路徑規(guī)劃進行了總結(jié)與評價，全局路徑規(guī)劃注重尋求最優(yōu)解，局部路徑規(guī)劃注重避障，同時介紹了基于仿生學(xué)的算法，最后對移動機器人路徑規(guī)劃的未來發(fā)展趨勢進行了展望。

1 全局路徑規(guī)劃方法

1.1 柵格法

柵格法將工作空間解耦為多個簡單的區(qū)域，建立一個便于計算機進行路徑規(guī)劃的環(huán)境模型，即將實際的物理空間抽象成算法能夠處理的抽象空間，實現(xiàn)相互間的映射。每個柵格點或者在自由空間中，用“0”表示，或者在障礙物空間中，用“1”表示，通過搜索柵格圖找到一條從起始柵格到目標(biāo)柵格的最短路徑[10-12]。若柵格較小，環(huán)境信息將會非常清晰，但會需要存儲較多的信息，規(guī)劃速度降低，實時性得不到保證；若柵格較大，信息存儲量將會少，規(guī)劃速度加快，但環(huán)境信息劃分會變得模糊，不利于有效路徑的規(guī)劃，所以需要在地圖網(wǎng)格分辨率與路徑規(guī)劃實時性上尋求平衡。

柵格法是公認(rèn)的最成熟的算法，也是安全系數(shù)最高的算法，直觀明了，常與其他方法集成使用，但方法受制于傳感器，消耗過多運算資源。鄭秀敏[13]等人采用柵格法表示環(huán)境，局部路徑規(guī)劃基于模擬退火法，用模擬退火法擺脫局部極小值，達到全局最優(yōu)，同時也對模擬退火法進行了改進；于紅斌[14]等人在柵格法的基礎(chǔ)上，在結(jié)點中加入記憶力，修改兩個結(jié)點之間的關(guān)聯(lián)程度，形成正反饋機制，最終得到一條最優(yōu)路徑，該算法在靜態(tài)路徑規(guī)劃中切實可行，并且搜索效率高于遺傳算法，但參數(shù)是依據(jù)經(jīng)驗值確定的，普遍性不高；朱磊[15]等人針對發(fā)生礦難的井下環(huán)境，采用柵格法建模，改進的負(fù)反饋遺傳算法規(guī)劃全局路徑，并以全局規(guī)劃的結(jié)果為基礎(chǔ)，設(shè)計了基于自由柵格和障礙柵格的相互轉(zhuǎn)換的局部避障方法，該方法具有較強魯棒性；王曙光[16]等人提出實時柵格法將其應(yīng)用于多機器人協(xié)作建立空間地圖，通過機器人的編隊在探索環(huán)境中直接完成環(huán)境建模，不再局限于單個機器人各自劃分一個小區(qū)域，柵格也不再局限于正方形，實時柵格法檢測障礙計算簡單，不需要進行局部地圖的拼接，但在實際情況下，由于地形起伏的環(huán)境因素，隊形會出現(xiàn)偏差，造成柵格位置的誤差，影響檢測結(jié)果。

1.2 A*算法

A*算法是一種在工作空間中求解最短路徑搜索方法，它將啟發(fā)式函數(shù)BFS和常規(guī)方法Dijkstra算法結(jié)合在一起[17-20]，在進行啟發(fā)式搜索提高效率的同時，可以保證找到一條最優(yōu)路徑。代價函數(shù)定義為f(m)=g(m)+h(m)。其中f(m)是從初始點S經(jīng)由中間點M到目標(biāo)點E的代價估計，g(m)是初始點S到達中間點M的實際距離，h(m)是是中間點M到目標(biāo)點E的估計距離，它是一種啟發(fā)式函數(shù)，評估任意結(jié)點到目標(biāo)點的代價，快速地導(dǎo)向目標(biāo)結(jié)點，省略大量無效的搜索節(jié)點。

A*算法能快速實現(xiàn)移動機器人的無碰最短路徑規(guī)劃，主要的計算量在于對節(jié)點狀態(tài)的檢測和最小代價的選擇[21]。Dan[22]等將A*算法用于對隨機語法進行解析，通過與各種算法的比較，可以看出A*算法大大減少了找到解析所需的時間，并且能給出最佳的、準(zhǔn)確的解析；Kagan[23]等將A*算法用于在離散空間中在線搜尋特定信息，啟發(fā)函數(shù)定義為搜索空間上信息距離，該算法具有較強的收斂性，獲得的結(jié)果可以用于彌補信息理論搜索過程的不足；由于算法本身原理的限制，規(guī)劃出的路徑折線多、轉(zhuǎn)折次數(shù)多、累積轉(zhuǎn)折角度大，王紅衛(wèi)[24]等人提出平滑A*算法，取出相鄰的3個節(jié)點，當(dāng)某一節(jié)點前后節(jié)點連線上無障礙物時，刪除中間節(jié)點，該算法優(yōu)化了路徑，減少了路徑長度，降低了轉(zhuǎn)折次數(shù)；A*算法規(guī)劃出的路徑曲率非連續(xù)，導(dǎo)致在轉(zhuǎn)折點處運動參量發(fā)生跳變，王殿君[25]在平滑A*算法基礎(chǔ)上加入了在拐點處調(diào)整自身位姿，更好實現(xiàn)自主定位功能，但兩者需要在A*算法規(guī)劃好的基礎(chǔ)上平滑路徑，增加了運行時間，實時性不高，尋路效率不高；規(guī)劃的場景較大時，往往由于龐大的計算量導(dǎo)致運行時間過長、內(nèi)存占用嚴(yán)重，趙曉[26]等人在A*算法的基礎(chǔ)上，結(jié)合跳點搜索算法將添加到OpenList和ClosedList的不必要節(jié)點用跳點代替，減少了算法的覆蓋面，大大加快了尋路速度，但規(guī)劃出來的路徑轉(zhuǎn)折點較多，不利于機器人直接執(zhí)行；王小紅[27]等人提出對鄰域進行擴展，將8鄰域擴展到24鄰域，使得機器人可以小角度行進，從而軌跡更加平滑，并且將啟發(fā)式函數(shù)不再單一的選擇曼哈頓距或者歐幾里得距離，將其進行融合以適應(yīng)具體環(huán)境，使得A*算法更加靈活，規(guī)劃出來的轉(zhuǎn)折點少，同時全局路徑更加平滑。

2 局部路徑規(guī)劃算法

2.1 人工勢場法

人工勢場是抽象的人造受力場，其中目標(biāo)點產(chǎn)生“引力”，障礙物產(chǎn)生“斥力”，最后通過求合力來控制移動機器人的運動[28-30]。人工勢場法主要用于局部環(huán)境中躲避動態(tài)避障物，此時的引力極是局部環(huán)境中的中間目標(biāo)，斥力極則是局部環(huán)境中的障礙物。該方法結(jié)構(gòu)簡單，便于底層的實時控制。但其存在局部極值點，易在狹窄的通道中擺動，當(dāng)臨近目標(biāo)點的地方存在障礙物時不能發(fā)現(xiàn)路徑等問題[31-32]。

Borenstein[33]等人提出了基于向量場直方圖方法的VFH算法，對人工勢場方法進行了改進，機器人可在多障礙物環(huán)境或狹窄通道中找出局部較優(yōu)的路徑，且運行軌跡合理。但是，此方法將機器人理想化為一個點，沒有考慮機器人的尺寸、動力學(xué)和運動學(xué)特性，這使得機器人很難按照VFH算法計算出來的預(yù)定軌線移動；Iwan[34]等人充分考慮機器人的尺寸、軌跡和運動學(xué)性能，提出了改進的VFH+方法，但只是一種純局部避障算法，容易在多個障礙物中迷失方向；之后他們加入了接下來幾個周期機器人的位置和周圍環(huán)境的關(guān)系的預(yù)測，在幾個可能方向角之間進行優(yōu)化選擇，提出了VFH*[35]算法，使得機器人能夠選擇一個局部較優(yōu)的方向，但本質(zhì)上仍然是局部避障算法，沒有考慮到周圍障礙物的速度，選擇出的運動方向有可能不是最優(yōu)的，章蘇書[36]提出可VFH#算法，考慮了障礙物的速度，并預(yù)測了機器人沿某方向前進會遇到的環(huán)境，使得機器人能找到最優(yōu)最安全的運動方向；S.S.Ge[37]等首次提出人工勢場法在臨近目標(biāo)點存在障礙物不可達問題，然后將機器人與目標(biāo)點的距離考慮到斥勢場函數(shù)中，保證目標(biāo)點為全局最小點；唐志榮[38]等人將道路邊界勢能場考慮在內(nèi)引入道路邊界斥力場模型，利用橢圓化距離代替?zhèn)鹘y(tǒng)斥力勢場中的實際距離，從而在較小車道空間獲得汽車避障局部路徑，保證汽車在避障過程中具有良好的穩(wěn)定性和舒適性。

2.2 動態(tài)窗口法DWA

動態(tài)窗口法DWA是在曲率速度法[39]的基礎(chǔ)上提出的，將機器人的位置控制轉(zhuǎn)化為速度控制，將避障問題描述為速度空間帶約束的優(yōu)化問題。該算法在速度空間中采樣多組速度，將有限的速度和加速度的運動約束考慮到動態(tài)窗的設(shè)計中，模擬這些速度在一定時間內(nèi)的運動軌跡，再通過一個評價函數(shù)對這些軌跡打分，選擇出最優(yōu)的速度。充分考慮了機器人的物理限制、環(huán)境約束以及當(dāng)前速度等因素，得到的路徑安全可靠，適用于局部路徑規(guī)劃[40-43]。

Piyapat[44]等提出field Dynamic Window Approach,將動態(tài)窗口法中只涉及了機器人軌跡上的障礙物改變?yōu)椴粌H考慮了軌跡上的障礙物，也考慮了臨近軌跡的障礙物，以避免機器人可能會撞到一些靠近軌跡但不在軌跡上的障礙物。該算法具有較好的魯棒性，經(jīng)驗證在涉及近軌跡障礙物時可以更安全地行進；Pablo[45]等提出了一種稱為共享控制動態(tài)窗口方法的共享控制方法。它通過控制界面接受用戶命令，提供最合適的、動態(tài)可行的軌跡，并提供導(dǎo)航輔助，在非結(jié)構(gòu)化環(huán)境中以及動態(tài)約束發(fā)揮重要作用的其他場景中駕駛車輛；程傳奇等[46]將動態(tài)窗口法和改進A*算法進行融合，構(gòu)造一種顧及全局最優(yōu)路徑的評價函數(shù)，可實時避障，路徑更加平滑，曲率變化的連續(xù)性及可輸出的運動控制參數(shù)更符合機器人的動力學(xué)控制；在障礙物較稠密區(qū)域，動態(tài)窗口法在穿越稠密障礙物時，存在繞行于稠密障礙物區(qū)域外側(cè)，造成總長度增加且速度和安全性不能兼顧的問題。

3 智能方法

3.1 遺傳算法

遺傳算法是一種模擬自然界進化過程，搜索最優(yōu)解的算法，在進化過程中進行遺傳操作，如選擇、交叉、變異[47-50]。選擇的目的是把優(yōu)化的個體直接遺傳到下一代，使適應(yīng)度值較好的路徑具有較大的生存機會；交叉的目的是通過配對交叉產(chǎn)生新的路徑個體，在遇到障礙物時多一種選擇；變異有增加一個點，減少一個點，移動一個點以及替換一段路徑，具有不確定性。

遺傳算法可以同時處理多個個體，具有內(nèi)在的隱并行性，且具有較高的自組織性、自適應(yīng)性和自學(xué)習(xí)性。但是針對復(fù)雜環(huán)境設(shè)計相應(yīng)的遺傳算子存在著較大困難，經(jīng)常會產(chǎn)生非法個體，Vincent[51]等在自主無人機上將遺傳算法與粒子群算法相融合去處理在三維環(huán)境下復(fù)雜問題，產(chǎn)生的路徑由線段，圓弧和垂直螺旋組成，通過使用“單程序，多數(shù)據(jù)”并行編程縮短執(zhí)行時間，并在現(xiàn)成多核CPU上實現(xiàn)了實時性能，可以實現(xiàn)無人機的實時路徑規(guī)劃，此外遺傳算法可以為粒子群算法產(chǎn)生出色的軌跡；陳剛等[52]設(shè)計了有效的路徑遺傳因子，提出了用翻越障礙物的能力替代穿越障礙物的長度的新適應(yīng)度計算方法，且充分運用背景知識進行啟發(fā)式變異，避免變異的盲目性，該算法有很強的魯棒性，適合于復(fù)雜環(huán)境下的路徑規(guī)劃；在三維空間中隨著維數(shù)的增加，傳統(tǒng)避障方法會出現(xiàn)計算量的加劇增加和實時性的大幅度降低問題，陳志軍等[53]采用基于模糊神經(jīng)網(wǎng)絡(luò)和遺傳算法建立機器人三維路徑規(guī)劃，模糊神經(jīng)網(wǎng)絡(luò)建立了三維路徑的五層結(jié)構(gòu)，遺傳算法來優(yōu)化模糊神經(jīng)網(wǎng)絡(luò)，優(yōu)化后的網(wǎng)絡(luò)輸出結(jié)果和期望輸出結(jié)果高度吻合，具有較高的適應(yīng)性。

3.2 蟻群算法

蟻群算法就是模擬蟻群覓食行為的優(yōu)化算法[54-57]。螞蟻在覓食過程中會在所經(jīng)過的路徑上留下信息素，并且在覓食過程中感知信息素的存在以及強度以此指導(dǎo)運動方向，某一路徑越短，選擇該路徑的螞蟻數(shù)量就越多，留下的信息素越強，被選擇的機率也就越高，因此大量螞蟻組成的集體覓食行為便表現(xiàn)出一種信息正反饋現(xiàn)象。

該算法具有分布式并行計算能力，可在全局的多點同時進行解的搜索，在求解非線性問題方面，具有高度的魯棒性。但是目前對于有約束的函數(shù)優(yōu)化問題，缺乏數(shù)學(xué)理論基礎(chǔ)，尚無相應(yīng)算法。Vahid[58]等將蟻群算法和模擬退火算法的融合，解決了無等待流水車間調(diào)度問題，改進了信息素路徑更新的方式，檢查搜索空間的一些不同區(qū)域并選擇最佳解決方案，蟻群算法中局部搜索的新方法對于解決無等待流水車間問題是有效的；王輝[59]等引入新的距離啟發(fā)函數(shù)因子于狀態(tài)轉(zhuǎn)移概率，并修改信息素更新規(guī)則局部更新和全局更新相結(jié)合，將此改進蟻群算法應(yīng)用于泊車系統(tǒng)自動導(dǎo)引車路徑規(guī)劃，規(guī)劃出的路徑長度短，收斂迭代次數(shù)少，具有較強的全局搜索能力和較好的收斂性能；在復(fù)雜環(huán)境下蟻群算法表現(xiàn)出收斂速度慢，容易陷入局部最優(yōu)，李龍澍等[60]通過優(yōu)化初始信息素的分布解決算法初期的盲目性，在信息素的揮發(fā)中注意保留優(yōu)秀路徑的優(yōu)勢同時避免過多影響后續(xù)螞蟻的選擇，算法陷入局部最優(yōu)，并通過優(yōu)化概率轉(zhuǎn)移規(guī)則來增加解的多樣性，強化全局搜索能力；彭凡彬[61]等在群機器人路徑搜索時，產(chǎn)生個別螞蟻開辟的新道路，給出算法跳出局部最優(yōu)解的一種可能，明顯改變了傳統(tǒng)算法的局部性調(diào)整，提高了傳統(tǒng)蟻群的搜索能力，規(guī)劃出的路徑更加圓滑，方便機器人的快速行走。

3.3 粒子群算法

粒子群算法是模擬鳥群飛行的仿生算法[62-66]。鳥群在隨機搜尋食物時，盡快找到食物的有效方法就是搜尋目前離食物最近的同伴位置，同伴位置在粒子群系統(tǒng)中為備選解，被稱為一個粒子，每個粒子根據(jù)自身的經(jīng)驗和相鄰粒子群的最佳經(jīng)驗向更好的位置飛行，不斷迭代尋找全局最優(yōu)解。

該算法為群體智能優(yōu)化算法，對目標(biāo)函數(shù)的性質(zhì)沒有要求，易于實現(xiàn)，魯棒性好，在各類多維連續(xù)空間優(yōu)化問題均取得良好效果，但存在過早收斂的問題，搜索性能對參數(shù)的依賴性過也過大，易于陷入局部極小值。Yilmaz[67]等采用改進粒子群優(yōu)化算法來解決混合模型雙側(cè)裝配線平衡問題，提出了組合選擇機制和解碼的新過程，增強了算法在解空間中搜索不同點的有效性；翁理國等[68]針對算法陷入局部最優(yōu)時較差的搜索能力和較差的收斂速度，提出了一種改進型多目標(biāo)粒子群算法，該算法引入環(huán)境選擇和配對選擇策略于適應(yīng)度值計算方法，根據(jù)此來選擇種群的個體歷史最優(yōu)值位置和全局歷史最優(yōu)值位置，采用自適應(yīng)原理改變對速度權(quán)重的計算方法，以此來平衡算法的全局搜索能力與局部搜索能力，使種群粒子快速地收斂于帕累托最優(yōu)邊界。王學(xué)武[69]在離散粒子群算法中加入萊維飛行，增加種群多樣性，很好地解決粒子群算法早熟的缺點，提高算法的尋優(yōu)能力，優(yōu)化效果穩(wěn)定。

4 展望

4.1 多機器人協(xié)同

多機器人協(xié)同是機器人的一個必然發(fā)展趨勢，不僅可以發(fā)揮個體功能，而且可以根據(jù)環(huán)境和任務(wù)的變化靈活、高效、快捷的組織多個機器人協(xié)同完成任務(wù)。在路徑規(guī)劃中對于未知區(qū)域地圖的建立，可以讓多個機器人并行的完成不同的子任務(wù)，成員之間相互交換信息，更有效和更精確地進行定位，且若單個機器人的定位錯誤時，不會對全局任務(wù)產(chǎn)生很大的影響，群體化智能使得系統(tǒng)的容錯能力更強，可靠性更高，目前研究的熱點是在火災(zāi)、地震、礦難、巡檢等復(fù)雜環(huán)境中，多機器人協(xié)同搜索。

4.2 空中機器人與水下機器人研究

移動機器人現(xiàn)如今大多是針對地面，如掃地機器人、足球機器人，針對空中和水下機器人則比較少。空中機器人在搜尋目標(biāo)、航拍攝影、農(nóng)業(yè)植保方面，水下機器人在探測海底資源，搜救被困人員、維護水下管線方面都有很大的發(fā)展空間，所以這將是未來的一個熱點及難點。所面臨的外部環(huán)境非常惡劣，且很難利用現(xiàn)有的傳感器獲知環(huán)境信息，不確定性更大。因此，路徑規(guī)劃與避障更加困難和迫切。

5 結(jié)論

機器人路徑規(guī)劃是機器人應(yīng)用中的一項重要技術(shù)，采用良好的機器人路徑規(guī)劃技術(shù)可以節(jié)省機器人作業(yè)時間，同時節(jié)約人力資源，減少資金投入，為機器人在多個行業(yè)的應(yīng)用奠定良好的基礎(chǔ)。將全局路徑規(guī)劃和局部路徑規(guī)劃相結(jié)合，可以在注重全局的情況下，提高機器人路徑規(guī)劃的避障精度，加快規(guī)劃速度，滿足實際應(yīng)用的需要。同時多機器人協(xié)同、空中機器人與水下機器人的研究也將是研究的熱點及難點問題。