典型智能算法在機器人路徑規劃中的研究綜述

羅丹 李丹 殷理杰

摘要：移動機器人的應用越來越廣泛，傳統規劃算法已不能滿足需求，因此智能算法被應用到路徑規劃中。首先，闡述了智能算法的相關信息和數據;其次，闡述了遺傳算法、蟻群算法三種典型智能優化算法的基本思想以及其在機器人路徑規劃問題中的最新研究成果;最后并對未來智能優化算法在機器人路徑規劃方面的研究進行了總結與展望。

關鍵詞：智能優化算法;路徑規劃;機器人;混合算法

中圖分類號：TP242? ? ?文獻標識碼：A

文章編號：1009-3044（2020）26-0180-02

1引言

隨著人工智能的發展，移動機器人被廣泛應用于軍事用途、智能交通等諸多領域。路徑規劃是在環境空間中，根據某一優化目標規劃出一條最優無碰撞路徑[1]。因此，國內外學者對路徑規劃做了諸多研究，常用傳統路徑規劃算法有可視圖法、柵格法、自由空間法。而隨著生活的智能化程度以及對機器人應用領域的增多，當工作空間的環境較為復雜時，傳統算法的搜索效率低下，會存在一些搜索的缺陷。自由空間法隨著障礙物數量的增加，計算的復雜度隨之增加，尋優能力變差。可視圖法的搜索效率很低且無法滿足路徑規劃的實時性要求。

隨著人工智能優化算法的不斷提出，近年來，學者們將遺傳算法、蟻群算法、人工免疫算法等進化算法和群智能優化算法應用到機器人路徑規劃中，并針對局部搜索和全局搜索提出多種改進機制，提高算法的尋優性能。通過查閱將近五年來發表在EI和SCI期刊上的關于機器人路徑規劃研究相關文獻，發現遺傳算法、蟻群算法、粒子群算法在機器人路徑規劃研究的論文數量居前，選取遺傳算法、蟻群算法、粒子群算法三種典型智能算法，對各個智能優化算法的基本思想以及其在機器人路徑規劃問題中的近期研究成果進行了闡述;并對未來智能優化算法在機器人路徑規劃方面的研究進行了總結與展望。

2基于遺傳算法的機器人路徑規劃

2.1遺傳算法的基本思想

遺傳算法是 Holland提出的，并進行了大量研究和推廣。遺傳算法的提出是以生物進化論為基礎，通過模擬自然界遺傳機制和生物進化論而形成的一種過程搜索最優解的算法。核心操作就是選擇、交叉、變異，從而使問題一步步接近最優解。遺傳算法以其具有并行搜索、簡單通用、魯棒性強等優點，由于遺傳算法提出較早，被廣泛地應用到各類問題中。

2.2遺傳算法在機器人路徑規劃上的應用

候仰強等人[2]研究雙機器人協調焊接復雜空間焊縫路徑規劃問題中，提出一種多目標遺傳算法，以焊接質量函數、機器人運動平穩性函數以及雙機器人碰撞函數三個為評價函數為優化目標，以“馬鞍形”空間焊縫為例進行了仿真驗證，結果表明研究方法是可行的。Milad等人[10]將多目標遺傳算法改進之后用到多個機器人路徑規劃問題上，以四機器人路徑規劃為例，仿真結果表明，能為所有機器人找到接近最優的解決方案。李等人[3]提出幾點關于遺傳算法在機器人路徑上的研究展望：可將遺傳算法與多種智能算法相結合，取長補短，解決更多的難題;多機器人協調工作機制是未來研究重點。

3 基于蟻群算法的機器人路徑規劃

3.1蟻群算法的基本思想

蟻群算法是1992年Marco Dorigo在他的博士論文中提出，其基本思想是源于螞蟻在尋找食物過程中通過釋放信息素，利用信息素濃度的大小，經過一段時間后，最終找到一條最短的路徑。蟻群算法初期主要用求解旅行商路徑規劃問題，但也存在收斂速度慢等不足。多年來各國學者提出了諸多改進，以提高其算法的收斂性，并陸續應用到大規模集成電路設計、車輛調度問題、機器人協作問題求解等領域。

3.2 蟻群算法在機器人路徑規劃上的應用

蟻群算法是一種較早提出的啟發式優化算法，在機器人路徑規劃領域得到了廣泛的應用，也獲得了較多的研究成果， Chen等人[4]提出了一種快速兩階段蟻群算法優化機器人路徑規劃問題。基本思想是將啟發式搜索分為兩個階段：預處理階段和路徑規劃階段，克服了基本蟻群算法本身的不足，通過與其他算法相比表明，該算法具有良好的性能和收斂速度。Zeng等人[5]對蟻群算法進行改進，提出一種自由步長的蟻群算法。仿真結果表明，與傳統的蟻群算法相比，自由步長蟻群算法能夠找到更短的路徑，收斂性更好。張瑋等人[6]提出改進煙花-蟻群混合算法求解最優路徑，將改進煙花算法獲得的最短路徑替換蟻群算法中的初始信息素分布，從而使蟻群算法在收斂速度上獲得提高。

4 粒子群算法

4.1遺傳算法的基本思想

粒子群算法（Particle Swarm Optimization，PSO）的思想是源于鳥類覓食，當鳥類在飛向目標食物時，會在速度的大小和方向上不斷模仿鳥群中優秀個體。基本粒子群算法的位置和速度更新公式為：

[vij（t+1）=wvij（t）+c1rand（0，1）[pbestij（t）-xij（t）]+c2rand（0，1）[gbestj（t）-xij（t）]xij（t+1）=xij（t）+vij（t+1）]

其中，用[xij]表示粒子i在第j維空間的位置，用[vij]表示粒子i在第j維空間的速度，[pbestij]表示粒子i在第j維空間的局部最優位置，[gbesti]表示粒子i在群體中全局最優位置，rand（0，1）表示[0，1]之間的隨機數，[c1]和[c2]是常數（表示學習因子），[w]表示慣性權重。

粒子群算法簡單容易操作，收斂速度快等優點，被廣泛應用于系統識別，神經網絡訓練，組合優化問題，多目標約束優化等領域。

4.2粒子群算法在機器人路徑規劃上的應用

陳等人[7]利用了一種 ES-PSO算法，以解決機器人平滑路徑規劃問題;通過仿真結果表明，該算法夠快速準確地尋找到機器人的平滑最優路徑。Das等人[8]結合遺傳算法和蜂群算法中的進化算子對粒子群算法改進提出，通過與DE和IPSO的比較，驗證了該算法的魯棒性和有效性。Fatin等人[9]提出了一種融合局部搜索算法和障礙物檢測與避障策略的混合PSOMFB算法。對該算法在不同環境下進行了測試，仿真結果表明，該方法在復雜動態環境下也能生成最優可行路徑。

5尋優性能比較

綜上所述三種智能優化算法在求解機器人路徑規劃問題時基本算法都存在各自的不足，學者們都在基本算法的基礎上進行了改進研究，現對3種智能優化算法進行性能比較如下。

[算法名稱 算法存在的不足 算法存在的優點 算法改進研究情況 遺傳算法 存在的收斂速度慢;易陷入局部最優 較強的全局搜索能力;易與其他算法混合 與其他算法混合;改進本身操作算子 蟻群算法 在收斂速度慢;易陷入局部最優;種群數量與收斂性的矛盾 具有較強的魯棒性;

較強的全局尋優能力 與其他算法混合;自身參數的調整 粒子群算法 后期收斂速度慢;易陷入局部最優 簡單容易操作;收斂速度快 與其他算法混合;改進粒子速度更新公式 ]

6結論與展望

本文從機器人路徑規劃的智能優化方法中，綜合研究數據和智能優化算法分類，對遺傳算法、蟻群算法、粒子群算法在機器人路徑規劃上的研究成果進行了論述。根據國內外近五年研究現狀，總結機器人路徑規劃問題的研究會集中在以下幾個方面。

1）與其他優化算法混合。智能算法自身都會存在的有一定的不足。當前研究者們已經在不斷地發掘不同的混合算法來解決實際路徑規劃問題，這一研究方向將會更加受到關注。

2）機器人之間的協同路徑規劃。現在的大部分工作環境都是多臺機器人同時工作，因此完成多臺機器人之間的協作，并獲得最優規劃路徑也將是一個熱點和難點。

3）高維復雜環境下的路徑優化應用。在目前的移動機器人路徑規劃優化，考慮二維空間的環境情況較多。而實際許多機器人的工作環境是更加復雜的，如三維工作環境、變化的環境等，學者們針對這類高維復雜的機器人路徑規劃研究較少，這是路徑規劃問題中的一個難點，同時也是以后的研究重點。

參考文獻：

[1] 杜永， 鄭萬群， 劉增環. 關于移動機器人運動路徑規劃仿真研究[J]. 計算機仿真， 2019， 36（1）：331-335.

[2] 侯仰強， 王天琪， 岳建鋒，等. 基于多目標遺傳算法的雙機器人協調焊接路徑規劃[J]. 中國機械工程， 2018， 29（16）：98-103.

[3] 李少波，宋啟松，李志昂，等.遺傳算法在機器人路徑規劃中的研究綜述[J].科學技術與工程，2020，20（2）：423-431.

[4] Chen X，Kong Y Y，Fang X，et al.A fast two-stage ACO algorithm for robotic path planning[J].Neural Computing and Applications， 2013，22（2）：313-319.

[5] Zeng MR，Xi L，XiaoAM.The free step length ant colony algorithm in mobile robot path planning[J].Advanced Robotics， 2016，30（23）：1509-1514.

[6] 張瑋， 馬焱， 趙捍東，等. 基于改進煙花-蟻群混合算法的智能移動體避障路徑規劃[J]. 控制與決策， 2019， 34（2）：114-122.

[7] 陳嘉林， 魏國亮， 田昕. 改進粒子群算法的移動機器人平滑路徑規劃[J]. 小型微型計算機系統， 2019， 40（12）.2550-2555.

[8]? Applied Soft Computing. Multi-robot path planning using improved particle swarm optimization algorithm through novel evolutionary operators [J/OL].http：//www.sciencedirect.com/science/article/pii/S1568494620302520.27 April 2020

[9] AjeilFH，IbraheemIK，SahibM A，etal.Multi-objective path planning of an autonomous mobile robot using hybrid PSO-MFB optimization algorithm[J].Applied Soft Computing，2020，89：106076.

[10] NazarahariM，KhanmirzaE，DoostieS.Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm[J].Expert Systems With Applications， 2019，115：106-120.

【通聯編輯：梁書】