移動機器人路徑規(guī)劃算法研究綜述

穆濤

【摘 要】 機器人路徑規(guī)劃能夠讓機器人在移動過程中高效準確地避開障礙物，是目前機器人領域的研究熱點，而規(guī)劃算法的研究是為了提高機器人路徑規(guī)劃的搜索速度，縮短搜索時間。因此成為了路徑規(guī)劃的核心內容，本文重點將移動機器人路徑規(guī)劃分成全局規(guī)劃和局部規(guī)劃兩類，然后對各類方法所對應的相關算法優(yōu)缺點和改進現狀進行分析和歸納，最后提出了移動機器人未來在路徑規(guī)劃研究的發(fā)展方向。

【關鍵詞】 移動機器人 全局路徑規(guī)劃 局部路徑規(guī)劃 混合路徑規(guī)劃

1.引言

近年來移動機器人目前在工業(yè)、農業(yè)、軍事、服務業(yè)等領域得到廣泛應用。實現機器人在未知環(huán)境下路徑規(guī)劃是一個關鍵技術問題，直接影響著機器人的智能水平。因此研究機器人路徑規(guī)劃對提高機器人的智能化水平、加快我國工業(yè)化進程具有重要的戰(zhàn)略意義。

移動機器人路徑規(guī)劃是指在工作環(huán)境中依照一個或多個評判標準（如時間最短、能耗最少等）尋找出一條從起始點到目標點的最優(yōu)或次優(yōu)的無碰撞路徑。本文根據機器人對環(huán)境信息的掌握程度將路徑規(guī)劃分為全局路徑規(guī)劃和局部路徑規(guī)劃。全局路徑規(guī)劃可獲取全局最優(yōu)或次優(yōu)路徑。局部路徑規(guī)劃可實現實時動態(tài)路徑規(guī)劃，具有較高的靈活性和實時性。下面將對這兩類常用算法進行詳細分析。

2.全局路徑規(guī)劃

2.1 A*算法。A*算法是一種靜態(tài)路網中求解最短路徑的最有效搜索方法，它通過遍歷當前節(jié)點的所有子節(jié)點，然后選擇估價代價最小的節(jié)點作為路徑節(jié)點，基于此節(jié)點再次進行下一步搜索，從而完成整個搜索過程，有搜索節(jié)點多和拐點過多的缺點。王中玉通過改進評價函數的權重比例和改進路徑生成策略，來減少生成路徑中的冗余點和拐點，以此來提高路徑的平滑性，進而提高路徑的搜索效率;李強則通過限制當前節(jié)點只朝目標節(jié)點所處的一個象限進行節(jié)點擴展，有效降低了尋路過程中搜索的節(jié)點數，提高了路徑搜索效率。

2.2 智能仿生算法。智能仿生算法是模擬生物進化和仿自然界動物昆蟲覓食筑巢等行為的算法，主要有遺傳算法、蟻群算法、粒子群算法等。

遺傳算法模擬自然界生物進化過程，通過選擇、交叉、變異等操作搜索最優(yōu)解，可同時處理多個個體，具有較高的自適應性和并行性，但有搜索耗時長，易出現局部最優(yōu)解的缺點。王功亮對適應度函數添加轉彎角度控制因子，把路徑最短和轉彎角度作為路徑個體適應度函數值大小的影響因素，最后規(guī)劃出的路徑軌跡轉彎次數減少且更加平滑;孫波通過對交叉、變異算子自調整策略進行改進，提高了算法的收斂速度。

蟻群算法來自于對螞蟻覓食行為的探索，螞蟻在覓食過程中會在已行走過的道路上留下一種稱為信息素的物質，特定時段上螞蟻遍歷的次數越多信息素濃度就越高，后繼覓食的螞蟻會根據信息素的濃度確定行走路徑，這樣濃度高的路徑會被選為最優(yōu)路徑。但蟻群算法存在計算周期長、收斂慢、易出現局部最優(yōu)等問題。徐宏宇等采用自適應啟發(fā)式函數，增加目標點的吸引力，使路徑快速準確的收斂于最優(yōu)路徑;封聲飛等對初始信息素進行差異化分配并對路徑啟發(fā)信息進行改進，提高了算法收斂速度和螞蟻搜索效率。

粒子群算法是模擬鳥群飛行捕食行為，獲得多維度尋優(yōu)能力的一種算法，它和遺傳算法相似也是從隨機解出發(fā)，通過迭代尋找最優(yōu)解。與遺傳算法相比有實現簡單，收斂快的優(yōu)點，但存在過早收斂的問題，搜索性能對參數的依賴性過也過大，易于陷入局部極小值。魏勇通過引入差分進化算法來動態(tài)調整變異概率和縮放因子，增加種群中個體的多樣性，擴大算法的搜索范圍，從而避免局部最優(yōu)路徑的產生，最后結果驗證了所提方案的有效性和可行性。王志中在路徑規(guī)劃中通過引入了跳出機制和牽引操作，跳出機制保持了種群多樣性和全局搜索能力，牽引操作加快了算法收斂速度，結果顯示規(guī)劃出的路徑在平滑度、規(guī)劃時間上較傳統粒子群算法具有優(yōu)勢。

3.局部路徑規(guī)劃

3.1 動態(tài)窗口法。動態(tài)窗口法主要是在速度（v，w）空間中采取多組速度，并模擬機器人在這些速度下一定時間內的軌跡，在得到多組軌跡后，對于這些軌跡進行評價，選取最優(yōu)軌跡所對應的速度來驅動機器人運動。它有計算不復雜，快速求得最優(yōu)解的優(yōu)點，但是較高的靈活性會極大的降低行駛的平穩(wěn)性。程傳奇提出了一種融合改進A*算法和動態(tài)窗口法的全局動態(tài)路徑規(guī)劃方法，在A*規(guī)劃的全局路徑的基礎上，通過動態(tài)窗口法進行實時動態(tài)路徑規(guī)劃，提高了路徑平滑性及局部避障能力。

3.2 人工勢場法。人工勢場是抽象的人造受力場，通過目標點產生的引力和障礙物產生的斥力的合力來控制移動機器人的運動。該方法結構簡單，便于底層的實時控制，規(guī)劃出來的路徑一般是比較平滑并且安全，但仍存在局部最優(yōu)和易在狹窄通道中動蕩的缺點。陳金鑫針對人工勢場法存在的局部極小缺陷，引入斥力偏轉模型，引導機器人在路徑規(guī)劃時避開局部極小點，再引入斥力增益系數函數，進一步優(yōu)化路徑規(guī)劃中航向改變過大的問題，在解決部分局部極小問題的同時提高了規(guī)劃路徑的質量，解決了靜態(tài)環(huán)境下機器人的路徑規(guī)劃問題;羅強在傳統的人工勢場法中同時引入相對速度和相對加速度因素，實現了機器人在動態(tài)環(huán)境下的自主移動。

3.3 神經網絡法。人工智能領域中的一種新型算法，模擬動物神經網絡行為，進行分布式并行信息處理。神經網絡具有優(yōu)秀的學習能力，但是一些情況下存在錯判的問題。王耀南針對神經網絡在一些情況下存在的路徑非最優(yōu)問題，通過對邊界附近和障礙物之間的路徑點引入了假想的非障礙物相鄰點，增大了激勵輸入，使得路徑點的活性值增大，改進后的生物激勵神經網絡方法適用于實時動態(tài)環(huán)境下的移動機器人路徑規(guī)劃，且全面提升了路徑質量。

4.混合路徑規(guī)劃方法

移動機器人路徑規(guī)劃方法研究雖然取得了重大成果，但在進行局部或全局路徑規(guī)劃時各種算法仍存在一定的局限性，因此混合路徑規(guī)劃算法開始引起大眾關注。相比全局和局部路徑規(guī)劃方法混合路徑規(guī)劃效率更高、實用性更強，目前多采用兩種算法結合的方法彌補各自存在的問題。孫波等在遺傳算法的選擇操作中引入模擬退火思想來提高算法的全局搜索能力，實驗表明改進后的算法效率好、可靠性高;陳爾奎采用改進的遺傳算法進行全局路徑規(guī)劃然后在規(guī)劃好的路徑的基礎上用改進的人工勢場法進行局部動態(tài)避障，解決了局部極小點問題，最后規(guī)劃的路徑的時間和長度都有所縮短?；旌下窂揭?guī)劃算法雖在一定程度上彌補了單個算法的缺陷，但也存在著算法復雜度增加，收斂速度慢等缺點。

5.展望

從移動機器人路徑規(guī)劃的研究現狀以及發(fā)展需求看，未來移動機器人的路徑規(guī)劃研究主要集中在以下四個方面。

1）現有算法的改進。雖然關于路徑規(guī)劃算法很多，并且取得很多成果，但是每種算法都有自己的局限性，不能很好地適應更復雜的環(huán)境，因此對算法進行不斷的創(chuàng)新改進儼然成為了一個成本相對較低突破點;

2）新路徑規(guī)劃算法的研究。隨著科技的發(fā)展，尋找更新更優(yōu)的路徑規(guī)劃算法解決復雜的路徑規(guī)劃問題將會成為一種趨勢。比如近幾年興起的深度學習、強化學習等或是未來新的仿生算法的出現;

3）多機器人協同路徑的研究。隨著機器人工作環(huán)境的不斷擴大、任務的復雜度的增加以及應用范圍的擴大，系統需根據環(huán)境和任務在保證成員之間相互交換信息的前提下高效、快速、準確地組織多個機器人協同并行的完成多個任務;

4）路徑規(guī)劃算法的有效結合。任何的單一路徑規(guī)劃算法都不可能解決所有實際應用中的路徑規(guī)劃問題，特別是面對復雜環(huán)境下的任務，加之研究新算法的難度較大，將出現更多的相互結合的路徑規(guī)劃算法來彌補彼此的不足。

6.總結

本文通過對全局和局部路徑規(guī)劃兩類算法所對應的常用算法的發(fā)展現狀和優(yōu)缺點進行分析和歸納，指出了路徑規(guī)劃算法未來的研究方向。隨著科技的發(fā)展，路徑規(guī)劃技術將會在更多的領域得到應用，并且將深入到我們生活的方方面面。

【參考文獻】

[1] 王坤.基于遺傳算法的移動機器人路徑規(guī)劃研究[D].哈爾濱工業(yè)大學，2012.

[2] 王耀南，潘琪，陳彥杰.改進型生物激勵神經網絡的路徑規(guī)劃方法[J].控制工程，2018.

[3] 陳爾奎，吳梅花.基于改進遺傳算法和改進人工勢場法的復雜環(huán)境下移動機器人路徑規(guī)劃[J].科學技術與工程，2018，18（33）：84-90.

[4] 霍鳳財，遲金，黃梓健.移動機器人路徑規(guī)劃算法綜述[J].吉林大學學報（信息科學版），2018，36（06）：46-54.

[5] 王春穎，劉平，秦洪政.移動機器人的智能路徑規(guī)劃算法綜述[J].傳感器與微系統，2018，37（8）：5-8.

[6] 王志中.基于改進粒子群算法的機器人路徑規(guī)劃[J].制造技術與機床，2018， No.668（02）：159-163.

[7] 朱龍彪，王景良，王輝.一種基于動態(tài)時間窗的泊車系統路徑規(guī)劃方法[J].工程設計學報.2018.

[8] 趙江，張巖，馬澤文.對AGV路徑規(guī)劃A星算法的改進與驗證[J].計算機工程與應用，2018，54（21）：222-228.

[9] 張福海， 李寧， 袁儒鵬. 基于強化學習的機器人路徑規(guī)劃算法[J]. 華中科技大學學報（自然科學版）， 2018， 46（12）：70-75.