王 旭，朱其新，朱永紅

1.蘇州科技大學(xué) 電子與信息工程學(xué)院，江蘇 蘇州 215009

2.蘇州科技大學(xué) 機(jī)械工程學(xué)院，江蘇 蘇州 215009

3.江蘇省建筑智慧節(jié)能重點(diǎn)實(shí)驗(yàn)室，江蘇 蘇州 215009

4.蘇州市共融機(jī)器人技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 蘇州 215009

5.景德鎮(zhèn)陶瓷大學(xué) 機(jī)電工程學(xué)院，江西 景德鎮(zhèn) 333001

機(jī)器人起源于20 世紀(jì)，由Fryer[1]和Carrera[2]在Vaucanson 和Jaquet 構(gòu)造的類人機(jī)器人基礎(chǔ)上做的研究。在工業(yè)革命結(jié)束時(shí)，機(jī)器人技術(shù)的進(jìn)步促進(jìn)了不同科學(xué)領(lǐng)域的發(fā)展，并創(chuàng)造了大批新設(shè)備以應(yīng)用于不同領(lǐng)域之中，如建筑、軍事、航空、運(yùn)輸?shù)?。機(jī)器人是由圖1中的幾個(gè)系統(tǒng)組成的，本文主要研究其控制系統(tǒng)中的路徑規(guī)劃技術(shù)。

圖1 機(jī)器人的六大系統(tǒng)Fig.1 Six systems of robot

移動(dòng)機(jī)器人通常應(yīng)用于各種復(fù)雜的環(huán)境中，圖2展示了四種場(chǎng)景下的移動(dòng)機(jī)器人。在各個(gè)領(lǐng)域都有特定功能的機(jī)器人來為人類服務(wù)[3-4]，以完成各種任務(wù)[5]，包括探索未知的環(huán)境、搜索被困的受害者和攜帶重要材料等。在緊急和危險(xiǎn)的場(chǎng)景中，移動(dòng)機(jī)器人甚至可能是不可替代的[6]。然而，自主移動(dòng)機(jī)器人的路徑規(guī)劃問題是當(dāng)前難以解決的問題之一[3]。路徑規(guī)劃的目的是以最優(yōu)的方式生成從起點(diǎn)到目標(biāo)點(diǎn)可行的安全路徑，避免自主移動(dòng)機(jī)器人運(yùn)動(dòng)過程中可能發(fā)生的所有碰撞[7-8]。路徑規(guī)劃在靜態(tài)地圖環(huán)境中，一般在機(jī)器人進(jìn)行移動(dòng)之前就需要找到整個(gè)解決方案。與之不同的是，對(duì)于動(dòng)態(tài)以及局部已知的環(huán)境，通常需要實(shí)時(shí)規(guī)劃，并且需要更多的計(jì)劃更新時(shí)間。移動(dòng)機(jī)器人路徑規(guī)劃的主要問題一般是計(jì)算的復(fù)雜性、路徑最優(yōu)值的存在和整體適應(yīng)性[4]。在二維移動(dòng)機(jī)器人路徑規(guī)劃算法領(lǐng)域，大部分研究的目的在于找到最優(yōu)解，但是隨著生產(chǎn)技術(shù)的發(fā)展，最優(yōu)路徑已經(jīng)不能滿足需求。所以，在最優(yōu)路徑、收斂速度、平滑性、搜索速度等條件中進(jìn)行統(tǒng)籌兼顧的改進(jìn)是此領(lǐng)域內(nèi)的最大任務(wù)和難點(diǎn)，也是研究的大勢(shì)所趨的方向。

圖2 各個(gè)領(lǐng)域的移動(dòng)機(jī)器人Fig.2 Mobile robots in various fields

1 路徑規(guī)劃研究現(xiàn)狀

路徑規(guī)劃是機(jī)器人學(xué)的基本問題之一[9-10]，也是研究最多的問題。目前，移動(dòng)機(jī)器人路徑規(guī)劃領(lǐng)域的研究者們已經(jīng)開發(fā)了許多技術(shù)，是當(dāng)今研究的熱點(diǎn)[11]。早期開發(fā)的確定性規(guī)劃技術(shù)表明，即使對(duì)于簡(jiǎn)單的系統(tǒng)，它的計(jì)算要求也很高[12]。確切的路線圖方法是早期路徑規(guī)劃的主要方法，如可見性圖[13]、Voronoi圖[14]、Delaunay三角圖[15]和自適應(yīng)路線圖[16]，這些方法試圖捕捉機(jī)器人搜索空間的連接性。而諸如Dijkstra 和A*等搜索算法被用來在連通性圖中尋找最優(yōu)解，D*則是針對(duì)動(dòng)態(tài)圖的。圖搜索方法的使用涉及到工作空間的離散化，其性能在高維度上有所下降。有效的離散化可以以犧牲完整性為代價(jià)，而高分辨率的離散化在計(jì)算上是昂貴的。新型計(jì)算方法的出現(xiàn)激發(fā)了它們?cè)诼窂揭?guī)劃中的應(yīng)用。模糊邏輯控制[17-18]、神經(jīng)網(wǎng)絡(luò)[19]、遺傳算法[20-21]、蟻群優(yōu)化[22]和模擬退火[13]等方法都被應(yīng)用于機(jī)器人路徑規(guī)劃。

二十一世紀(jì)以來，隨著人工智能、傳感器、網(wǎng)絡(luò)和通信技術(shù)的快速發(fā)展，研究者們開始重視機(jī)器人的智能化[23]。在執(zhí)行任務(wù)時(shí)，機(jī)器人需要使用路徑規(guī)劃技術(shù)對(duì)環(huán)境進(jìn)行建模并定位其位置，控制運(yùn)動(dòng)，檢測(cè)障礙物并避開障礙物。從起點(diǎn)到目標(biāo)點(diǎn)的安全路徑規(guī)劃（通過檢測(cè)和避開障礙物）是移動(dòng)機(jī)器人的最基本的功能。因此，作為移動(dòng)機(jī)器人研究的重要組成部分，路徑規(guī)劃技術(shù)將直接影響移動(dòng)機(jī)器人完成任務(wù)的效率。

本文通過將路徑規(guī)劃算法劃分為全局和局部?jī)刹糠?，注重?duì)啟發(fā)式路徑規(guī)劃算法進(jìn)行梳理歸納和全面評(píng)述。對(duì)Dijkstra 算法、A*算法、RRT 算法、遺傳算法、人工勢(shì)場(chǎng)法、模擬退火算法、D*算法、蟻群算法、模糊推理法、強(qiáng)化學(xué)習(xí)法進(jìn)行了深入分析。引用了領(lǐng)域內(nèi)最新的文章，結(jié)合對(duì)各個(gè)算法的改進(jìn)策略，對(duì)改進(jìn)后的算法，在優(yōu)勢(shì)、局限性和適用場(chǎng)景三個(gè)方面進(jìn)行比較。

2 基于先驗(yàn)信息的全局路徑規(guī)劃

全局路徑規(guī)劃一般屬于離線（靜態(tài)）的規(guī)劃，移動(dòng)機(jī)器人需要事先掌握地圖所有的環(huán)境信息，綜合先驗(yàn)完全信息來進(jìn)行路徑規(guī)劃。在這種問題中，障礙物的位置一般是固定的。應(yīng)用于此類問題的算法有：Dijkstra算法、A*算法、RRT算法、遺傳算法等。

2.1 Dijkstra算法

1956 年，由Dijkstra 首次發(fā)現(xiàn)迪杰斯特拉算法[24]。Dijkstra 算法作為典型的求解最短路徑的算法，經(jīng)常被用于計(jì)算移動(dòng)機(jī)器人在運(yùn)動(dòng)過程中單個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑[25]。其主要特點(diǎn)是以源節(jié)點(diǎn)為中心向外，通過迭代來選擇下一個(gè)節(jié)點(diǎn)進(jìn)行層層擴(kuò)展，為了確保每一次迭代行進(jìn)的路程是最短，該算法每次迭代時(shí)選擇當(dāng)前節(jié)點(diǎn)最近的子節(jié)點(diǎn)作為下一個(gè)節(jié)點(diǎn)[26]。同時(shí)在每一次迭代過程中，都要對(duì)源節(jié)點(diǎn)到所有遍歷經(jīng)過的節(jié)點(diǎn)之間的最短路徑進(jìn)行更新，最終得到最短路徑。

在幾十年的發(fā)展中，Dijkstra 算法顯示出強(qiáng)悍的競(jìng)爭(zhēng)力。因?yàn)閷?shí)用性較高，該算法已經(jīng)被多數(shù)研究者應(yīng)用于實(shí)際程序中，例如谷歌地圖[27]將此算法應(yīng)用于自動(dòng)駕駛導(dǎo)航之中。張瑜等[28]將Dijkstra的算法結(jié)合到一個(gè)動(dòng)態(tài)窗口中，并對(duì)DWA中速度采樣空間進(jìn)行約束優(yōu)化，用作未知環(huán)境中的路徑規(guī)劃，解決了清洗機(jī)器人加速過大導(dǎo)致的偏移量誤差大的問題。韋榮杰等[29]深入研究了一種基于控制的移動(dòng)機(jī)器人避障路徑規(guī)劃設(shè)計(jì)系統(tǒng)，并且做到了不需要繁重的計(jì)算量和不用占用較高的內(nèi)存。Alshammrei 等[30]對(duì)Dijkstra 算法進(jìn)行了改進(jìn)，有效地解決包括障礙物在內(nèi)的環(huán)境中的最優(yōu)路徑規(guī)劃，但是路線的平滑度和連續(xù)性較一般。Durakli 等在文獻(xiàn)[31]中的研究，結(jié)構(gòu)更加簡(jiǎn)單，不需要添加任何中間節(jié)點(diǎn)，通過引入貝塞爾曲線修剪路徑，使得路徑更加平滑。此外，這種改進(jìn)算法可以在動(dòng)態(tài)環(huán)境中運(yùn)行并檢測(cè)到移動(dòng)的障礙物，實(shí)時(shí)地更新路徑。

為了進(jìn)一步提高Dijkstra算法的性能，文獻(xiàn)[32]采用Dijkstra 算法和蟻群算法混合并引入隨機(jī)節(jié)點(diǎn)選擇機(jī)制，文獻(xiàn)[33]采用遺傳算法優(yōu)化Dijkstra算法的最短路徑和投遞順序。這兩種方法分別可以使其具有更好的全局搜索能力和更短的路徑長(zhǎng)度，但同時(shí)也增加了算法的復(fù)雜度和路徑的復(fù)雜度。姜辰凱等[34]針對(duì)智能倉(cāng)儲(chǔ)中的路徑規(guī)劃問題將Dijkstra算法優(yōu)化，進(jìn)行時(shí)間窗排布，提出了一種路徑長(zhǎng)度更短，轉(zhuǎn)彎角度更小的改進(jìn)算法。此外，該算法還被廣泛用于疏散線路規(guī)劃[35]、鐵路線路及船舶航線規(guī)劃、物流調(diào)度等領(lǐng)域。改進(jìn)Dijkstra 算法的文獻(xiàn)對(duì)比如表1所示。

表1 Dijkstra算法改進(jìn)分析Table 1 Improvement analysis of Dijkstra algorithm

總的來說，Dijkstra 由于其算法結(jié)構(gòu)簡(jiǎn)單，收斂性好，所以在最優(yōu)路徑問題和疏散問題中的應(yīng)用較廣。從所引用的文獻(xiàn)中可以發(fā)現(xiàn)，因?yàn)樾枰闅v更多的節(jié)點(diǎn)，導(dǎo)致計(jì)算量龐大，算法復(fù)雜度高，還會(huì)占用更大的內(nèi)存，所以效率不高。

2.2 A*算法

A*搜索算法最早由斯坦福教授Nilsson 等[36]所發(fā)明。此算法基于Dijkstra 算法進(jìn)行了深入研究，針對(duì)單個(gè)目標(biāo)做了優(yōu)化，算法的宗旨在于優(yōu)先考慮似乎更接近目標(biāo)的路徑。A*算法與其他路徑規(guī)劃算法的最大區(qū)別在于啟發(fā)式函數(shù)的組成[37]。啟發(fā)式函數(shù)引導(dǎo)A*算法搜索最短路徑，傳統(tǒng)A*算法的啟發(fā)式函數(shù)一般使用曼哈頓距離[38]、歐幾里德距離[39]和切比雪夫[40（]對(duì)角線距離）。

Wang 等[41]提出了一種改進(jìn)A*算法的路徑規(guī)劃方法，通過對(duì)啟發(fā)式函數(shù)進(jìn)行加權(quán)來提高計(jì)算效率，縮短處理時(shí)間，有效地解決了旅行商問題中的道路成本，但還存在著路徑過長(zhǎng)等局限性。Erke 等[42]提出了一種通過全局規(guī)劃生成的準(zhǔn)則，以開發(fā)啟發(fā)式函數(shù)和變步長(zhǎng)A*算法。與現(xiàn)有技術(shù)相比，所提的改進(jìn)算法具有更好的魯棒性和穩(wěn)定性。熊旭等[43]應(yīng)用了基于A*算法生成路徑并使用貝塞爾曲線進(jìn)行平滑處理，通過解決A*算法沒有考慮車輛輪廓和缺乏速度規(guī)劃的問題，保證了車輛的穩(wěn)定性，同時(shí)也提高了A*算法在自動(dòng)駕駛車輛規(guī)劃中的適用性。鄭濤等[44]在A*算法的代價(jià)函數(shù)中加入了角度評(píng)價(jià)代價(jià)函數(shù)，并利用跳點(diǎn)搜索的特性來提高搜索速度。

為了解決傳統(tǒng)算法所存在的節(jié)點(diǎn)冗余問題，張燕等[45]介紹了路徑二次規(guī)劃的關(guān)鍵點(diǎn)選擇策略，該策略刪除了冗余的轉(zhuǎn)彎節(jié)點(diǎn)和無效節(jié)點(diǎn)。付麗霞等[46]研究了不同障礙物尺度下網(wǎng)格路徑規(guī)劃的A*算法。同時(shí)，引入了改進(jìn)的A*算法來優(yōu)化關(guān)鍵點(diǎn)并簡(jiǎn)化關(guān)鍵點(diǎn)的路徑。宋芮等[47]提出了一種改進(jìn)算法，以解決傳統(tǒng)A*算法受地圖分辨率約束的問題。Wang等[48]使用開始目標(biāo)代價(jià)函數(shù)對(duì)目標(biāo)序列進(jìn)行排序，并將改進(jìn)的A*算法和動(dòng)態(tài)窗口法相結(jié)合應(yīng)用于多目標(biāo)點(diǎn)規(guī)劃。表2 是近幾年部分改進(jìn)策略的對(duì)比分析。

表2 A*算法改進(jìn)分析Table 2 Improvement analysis of A* algorithm

可以看到A*算法作為經(jīng)典的啟發(fā)式算法，其計(jì)算效率較高，被廣泛用于函數(shù)優(yōu)化問題和設(shè)計(jì)優(yōu)化問題。同時(shí)由于其啟發(fā)式函數(shù)的魯棒性較好，在最新的研究中通常被用于和其他算法的融合，進(jìn)一步提高了算法性能。

2.3 快速隨機(jī)搜索樹算法（RRT）

快速隨機(jī)搜索樹（RRT）算法[49]是可以通過搜索可行路徑步驟在所有引用的應(yīng)用范圍上應(yīng)用于路徑規(guī)劃的幾種技術(shù)之一。RRT 算法允許通過有效探索具有凸和非凸障礙的多維搜索空間來規(guī)劃完整和非完整系統(tǒng)的路徑。其操作包括從待規(guī)劃路徑的初始位置（根節(jié)點(diǎn)）擴(kuò)展樹形數(shù)據(jù)結(jié)構(gòu)[50]，直到其一個(gè)樹枝到達(dá)目標(biāo)位置（最后一個(gè)葉節(jié)點(diǎn)）。

目前，基于RRT的算法已經(jīng)被廣泛地用于機(jī)器人路徑規(guī)劃[51]中。其中，對(duì)采樣方式的改進(jìn)是研究的熱門。李柄輝等[52]提出了一種自適應(yīng)雙向搜索改進(jìn)算法，可以很好地處理狹窄通道環(huán)境，同時(shí)保留RRT算法在其他環(huán)境中規(guī)劃路徑的能力。所提出的規(guī)劃器被證明能夠適應(yīng)各種環(huán)境，并且可以在短時(shí)間內(nèi)完成路徑規(guī)劃?？到鸸鹊萚53]提出了一種基于三角不等式的RRT-Connect 算法，利用三角不等式原理解決了RRT-Connect算法的尋優(yōu)問題。所提出的算法在相似的樣本數(shù)量和計(jì)劃時(shí)間中顯示出比RRT-Connect 算法更短的路徑。Jeong 等[54]和廖兵等[55]同樣引用了三角重新布線的思想，前者擴(kuò)大了可能的父頂點(diǎn)集，并且使算法具有更好的初始解和收斂性，后者在加快收斂速度的同時(shí)顯著降低了算法的成本。

Wang 等[56]將采樣點(diǎn)進(jìn)行聚類，隨后在每個(gè)中心生成一棵樹，最后使用強(qiáng)化學(xué)習(xí)來擴(kuò)展這些樹。Lai等[57-58]通過多個(gè)本地樹來調(diào)整全局搜索狀態(tài)。文獻(xiàn)[58]還提出了使用貝葉斯估計(jì)來調(diào)整采樣方向，來增強(qiáng)算法在復(fù)雜困難環(huán)境中的處理能力。這些改進(jìn)算法通常根據(jù)空間信息計(jì)算并選擇合適的樹擴(kuò)展方向并且具有很高的計(jì)算復(fù)雜度。此外，RRT 算法在自動(dòng)泊車，自動(dòng)駕駛以及物體跟蹤行業(yè)有著廣泛的應(yīng)用。

從表3 中不難發(fā)現(xiàn)，最近的研究已經(jīng)基本解決了RRT算法在狹窄通道中找不到解的問題，但是面對(duì)復(fù)雜環(huán)境時(shí)，其計(jì)算數(shù)據(jù)量大的局限性是有待克服的。

表3 RRT算法改進(jìn)分析Table 3 Improvement analysis of RRT algorithm

2.4 遺傳算法（GA）

遺傳算法是由John H.Holland教授在著作《自然與人工系統(tǒng)中的適應(yīng)》中提出的一種相對(duì)完整的理論和方法。此算法向達(dá)爾文的進(jìn)化論學(xué)習(xí)，通過模擬自然進(jìn)化的過程來構(gòu)建人工系統(tǒng)的模型。GA利用計(jì)算機(jī)科學(xué)和自然生物遺傳學(xué)來解決復(fù)雜的問題，主要涉及編碼、初始化種群、適應(yīng)度函數(shù)及值的計(jì)算、選擇操作、交叉操作、突變操作。圖3是遺傳算法的簡(jiǎn)單流程。

圖3 遺傳算法流程圖Fig.3 Genetic algorithm flow chart

遺傳算法具有簡(jiǎn)單、通用性強(qiáng)、魯棒性強(qiáng)，適合并行處理的特點(diǎn)。作為啟發(fā)式優(yōu)化算法的典型代表，GA 的搜索策略和優(yōu)化不依賴于問題的梯度信息。GA易于通過編程實(shí)現(xiàn)，并且該算法對(duì)優(yōu)化問題的約束很少，可以輕松地使用它來修改現(xiàn)有的元啟發(fā)式優(yōu)化算法，以實(shí)現(xiàn)更好的性能。因此，GA 因其強(qiáng)大的全局優(yōu)化能力和高效的并行性而在路徑規(guī)劃中得到廣泛的應(yīng)用[59]。

張昭君等[60]為了解決傳統(tǒng)遺傳算法隨機(jī)初始化所導(dǎo)致可行個(gè)體的概率低和過早收斂問題，對(duì)初始化種群進(jìn)行了改進(jìn)，提出了一種具有混合初始化方法的新型遺傳算法。該方法可以生成更好的初始種群同時(shí)通過刪除和反向操作來提高算法的性能。同樣在針對(duì)初始化種群的改進(jìn)中，Lee 等[61]提出一種基于有向無環(huán)圖的方法來提高算法性能；郝坤等[62]提出了基于多種群遷移的方法，將初始種群進(jìn)行了連接，使離散路徑連接到連續(xù)路徑；李凱榮等[63]提出了隨機(jī)搜索法和升序法相結(jié)合產(chǎn)生初始種群的方法來提升路徑規(guī)劃效率。而在適應(yīng)度函數(shù)的改進(jìn)方面，張錚等[64]提出一個(gè)改進(jìn)的適應(yīng)度函數(shù)，優(yōu)化了自適應(yīng)交叉變異操作，通過平衡閾值優(yōu)化其性能來應(yīng)用于動(dòng)態(tài)環(huán)境規(guī)劃；Lamin 等[65]提出了一種適合于遺傳算法的適應(yīng)度函數(shù)，通過減少其路徑中的轉(zhuǎn)彎次數(shù)以達(dá)到目標(biāo)。遺傳算子優(yōu)化也是遺傳算法的一個(gè)改進(jìn)方向。張瓊冰等[66]設(shè)計(jì)了一種新的交叉機(jī)制，該機(jī)制帶有可變長(zhǎng)度的交叉算子，成功提高了遺傳算法的收斂速度；為了處理運(yùn)動(dòng)目標(biāo)的問題，Patle 等[67]在此基礎(chǔ)上提出了基于矩陣二進(jìn)制編碼的遺傳算法（MGA），用于單機(jī)器人和多機(jī)器人系統(tǒng)的復(fù)雜環(huán)境中。在這種方法中，機(jī)器人可以很容易地跟蹤移動(dòng)障礙物和移動(dòng)目標(biāo)，并在短時(shí)間內(nèi)到達(dá)目的地；Doostie 等[68]提出一種新的自適應(yīng)遺傳算法，采用A*算法尋找中間節(jié)點(diǎn)來擬合可行曲線，最后再引入鄰域遺傳算子。對(duì)于染色體長(zhǎng)度的改進(jìn)，倪建軍等[69]提出了另一種新型遺傳算法。在他們的方法中，染色體的長(zhǎng)度被修改以獲得最佳輸出。GA方法對(duì)環(huán)境（已知和未知）做出了有效的反應(yīng)；因此，它被用于水下機(jī)器人[70]和空中機(jī)器人[71]的三維路徑規(guī)劃問題，以及仿人機(jī)器人[72]的二維路徑規(guī)劃。表4 是遺傳算法部分改進(jìn)策略的對(duì)比分析。

表4 遺傳算法改進(jìn)分析Table 4 Improvement analysis of genetic algorithm

遺傳算法雖然具有較強(qiáng)的路徑搜索能力和較高的效率，在函數(shù)優(yōu)化問題中展現(xiàn)出較強(qiáng)的競(jìng)爭(zhēng)力，但其需要具體的經(jīng)驗(yàn)，所以在面對(duì)未知環(huán)境時(shí)效果一般。

3 基于傳感器信息的局部路徑規(guī)劃

局部路徑規(guī)劃一般屬于在線（動(dòng)態(tài)）的規(guī)劃，移動(dòng)機(jī)器人的內(nèi)部傳感器必須實(shí)時(shí)收集環(huán)境地圖信息，確定地圖和障礙的分布情況，從而選擇從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑。應(yīng)用于此類問題的算法有：人工勢(shì)場(chǎng)法、模擬退火算法、D*算法、蟻群算法、模糊推理法、強(qiáng)化學(xué)習(xí)法等。

3.1 人工勢(shì)場(chǎng)法（APF）

1985 年，Khatib[73]提出了用于移動(dòng)機(jī)器人導(dǎo)航的APF方法。根據(jù)他的觀點(diǎn)，目標(biāo)和障礙物就像帶電的表面，總電勢(shì)在機(jī)器人上產(chǎn)生了假想力。如圖4所示，這個(gè)假想力將機(jī)器人吸引向目標(biāo)，并使其遠(yuǎn)離障礙物。在這里，機(jī)器人沿著負(fù)的梯度，避開障礙物，到達(dá)目標(biāo)點(diǎn)。人工勢(shì)場(chǎng)算法結(jié)構(gòu)簡(jiǎn)單，能夠滿足實(shí)時(shí)控制的要求。因此，該算法在處理動(dòng)態(tài)避障路徑規(guī)劃方面還具有顯著優(yōu)勢(shì)[74]。

圖4 人工勢(shì)場(chǎng)法原理Fig.4 Principle of artificial potential field method

朱其丹等[75]在2006 年提出了一種無局部極小值的勢(shì)場(chǎng)函數(shù)構(gòu)造，能夠針對(duì)特定環(huán)境而合理地逃逸局部極小值，從根本上解決了局部極小值問題。為了改進(jìn)對(duì)環(huán)境的高要求，2017年，Abdalla等[76]提出了一種將人工勢(shì)場(chǎng)法與模糊控制邏輯相結(jié)合的思想，放棄了具有局部最小問題的初始路徑，直到傳感器確認(rèn)不存在碰撞風(fēng)險(xiǎn)為止。張成[77]將改進(jìn)的人工勢(shì)場(chǎng)方法與混沌優(yōu)化算法相結(jié)合，解決了移動(dòng)機(jī)器人在未知復(fù)雜環(huán)境中的擺動(dòng)問題。王宏等[78]采用模型預(yù)測(cè)控制算法進(jìn)行路徑規(guī)劃，將障礙物和潛在碰撞嚴(yán)重程度的人工電位場(chǎng)添加到控制目標(biāo)中。王鵬偉等[79]提出了一種基于改進(jìn)人工勢(shì)場(chǎng)算法的避障設(shè)計(jì)。對(duì)人工勢(shì)場(chǎng)方法進(jìn)行了改進(jìn)，重建了障礙物的排斥場(chǎng)范圍，最后生成無碰撞路徑。姚慶峰等[80]將人工勢(shì)場(chǎng)方法改進(jìn)為一種黑洞勢(shì)場(chǎng)和強(qiáng)化學(xué)習(xí)相結(jié)合的方法，解決了局部穩(wěn)定點(diǎn)的問題。林澤南等[81]基于APF方法提出了一種新的排斥場(chǎng)。將全局路徑的長(zhǎng)度和平滑度作為粒子群優(yōu)化（PSO）的適應(yīng)度函數(shù)，以獲得APF中的障礙物影響范圍、引力系數(shù)和排斥系數(shù)。Duhe等[82]提出了排斥場(chǎng)的四種替代公式：校正多項(xiàng)式、切向和徑向分量、泊松勢(shì)和偽分?jǐn)?shù)勢(shì)，有效地減少了移動(dòng)機(jī)器人靠近障礙物時(shí)出現(xiàn)的振蕩。

從表5中可以發(fā)現(xiàn)，人工勢(shì)場(chǎng)法是局部路徑規(guī)劃中實(shí)用性較高的算法，在未知的環(huán)境中具有較強(qiáng)的避障能力。最近的研究通常是將人工勢(shì)場(chǎng)算法和其他算法進(jìn)行融合改進(jìn)，在解決運(yùn)動(dòng)規(guī)劃和避障問題中具有較好的魯棒性。但是在規(guī)劃時(shí)間和路徑的最優(yōu)問題方面，還需要進(jìn)一步的研究改進(jìn)。

表5 人工勢(shì)場(chǎng)法改進(jìn)分析Table 5 Improvement analysis of artificial potential field method

3.2 D＊算法

D*算法是基于A*算法的動(dòng)態(tài)化改進(jìn)，也是一種探路算法。它對(duì)路徑的未被探索的部分進(jìn)行假設(shè)，并基于這些假設(shè)找到從當(dāng)前坐標(biāo)到目標(biāo)坐標(biāo)的最短路徑。隨后機(jī)器人沿著這條路徑移動(dòng)，當(dāng)它注意到新的障礙物信息時(shí)，它會(huì)把這些信息添加到地圖上。在到達(dá)目標(biāo)坐標(biāo)之前，或在確定目標(biāo)坐標(biāo)無法到達(dá)之前，重復(fù)這一次過程。在穿越未知的地形時(shí)，往往會(huì)遇到新的障礙，因此，重新規(guī)劃的過程需要更加快速。啟發(fā)式搜索算法利用從以往問題中獲得的經(jīng)驗(yàn)，加速對(duì)現(xiàn)有問題的搜索，從而加快搜索類似問題的序列。

Stentz[83]最早在1995 年提出D*算法以用于火星探測(cè)器的動(dòng)態(tài)避障。Drake 等[84]設(shè)計(jì)一種新的路徑規(guī)劃器，旨在追求移動(dòng)目標(biāo)。此規(guī)劃器使用D*作為其初始路徑查找的基礎(chǔ)，然后從其搜索樹中獲取數(shù)據(jù)，以便在目標(biāo)移動(dòng)時(shí)快速重新規(guī)劃路徑。通過在搜索樹中存儲(chǔ)部分解路徑，以加快當(dāng)前搜索速度，而不會(huì)失去最優(yōu)性保證。但是，所有這些算法都優(yōu)化了一個(gè)目標(biāo)：最小化沿計(jì)劃路徑的邊緣成本值之和。但是在復(fù)雜未知的動(dòng)態(tài)環(huán)境中，大尺寸區(qū)域處理始終是弱點(diǎn)，特別是在基于D*的路徑規(guī)劃中存在不必要的動(dòng)態(tài)區(qū)域[85]。

在最新的研究中，許新寧等[86]通過自動(dòng)分割聚類地圖的方法，使用障礙物位置的信息來自動(dòng)計(jì)算。俞建華等[87]針對(duì)位置環(huán)境的路徑規(guī)劃問題，將D*進(jìn)行了改進(jìn)，引入Dubins 算法進(jìn)行局部路徑平滑處理。孫兵等[88]在原有成本函數(shù)的基礎(chǔ)上增加了障礙物成本項(xiàng)和轉(zhuǎn)向角成本項(xiàng)作為約束條件，從而保證了導(dǎo)航的安全。任忠強(qiáng)等[89]提出一種在多目標(biāo)增量搜索算法的基礎(chǔ)上引入了MOPBD*的次優(yōu)變體的改進(jìn)策略，實(shí)現(xiàn)了比現(xiàn)有的多目標(biāo)路徑規(guī)劃增量方法快一個(gè)數(shù)量級(jí)的優(yōu)勢(shì)。李孟澤等[90]設(shè)計(jì)了基于分散式邊緣計(jì)算的系統(tǒng)架構(gòu)，做到了可以實(shí)時(shí)更新地圖信息，改進(jìn)任務(wù)路徑來進(jìn)行重新規(guī)劃。

表6是上述文獻(xiàn)的改進(jìn)分析對(duì)比?？偟膩碚f，D*算法雖然計(jì)算量大，路徑不平滑，但是在處理動(dòng)態(tài)障礙問題下，具有較強(qiáng)的可靠性，經(jīng)常被用于未知環(huán)境的動(dòng)態(tài)規(guī)劃問題。

表6 D*算法改進(jìn)分析Table 6 Improvement analysis of D* algorithm

3.3 模擬退火算法（SA）

模擬退火算法（simulated annealing，SA）最早是由Metropolis 提出的基于蒙特卡羅（Monte Carlo）思想設(shè)計(jì)的。1983 年，Kirkpatrick 等[91]將退火思想加入到優(yōu)化領(lǐng)域，常用于在較大的解空間中搜索近似全局最優(yōu)解的優(yōu)化算法。

SA作為一種優(yōu)化技術(shù)，可以處理具有非線性，不連續(xù)性和隨機(jī)性程度的成本函數(shù)。它還可以處理強(qiáng)加給這些成本函數(shù)的任意邊界條件和約束。Tavares 等[92]提出了路徑的三種情況：折線、貝塞爾曲線、樣條插值曲線。并且在所提出的SA 算法中，每次迭代時(shí)評(píng)估每個(gè)連續(xù)參數(shù)的靈敏度，增加接受的解的數(shù)量。每個(gè)參數(shù)的敏感性與它在下一個(gè)候選項(xiàng)的定義中的概率分布相關(guān)聯(lián)。Ganeshmurthy 等[93]提出了一種將基于啟發(fā)式的方法組合到基于模擬退火算法的方法中，用于動(dòng)態(tài)機(jī)器人路徑規(guī)劃，通過組合啟發(fā)式方法對(duì)運(yùn)行時(shí)和離線路徑規(guī)劃進(jìn)行了改進(jìn)。孫琦等[94]通過啟發(fā)式遺傳算法降低模型在初始搜索路徑中的隨機(jī)性，然后結(jié)合Beam 搜索方法減少搜索所占用的空間和時(shí)間。苗輝等[95]開發(fā)了一種增強(qiáng)的SA 方法，該方法將兩個(gè)額外的數(shù)學(xué)運(yùn)算符和初始路徑選擇啟發(fā)式方法集成到標(biāo)準(zhǔn)SA 中，用于移動(dòng)機(jī)器人的動(dòng)態(tài)路徑規(guī)劃。它顯著提高了SA 的計(jì)算性能，同時(shí)提供了最佳的機(jī)器人路徑解決方案，從而使其實(shí)時(shí)和在線應(yīng)用成為可能。張琦等[96]將模擬退火（SA）和蟻群優(yōu)化（ACO）算法相結(jié)合提出一種新的路徑規(guī)劃方法SAACO，用于解決未知環(huán)境下的移動(dòng)機(jī)器人路徑規(guī)劃問題。翟龍鎮(zhèn)等[97]將模擬退火和遺傳算法結(jié)合，并且設(shè)計(jì)了自適應(yīng)因子，避免搜索過程陷入局部最優(yōu)解的同時(shí)，維持了種群的多樣性。表7是改進(jìn)模擬退火算法的分析對(duì)比。

表7 模擬退火算法改進(jìn)分析Table 7 Improvement analysis of simulated annealing algorithm

3.4 模糊推理法

Zadeh 于1965 年最早提出模糊集的概念。在之后的研究中，Cordón等[98]用模糊邏輯算法表示從狀態(tài)空間到控制空間的非線性映射。在路徑規(guī)劃中，先由模糊推理處理從傳感器檢測(cè)到的地圖和障礙物信息，其次根據(jù)定義的模糊規(guī)則來進(jìn)行模糊推理和決策。推理的結(jié)果被去模糊化以控制移動(dòng)機(jī)器人的運(yùn)動(dòng)。對(duì)于采用模糊邏輯算法的避障[99]，通常將機(jī)器人與周圍障礙物之間的感覺信息作為模糊控制器的輸入，并為機(jī)器人輸出新的移動(dòng)指令。圖5是模糊推理的流程。

圖5 模糊推理過程Fig.5 Fuzzy reasoning process

為了更好地適應(yīng)動(dòng)態(tài)環(huán)境，宋琦等[100]將改進(jìn)的蟻群算法與模糊邏輯方法整合到模糊邏輯蟻群優(yōu)化（FLACO）中，提高了求解精度，節(jié)約了運(yùn)算成本。Mirza[101]將模糊邏輯與神經(jīng)網(wǎng)絡(luò)結(jié)合，使它們?cè)趧?dòng)態(tài)環(huán)境中具有強(qiáng)大的處理和適應(yīng)能力。王寧等[102]和Lee[103]在解決水中航行器路徑規(guī)劃問題時(shí)，將人工勢(shì)場(chǎng)法和模糊邏輯結(jié)合，克服了全局路徑規(guī)劃的缺點(diǎn)，有效的避免與障礙物發(fā)生碰撞。孫冰等[104]利用粒子群優(yōu)化算法對(duì)模糊邏輯的隸屬函數(shù)值進(jìn)行優(yōu)化，解決了路徑規(guī)劃中模糊邏輯的邊界設(shè)計(jì)嚴(yán)重依賴專家經(jīng)驗(yàn)的問題。Gharajeh 等[105]提出了一種基于自適應(yīng)神經(jīng)模糊推理系統(tǒng)，使移動(dòng)機(jī)器人能夠進(jìn)行自主無碰撞，有效地找到不同場(chǎng)景下通過障礙物的無碰撞路徑。王京華等[106]提出一種空間取點(diǎn)的優(yōu)化方法，結(jié)合了Dijkstra 算法的原理。與圖搜索算法相比，該算法大大減少了規(guī)劃時(shí)間，提供了更靈活的轉(zhuǎn)彎角度。與采樣算法相比，該算法可以更好地考慮機(jī)器人的尺寸以及速度和轉(zhuǎn)彎角度之間的關(guān)系，同時(shí)估計(jì)每一步的運(yùn)動(dòng)狀態(tài)。表8是近幾年對(duì)模糊算法進(jìn)行改進(jìn)的對(duì)比。

表8 模糊算法改進(jìn)分析Table 8 Improvement analysis of fuzzy algorithm

3.5 蟻群算法（ACO）

蟻群算法（ant colony algorithm，ACO）是由意大利學(xué)者Dorigo[107]在1992年所提出。該算法是模仿螞蟻尋找食物來源的行為[108]而衍生出的元啟發(fā)式算法。蟻群算法因其并行處理、分布式計(jì)算和較強(qiáng)的魯棒性，近年來被廣泛應(yīng)用到移動(dòng)機(jī)器人路徑規(guī)劃領(lǐng)域[109]。圖6 是蟻群優(yōu)化原理的仿生示意圖。

圖6 蟻群尋找食物源Fig.6 Ant colony searching for food source

作為智能優(yōu)化算法[110]的典型，蟻群算法在路徑規(guī)劃領(lǐng)域彰顯了極強(qiáng)的競(jìng)爭(zhēng)力。Utkarsh等[111]在網(wǎng)格地圖中結(jié)合了移動(dòng)機(jī)器人的定向運(yùn)動(dòng)和矢量運(yùn)動(dòng)，提出了一種快速的蟻群算法。王麗娜等[112]提出了一種改進(jìn)的蟻群算法。通過引入Floyd 算法來生成引導(dǎo)路徑，并增加引導(dǎo)路徑上的信息素含量。通過初始信息素的差異，引導(dǎo)蟻群快速找到目標(biāo)節(jié)點(diǎn)。其次，應(yīng)用回退策略，減少因落入陷阱而死亡的螞蟻數(shù)量，提高螞蟻找到目標(biāo)節(jié)點(diǎn)的概率。羅強(qiáng)等[113]提出一種改進(jìn)的蟻群優(yōu)化算法，構(gòu)建分配不等的初始信息素和采用偽隨機(jī)狀態(tài)轉(zhuǎn)換規(guī)則選擇路徑，解決了蟻群算法局部最優(yōu)、收斂速度慢、搜索效率低的問題。Akka等[114]為了避免蟻群算法容易陷入局部最優(yōu)解的缺陷，對(duì)信息素矩陣更新方法進(jìn)行了優(yōu)化。Uriol 等[115]分析并調(diào)整了ACO 算法的參數(shù)并且證明了ACO 算法在復(fù)雜環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃的適用性。改進(jìn)蟻群算法路徑平滑度的方案也是研究的熱門。戴曉林等[116]引入A*算法的求值函數(shù)和彎曲抑制算子，提高蟻群算法的啟發(fā)式信息，加快收斂速度，增加全局路徑的平滑度。楊輝等[117]提出了一種高效的雙層蟻群優(yōu)化算法，由兩個(gè)獨(dú)立連續(xù)運(yùn)行的蟻群算法組成。首先，提出一種并行精英蟻群優(yōu)化方法[118]，在復(fù)雜地圖中生成初始無碰撞路徑，其次應(yīng)用一種稱為轉(zhuǎn)折點(diǎn)優(yōu)化算法的路徑改進(jìn)算法，在長(zhǎng)度、平滑度和安全性方面對(duì)初始路徑進(jìn)行優(yōu)化。表9是改進(jìn)蟻群算法的文獻(xiàn)分析。

表9 蟻群算法改進(jìn)分析Table 9 Improvement analysis of ant colony algorithm algorithm

3.6 強(qiáng)化學(xué)習(xí)法

隨著智能科學(xué)的發(fā)展和人工智能的蓬勃發(fā)展，人工智能路徑規(guī)劃技術(shù)迅速成為專家學(xué)者研究的重點(diǎn)，而現(xiàn)有的一些路徑規(guī)劃算法采用許多靜態(tài)策略，并且每個(gè)策略都與一個(gè)獨(dú)立的環(huán)境實(shí)例進(jìn)行長(zhǎng)時(shí)間的交互，沒有提出環(huán)境建模方法的判斷。強(qiáng)化學(xué)習(xí)因?yàn)槠錈o需建立路徑規(guī)劃問題的數(shù)學(xué)模型和環(huán)境圖的特點(diǎn)，逐漸被用于協(xié)作解決避障、路徑規(guī)劃等問題。圖7是強(qiáng)化學(xué)習(xí)的基本框架。

圖7 強(qiáng)化學(xué)習(xí)的基本框架Fig.7 Basic framework of reinforcement learning

在求解路徑規(guī)劃問題的強(qiáng)化學(xué)習(xí)算法中，Q-learning算法是一種比較常用的與環(huán)境交互的學(xué)習(xí)方法。它是一種無模型的典型的強(qiáng)化學(xué)習(xí)方法[119-120]。這種方法不需要完整的環(huán)境知識(shí)。使機(jī)器人能夠從環(huán)境中學(xué)習(xí)適當(dāng)?shù)男袨椋⒃跈C(jī)器人路徑規(guī)劃中取得了良好的效果。Q-learning通過連續(xù)估計(jì)狀態(tài)值函數(shù)和優(yōu)化Q函數(shù)獲得最優(yōu)策略。Q-learning在一定程度上不同于普通的時(shí)差方法（TD）。它采用狀態(tài)-動(dòng)作對(duì)的Q(s,a)函數(shù)進(jìn)行迭代計(jì)算。在智能體的學(xué)習(xí)過程中，需要檢查相應(yīng)行為是否合理，以確保最終結(jié)果收斂。

Bae等[121]將Q-learning和卷積神經(jīng)網(wǎng)絡(luò)（CNN）相結(jié)合，使移動(dòng)機(jī)器人可以在各種環(huán)境中靈活高效地移動(dòng)。Maw 等[122]提出了一種混合路徑規(guī)劃算法，該算法利用深度強(qiáng)化學(xué)習(xí)進(jìn)行局部規(guī)劃，使目標(biāo)能夠?qū)崟r(shí)避免碰撞。ZENG等[123]將Q-learning算法應(yīng)用于動(dòng)態(tài)環(huán)境下的移動(dòng)機(jī)器人導(dǎo)航，控制q值表大小，提高導(dǎo)航算法的速度。Low 等[124]引入部分引導(dǎo)Q-learning 的概念，初始化Q 表，加速Q(mào) 學(xué)習(xí)的收斂。Q-learning 算法也可用于求解基于網(wǎng)格圖的路徑規(guī)劃問題。2010年，Bonny等[125]提出了一種擴(kuò)展的Q-learning算法，通過引入標(biāo)志變量，加快了Q函數(shù)的收斂速度，提高了算法的效率。

在近幾年最新的研究中，Abdi 等[126]開發(fā)了一種結(jié)合計(jì)算機(jī)視覺、Q 學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)的新路徑規(guī)劃方法。Sahu等人[127]提出了一種創(chuàng)新的方法來解決移動(dòng)機(jī)器人對(duì)在已知靜態(tài)和復(fù)雜環(huán)境下的路徑規(guī)劃和同步問題，該問題解決了移動(dòng)機(jī)器人從預(yù)定的起始位置到預(yù)設(shè)的目標(biāo)位置的混合算法的設(shè)計(jì)，結(jié)合了改進(jìn)Q-learning 的優(yōu)點(diǎn)和粒子群優(yōu)化[128]的特點(diǎn)（PSO）。Kim 等[129]利用Qlearning 對(duì)探索策略進(jìn)行了調(diào)整，實(shí)現(xiàn)了實(shí)時(shí)路徑規(guī)劃。郭曉偉等[130]提出了一種改進(jìn)的Q 學(xué)習(xí)算法來解決數(shù)字孿生裝配系統(tǒng)中的移動(dòng)機(jī)器人路徑規(guī)劃。

此外，Sarsa 算法是一種基于Q 學(xué)習(xí)算法的模型無關(guān)的強(qiáng)化學(xué)習(xí)方法。在移動(dòng)機(jī)器人路徑規(guī)劃領(lǐng)域，Sarsa算法也可以與其他方法相結(jié)合。Asghari[131]等將Sarsa算法與遺傳算法（GA）相結(jié)合來進(jìn)行科學(xué)的調(diào)度分配。

表10 是強(qiáng)化學(xué)習(xí)算法改進(jìn)策略的分析對(duì)比，作為智能優(yōu)化算法的代表，強(qiáng)化學(xué)習(xí)算法體現(xiàn)了較強(qiáng)的實(shí)用性和適應(yīng)性。對(duì)強(qiáng)化學(xué)習(xí)算法的改進(jìn)可以在很多方向，總的來說，強(qiáng)化學(xué)習(xí)具有收斂快、時(shí)間短、路徑優(yōu)等優(yōu)點(diǎn)，仍存在計(jì)算復(fù)雜的局限性。表11 是上述所有算法的對(duì)比。

表10 強(qiáng)化學(xué)習(xí)法改進(jìn)分析Table 10 Improvement analysis of reinforcement learning

表11 所有算法的對(duì)比Table 11 Comparison of all algorithms

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

4.1 總結(jié)

本文將路徑規(guī)劃算法簡(jiǎn)單地分為兩大類——全局和局部，綜述了移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的研究進(jìn)展。此分類沒有明確的界限，很多算法對(duì)于兩種路徑規(guī)劃都適用。為了獲得最優(yōu)路徑，針對(duì)不同的需求選擇不同的路徑規(guī)劃算法尤為重要。文章針對(duì)不同算法進(jìn)行了討論和研究。其中，Dijkstra算法結(jié)構(gòu)簡(jiǎn)單，但需要遍歷更多的節(jié)點(diǎn)，因此效率不高。A*算法的關(guān)鍵是建立一個(gè)評(píng)估函數(shù)，以確保最短路徑搜索始終沿著目標(biāo)方向，這比Dijkstra算法的效率更高。適用于求解靜態(tài)環(huán)境下的最短路徑。RRT 算法適用于高維空間和復(fù)雜約束條件下的路徑規(guī)劃，路徑生成的可行性可以滿足要求。但是由于其隨機(jī)采樣的特性，往往規(guī)劃時(shí)間較長(zhǎng)。GA 因其在合適的參數(shù)下具有較強(qiáng)的路徑搜索能力和較高的效率而被廣泛應(yīng)用，但參數(shù)的選擇主要取決于經(jīng)驗(yàn)，這對(duì)求解結(jié)果有很大影響。好的路徑規(guī)劃技術(shù)不僅可以節(jié)省大量時(shí)間，還可以減少人力和生產(chǎn)資源的投入。人工勢(shì)場(chǎng)算法（APF）結(jié)構(gòu)簡(jiǎn)單，能夠滿足實(shí)時(shí)控制的要求。因此，該算法在處理動(dòng)態(tài)避障路徑規(guī)劃方面還具有顯著優(yōu)勢(shì)。D*算法與A*相反，A*算法從起點(diǎn)到目標(biāo)點(diǎn)進(jìn)行搜索，而D*是從目標(biāo)點(diǎn)向起點(diǎn)進(jìn)行搜索進(jìn)行反向傳播，反向搜索。模擬退火算法（SA）作為一種優(yōu)化技術(shù)，可以處理具有非線性、不連續(xù)性和隨機(jī)性程度的成本函數(shù)。常用于在較大的解空間中搜索近似全局最優(yōu)解的優(yōu)化算法。模糊控制算法對(duì)于不確定性、隨機(jī)性比較強(qiáng)的環(huán)境處理能力非常出眾。能夠適應(yīng)多障礙復(fù)雜的環(huán)境，且可以安全避障，避障路徑較為平滑。但是其對(duì)模糊控制器的專家經(jīng)驗(yàn)要求較高。蟻群算法（ACO）具有并行處理、分布式計(jì)算和較強(qiáng)的魯棒性，但是容易陷入局部最優(yōu)，并且收斂速度慢和面對(duì)復(fù)雜環(huán)境搜索效率低。而強(qiáng)化學(xué)習(xí)算法的優(yōu)勢(shì)在于不需要完整的環(huán)境信息，能夠讓機(jī)器人從環(huán)境中學(xué)習(xí)適當(dāng)?shù)男袨?。但是一般來說，其計(jì)算復(fù)雜度較高，訓(xùn)練時(shí)間較長(zhǎng)。

此外，與靜態(tài)環(huán)境相比，基于動(dòng)態(tài)環(huán)境發(fā)表的研究論文很少。而在動(dòng)態(tài)環(huán)境中，針對(duì)移動(dòng)目標(biāo)問題的機(jī)器人路徑規(guī)劃研究較少，針對(duì)移動(dòng)障礙問題的機(jī)器人路徑規(guī)劃研究較少。到目前為止，大多數(shù)論文只展示了模擬分析，關(guān)于實(shí)時(shí)應(yīng)用的論文要少得多。與單一移動(dòng)機(jī)器人系統(tǒng)相比，關(guān)于多個(gè)移動(dòng)機(jī)器人系統(tǒng)導(dǎo)航的論文較少。與獨(dú)立算法相比，關(guān)于混合算法的論文要少得多。

隨著生產(chǎn)力的發(fā)展，路徑規(guī)劃技術(shù)也會(huì)逐漸變得高效和智能，在各個(gè)領(lǐng)域得到應(yīng)用，與人們的生活息息相關(guān)。

4.2 發(fā)展趨勢(shì)

隨著計(jì)算機(jī)、傳感器技術(shù)飛速發(fā)展，路徑規(guī)劃技術(shù)日新月異。在具體的路徑規(guī)劃算法中，都各自存在著優(yōu)勢(shì)和局限性。在今后的研究中，還需不斷地跟進(jìn)這些理論和實(shí)踐。根據(jù)現(xiàn)在的發(fā)展?fàn)顩r，未來還可以在以下幾個(gè)方面進(jìn)行關(guān)注：

（1）新的混合方法

應(yīng)用新開發(fā)的混合算法就是將路徑規(guī)劃的不同算法取長(zhǎng)補(bǔ)短，進(jìn)行有效結(jié)合。將路徑規(guī)劃的算法進(jìn)行合理的結(jié)合能做到提高效率。很多方法如強(qiáng)化學(xué)習(xí)法[132]和模糊推理法[133]已經(jīng)被應(yīng)用到路徑規(guī)劃問題中。例如人工勢(shì)場(chǎng)法和強(qiáng)化學(xué)習(xí)法的混合[134]可以有效地避免碰撞，使機(jī)器人快速、安全地到達(dá)目標(biāo)點(diǎn)。將模糊算法和Dijkstra 算法混合[106]，可以再找到最優(yōu)且平滑的路徑。類似的這些混合式算法具有很大的發(fā)展前景。

（2）基礎(chǔ)算法的改進(jìn)

在現(xiàn)實(shí)場(chǎng)景中，路徑規(guī)劃過程都會(huì)面對(duì)許多挑戰(zhàn)，尤其是例如收斂慢、計(jì)算量大的局限性，從而導(dǎo)致路徑質(zhì)量差、路徑振蕩等問題。而群體優(yōu)化、蟻群優(yōu)化、退火算法等受自然啟發(fā)的方法可以為路徑規(guī)劃注入智能。需要新的仿真方法來集成動(dòng)態(tài)環(huán)境中的機(jī)器人行為。此外，在機(jī)器人系統(tǒng)中，應(yīng)該研究具有單位負(fù)載可達(dá)性約束的路徑規(guī)劃方法。因此在具體思想上進(jìn)行改進(jìn)，可以有效地提升算法的效率，解決路徑規(guī)劃中的問題。

（3）復(fù)雜環(huán)境的路徑規(guī)劃

移動(dòng)機(jī)器人路徑規(guī)劃大多數(shù)解決了地面二維環(huán)境下智能機(jī)器人的路徑規(guī)劃研究，例如掃地機(jī)器人、服務(wù)機(jī)器人、安防巡檢機(jī)器人等；而面向水下[135]和空中機(jī)器人的三維路徑規(guī)劃研究就相對(duì)較少。例如在水下機(jī)器人領(lǐng)域，許多特定的算法被提出用來解決水下環(huán)境的路徑導(dǎo)航規(guī)劃[136-137]，相比于二維模型更加復(fù)雜，需要考慮的影響因素也隨之增加。

隨著移動(dòng)機(jī)器人技術(shù)的發(fā)展，路徑規(guī)劃的研究也將逐漸深入到復(fù)雜高維的地形環(huán)境中。此時(shí)就需要新的決策模型，機(jī)器人將在復(fù)雜環(huán)境中發(fā)揮至關(guān)重要的作用，需要新的方法來支持關(guān)于如何在復(fù)雜地圖系統(tǒng)中規(guī)劃和優(yōu)化路徑的決策。高維和復(fù)雜環(huán)境中移動(dòng)機(jī)器人的路徑規(guī)劃是未來的一條必不可少的研究方向。

（4）多機(jī)器人路徑規(guī)劃

需要新的方法來進(jìn)行多機(jī)器人路徑規(guī)劃，因?yàn)橐苿?dòng)機(jī)器人正在進(jìn)入新的環(huán)境并提供更多的服務(wù)。需要包括動(dòng)態(tài)環(huán)境的不確定性（如交通、變化的行進(jìn)路徑和距離、區(qū)域內(nèi)的變化的服務(wù)點(diǎn)和不同的服務(wù)活動(dòng)）的方法來確定多機(jī)器人的協(xié)同。此外，需要找到多機(jī)器人的最佳比率的方法。仿真建模結(jié)合大數(shù)據(jù)、機(jī)器學(xué)習(xí)和預(yù)測(cè)分析可以支持這一點(diǎn)。此外，排隊(duì)、流動(dòng)和交通理論可以幫助分析整體避障，作為評(píng)估性能改善或降低的一個(gè)因素。在多機(jī)器人領(lǐng)域，多無人機(jī)編隊(duì)路徑規(guī)劃[138]也是研究的熱門方向，該研究不僅需要考慮多機(jī)器人，更需要考慮三維環(huán)境的避障問題。也是今后研究的重難點(diǎn)。