論移動機器人的智能路徑規(guī)劃算法綜述

王承平

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

關(guān)鍵詞：移動機器人 路徑規(guī)劃 啟發(fā)式搜索算法 強化學(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 引文

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

2 Dijkstra算法

2.1 Dijkstra基本原理

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

2.2 Dijkstra算法優(yōu)化

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

3 A*算法

3.1 A*算法基本原理

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

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

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

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

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

5 結(jié)束語

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

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

參考文獻：

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

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

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

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

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