王承平

摘 要：移動(dòng)機(jī)器人是現(xiàn)階段科研工作的重點(diǎn)內(nèi)容之一，并且受到社會(huì)各界人士的廣泛關(guān)注?；诖?，本文針對(duì)當(dāng)前移動(dòng)機(jī)器人的智能路徑規(guī)劃算法進(jìn)行研究，但是移動(dòng)機(jī)器人路徑規(guī)劃要從實(shí)際應(yīng)用出發(fā)，所以很難從復(fù)雜的環(huán)境中尋找到一條最優(yōu)化的路徑，因此將移動(dòng)機(jī)器人的常規(guī)算法進(jìn)行總結(jié)分析，并闡述各種算法的優(yōu)點(diǎn)及缺點(diǎn)，并提出計(jì)算機(jī)智能算法的應(yīng)用路徑規(guī)劃的探究，希望能對(duì)移動(dòng)機(jī)器人路徑規(guī)劃算法的科研人員提供思路。

關(guān)鍵詞：移動(dòng)機(jī)器人 路徑規(guī)劃 啟發(fā)式搜索算法 強(qiáng)化學(xué)習(xí)算法

An Overview of Intelligent Path Planning Algorithms for Mobile Robots

Wang ChengPing

Abstract：Mobile robot is one of the key contents of scientific research at this stage， and has been widely concerned by people from all walks of life. Based on this， this paper studies the current intelligent path planning algorithm of mobile robot， but the path planning of mobile robot should start from the practical application， so it is difficult to find an optimal path from the complex environment. Therefore， the conventional algorithms of mobile robot are summarized and analyzed， and the advantages and disadvantages of various algorithms are described. The paper also puts forward the application of computer intelligent algorithm and the exploration of path planning， hoping to provide ideas for researchers of mobile robot path planning algorithm.

Key words：mobile robot， path planning， heuristic search algorithm， reinforcement learning algorithm

1 引文

移動(dòng)機(jī)器人的路徑規(guī)劃主要指的是移動(dòng)機(jī)器人在復(fù)雜的環(huán)境下找到一條無障礙路徑?，F(xiàn)階段許多已知環(huán)境下的路徑規(guī)劃算法已經(jīng)成熟，能實(shí)現(xiàn)無碰撞運(yùn)行，但是在無知的環(huán)境中，移動(dòng)機(jī)器人需要根據(jù)傳感器來收集局部信息，進(jìn)而運(yùn)用相關(guān)算法實(shí)現(xiàn)路徑規(guī)劃，但是現(xiàn)階段未知環(huán)境的路徑規(guī)劃算法依舊處于試驗(yàn)階段。而且近幾年我國各大企業(yè)都在研究無人駕駛技術(shù)，而無人駕駛技術(shù)的人工智能算法也涉及路徑規(guī)劃，因此相關(guān)人員可以借鑒其技術(shù)，從而更好的推動(dòng)移動(dòng)機(jī)器人路徑規(guī)劃。

2 Dijkstra算法

2.1 Dijkstra基本原理

Dijkatra算法是一種圖搜索算法，其由荷蘭科學(xué)家Edsger wybe Dijk stra在1959年提出，主要為了解決賦權(quán)圖最短路徑問題，這種算法后來被改進(jìn)應(yīng)用在移動(dòng)機(jī)器人上面，進(jìn)而解決移動(dòng)機(jī)器人路徑規(guī)劃問題。而且這種算法的基本原理是在某一個(gè)特定區(qū)域選取一點(diǎn)作為起始點(diǎn)，學(xué)術(shù)上稱之為原點(diǎn)，在計(jì)算原點(diǎn)到區(qū)域某一點(diǎn)的所有路徑，再將這些路徑進(jìn)行比較，進(jìn)而選出最短的路徑，如果中間添加其他階段，需要計(jì)算原點(diǎn)到第一個(gè)節(jié)點(diǎn)的距離，第一個(gè)階段到第二個(gè)階段的距離，兩個(gè)階段的距離進(jìn)行相加，如果距離更短將進(jìn)行更新迭代，直到區(qū)域內(nèi)所有路徑全部完成。這種算法實(shí)現(xiàn)相對(duì)簡(jiǎn)單，復(fù)雜度相對(duì)低，在物流運(yùn)輸及外賣配送中應(yīng)用較多。但是Dijkstra算法一直都是在選擇區(qū)域內(nèi)最短的路徑，因此其有著很大的局限性[1]。此外，Dijkstra算法需要原點(diǎn)到節(jié)點(diǎn)的所有距離，這種算法會(huì)導(dǎo)致時(shí)間消耗較長(zhǎng)，計(jì)算所占據(jù)的內(nèi)存較大。

2.2 Dijkstra算法優(yōu)化

Dijkstra算法有著很多的優(yōu)勢(shì)，但是也存在著明顯的問題，即耗時(shí)長(zhǎng)、算法占據(jù)存儲(chǔ)空間大，因此提出相應(yīng)優(yōu)化方法，用來優(yōu)化與解決相應(yīng)的問題。第一，多節(jié)點(diǎn)并行優(yōu)化方法，這種優(yōu)化法與傳統(tǒng)的Dijkstra算法相比有著明顯的優(yōu)勢(shì)，他采用多節(jié)點(diǎn)同時(shí)進(jìn)行路徑規(guī)劃，并采用多線程對(duì)不同的節(jié)點(diǎn)進(jìn)行計(jì)算，在提高速度的同時(shí)還能保證多線程的安全性與精準(zhǔn)性。經(jīng)過相關(guān)的實(shí)驗(yàn)表明，多節(jié)點(diǎn)并行算法所用的時(shí)間要比傳統(tǒng)的Dijkstra算法時(shí)間短，而且縮短的時(shí)間會(huì)隨著原點(diǎn)區(qū)域面積的變大而變大，比較適合大范圍的路徑規(guī)劃。第二，松弛Dijkstra優(yōu)化算法，這種優(yōu)化法的主要特點(diǎn)是將Dijkstra與A*算法進(jìn)行結(jié)合，兩者都是計(jì)算最短路徑的常用算法，但是一種建立在抽象的圖論層面，一種是建立在常用游戲地圖的最短路徑應(yīng)用[2]。因此在建立建模后可以采用逆向搜索策略，計(jì)算節(jié)點(diǎn)到原點(diǎn)的距離，在開始時(shí)節(jié)點(diǎn)從常規(guī)的8個(gè)方向出發(fā)，進(jìn)而選取最短的路徑。在兩個(gè)方向的路徑距離相同時(shí)，按相同的概率選擇其中任何一個(gè)展開。該方法能在障礙物密度較大的復(fù)雜環(huán)境下進(jìn)行路徑規(guī)劃，但需進(jìn)一步研究減小誤差的方法，以獲得最優(yōu)解。Dijkstra算法的優(yōu)化主要解決計(jì)算時(shí)間長(zhǎng)、計(jì)算量大、回溯線程規(guī)劃等問題，多節(jié)點(diǎn)并行優(yōu)化方法能有效的提高計(jì)算效率，但是實(shí)際的計(jì)算量并沒有變化，這種優(yōu)化算法對(duì)復(fù)雜的大型地圖有著明顯的效果。第二種優(yōu)化方法可以分層次進(jìn)行規(guī)劃，將規(guī)劃空間層次、方向分別進(jìn)行設(shè)定節(jié)點(diǎn)，最后整合所有的路徑，可以追溯到每一層的擴(kuò)展進(jìn)度。

3 A*算法

3.1 A*算法基本原理

A*算法由Hart PE、NILsson、Raphael B在1968年提出的，算法的基本原理是在Dijkstra算法的基礎(chǔ)上引入函數(shù)公式F（n）=G+H，進(jìn)而形成A*算法，而且當(dāng)H（n）為0時(shí)，A*算法即為Dijkstra算法。其次，在使用A*算法進(jìn)行路徑規(guī)劃前需要了解A*算法涉及的相關(guān)概念，其中包括搜索區(qū)域、開放列表、父節(jié)點(diǎn)、路徑排序、啟發(fā)函數(shù)[3]。搜索區(qū)域指的是將簡(jiǎn)單的區(qū)域圖分成二維數(shù)組，在二維數(shù)組中每個(gè)元素對(duì)應(yīng)相關(guān)的小區(qū)域，這些小區(qū)域能組成不同形狀的大區(qū)域，將一個(gè)單位數(shù)組的中心點(diǎn)稱之為區(qū)域節(jié)點(diǎn)。開放列表（Open List）指的是在路徑規(guī)劃過程中，我們把要檢測(cè)的節(jié)點(diǎn)放到開放列表中，同時(shí)將被檢測(cè)到的節(jié)點(diǎn)存儲(chǔ)到關(guān)閉列表中。父節(jié)點(diǎn)（parent）指的是在路徑規(guī)劃中能用來回溯的節(jié)點(diǎn)，在開發(fā)時(shí)可以考慮使用雙向鏈表結(jié)構(gòu)中的父節(jié)點(diǎn)指針，進(jìn)而方便節(jié)點(diǎn)的回溯。路徑排序（Path Sorting）指的是原點(diǎn)具體向那個(gè)節(jié)點(diǎn)移動(dòng)由函數(shù)公式F（n）=G+H來確定，G表示原點(diǎn)生成路徑到目標(biāo)節(jié)點(diǎn)的移動(dòng)，H制定估計(jì)的待測(cè)網(wǎng)絡(luò)移動(dòng)端到節(jié)點(diǎn)的移動(dòng)。啟發(fā)函數(shù)（Heuristics Function）指的是路徑試探，也稱為啟發(fā)函數(shù)H，只要功能是在未知區(qū)域內(nèi)尋找唯一的路徑，所以在使用計(jì)算啟發(fā)函數(shù)時(shí)要取決于實(shí)際場(chǎng)景[4]。在實(shí)驗(yàn)?zāi)Ｐ椭校琀采用傳統(tǒng)的曼哈頓距離（Manhattan Distance），即原點(diǎn)到節(jié)點(diǎn)橫向和縱向行走的距離之和。因此，A*算法在處理最短路徑規(guī)劃問題上效果顯著，其函數(shù)公式能在一定程度上避免全圖節(jié)點(diǎn)搜索，進(jìn)而提高算法的應(yīng)用效率。但是其在搜索時(shí)會(huì)使用父節(jié)點(diǎn)來估算回溯路徑，這樣會(huì)造成生產(chǎn)路徑平滑性差，一旦路徑存在障礙物移動(dòng)機(jī)器人將無法按照規(guī)劃路徑進(jìn)行移動(dòng)，而且在規(guī)劃路徑時(shí)相對(duì)復(fù)雜，導(dǎo)致計(jì)算量加大，計(jì)算存儲(chǔ)空間占用率增加，從而降低算法效率。

3.2 A*算法優(yōu)化

A*算法在實(shí)際應(yīng)用中有著明顯的優(yōu)勢(shì)，但是也存在計(jì)算量大、計(jì)算存儲(chǔ)空間占用率大等問題，所以對(duì)A*算法進(jìn)行優(yōu)化，進(jìn)而適應(yīng)移動(dòng)機(jī)器人路徑規(guī)劃需求。第一種，針對(duì)A*算法基礎(chǔ)條件的啟發(fā)算法進(jìn)行優(yōu)化，首先通過設(shè)定距離函數(shù)和靜態(tài)權(quán)值，靜態(tài)權(quán)值為原點(diǎn)到目標(biāo)節(jié)點(diǎn)的矢量，而且還要將節(jié)點(diǎn)與目標(biāo)點(diǎn)的距離、方向、角度進(jìn)行統(tǒng)一化處理，再用相應(yīng)的函數(shù)計(jì)算其對(duì)路徑的影響。其次，改進(jìn)鄰域搜索矩陣，根據(jù)移動(dòng)機(jī)器人的大小和未知地域地圖的分辨率進(jìn)行調(diào)整，使移動(dòng)機(jī)器人與未知區(qū)域障礙物保持一定的距離，避免機(jī)器人在移動(dòng)時(shí)碰到障礙物。最后，采用貝塞爾曲線來增加路徑的可行性[5]。第二種，針對(duì)搜索法的進(jìn)行優(yōu)化，將跳點(diǎn)搜索法應(yīng)用在A*算法的節(jié)點(diǎn)搜索中，在擴(kuò)展節(jié)點(diǎn)的過程中，篩選出某些特殊的節(jié)點(diǎn)當(dāng)作跳點(diǎn)，再將兩個(gè)跳點(diǎn)進(jìn)行連接進(jìn)而實(shí)現(xiàn)大范圍的搜索，這樣做法可以不用計(jì)算兩個(gè)跳點(diǎn)之間的路徑，所以在實(shí)際應(yīng)用中不需要將每個(gè)節(jié)點(diǎn)都進(jìn)行路徑規(guī)劃，從而極大的減少內(nèi)存消耗。第三種，雙向處理A*算法，這種算法采用并行模式，這種模式和Dijkstra多節(jié)點(diǎn)運(yùn)行有部分相似，A*并行模式是從原點(diǎn)和終點(diǎn)同時(shí)進(jìn)行獨(dú)立搜索，兩條路徑在開放列表中都有著相同的節(jié)點(diǎn)，這表明兩條路徑已經(jīng)在搜索地域相遇，進(jìn)而判斷路徑規(guī)劃完成，使得相同的路徑在計(jì)算時(shí)所需要的時(shí)間更短。第四種，改進(jìn)A*算法估算函數(shù)，將G和H設(shè)置不同的權(quán)重，當(dāng)節(jié)點(diǎn)距離目標(biāo)點(diǎn)遠(yuǎn)時(shí)，要增加權(quán)重，當(dāng)節(jié)點(diǎn)距離目標(biāo)點(diǎn)近時(shí)，降低權(quán)重，這樣將方向與距離變差較大的節(jié)點(diǎn)排除，進(jìn)而減少搜索的節(jié)點(diǎn)數(shù)量，減少計(jì)算內(nèi)存的消耗。因此，對(duì)A*算法的優(yōu)化主要包括：?jiǎn)l(fā)函數(shù)改進(jìn)、節(jié)點(diǎn)擴(kuò)展改進(jìn)、搜索方法改進(jìn)等，這些都能有效的解決A*算法在不同環(huán)境下的運(yùn)算量過大與路徑規(guī)劃中存在的問題。而且這種改進(jìn)使得搜索過程不再需要全圖節(jié)點(diǎn)搜索，只需要在地域擴(kuò)展時(shí)對(duì)目標(biāo)方向的節(jié)點(diǎn)進(jìn)行搜索，進(jìn)而減少計(jì)算量。而且技術(shù)在計(jì)算量較大的情況下，搜索方式的優(yōu)化也能保證路徑規(guī)劃的速度和質(zhì)量。

4 強(qiáng)化學(xué)習(xí)算法在路徑規(guī)劃上的應(yīng)用

強(qiáng)化學(xué)習(xí)的算法包括：Dyna算法、Sarsa算法、時(shí)間差算法TD、Q-Learning算法、Actor-Critic算法等，其中時(shí)間差TD算法是最早的強(qiáng)化學(xué)習(xí)算法，之后的Sarsa算法等都是在TD算法的基礎(chǔ)上進(jìn)行改進(jìn)的，區(qū)別在于迭代動(dòng)作函數(shù)Q（s，a）或狀態(tài)值函數(shù)V（s）。時(shí)間算法與其演變的算法主要應(yīng)用在已知環(huán)境中，但是Dyna算法是建立全新的環(huán)境模型來代替真實(shí)環(huán)境，從而對(duì)虛擬樣本函數(shù)值進(jìn)行迭代，進(jìn)而實(shí)現(xiàn)強(qiáng)化學(xué)習(xí)。其次，現(xiàn)階段強(qiáng)化學(xué)習(xí)算法中Actor-Critic算法具備記憶功能，其收斂質(zhì)量得到保證，而且能提高收斂速度，是一種具備估計(jì)值函數(shù)和策略學(xué)習(xí)方法的算法。但是強(qiáng)化學(xué)習(xí)算法還處于發(fā)展階段，收斂速度和狀態(tài)是目前主要研究問題，而在收斂速度問題上面Q-Learning算法的具有良好的穩(wěn)定性。此外，還可以采用策略與啟發(fā)函數(shù)的優(yōu)化對(duì)Sarsa算法進(jìn)行改良，從而提高收斂速度。

5 結(jié)束語

綜上所述，目前移動(dòng)機(jī)器人路徑規(guī)劃算法的研究雖然取得一定的研究成果，但是普遍都存在一些問題和不足，其中Dijkstra算法適用于局部地區(qū)，A*算法存儲(chǔ)量和計(jì)算量大等，這些問題雖然都進(jìn)行優(yōu)化，但是仍然存在很大的局限性，在未知環(huán)境中的路勁規(guī)劃存在明顯缺陷，因此最好結(jié)合最新的智腦和強(qiáng)化學(xué)習(xí)算法，從而滿足移動(dòng)機(jī)器人的路徑規(guī)劃，而且其具有自主發(fā)展能力，通過模仿和與環(huán)境的相互作用來進(jìn)行行為和計(jì)劃，并通過少量的樣本學(xué)習(xí)，克服強(qiáng)化學(xué)習(xí)中資源浪費(fèi)的缺點(diǎn)，使機(jī)器人具有發(fā)展能力，并不斷提高其智能水平。

基金項(xiàng)目：江蘇省科技廳高校自然科學(xué)面上項(xiàng)目“基于樹莓派控制的安全巡防小車研究”（項(xiàng)目編號(hào)：20KJD520006）。

參考文獻(xiàn)：

[1]萬方，周風(fēng)余，尹磊，等. 基于電勢(shì)場(chǎng)法的移動(dòng)機(jī)器人全局路徑規(guī)劃算法[J]. 機(jī)器人，2019， v.41（06）：48-56.

[2]黃魯， 周非同. 基于路徑優(yōu)化D～*Lite算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 控制與決策， 2020， v.35（04）：112-119.

[3]江明， 王飛， 葛愿，等. 基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究[J]. 儀器儀表學(xué)報(bào)， 2019， 040（002）：113-121.

[4]徐曉蘇， 袁杰. 基于改進(jìn)強(qiáng)化學(xué)習(xí)的移動(dòng)機(jī)器人路徑規(guī)劃方法[J]. 中國慣性技術(shù)學(xué)報(bào)， 2019（3）.

[5]王洪斌， 郝策， 張平，等. 基于A～*算法和人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 中國機(jī)械工程， 2019.