移動(dòng)機(jī)器人路徑規(guī)劃算法綜述*

張晶 蔡志全 韓永成 牛彩霞

（唐山工業(yè)職業(yè)技術(shù)學(xué)院）

在智能化時(shí)代環(huán)境下，人工智能技術(shù)開始得到關(guān)注，而且在移動(dòng)機(jī)器人這一領(lǐng)域也展開深入研究，將不同學(xué)科技術(shù)加以整合，應(yīng)用在各個(gè)行業(yè)領(lǐng)域。機(jī)器人本質(zhì)上屬于新工具，不僅為行業(yè)發(fā)展提供了動(dòng)力，還極大地增加了人們生活的便捷性，減輕工作與勞動(dòng)壓力。因?yàn)橐苿?dòng)機(jī)器人關(guān)系到不同技術(shù)，整體質(zhì)量也直接決定了智能化程度，所以在路徑規(guī)劃階段，一般會(huì)通過2種路徑加強(qiáng)機(jī)器人科技科水平，為我國(guó)科技行業(yè)的進(jìn)步添磚加瓦。這里提到移動(dòng)機(jī)器人路徑規(guī)劃，需要運(yùn)用到不同形式的傳感器影響機(jī)器人，并且按照環(huán)境感知，在評(píng)判標(biāo)準(zhǔn)作用下規(guī)劃出安全性最佳的運(yùn)行路線。路徑規(guī)劃期間按照機(jī)器人功能，可使用不同的算法，得出機(jī)器人繞過一些障礙物的時(shí)間、效率。常見的路徑規(guī)劃算法有全局、局部和人工智能三種類型，在移動(dòng)機(jī)器人路徑規(guī)劃中分別有不同的作用。下文圍繞移動(dòng)機(jī)器人路徑規(guī)劃算法分別展開討論。

一、移動(dòng)機(jī)器人路徑規(guī)劃概述

移動(dòng)機(jī)器人路徑規(guī)劃屬于技術(shù)研發(fā)領(lǐng)域，常見的機(jī)器人路徑規(guī)劃技術(shù)是以任意參數(shù)指標(biāo)為對(duì)象，從任務(wù)區(qū)域挑選出從起點(diǎn)到終點(diǎn)連接的最佳避障路徑，換言之，也可以理解為在若干個(gè)約束條件下所獲得的可行解。分析移動(dòng)機(jī)器人的路徑規(guī)劃效果，通常會(huì)對(duì)機(jī)器人運(yùn)行、任務(wù)完成實(shí)時(shí)結(jié)果帶來直接的影響[1]。

最初關(guān)注機(jī)器人路徑規(guī)劃的分析，可以追溯到20世紀(jì)，迄今為止世界上所有的機(jī)器人研發(fā)依然在持續(xù)進(jìn)行，并且從技術(shù)上獲得了顯著成效。按照環(huán)境信息特征，將路徑規(guī)劃劃分為離散域范圍、連續(xù)域范圍兩種類型；按照路徑規(guī)劃算法被發(fā)現(xiàn)的順序，則有傳統(tǒng)算法和現(xiàn)代智能算法兩種類型。結(jié)合移動(dòng)機(jī)器人理解的工作區(qū)域信息層次，路徑規(guī)劃主要有兩類，即全局路徑規(guī)劃、局部路徑規(guī)劃。其一，全局路徑規(guī)劃。按照掌握的全局環(huán)境信息可創(chuàng)建抽象全區(qū)域環(huán)境地圖模型，該模型中可以通過尋優(yōu)搜索算法，得出機(jī)器人運(yùn)行的全局最優(yōu)、次優(yōu)路徑，對(duì)移動(dòng)機(jī)器人朝目標(biāo)點(diǎn)進(jìn)行安全移動(dòng)加以引導(dǎo)。該路徑規(guī)劃算法首先需要理解環(huán)境信息并構(gòu)建地圖模型，其次則涉及到全局路徑搜索、機(jī)器人引導(dǎo)。其二，局部路徑規(guī)劃。機(jī)器人完成任務(wù)期間，按照所攜帶傳感器獲取的局部環(huán)境信息，便可以展開實(shí)時(shí)動(dòng)態(tài)路徑規(guī)劃，這一類型路徑規(guī)劃算法的靈活性、實(shí)時(shí)性非常強(qiáng)。但是在局部環(huán)境特點(diǎn)影響下，所得到的路徑有可能僅為局部最優(yōu)，并非是全局最優(yōu)，還有可能無法達(dá)到目標(biāo)[2]。實(shí)際上對(duì)于移動(dòng)機(jī)器人路徑規(guī)劃而言，可以將全局與局部?jī)煞N路徑規(guī)劃算法加以組合，通過前者獲得機(jī)器人的全局優(yōu)化路徑，再利用后者達(dá)到實(shí)時(shí)避障的效果。

二、移動(dòng)機(jī)器人路徑規(guī)劃的常見算法

（一）全局路徑規(guī)劃算法

1.圖搜索算法

圖搜索算法涵蓋了諸多不同類型的算法，如A*算法，針對(duì)移動(dòng)機(jī)器人確定目標(biāo)關(guān)鍵點(diǎn)，一般是機(jī)器人與障礙物，機(jī)器人環(huán)繞障礙物之后遵循“以點(diǎn)成線，以線成面”的原則直接構(gòu)圖即為可視圖?？梢晥D目標(biāo)點(diǎn)可見，點(diǎn)與點(diǎn)之間的頂點(diǎn)需要保證清晰度。圖搜索算法在運(yùn)用中，可以得出最短路線，即起點(diǎn)和目標(biāo)點(diǎn)之間的最短距離[3]。利用這種優(yōu)化算法，刪除一些多余的連線，可視圖得到簡(jiǎn)化處理之后搜索時(shí)間也就隨之縮短。

2.快速隨機(jī)搜索樹

快速隨機(jī)搜索樹（Rapidexploration Random Tree，RRT）作為全局路徑規(guī)劃算法，是在采樣基礎(chǔ)上延伸而來的搜索算法，在高維非歐空間搜索中適用性極高。利用快速隨機(jī)搜索樹算法，針對(duì)多維度空間中不完整性約束問題能夠快速做出處理。路徑規(guī)劃起點(diǎn)作為搜索樹根節(jié)點(diǎn)，按照規(guī)定準(zhǔn)則可以設(shè)定搜索樹的節(jié)點(diǎn)，再結(jié)合路徑規(guī)劃已知約束條件，已經(jīng)確定的節(jié)點(diǎn)再擴(kuò)展之后可得出新節(jié)點(diǎn)，在搜索樹中儲(chǔ)存，隨之不斷重復(fù)上述流程，直至找到終點(diǎn)。通過此算法一方面可以展開隨機(jī)采樣，使機(jī)器人探索并未探查的空間，另一方面在探索期間也會(huì)優(yōu)化搜索樹[4]。

快速隨機(jī)搜索樹算法屬于快速搜索算法，具有探索速度快、搜索力強(qiáng)、地圖預(yù)處理操作便捷等優(yōu)勢(shì)，但是在搜索過程中比較盲目，特別是高維、動(dòng)態(tài)環(huán)境下，可能增加探索的時(shí)間與計(jì)算復(fù)雜性，還有可能陷入死區(qū)中，導(dǎo)致局部最小值。面對(duì)此算法計(jì)算復(fù)雜的問題，建議將RRT算法和滾動(dòng)路徑規(guī)劃算法結(jié)合，起到移動(dòng)機(jī)器人在線避障的引導(dǎo)作用，可以降低RRT算法復(fù)雜程度，還加強(qiáng)了實(shí)時(shí)性。以此為基礎(chǔ)引入選擇性參數(shù)，優(yōu)化傳統(tǒng)算法統(tǒng)一概率，可以提高RRT算法收斂效率，加強(qiáng)算法路徑規(guī)劃指向性。經(jīng)過改進(jìn)之后的RRT算法，可以運(yùn)用在滾動(dòng)窗口改進(jìn)路徑規(guī)劃算法中，既保證了原有RRT算法在隨機(jī)搜索方面的優(yōu)勢(shì)，又對(duì)估價(jià)收斂標(biāo)準(zhǔn)函數(shù)引導(dǎo)搜索樹生長(zhǎng)進(jìn)行了引導(dǎo)，縮短算法運(yùn)算所花費(fèi)的時(shí)間。面對(duì)局部最小問題，建議采用回歸分析法，篩選出新節(jié)點(diǎn)，保證算法智能趨近終點(diǎn)優(yōu)勢(shì)的基礎(chǔ)上，還可以對(duì)未知空間展開探索[5]。另外，快速隨機(jī)搜索樹基礎(chǔ)上還提出了高自由度關(guān)節(jié)移動(dòng)機(jī)器人的方法，在高維空間中具有極高的適應(yīng)性，按照路徑復(fù)雜性確定機(jī)器人主體，并且篩選出機(jī)器人關(guān)節(jié)，也就是所謂的配置空間、采樣自適應(yīng)維度路徑規(guī)劃。該路徑規(guī)劃與自適應(yīng)快速隨機(jī)搜索樹算法結(jié)合之后，利用自適應(yīng)選擇主體，可在自適應(yīng)三維空間范圍內(nèi)循序漸進(jìn)的增加RRT。因?yàn)閭鹘y(tǒng)形式的快速搜索隨機(jī)樹算法在運(yùn)用中收斂速度不高，建議與多約束條件改進(jìn)算法加以融合，此算法同時(shí)涉及到環(huán)境約束、運(yùn)動(dòng)學(xué)約束，通過啟發(fā)方法采樣節(jié)點(diǎn)，極大地保證了路徑規(guī)劃速度[6]。

3.智能仿生算法

智能仿生算法的核心是對(duì)自然界所有動(dòng)物進(jìn)化的過程、昆蟲覓食捕獵行為等進(jìn)行模擬，以此來規(guī)劃移動(dòng)機(jī)器人運(yùn)行路徑，常見的有蟻群算法、粒子群算法等。其一，蟻群算法。此算法是在螞蟻覓食行為基礎(chǔ)上延伸而來，一般螞蟻覓食期間會(huì)分泌出信息素，在已經(jīng)走過道路遺留痕跡，后續(xù)再有覓食的螞蟻便會(huì)根據(jù)遺留的信息素明確路線，搜索得出信息素濃度，一般濃度高即為最短路徑[7]?；诖?，蟻群算法領(lǐng)域的全局路徑規(guī)劃，可以按照蟻群數(shù)量、啟發(fā)因子、信息素?cái)?shù)量等確定移動(dòng)機(jī)器人規(guī)劃路徑，經(jīng)過信息素改進(jìn)后可以進(jìn)一步提高算法收斂速度和搜索效率。

4.遺傳算法

遺傳算法（Genetic Algorithm，GA）屬于全局優(yōu)化搜索算法范疇，其是在達(dá)爾文進(jìn)化思想基礎(chǔ)上延伸而來，以自然選擇與遺傳產(chǎn)生的交叉、變異、遺傳等現(xiàn)象，展開仿真模擬，遵循優(yōu)勝劣汰原則，并且結(jié)合結(jié)果獲得候選解，在所有候選解當(dāng)中可以發(fā)現(xiàn)最優(yōu)解。遺傳算法具有迭代優(yōu)勢(shì)，并且組合其他算法，展現(xiàn)出自組織性、自學(xué)習(xí)性的特點(diǎn)，移動(dòng)機(jī)器人路徑規(guī)劃最優(yōu)路徑的搜索性也非常強(qiáng)。遺傳算法的操作比較簡(jiǎn)單，很少會(huì)受外部環(huán)境影響，但是實(shí)時(shí)運(yùn)算和搜索效率不高，極易于陷入到局部最優(yōu)解。算法運(yùn)行階段，不重要的種群存在則會(huì)增加計(jì)算難度，降低算法運(yùn)行效率，在線路徑規(guī)劃的適用性不高。

（二）局部路徑規(guī)劃算法

1.模擬退火算法

模擬退火算法是目前移動(dòng)機(jī)器人路徑規(guī)劃中，組合優(yōu)化問題最為有效地解決算法，處理算法期間金屬熱在算法有效退火，初期控制金屬環(huán)溫度，即使遇到突發(fā)性事件，也可以隨機(jī)搜索，快速地收集數(shù)據(jù)。結(jié)合路徑規(guī)劃現(xiàn)狀，使用模擬退火算法，具有操作簡(jiǎn)單、有效性強(qiáng)、控制數(shù)據(jù)少以及彈性等諸多優(yōu)勢(shì)，但是也會(huì)出現(xiàn)一定概率，導(dǎo)致速度緩慢[8]。運(yùn)用模擬退火算法進(jìn)行移動(dòng)機(jī)器人局部路徑規(guī)劃，使路徑擺脫原始路徑，探索出新目標(biāo)點(diǎn)，找到最佳移動(dòng)路徑。

2.人工勢(shì)場(chǎng)算法

人工勢(shì)場(chǎng)算法在移動(dòng)機(jī)器人路徑規(guī)劃中運(yùn)用，針對(duì)機(jī)器人所在環(huán)境展開規(guī)劃，在人工場(chǎng)范圍內(nèi)運(yùn)動(dòng)，其本質(zhì)上屬于抽象意義的人造受力場(chǎng)，利用目標(biāo)點(diǎn)對(duì)輸出機(jī)器人形成引力與障礙物斥力，基于不同環(huán)境所形成的合力也可以明確機(jī)器人輸出。此算法的結(jié)構(gòu)比較簡(jiǎn)單，在底層實(shí)時(shí)控制方面具有明顯的優(yōu)勢(shì)，最終規(guī)劃路徑也十分平滑，保證了移動(dòng)機(jī)器人運(yùn)行的安全性。但是人工勢(shì)場(chǎng)算法依然存在局部最優(yōu)、狹窄通道動(dòng)蕩等問題[9]。如果環(huán)境要求過于嚴(yán)格，其虛擬合力即為零，此時(shí)會(huì)影響到移動(dòng)機(jī)器人的運(yùn)行，無法繼續(xù)執(zhí)行任務(wù)。通過人工勢(shì)場(chǎng)啟發(fā)函數(shù)，便可達(dá)到全局最優(yōu)，并規(guī)避局部最優(yōu)帶來的影響。面對(duì)人工勢(shì)場(chǎng)算法潛在問題，可以結(jié)合斥力模型，路徑規(guī)劃階段移動(dòng)機(jī)器人規(guī)避局部極小點(diǎn)，使得路徑規(guī)劃面臨問題得到解決。

（三）基于人工智能算法的路徑規(guī)劃技術(shù)

基于人工智能算法的路徑規(guī)劃表現(xiàn)最為突出的就是深度強(qiáng)化學(xué)習(xí)算法（Deep Reinforcement Learning,DQN)，所謂深度強(qiáng)化學(xué)習(xí)，是深度學(xué)習(xí)感知能力、強(qiáng)化學(xué)習(xí)決策能力的融合，按照輸入圖像展開精準(zhǔn)控制，其本質(zhì)上與人類的思維方式更為接近，是人工智能領(lǐng)域也得到了極大的關(guān)注。深度學(xué)習(xí)感知力較強(qiáng)，但決策力不高，強(qiáng)化學(xué)習(xí)本身有一定的決策力，面對(duì)感知問題卻無法得出有效的結(jié)論。將兩種算法結(jié)合后的深度強(qiáng)化學(xué)習(xí)具有自監(jiān)督學(xué)習(xí)能力，可在復(fù)雜的環(huán)境中可自主與周圍環(huán)境進(jìn)行交互。同時(shí)其在決策與狀態(tài)分析也有很好的表現(xiàn)能力。深度強(qiáng)化學(xué)習(xí)在路徑規(guī)劃方面最主要的優(yōu)勢(shì)在于其不依賴人工標(biāo)記軌跡，只需設(shè)置規(guī)劃原則如運(yùn)行路徑最短、無障礙物碰撞和目標(biāo)點(diǎn)等，然后在虛擬實(shí)驗(yàn)平臺(tái)或者現(xiàn)實(shí)環(huán)境中訓(xùn)練神經(jīng)網(wǎng)絡(luò)即可。但是深度強(qiáng)化學(xué)習(xí)在路徑規(guī)劃上仍也存在很多不足之處，如路徑規(guī)劃時(shí)效性差、遇障礙多次轉(zhuǎn)向等問題，需要從改進(jìn)神經(jīng)網(wǎng)絡(luò)模型、獎(jiǎng)勵(lì)函數(shù)和多算法融合方面進(jìn)行探索改進(jìn)，為移動(dòng)機(jī)器人路徑規(guī)劃這種比較復(fù)雜的系統(tǒng)感知決策問題梳理思路。

DQN算法主要有神經(jīng)網(wǎng)絡(luò)、Q learning兩種，被稱作 Deep Q Network。該算法中包括記憶庫(kù)，記載著學(xué)習(xí)的所有經(jīng)歷。Q learning屬于off-policy 離線學(xué)習(xí)法，可以學(xué)習(xí)目前正在經(jīng)歷的內(nèi)容，也可以學(xué)習(xí)以往經(jīng)歷的內(nèi)容，整體范圍比較廣。因此，當(dāng)DQN更新時(shí)便可以隨機(jī)抽取已有經(jīng)歷學(xué)習(xí)，有利于提高神經(jīng)網(wǎng)絡(luò)更新的效率。此外，F(xiàn)ixed Q-targets 的應(yīng)用需要打亂相關(guān)性，若在移動(dòng)機(jī)器人路徑規(guī)劃中應(yīng) 用 fixed Q-targets，DQN所涉及到的2個(gè)結(jié)構(gòu)一致，但是參數(shù)存在差異的神經(jīng)網(wǎng)絡(luò)，可以預(yù)估神經(jīng)網(wǎng)絡(luò)參數(shù)，加強(qiáng)路徑規(guī)劃精準(zhǔn)性。

三、移動(dòng)機(jī)器人路徑規(guī)劃算法應(yīng)用前景

如今移動(dòng)機(jī)器人技術(shù)已經(jīng)非常先進(jìn)，在計(jì)算機(jī)、傳感器、人工智能等各項(xiàng)技術(shù)的飛速發(fā)展下，路徑規(guī)劃也獲得了非常顯著的研究效果，但是路徑規(guī)劃算法之間的差異、限制，還需要在基礎(chǔ)理論與技術(shù)層面加以優(yōu)化。立足于移動(dòng)機(jī)器人路徑規(guī)劃算法的發(fā)展現(xiàn)狀，路徑規(guī)劃算法今后的發(fā)展前景非?？捎^，也為我國(guó)人工智能行業(yè)的發(fā)展夯實(shí)了基礎(chǔ)。為此，分析今后移動(dòng)機(jī)器人路徑規(guī)劃算法的應(yīng)用前景，主要表現(xiàn)在以下四方面：

第一，現(xiàn)有的路徑規(guī)劃算法將得到不斷改進(jìn)與優(yōu)化。路徑規(guī)劃算法的應(yīng)用，其中任意一種算法難免會(huì)遇到問題，特別是算法自身存在的局限性。在移動(dòng)機(jī)器人路徑規(guī)劃中進(jìn)行改進(jìn)，有利于提高算法性能，將移動(dòng)機(jī)器人面臨的問題予以解決。

第二，混合算法將得到廣泛應(yīng)用。路徑規(guī)劃中采用混合算法，是將不同算法進(jìn)行組合。獨(dú)立算法無法解決切實(shí)存在的路徑規(guī)劃問題，特別是交叉學(xué)科面臨的新問題。考慮到研發(fā)各種新算法具有很大難度，所以可以通過不同的路徑規(guī)劃算法優(yōu)勢(shì)，達(dá)到互補(bǔ)效果，為解決路徑規(guī)劃問題探索新思路。例如群體智能算法、強(qiáng)化學(xué)習(xí)算法和神經(jīng)網(wǎng)絡(luò)等，在移動(dòng)機(jī)器人路徑規(guī)劃問題均得到了組合應(yīng)用，通過這種互補(bǔ)混合算法，不僅加快了算法之間的融合，利用取長(zhǎng)補(bǔ)短與優(yōu)勢(shì)互補(bǔ)，還會(huì)延伸出大量?jī)?yōu)秀算法。人工智能、數(shù)理、仿生算法等經(jīng)過組合之后，在移動(dòng)機(jī)器人路徑規(guī)劃中應(yīng)用也呈現(xiàn)出可觀的發(fā)展前景。

第三，多種機(jī)器人協(xié)同合作。移動(dòng)機(jī)器人的作業(yè)范圍近年來逐漸拓寬，加上作業(yè)任務(wù)難度增加、復(fù)雜程度更高，所以單一機(jī)器人無法快速完成規(guī)定的任務(wù)，此時(shí)便要多種機(jī)器人協(xié)同合作，既可以提高機(jī)器人的工作效率，又能夠杜絕因改變作業(yè)環(huán)境、機(jī)器人系統(tǒng)局部故障等原因造成的工作停滯事故。單一機(jī)器人處于某種關(guān)注環(huán)境下，有時(shí)并不能很好地達(dá)到使用要求，通過多機(jī)器人協(xié)同合作的方法可以解決該問題。另外，多機(jī)器人在運(yùn)行期間也會(huì)出現(xiàn)一些故障，例如路徑規(guī)劃更加復(fù)雜，障礙物和機(jī)器人數(shù)量更多，也在路徑規(guī)劃階段面臨困難。所以，多種機(jī)器人協(xié)同運(yùn)行將成為今后行業(yè)領(lǐng)域內(nèi)研究的重點(diǎn)。

第四，當(dāng)移動(dòng)機(jī)器人處在比較復(fù)雜的且多維環(huán)境下，移動(dòng)機(jī)器人路徑規(guī)劃將成為關(guān)注要點(diǎn)。面對(duì)具體對(duì)象，移動(dòng)機(jī)器人路徑規(guī)劃一般是以陸地作業(yè)機(jī)器人路徑規(guī)劃為對(duì)象，此條件下比較常用掃地機(jī)器人、反恐防爆機(jī)器人。面對(duì)空中飛行機(jī)器人、水下機(jī)器人，對(duì)比掃地機(jī)器人等生活中使用幾率比較高的設(shè)備，總體來說研究不夠深入。目前，空間探測(cè)對(duì)移動(dòng)機(jī)器人提出的嚴(yán)格要求，所以移動(dòng)機(jī)器人研究重點(diǎn)也開始轉(zhuǎn)移到崎嶇地形、障礙物比較多的復(fù)雜環(huán)境。立足于路徑規(guī)劃環(huán)境描述這一角度，二維平面環(huán)境下的路徑規(guī)劃工作量比較大，三維環(huán)境的路徑規(guī)劃相對(duì)較少。即便如此，仍然有一些移動(dòng)機(jī)器人的工作環(huán)境為三維環(huán)境空間，例如飛行器。此外，陸地機(jī)器人一般是在相對(duì)穩(wěn)定的陸地環(huán)境中運(yùn)行，飛行機(jī)器人和仿生魚類機(jī)器人的工作環(huán)境與之相比，其惡劣程度也有所增加，傳感器的使用也更加嚴(yán)格，還存在一些危險(xiǎn)因素。為此，飛行器、仿生魚類機(jī)器人在研究過程中需要重點(diǎn)分析，全面總結(jié)，從現(xiàn)實(shí)環(huán)境著手展開移動(dòng)機(jī)器人路徑規(guī)劃。

四、結(jié)束語(yǔ)

綜上所述，移動(dòng)機(jī)器人是在人工智能技術(shù)基礎(chǔ)上延伸而來的全新行業(yè)領(lǐng)域，融合了互聯(lián)網(wǎng)、人工智能等多項(xiàng)先進(jìn)技術(shù)。機(jī)器人研究最為重要的是路徑規(guī)劃，在此環(huán)節(jié)需要使用大量算法，只有如此才能夠規(guī)劃最優(yōu)機(jī)器人行進(jìn)路線，提高運(yùn)行效率與質(zhì)量，以免因?yàn)槁窂揭?guī)劃不合理，導(dǎo)致出現(xiàn)延長(zhǎng)行進(jìn)時(shí)間的現(xiàn)象。基于本文的分析，圖搜索算法、快速隨機(jī)搜索樹、智能仿生算法、遺傳算法、模擬退火算法、人工勢(shì)場(chǎng)算法等均可以在路徑規(guī)劃中應(yīng)用，除了單一算法的使用外，還可以將算法組合應(yīng)用，進(jìn)一步優(yōu)化路徑規(guī)劃效果。此外，工作人員對(duì)現(xiàn)有算法進(jìn)行改進(jìn)，還可以起到良好的優(yōu)化效果，提高移動(dòng)機(jī)器人行進(jìn)效率，也為我國(guó)移動(dòng)機(jī)器人的研究積累經(jīng)驗(yàn)。