羅丹 李丹 殷理杰

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

關(guān)鍵詞：智能優(yōu)化算法;路徑規(guī)劃;機(jī)器人;混合算法

中圖分類號：TP242? ? ?文獻(xiàn)標(biāo)識碼：A

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

1引言

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

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

2基于遺傳算法的機(jī)器人路徑規(guī)劃

2.1遺傳算法的基本思想

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

2.2遺傳算法在機(jī)器人路徑規(guī)劃上的應(yīng)用

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

3 基于蟻群算法的機(jī)器人路徑規(guī)劃

3.1蟻群算法的基本思想

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

3.2 蟻群算法在機(jī)器人路徑規(guī)劃上的應(yīng)用

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

4 粒子群算法

4.1遺傳算法的基本思想

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

[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維空間的局部最優(yōu)位置，[gbesti]表示粒子i在群體中全局最優(yōu)位置，rand（0，1）表示[0，1]之間的隨機(jī)數(shù)，[c1]和[c2]是常數(shù)（表示學(xué)習(xí)因子），[w]表示慣性權(quán)重。

粒子群算法簡單容易操作，收斂速度快等優(yōu)點(diǎn)，被廣泛應(yīng)用于系統(tǒng)識別，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，組合優(yōu)化問題，多目標(biāo)約束優(yōu)化等領(lǐng)域。

4.2粒子群算法在機(jī)器人路徑規(guī)劃上的應(yīng)用

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

5尋優(yōu)性能比較

綜上所述三種智能優(yōu)化算法在求解機(jī)器人路徑規(guī)劃問題時基本算法都存在各自的不足，學(xué)者們都在基本算法的基礎(chǔ)上進(jìn)行了改進(jìn)研究，現(xiàn)對3種智能優(yōu)化算法進(jìn)行性能比較如下。

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

較強(qiáng)的全局尋優(yōu)能力 與其他算法混合;自身參數(shù)的調(diào)整 粒子群算法 后期收斂速度慢;易陷入局部最優(yōu) 簡單容易操作;收斂速度快 與其他算法混合;改進(jìn)粒子速度更新公式 ]

6結(jié)論與展望

本文從機(jī)器人路徑規(guī)劃的智能優(yōu)化方法中，綜合研究數(shù)據(jù)和智能優(yōu)化算法分類，對遺傳算法、蟻群算法、粒子群算法在機(jī)器人路徑規(guī)劃上的研究成果進(jìn)行了論述。根據(jù)國內(nèi)外近五年研究現(xiàn)狀，總結(jié)機(jī)器人路徑規(guī)劃問題的研究會集中在以下幾個方面。

1）與其他優(yōu)化算法混合。智能算法自身都會存在的有一定的不足。當(dāng)前研究者們已經(jīng)在不斷地發(fā)掘不同的混合算法來解決實(shí)際路徑規(guī)劃問題，這一研究方向?qū)邮艿疥P(guān)注。

2）機(jī)器人之間的協(xié)同路徑規(guī)劃?，F(xiàn)在的大部分工作環(huán)境都是多臺機(jī)器人同時工作，因此完成多臺機(jī)器人之間的協(xié)作，并獲得最優(yōu)規(guī)劃路徑也將是一個熱點(diǎn)和難點(diǎn)。

3）高維復(fù)雜環(huán)境下的路徑優(yōu)化應(yīng)用。在目前的移動機(jī)器人路徑規(guī)劃優(yōu)化，考慮二維空間的環(huán)境情況較多。而實(shí)際許多機(jī)器人的工作環(huán)境是更加復(fù)雜的，如三維工作環(huán)境、變化的環(huán)境等，學(xué)者們針對這類高維復(fù)雜的機(jī)器人路徑規(guī)劃研究較少，這是路徑規(guī)劃問題中的一個難點(diǎn)，同時也是以后的研究重點(diǎn)。

參考文獻(xiàn)：

[1] 杜永， 鄭萬群， 劉增環(huán). 關(guān)于移動機(jī)器人運(yùn)動路徑規(guī)劃仿真研究[J]. 計(jì)算機(jī)仿真， 2019， 36（1）：331-335.

[2] 侯仰強(qiáng)， 王天琪， 岳建鋒，等. 基于多目標(biāo)遺傳算法的雙機(jī)器人協(xié)調(diào)焊接路徑規(guī)劃[J]. 中國機(jī)械工程， 2018， 29（16）：98-103.

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

[4] Chen X，Kong Y Y，F(xiàn)ang 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ìn)煙花-蟻群混合算法的智能移動體避障路徑規(guī)劃[J]. 控制與決策， 2019， 34（2）：114-122.

[7] 陳嘉林， 魏國亮， 田昕. 改進(jìn)粒子群算法的移動機(jī)器人平滑路徑規(guī)劃[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 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.

【通聯(lián)編輯：梁書】