改進螢火蟲算法求解多機器人路徑規劃

摘 要：為解決多機器人在靜態環境中的路徑規劃問題，以路徑長度為優化目標模型，并針對此模型設計了多機器人螢火蟲算法（MR-FA）。首先，考慮到路徑安全性對環境中的障礙物采取擴張操作，設計初始化規則以提高生成初始種群的效率；其次，根據算法的連續性原理及特點，設計個體等長策略將維度不一致的個體轉變為等維度個體以便于螢火蟲的移動更新，并對移動更新后的不可行解采取路徑修正策略；然后對規劃出的每個機器人的移動路徑進行碰撞檢測，同時針對機器人不同的碰撞情況設計相應的避碰策略，即暫停—回退策略（PFS）、局部路徑重規劃策略（LPRS）；最后，為驗證MR-FA的有效性，在三組環境中進行仿真實驗并與其他三種算法進行對比，綜合得出MR-FA在解決多機器人路徑規劃時更有優勢。

關鍵詞：多機器人路徑規劃； 避障策略； 多機器人螢火蟲算法

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

文章編號：1001-3695（2023）03-025-0800-05

doi： 10.19734/j.issn.1001-3695.2022.07.0369

Improved firefly algorithm for multi-robot path planning

Yu Fuzea， Pan Dazhia，b

（a.School of Mathematics amp; Information， b.Institute of Computing Method amp; Application Software， China West Normal University， Nanchong Sichuan 637009， China）

Abstract：In order to solve the path planning problem of multi-robots in static environment， the path length was used as the optimization target model， and this paper designed a multi-robot firefly algorithm（MR-FA） for this model. Firstly， considering the path security to expand the obstacles in the environment， MR-FA designed an initialization rule to improve the efficiency of generating the initial population. Secondly， according to the continuity principle and characteristics of the algorithm， it designed an individual isometric strategy to convert individuals with inconsistent dimensions into equal-dimensional individuals to facilitate the mobile update of fireflies， and designed initialization rules to improve the efficiency of generating initial populations. Then， it performed collision detection on the planned movement path of each robot， and designed corresponding collision avoidance strategies for different collision situations of robots： pause-fallback strategy， local path replanning strategy. Finally， this paper carried out the simulation experiments in three groups of environments and compared the effectiveness of MR-FA with the other three algorithms. It can be concluded that MR-FA has more advantages in solving multi-robot path planning.

Key words：multi-robot path planning; obstacle avoidance strategy; multi-robot firefly algorithm

0 引言

移動機器人在生產生活中的作用越來越重要，由于工作任務逐漸多元化、復雜化以及智能技術的不斷提升，單個機器人難以完成任務或者效率低下，此時就需要多個機器人協同工作，多機器人系統相對于單機器人系統具有許多顯而易見的優勢［1］ ，同時隨著無線通信技術、傳感器技術、嵌入式計算技術的不斷發展，多機器人系統的研究受到了廣泛關注［2］ 。多機器人路徑規劃是其重要研究內容之一，其主要任務是為群體中的每一個機器人找到一條從各自的起點到終點的最優路徑，并保證機器人之間、機器人與障礙物之間無碰撞［3］ 。

多機器人路徑規劃是一個NP-hard問題，近年來不少學者已經提出了相關算法及模型來求解。例如，屈立成等人［4］針對傳統二維柵格地圖中機器人只能在二維坐標空間上進行區分而無法表現其在時間維度上的發展變化，提出了三維時空地圖和運動分解的多機器人路徑規劃算法；Das等人［5］對粒子群算法進行改進并與其他算法融合用于求解多機器人路徑規劃，提出粒子群—微分攝動速度算法（PSO-DV）來求解多機器人路徑規劃，隨后提出了改進粒子群—進化算法 （IPSO-EOPs）［6］；Paikray等人［7］在粒子群算法中融入正余弦算子，在復雜和未知工作空間中為每個機器人生成無碰撞最優軌跡；Tian等人［8］提出了一種跳躍機制粒子群算法（JPSO）規劃機器人的移動路徑，并為避免機器人之間的碰撞設計了安全間隙避障算法（SGOA）；Thabit等人［9］將路徑長、光滑度、安全性作為目標引入概率窗的概念，結合機器人的傳感信息及經驗給每個可達位置分配概率以提高粒子群算法的規劃效率；Das 等人［10］提出了一種在動態環境下利用改進的引力搜索算法求解多機器人軌跡；陳南凱等人［11］提出了一種改進的生物激勵神經網絡算法用于求解多機器人協同全區域覆蓋巡檢以及多任務點協同巡檢。

在實現多機器人在同一空間中的移動工作任務時，用群體智能算法求解時大多將算法離散化，而機器人所在空間也將離散化，這將會導致規劃路徑的精確性降低等問題。本文保留螢火蟲算法的連續特性，同時利用螢火蟲算法具有原理簡單、參數少、易于實現等優點，以多機器人移動的路徑總長度為目標，設計了一種基于螢火蟲算法的多機器人路徑規劃算法，使用改進的螢火蟲算法得到多機器人移動的連續全局最優路徑，同時為避免出現機器人之間的碰撞，設計了兩種避障策略進行調節，并通過仿真實驗分析本文算法的性能。

1 環境建模及基本螢火蟲算法

1.1 環境建模

在現實生產生活中，機器人都具有一定的尺寸，那么機器人在執行任務過程中的避碰就是一個值得注意的問題，為避免機器人與任務空間中的障礙物產生碰撞，本文對障礙物進行膨脹操作，將障礙物大小在自身原始大小的基礎上進行擴張，擴張大小為機器人的半徑大小，如圖1所示。

1.2 基本螢火蟲算法

2008年Yang［12］根據自然界中螢火蟲的發光行為提出了螢火蟲算法（firefly algorithm，FA），FA作為一種新的元啟發式算法被大范圍地應用于多個領域。螢火蟲利用自身發出的光作為信號吸引其他螢火蟲，而螢火蟲的吸引力由發光的節奏、頻率和被觀察到的時間決定，當一個螢火蟲光亮較高時就有可能吸引另一個光亮較弱的螢火蟲向其移動，最亮的螢火蟲則做隨機移動，在此過程中螢火蟲自身位置隨之改變。若將螢火蟲所在位置表示問題空間的可行解，以螢火蟲發光的亮度為目標函數，通過螢火蟲群體的移動實現對目標函數的尋優。

2 改進的螢火蟲算法

2.1 個體編碼及目標函數

本文按照圖1的方式對環境進行建模，鑒于FA是一種連續算法，所以將個體編碼設定為p={（x1，y1），（x2，y2），…，（xn，yn）}，其中xi、yi（i=1，2，…，n）分別表示路徑節點的橫縱坐標，（xs，ys）、（xe，ye）分別為機器人路徑的起止點坐標。

為使得生成的個體均可行，利用式（1）～（3）定義個體的生成，當節點（xi，yi）與終點直接連接的線段為安全路徑時停止。

其中：rand1、rand2∈（0，1）；disi，e為（xi，yi）到終點的距離；disi，ecos（theta）、disi，esin（theta）為機器人當前位置出發在x、y方向上的最大移動距離，使用disi，e的目的在于使機器人在下一步的選擇上更趨近終點。由式（2）可知λ∈（-1，1），這樣促使機器人對于下一步的選擇更具隨機性，擴大了行走選擇范圍，也有利于避開障礙物。此種初始方式得到的個體長度不一致，相對于等長個體而言，可避免由于間隔劃分不合適而導致無法形成可行個體，以至于要多次嘗試劃分合適間隔的問題。機器人路徑規劃常選擇的目標是從起點到目標點的過程中機器人所走路徑長，因此本文目標設定為所有機器人行走總路程。

其中：nR為機器人數量。

2.2 螢火蟲更新規則

FA的核心思想是在螢火蟲感知域內，亮度高的螢火蟲吸引亮度比它低的向其移動，移動后的螢火蟲位置得到更新，而種群中亮度最高的螢火蟲則做隨機飛行。FA的數學模型包括相對亮度、吸引力、移動更新方式三個部分。

由于螢火蟲的絕對亮度與目標函數息息相關，螢火蟲的絕對亮度由式（5）定義，相對亮度由式（6）定義。

其中：Bij、rij分別為個體i、j間的相對亮度、距離；γ∈（0，1）為光吸收因子。螢火蟲之間的吸引強度是相對的，由其亮度及rij決定，螢火蟲的吸引力由式（7）定義。

其中：β0為r=0時的吸引力。當螢火蟲i被另一只更明亮的螢火蟲j引導，移動后的位置由式（8）定義。

其中：α是隨機參數；rand∈（0，1）。同時為避免種群中的某些個體在多次循環后陷入局部最優，設定一個停滯閾值stop，stop為正整數，如果個體停滯的次數超過閾值，則將此個體按照式（9）的方式更新，其中，pbest為全局最優個體。

2.3 個體等長及修正策略

螢火蟲群體在經過連續化變換后得到的個體不一定為可行解，因此采取相應的策略將不可行解轉換為可行解，本文采取Hidalgo-Paniagua等人［13］提出的路徑安全操作（path safety operator，PaSO）對不可行路徑進行修正。

2.4 路徑增強策略

為減少路徑節點的數量以及增強路徑的光滑度，同時為提高個體等長策略操作效率，設計刪除操作和光滑操作對個體路徑進行優化。刪除操作將路徑中多余的節點刪除，光滑操作縮短路徑長的同時增強路徑光滑度，有利于降低機器人能耗，具體操作如圖3所示。

2.5 多機器人避障策略

對于單個機器人而言，只需從起點安全抵達終點即可。當在同一環境中工作的機器人數量增加且各個機器人的起止點又不同時，在用MR-FA求解得到每個機器人的最優路徑后，可能會存在機器人沿著規劃的路徑行走過程中與其他機器人發生碰撞的問題。從路徑規劃上考慮，只有當兩個機器人的移動路徑存在交點或者相同路徑段時才有可能發生碰撞，因此定義一個安全距離2r來確保運行過程的安全性，當li-lj＜2r時則判定機器人i、j會發生碰撞，其中li、lj為機器人從起點抵達路徑交叉點走過的路徑長。

針對機器人之間的碰撞，現有優先級法［14］ 、交通規則法、幾何修正法等對其進行調整。目前常用的是優先級法，每個機器人都有一個級別，當兩個機器人將要發生碰撞時，低級別機器人會在安全區域內暫停行走，直到高級別機器人通過碰撞域。文獻［15，16］細致地分析了機器人碰撞的多種情況，包括路徑點沖突、路徑段沖突、目標點占道沖突，并設計了多種避撞策略。經過綜合分析，筆者認為文獻［15，16］中的機器人碰撞類型分類過于復雜、避撞策略過多，只需將機器人碰撞情況分為兩種情況并設計兩個多機器人避碰策略（multi-robot collision avoidance strategy，MR-CAS）：暫停—回退策略（pause-fallback strategy，PFS）解決可通過暫停而避免的交叉點碰撞問題；局部路徑重規劃策略（local path replanning strategy，LPRS）解決無法通過暫停而造成的路徑點碰撞問題。

1）PFS 如圖4所示，機器人A、B在行駛過程中，根據檢測機制可知機器人A、B會在交叉點O處碰撞，根據文獻［15］計算出臨界位置分別為C、D處。若B的優先級高于A，根據優先級原理，A就在C處等待，當機器人B到D′位置時，A再沿著路線移動，如圖4（a）所示；若A的優先級高于B，且當B暫停時A沿著路徑移動也會與B碰撞，B就采取回退策略，當B退回到安全區域后A再沿著路線移動，直到A到達C′點，B再移動，如圖4（b）所示。

2）LPRS 如圖5（a）所示，當機器人A的終點C到機器人B的移動路徑距離小于安全距離，并且A到達終點后B還未通過此位置，就意味著B在移動過程中定會與A碰撞，此時就采取LPRS。如圖5（b）所示，D為起點，而對于下一個節點的選擇方式以D為圓心，r為半徑構建圓，將圓周進行m等分，則得到m-1個可選擇的節點，采取式（10）（11）計算每個可行節點的nf值，選擇nf值最小的作為下一個節點，直到當前節點能直接無障礙地到達局部路徑的終點，并對路徑采取優化操作。如圖5（a）所示，當A已經到達終點C，而此時B才移動到位置E處，那么以C為圓心，2r為障礙物半徑，采取LPRS得到由D到D′的路徑為D→e1→e2→D′→…→終點，優化后的路徑為E→Q→…→終點。

2.6 MR-FA算法步驟

為提高螢火蟲算法在多機器人路徑尋優過程中的性能，本文提出的多機器人螢火蟲算法（multi-robot firefly algorithm，MR-FA）如算法2所示。

3 仿真實驗及分析

為驗證MR-FA的有效性，將MR-FA與基本螢火蟲算法、JPSO［8］、IGSA［10］等算法在不同的環境中進行對比實驗，每個算法測試20次，不同環境中每個機器人的起止點如表1所示。對于算法參數的設定為：種群數50、最大迭代次數100、停滯次數stop=10。在環境1、2中進行測試，機器人半徑為0.1。首先，通過實驗仿真可得到如表2所示的平均最優路徑長，根據數據對比可知MR-FA規劃的路徑總體上優于其他三種算法。其次，圖6為四種算法在環境1中規劃的最優路徑，MR-FA、FA、JPSO和IGSA規劃的路線交點分別有8、8、10和7個，但并不存在碰撞點，同樣地，如圖7所示四種算法在環境2中規劃的路線交點分別有12、12、10、12個，但是依舊不存在碰撞點。表3為圖6、7中的最優路徑長，表4為各算法多次測試得到的最差路徑長的對比，綜合對比易知MR-FA規劃的路徑明顯優于其他三種算法，并且通過數據對比易知其收斂精度明顯高于其他算法。最后，對四種算法進行時間復雜度的分析可知，MR-FA、FA、JPSO、IGSA的時間復雜度均為m_iter×n×dim，其中n為個體數量，dim為個體長度。

上述兩組實驗已經驗證了MR-FA在多機器人路徑規劃上的有效性，接下來為驗證避障策略MR-CAS的優勢，在環境3中進行測試并與文獻［7］中設計的避障策略SGOA進行對比，機器人的起止點設定為表1中的環境3，半徑為0.5。

首先，MR-FA、JPSO分別規劃可得到如圖8（a）（b）所示的最優路徑，以及對應如表5所示的最優路徑長；其次，圖8（a）中MR-FA規劃的路徑有10個交叉點，根據碰撞預測機制檢測到在N點處機器人B和D會發生碰撞，如圖8（b）所示JPSO規劃的路徑有12個交叉點，但在M點處機器人B和D會發生碰撞。根據避障策略，可分為以下兩種情況：

a）若機器人B、D優先級大小為B＜D，如圖8（c）所示，根據PFS原理機器人B需在N1處暫停，當機器人D通過碰撞域到達N3后B再移動，又因為機器人E在到達終點時機器人A才到N4處，如果機器人A按照原來路徑前進就會在N5處與E碰撞，所以根據LPRS原理對機器人A的路徑進行修正，機器人A從N4點起沿著曲線路徑移動。同理根據SGOA，如圖8（d）所示，機器人B在N1處暫停，等待機器人D通過后再前進；因為機器人E在到達終點后，機器人A才到N4點，如果機器人A按照原來路徑前進，就會在N5處與E碰撞，因此對機器人A的路徑進行修正，機器人A從N5點起沿著曲線移動。

b）若機器人B、D優先級大小為B＞D，如圖8（e）所示，根據PFS原理D需在N2處暫停，但是在此處暫停也會導致B與其相撞，因此D需要退回到N6處，當機器人B通過碰撞域到達N3后D再移動，又因為機器人E在到達終點時機器人A才到N4處，如果機器人A按照原來路徑前進就會在N5處與E碰撞，因此按照LPRS原理對機器人A的路徑進行修正，機器人A從N4點起沿著曲線路徑移動；同理根據SGOA機制，如圖8（d），D在N6處暫停，等待機器人B通過后再前進，機器人A從N5點起沿著曲線移動。

最后，經過修正后的機器人移動路徑長如表6所示，可得出結論：不論是在路徑修正前還是修正后，MR-FA規劃的機器人移動路徑在路徑長上都優于JPSO算法。

綜上所述，MR-FA可規劃出不同規格環境的最優路徑，雖然在時間復雜度上與其他三種算法一樣，但是規劃結果在路徑長度方面相較于其他三種算法都有所提高，具有更好的尋優能力，并且本文提出的避障策略能更好地實現避障，并且規劃的避障路徑更優。

4 結束語

針對多機器人路徑規劃問題，以路徑長為決策目標，提出MR-FA用于求解，設計了個體等長策略、路徑增強策略、多機器人避碰策略等。對于該問題模型，本文先規劃出每個機器人的最優路徑，再對路徑進行碰撞檢測，對預測到會產生碰撞的路徑采取相應的暫停—回退策略（PFS）或者局部路徑重規劃策略（LPRS）。在不同的場景中對算法性能進行測試，并與FA、JPSO、IGSA三種算法進行對比分析，根據結果易知MR-FA在多機器人路徑規劃上更具優勢，并且若是機器人之間會發生碰撞，那么經過PFS、LPRS修正后的路徑能更高效地實現避障。當然，本文的決策目標考慮單一，缺乏對動態環境、位置環境的考慮，這將是后續研究的重點及改進之處。

參考文獻：

［1］丁皓， 劉浩宇， 莊逸， 等. 基于四輪差速模型的多機器人路徑規劃［J/OL］. 控制工程.（2021-08-12）. https：//doi.org/10.14107/j.cnki.kzgc.20210058. （Ding Hao， Liu Haoyu， Zhuang Yi， et al. Multi-robot path planning based on four-wheel differential speed model［J/OL］. Control Engineering of China.（2021-08-12）. https：//doi.org/10.14107/j.cnki.kzgc.20210058.）

［2］顧軍華， 孟慧婕， 夏紅梅，等. 基于改進蟻群算法的多機器人路徑規劃研究［J］. 河北工業大學學報， 2016，45（5）： 28-34. （Gu Junhua， Meng Huijie， Xia Hongmei， et al. Research on multi-robots path planning of robot based on improved ant colony algorithm［J］. Journal of Hebei University of Technology， 2016，45（5）： 28-34.）

［3］張凱翔， 毛劍琳， 宣志瑋，等. 面向關隘地形的分層調度多機器人路徑規劃［J/OL］. 計算機集成制造系統.（2021-01-26）. https：//kns.cnki.net/kcms/detail/11.5946.TP.20220124.1927.006.html. （Zhang Kaixiang， Mao Jianlin， Xuan Zhiwei， et al. Hierarchical scheduling based multi-agent path finding for pass terrain［J/OL］. Computer Integrated Manufacturing System.（2021-01-26）. https：//kns.cnki.net/kcms/detail/11.5946.TP.20220124.1927.006.html.）

［4］屈立成， 呂嬌， 趙明， 等. 基于三維時空地圖和運動分解的多機器人路徑規劃算法［J］. 計算機應用， 2020，40（12）： 3499-3507. （Qu Licheng， Lyu Jiao， Zhao Ming， et al. Multi-robot path planning algorithm based on 3D spatiotemporal maps and motion decomposition［J］. Journal of Computer Applications， 2020，40（12）： 3499-3507.）

［5］Das P K， Behera H S， Das S， et al. A hybrid improved PSO-DV algorithm for multi-robot path planning in a clutter environment［J］. Neurocomputing， 2016，207（9）： 735-753.

［6］Das P K， Jena P K. Multi-robot path planning using improved particle swarm optimization algorithm through novel evolutionary operators［J］. Applied Soft Computing， 2020，92（7）： 106312.

［7］Paikray H K， Das P K， Panda S. Optimal multi-robot path planning using particle swarm optimization algorithm improved by sine and cosine algorithms［J］. Arabian Journal for Science and Enginee-ring， 2021，46（4）： 3357-3381.

［8］Tian Shasha， Li Yuanxiang， Kang Yilin， et al. Multi-robot path planning in wireless sensor networks based on jump mechanism PSO and safety gap obstacle avoidance［J］. Future Generation Compu-ter Systems， 2021，118（5）： 37-47.

［9］Thabit S， Mohades A. Multi-robot path planning based on multi-objective particle swarm optimization［J］. IEEE Access， 2018，7： 2138-2147.

［10］Das P K， Behera H S， Jena P K， et al. Multi-robot path planning in a dynamic environment using improved gravitational search algorithm［J］. Journal of Electrical Systems and Information Technology， 2016，3（2）： 295-313.

［11］陳南凱， 王耀南， 賈林. 基于改進生物激勵神經網絡算法的多移動機器人協同變電站巡檢作業［J］. 控制與決策， 2022， 37（6）： 1453-1459. （Chen Nankai， Wang Yaonan， Jia Lin. Multi-mobile robot cooperation inspection operation based on improved biological excitation neural network algorithm in substation［J］. Control and Decision， 2022，37（6）： 1453-1459.）

［12］Yang Xinshe. Firefly algorithm， stochastic test functions and design optimisation［J］. International Journal of Bio-Inspired Computation， 2010，2（2）： 78-84.

［13］Hidalgo-Paniagua A， Vega-Rodríguez M A， Ferruz J， et al. Solving the multi-objective path planning problem in mobile robotics with a firefly-based approach［J］. Soft Computing-A Fusion of Foundations，Methodologies and Applications， 2017，21（4）： 949-964.

［14］Kala R. Multi-robot path planning using co-evolutionary genetic programming［J］. Expert Systems with Applications， 2012，39（3）： 3817-3831.

［15］段益琴. 基于多目標優化的多機器人路徑規劃研究［D］. 重慶： 重慶郵電大學， 2020. （Duan Yiqin. Research on multi-robot path planning based on multi-objective optimization［D］. Chongqing： Chongqing University of Posts amp; Telecommunications， 2020.）

［16］胡倩倩. 基于貝茲曲線融合改進遺傳算法的多移動機器人分層路徑規劃方法［D］. 揚州： 揚州大學， 2021. （Hu Qianqian. Hierarchical path planning method for multiple mobile robots based on Bézier curve fusion improved genetic algorithm［D］. Yangzhou： Yangzhou University， 2021.）

收稿日期：2022-07-25；修回日期：2022-09-19 基金項目：國家自然科學基金資助項目（11871059）；四川省教育廳自然科學基金資助項目（18ZA0469）；西華師范大學英才科研基金資助項目（17YC385）

作者簡介：虞馥澤（1997-），女，四川宜賓人，碩士，主要研究方向為組合優化、智能計算；潘大志（1974-），男（通信作者），四川三臺人，教授，博士，主要研究方向為智能計算、算法設計（pdzzj@126.com）．