李瓊瓊 布升強 楊家富

（南京林業(yè)大學(xué)機械電子工程學(xué)院，南京210037）

移動機器人路徑規(guī)劃是指在有障礙物的環(huán)境 中，根據(jù)時間最短、距離最短和轉(zhuǎn)折點最少等要求快速規(guī)劃出一條連接起始點、目標(biāo)點且與障礙物無碰撞的路徑［1］。傳統(tǒng)路徑規(guī)劃算法主要有快速搜索隨機樹算法（Rapidly-exploring Random Trees，RRT）［2］、人工 勢 場 法 （Artificial Potential Field，APF）［3］和 可 視 圖 法 （Visibility Graph，VG）［4］等。近些年來，隨著科學(xué)技術(shù)的發(fā)展，新的路徑規(guī)劃算法不斷地涌現(xiàn)，其中以借鑒生物智能理論與方法提出的生物群體智能算法尤為突出。生物群體智能算法因具有原理簡單、穩(wěn)定性良好、能自控制和自適應(yīng)性等特點，在移動機器人、無人機、無人船和無人車路徑規(guī)劃中得到了廣泛地應(yīng)用。

1 群體智能算法及其分類

群體智能算法包括非生物智能算法和生物群體智能算法兩種。非生物智能算法是依據(jù)自然現(xiàn)象或規(guī)律提出的算法，代表算法有煙花爆炸算法（Fireworks Algorithm，F(xiàn)WA）［5］、智能水滴算法（IntelligentWater Drop，IWD）［6］和頭腦風(fēng)暴算法（Brain Storm Optimization Algorithm，BSO）［7］等。生物群體智能算法是受到自然界生物群體智能現(xiàn)象啟發(fā)所提出的一種隨機算法，但是到目前為止沒有明確的定義和統(tǒng)一的分類標(biāo)準(zhǔn)，部分學(xué)者根據(jù)生物群體智能算法的起源，將其籠統(tǒng)地歸納為受到生物群體行為啟發(fā)的啟發(fā)式算法［8］。本文基于生物群體智能算法的原理和路徑搜索機制將其分為功能仿生算法、信息仿生算法、成分（化學(xué)）仿生算法三類。

群體智能算法分類如圖1所示，主要列出了已成功應(yīng)用于移動機器人路徑規(guī)劃中的算法，基于不同的類別，重點討論近些年提出的生物群體智能算法在移動機器人路徑規(guī)劃中的研究成果及算法改進(jìn)策略。

圖1 群體智能算法的分類Fig.1 Classification of Swarm Intelligence Algorithm

2 生物群體智能算法在移動機器人路徑規(guī)劃的應(yīng)用

生物群體智能算法發(fā)展歷史如圖2所示，2002年開始生物群體智能算法逐漸成為研究熱點，新的算法不斷涌現(xiàn)。

圖2 生物群體智能算法發(fā)展歷史Fig.2 Development History of Biological Swarm Intelligence Algorithm

2.1 功能仿生算法

功能仿生算法是模擬生物體的某特定生理功能在覓食、群居、逃脫或其他生物行為中的作用而提出的算法。自然界中蝙蝠利用聲納來探測獵物、避免障礙物，天牛依靠兩個觸角接收到食物氣味的強弱動態(tài)改變自身的運動方向，YANG教授模擬蝙蝠利用超聲波對障礙物或目標(biāo)進(jìn)行探測的行為于2010年提出蝙蝠算法（Bat Algorithm，BA），JIANG基于天牛覓食原理在2017年提出天牛須搜索算法（Beetle Antennae Search Algorithm，BAS）。近年來，功能仿生算法已經(jīng)廣泛地應(yīng)用到視覺跟蹤［9］和資源調(diào)度［10］中，在移動機器人路徑規(guī)劃中的應(yīng)用也逐漸成熟。

2013年Niknam T等［11］基于混沌策略產(chǎn)生蝙蝠的初始種群，賀興時［12］和 Alihodzic［13］分別把模擬退火法、差分簡化策略引入到基本蝙蝠算法中，Khooban等［14］在基礎(chǔ)蝙蝠算法中引入交叉變異算子，以上改進(jìn)策略都在一定程度上增加了種群的多樣性，但增加種群多樣性僅僅能使算法具有更高的分類精度和更強的跳出局部最優(yōu)的能力，難以提高和平衡算法的全局與局部之間的尋優(yōu)能力，為了解決此問題，仉新等［15］利用小生境理論優(yōu)化傳統(tǒng)蝙蝠算法，引入排擠機制和懲罰函數(shù)提高了算法的全局搜索能力，LIU等［16］聚焦于蝙蝠算法的位置改進(jìn)，引入鄰域算子將位置更新改進(jìn)為動態(tài)鄰域操作，但還是存在全局路徑規(guī)劃效率低和精度低等問題。與蝙蝠算法相似，天牛須搜索算法沒有較多的參數(shù)需要調(diào)整，WU Qing等［17］基于生物退回機制（生物在覓食、遷移等過程中具有進(jìn)入死胡同就會后退一段距離并重新進(jìn)行搜索的特性）提出一種改進(jìn)的天牛須搜索算法，改進(jìn)算法沒有明顯縮短路徑長度，但在運行時間上具有非常顯著的優(yōu)勢。為了提高算法的路徑搜索速度和精度，LEIM［18］，趙玉強［19］分別將蝙蝠算法與花朵授粉算法（Flower Pollination Algorithm，F(xiàn)PA）、遺傳算法（Genetic Algorithm，GA）融合，加快了全局搜索時的收斂速度。

功能仿生算法數(shù)學(xué)模型簡單，需要改進(jìn)的參數(shù)較少，對生物種群整體的要求不高，更注重對于個體的位置、速度的更新。兩種功能仿生算法的主要改進(jìn)措施及其優(yōu)點如表1所示，功能仿生算法進(jìn)行路徑規(guī)劃時主要存在容易陷入局部最優(yōu)值、搜索精度低和無法平衡算法的全局和局部的搜索能力等問題。針對以上問題，主要通過引入混沌、差分、變異交叉算子等策略初始化種群，增加種群的隨機性和多樣性以防止算法搜索路徑時陷入局部最優(yōu)并且主要采用融合算法加快全局搜索收斂速度。

表1 主要功能仿生算法Tab.1 Main Function Bionic Algorithms

2.2 信息仿生算法

信息仿生算法是模擬生物體在器官、個體、群體等進(jìn)行信息傳遞和智能行為的基本原理而提出的算法。早在 1995年，美國社會學(xué)家Kenney通過模擬鳥群捕食行為，設(shè)計出粒子群優(yōu)化算 法 （Particle Swarm Optimization，PSO）［20］。2002年，Passino遵循最優(yōu)覓食原則，模擬人體內(nèi)大腸桿菌（E.coli）或粘細(xì)菌（覓食行為，提出細(xì)菌覓食優(yōu)化算法（Bacterial Foraging Optimization Algorithm，BFO），因細(xì)菌覓食算法具有突出的并行搜索優(yōu)點，現(xiàn)已成功地應(yīng)用于圖像處理［21］、資源調(diào)度［22］和機器人技術(shù)［23］等領(lǐng)域。2005年土耳其學(xué)者Karaboga受到蜜蜂覓食行為的啟發(fā)提出了人工蜂群算法（Artificial Bee Colony Algorithm，ABC），已經(jīng)廣泛地應(yīng)用到神經(jīng)網(wǎng)絡(luò)訓(xùn)練中［24］。

PSO的核心是一組位置與速度狀態(tài)方程，計算簡單、易于實現(xiàn)，但該模型的隨機性大、群體智能性低、算法優(yōu)化精度低，粒子易早熟。秦元慶等［25］在2004年采用Dijkstra算法在MAKLINK圖中搜索最短路徑，再使用PSO進(jìn)行二次路徑優(yōu)化，但PSO的全局優(yōu)化能力受到二次優(yōu)化的限制，得到的路徑不是最優(yōu)；SHENG Longyu［26］以遺傳算法、自適應(yīng)遺傳算法為對比算法進(jìn)行車輛路徑規(guī)劃仿真試驗，試驗結(jié)果證明PSO算法所規(guī)劃出的路徑較優(yōu)，說明盡管傳統(tǒng)的PSO算法在規(guī)劃路徑存在優(yōu)化能力受限等問題，但相比遺傳算法仍具有較大的優(yōu)勢。為了提高路徑搜索效率，NIE Zhibin等［27］在基礎(chǔ)PSO算法中引入非線性慣性權(quán)重系數(shù)并融合模擬退火算法；康玉祥等［28］基于梯度下降法中的變量沿著負(fù)梯度方向變化的原則，引入自適應(yīng)粒子位置更新系數(shù)提高了搜索精度，以上改進(jìn)策略旨在提高路徑搜索的效率，卻沒考慮到移動機器人搜索路徑的過程中與障礙物碰撞導(dǎo)致的精度問題。李擎［29］從避障策略出發(fā)，提出“可移動區(qū)域”的概念，將迭代過程中的無效粒子設(shè)置為全局最優(yōu)解的避障策略；GAO Qiong［30］提出非目標(biāo)區(qū)域的障礙物填充、坡度對比的碰撞檢測、碰撞類型的標(biāo)記和避障處理的避障策略；陳秋蓮等［31］采用神經(jīng)網(wǎng)絡(luò)統(tǒng)一靜態(tài)和動態(tài)的障礙物表示和碰撞的模型，快速實現(xiàn)障礙物與路徑的檢測，引入以上避障策略均能快速規(guī)劃出無碰撞的路徑。

BFO包括趨化、復(fù)制和驅(qū)散三個步驟。在趨化過程中，細(xì)菌運動模式包括翻轉(zhuǎn)和前進(jìn)，細(xì)菌向任意方向移動單位步長定義為翻轉(zhuǎn)。CHEN Hanning等［32］通過自適應(yīng)調(diào)整其運行長度單元在局部搜索和全局搜索中取得良好的平衡。對于較復(fù)雜的環(huán)境，BFO算法不僅容易陷入局部最優(yōu)，還具有較差的收斂性，其性能隨著搜索空間維數(shù)的增加和問題復(fù)雜度的增加而大大降低，為了提高算法整體的收斂性和尋優(yōu)能力，LIANG Xiaodan等［33］引入最優(yōu)覓食機制使得搜索主體能最大范圍的搜索周圍的環(huán)境；譚立靜［34］等從群體拓?fù)浣Y(jié)構(gòu)出發(fā)，在傳統(tǒng)BFO算法中引入全面學(xué)習(xí)策略；Nizar［35］利用BFO算法模型中細(xì)菌“翻滾”和“運行”策略，保證機器人能夠在不碰撞任何障礙的情況下完成全局路徑搜索；Yisti Vita Via為每個細(xì)菌選擇消除和擴(kuò)散的概率；Abdi［36］采用APF融合算法將APF中的引力、斥力場的概念引入到基本BFO算法中。最優(yōu)覓食機制、全面學(xué)習(xí)策略和定義消除、擴(kuò)散的概率等策略的引入，擴(kuò)大了算法的搜索空間，避免細(xì)菌個體與障礙物碰撞和逃離局部搜索的狀態(tài)。

ABC參數(shù)少，簡單靈活，具有較好的探索能力，但由于人工蜂群的搜索隨機性大，導(dǎo)致算法在尋優(yōu)的過程中容易陷入局部搜索停滯，無法實時搜索，具有全局搜索能力不強和局部搜索精度不足等缺點。MA Qianzhi等［37］以預(yù)測控制理論為參考，使用一系列滾動窗口中的局部路徑代替全局路徑以滿足實時要求。黎竹娟［38］把機器人路徑規(guī)劃模擬為蜜蜂尋找蜜源，蜂群之間通過信息交流，協(xié)作搜索到全局最優(yōu)路徑。針對ABC算法容易陷入局部最優(yōu)的缺點，LIANG Junhao［39］利用精英個體來保持種群良好的進(jìn)化能力；WANG Song［40］在傳統(tǒng)的人工蜂群算法中引入交叉變異算子以增加種群的多樣；LIZhaoying等［41］從環(huán)境地圖方面改進(jìn)，基于凹多邊形凸分解原理將凹點與其可見頂點連接起來，最后利用人工蜂群算法在所有的連接域中搜索最優(yōu)路徑，但算法迭代到后期時，食物來源幾乎都是最優(yōu)的，位置的有效數(shù)量的差異較小導(dǎo)致路徑搜索速度較慢；Contreras-Cruz［42］把人工蜂群算法應(yīng)用到多移動機器人之間的協(xié)調(diào)運作中；張林等［43］將障礙物邊緣平滑化以減少位置參數(shù)，在原算法中引入自適應(yīng)搜索因子以提高算法的收斂速度和搜索精度。

信息仿生算法具有普遍適用性，模型簡單且易于實現(xiàn)，但算法控制參數(shù)較多且沒有明確的取值標(biāo)準(zhǔn)，只能依據(jù)經(jīng)驗，導(dǎo)致算法在不同的搜索時期不能匹配到最優(yōu)參數(shù)，且因傳統(tǒng)的信息仿生算法缺乏信息交流，收斂緩慢且易陷入局部最優(yōu)，研究學(xué)者多數(shù)以引入精英策略、使用融合算法增加種群的多樣性，避免算法在搜索路徑時陷入局部最優(yōu)；通過引入自適應(yīng)搜索機制、改進(jìn)算法參數(shù)等辦法擴(kuò)大算法的搜索范圍，減少無效搜索的次數(shù)，提高了算法的收斂速度和搜索精度。在眾多的應(yīng)用領(lǐng)域中，信息仿生算法大多數(shù)還停留在靜態(tài)、單目標(biāo)問題的處理上，在動態(tài)和多目標(biāo)的問題的求解應(yīng)用較少。主要信息仿生算法及比較參見表2。

表2 主要信息仿生算法Tab.2 Main Information Bionic Algorithm

2.3 成分仿生算法

成分仿生算法是從化學(xué)的角度模擬生物體的行為與功能，通過模擬昆蟲分泌、釋放微量化學(xué)物質(zhì)來實現(xiàn)覓偶、聚集等活動行為提出的算法。主要成分仿生算法可參見表3。1992年意大利學(xué)者DORIGO M模擬蟻群覓食活動規(guī)則提出了蟻群算法（Ant Colony Optimization，ACO）；2009年劍橋大學(xué)的楊新社教授模擬螢火蟲群體發(fā)光、趨光行為提出了螢火蟲算法（Firefly Algorithm，F(xiàn)A），由于光亮度低的螢火蟲總是受到亮度強的螢火蟲的吸引，在螢火蟲個體移動的過程中實現(xiàn)對解空間地探索，從而完成算法尋優(yōu)。由于生物體分泌的化學(xué)物質(zhì)具有揮發(fā)性，成分仿生算法在路徑搜索性能上易出現(xiàn)過早的停滯狀態(tài)，無法發(fā)現(xiàn)更優(yōu)的路徑，許多研究學(xué)者對傳統(tǒng)成分仿生算法進(jìn)行改進(jìn)。

表3 主要成分仿生算法Tab.3 Main Composition Bionic Algorithm

屈鴻［44］通過修改蟻群算法中信息素的更新步驟、調(diào)整轉(zhuǎn)移概率，限定信息素濃度的上下界限，解決了由于信息素?fù)]發(fā)或更新引起的局部搜索停滯等問題。當(dāng)外界環(huán)境較為復(fù)雜時，移動機器人可能會陷入死鎖狀態(tài)，且隨著局部信息素的更新，會出現(xiàn)死角邊緣周圍的信息素不斷生長，螞蟻將很容易在下一次迭代中重復(fù)選擇死角路徑，如果保持這樣，就會延遲找到最短的路徑，甚至找不到最短的路徑，ZHU Xiaoguang等［45］為了避免移動機器人路徑死鎖，建立了一個死角表。王曉燕等［3］使用懲罰功能對死鎖邊上信息素進(jìn)行懲罰，使螞蟻擺脫束縛，在當(dāng)前路徑上重新選擇節(jié)點進(jìn)行搜索。劉建華［46］在蟻群算法中融合APF算法，全局路徑的信息素沿著勢場合力的方向四周擴(kuò)散，信息素分布均勻，使蟻群向具有較高適應(yīng)值的空間搜索，減少螞蟻搜索過程中“迷失”的數(shù)量，但所規(guī)劃出的路徑轉(zhuǎn)折點數(shù)量較多，收斂速度過快導(dǎo)致路徑不是最優(yōu)；2018年LIAO Jinquan［47］提出人工免疫和蟻群融合算法，人工免疫算法中的抗體靶向攻擊和免疫系統(tǒng)的自動調(diào)節(jié)功能給出正反饋信息，然后利用蟻群算法進(jìn)行局部構(gòu)建，解決了路徑規(guī)劃實驗中局部優(yōu)化但未達(dá)到全局最優(yōu)的問題。馬小陸［48］將跳點算法和蟻群算法相融合，由于蟻群算法自身的正反饋機制，搜尋解的質(zhì)量在增加，但信息素隨著時間不斷揮發(fā)，導(dǎo)致搜尋解的選擇性降低，為了解決蟻群算法搜索能力和收斂速度之間的矛盾，Saroj Kumar等［49］在傳統(tǒng)的蟻群算法上融合混合正余弦算法，利用正余弦函數(shù)的震蕩性趨于全局最優(yōu)解。蟻群算法的核心是信息素濃度的更新和轉(zhuǎn)移策略的改進(jìn)，與蟻群算法相似，螢火蟲算法的核心是光吸收系數(shù)和算法參數(shù)，LIU Chang［50］在基本螢火蟲算法中引入自適應(yīng)隨機參數(shù)和自適應(yīng)吸光系數(shù)、Arup Kumar Sadhu等［51］通過 Q學(xué)習(xí)策略控制隨機化螢火蟲算法參數(shù)和光吸收系數(shù)、薛晗等［52］提出一種基于文化算法框架的螢火蟲優(yōu)化算法，可以通過調(diào)整FA的隨機化參數(shù)和光吸收系數(shù)實現(xiàn)平衡探索候選解空間和開發(fā)新搜索方向的功能，但僅僅對參數(shù)進(jìn)行改進(jìn)，算法易陷入局部最優(yōu)，若將路徑長度作為唯一的目標(biāo)函數(shù)，每一步都要計算步長及坐標(biāo)，對于大范圍的路徑規(guī)劃來說需要較大的計算量且不能保證找到最優(yōu)路徑。為了解決路徑不是最優(yōu)問題，徐曉光等［53］通過使用小生境螢火蟲算法，得到多條優(yōu)化路徑以便二次擇優(yōu)；Alejandro［54］提出多目標(biāo)（路徑安全性、路徑長度和路徑平滑）函數(shù)的螢火蟲算法，提高了路徑的規(guī)劃質(zhì)量。

成分仿生算法結(jié)構(gòu)單一，算法核心都是改進(jìn)某類化學(xué)分泌物的揮發(fā)速度和更新步驟，相應(yīng)地，針對成分仿生算法的改進(jìn)較為單一，對于蟻群算法，主要是采用修改信息素的更新步驟、調(diào)整其轉(zhuǎn)移概率；對于螢火蟲算法，主要是改進(jìn)隨機參數(shù)和吸光系數(shù)，但僅僅改進(jìn)成分仿生算法的參數(shù)不能使其搜索路徑的性能有較大提升，最優(yōu)的策略是在改進(jìn)參數(shù)的前提下，融合其他算法以提高算法的整體性能。

3 生物群體智能在移動機器人路徑規(guī)劃中的應(yīng)用性能對比

每類生物群體智能算法在進(jìn)行路徑規(guī)劃時都會存在自身的一些不足之處，綜上所述，得出的結(jié)果如表4所示，可以看出功能仿生算法、信息仿生算法和成分仿生算法都存在著預(yù)先設(shè)定參數(shù)的問題，并且結(jié)果嚴(yán)重依賴參數(shù)的選取，往往會因為參數(shù)的取值問題而影響到最終的路徑規(guī)劃結(jié)果。功能仿生算法和信息仿生算法都具有容易陷入局部最優(yōu)值的缺點。成分仿生算法的控制參數(shù)最少，但搜索機制不易改進(jìn)，路徑規(guī)劃結(jié)果較差?；谏鲜龇治觯畔⒎律惴ǖ穆窂揭?guī)劃效果相比于其他兩類算法較好，雖然信息仿生算法需要設(shè)定的參數(shù)較多，但通過引入自適應(yīng)搜索機制、融合其他算法能極大地提高算法搜索路徑的性能。

表4 各分類算法在移動機器人路徑規(guī)劃應(yīng)用中的對比Tab.4 Comparison of Different Classification Algorithms in Mobile Robot Path Planning

4 生物群體智能算法研究趨勢

依據(jù)生物群體智能算法的原理和機制將其分為功能仿生算法、信息仿生算法和成分仿生算法三類。在研究分析各類算法的基礎(chǔ)上，對應(yīng)用于移動機器人路徑規(guī)劃的算法存在的問題、解決方案和取得的優(yōu)化效果進(jìn)行綜合比較，考慮到移動機器人路徑規(guī)劃的準(zhǔn)確性和實時性的要求，未來生物群體平衡自適應(yīng)搜索算法、邊緣算法和云網(wǎng)融合技術(shù)將是移動機器人路徑規(guī)劃的研究熱點。

生物學(xué)家利用Logistic方程研究生物種群生長規(guī)律，發(fā)現(xiàn)只有當(dāng)種群數(shù)量的變化符合Logistic方程規(guī)律時整個種群才能維持平衡。相應(yīng)的，生物群體智能算法是模擬生物群體智能行為提出的算法，在進(jìn)行路徑規(guī)劃尋優(yōu)時，只有設(shè)置算法中的種群數(shù)量符合Logistic方程曲線變化規(guī)律，再結(jié)合自適應(yīng)搜索策略才能保證算法在不同的搜索階段均能匹配到最優(yōu)參數(shù)，才能根據(jù)環(huán)境變化信息時時更新搜索機制以達(dá)到最佳路徑尋優(yōu)效果。

生物群體智能算法在進(jìn)行路徑規(guī)劃時需要大量的復(fù)雜計算，計算過程緩慢導(dǎo)致算法搜索策略不能及時更新從而無法適應(yīng)環(huán)境的變化。邊緣算法是在高寬帶、時間敏感型和物聯(lián)網(wǎng)集成的背景下發(fā)展起來的一種新的計算模式，邊緣算法能夠?qū)⒊绦虿糠忠苿拥礁浇脑O(shè)備中進(jìn)行處理，提高數(shù)據(jù)處理速度，有力地解決移動機器人運算能力不足的問題，是移動機器人路徑規(guī)劃算法最重要的發(fā)展趨勢之一。

隨著云計算、大數(shù)據(jù)等新興信息技術(shù)的發(fā)展和5G建設(shè)的全面啟動，極大地解決了終端計算能力問題，未來網(wǎng)絡(luò)基礎(chǔ)設(shè)施和流量布局將會由一個個數(shù)據(jù)中心決定，近些年來在云網(wǎng)融合背景下以實現(xiàn)網(wǎng)絡(luò)、存儲、數(shù)據(jù)計算、資源調(diào)度和任務(wù)分配等功能。云網(wǎng)融合技術(shù)通過云計算和網(wǎng)絡(luò)連接等能實現(xiàn)對移動機器人各性能參數(shù)的實時監(jiān)測，對變化的地圖環(huán)境及時調(diào)整行駛策略。