基于IF&IABC 算法的多機器人路徑規劃研究*

王希宇 魏 赟

（上海理工大學光電信息與計算機工程學院 上海 200093）

1 引言

隨著科學技術的發展，機器人的應用成為生產生活中不可或缺的一部分。所以許多學者對機器人技術進行了深入的研究。其中，對于機器人路徑規劃問題受到國內外學者的青睞。目前，單機器人的路徑規劃問題已經日趨成熟，但對于多機器人的路徑規劃而言，還需要進一步的研究。近年來，用于解決多機器人路徑規劃問題的方法很多，例如：動態窗口法、模糊控制法和人工勢場法等，但這些方法算法復雜，耗時久，效率低。因此，群智能算法的應用成為了研究的熱點。白建龍、王輝［1～6］等對傳統蟻群算法進行了改進，通過負反饋機制解決蟻群算法易陷入局部最優解的問題，通過引入距離啟發函數因子、改進狀態轉移規則和采取歸一化處理的動態信息素更新策略進行優化改進。但是，該方法計算量大導致搜索時間過長；Kamalova Albina，Contreras-cruz M A，劉二輝［7～10］等通過模擬灰狼的協同捕食行為提出了改進的狼群算法，引入路徑微調算子來提高算法的局部開發能力，提出一種非線性收斂因子公式，又引入初始解生成算法提高初始種群的質量，但是易陷于局部最優并且收斂速度不理想；Chakraborty J，Jan F［11～13］等分別對多機器人系統在復雜環境下進行了路徑規劃，但是都沒有體現群機器人的主要特征，即機器人之間的交互機制。陳久梅、杜霖［14～16］等提出了自適應粒子群算法，在粒子更新過程中以一定概率接受劣解，定義了粒子活躍度概念，并在離散狀態角度分析了算法。但是對于優化方面的處理不夠理想，很容易陷入局部最優；趙曉、張丹露［17～20］等提出了基于預約表下的改進A*算法，構建考慮全局最優路徑的評估函數可以使路徑更平滑，但在任務較稠密區域，容易造成總長度增加過大的問題；孔德鵬、魏鋒濤［21～25］等提出基于精英引導和量子行為的人工蜂群算法，但是，存在一些缺點，例如容易陷入局部最優解和收斂速度慢。

綜上，由于蜂群算法相較于其他算法具有輸入參數少，收斂速度快，且可調節收斂精度的優勢［26］，因此，本文對基本的人工蜂群算法進行了改進，規劃機器人的路徑，結合具有速度反饋的模糊算法規劃機器人的避障行為，從而控制機器人在特定狀態下準確方便地改變路徑，保證其在最佳路徑狀態下運行到目標點，從而求得用于解決機器人路徑規劃問題的最佳方案。

2 算法思想

機器人路徑規劃的目標是規劃出每個機器人在起點到目標點之間的最優路徑。本文采用改進的蜂群算法規劃機器人的路徑。利用混沌思想和反向學習策略初始化種群，通過免疫信息調節機制在當前解和反向解之間進行選擇，擴大種群多樣性，增強跳出局部最優的能力；通過引入量子策略改進鄰域搜索，引入獨立的慣性權重來調節全局和局部尋優能力；用邊界變異法將過界的蜜蜂位置轉移到可行解的位置，避免算法在搜索的過程中陷入局部最優，從而導致效率降低。結合具有速度反饋的模糊算法規劃機器人的避障行為，從而控制機器人在特定狀態下準確方便地改變路徑，保證其在最佳路徑狀態下運行到目標點。另外設計一個速度模糊控制器進行速度的反饋，使機器人在轉彎處減小步長，以防止側移，從而得出最優的路徑規劃解決方案。最后進行仿真驗證，證明本文IF&IABC的優越性，為解決機器人的路徑規劃問題提出了新的思路。

3 基于改進蜂群算法規劃路徑

3.1 環境建模

首先利用網格矩陣建立環境模型（如圖1 所示）。機器人所處的環境由目標點和靜態障礙物構成。機器人從初始點出發，經過路徑點，繞開障礙物，最終到達目標位置。機器人路徑規劃的目的是尋找出機器人的最優安全無碰撞路徑P1,P2,…,Pi。當機器人與所探測到障礙物的距離大于安全距離時，機器人利用改進的人工蜂群算法向目標點運動。機器人可以借助左側、前方、右側3 組傳感器探測障礙物的方向和距離，可以利用方位傳感器感應目標點與當前機器人運行方向的夾角。

圖1 模型示意圖

3.2 節點約束

為了防止機器人之間的碰撞，本文設置各節點允許多個機器人同時經過，同一節點最大允許同時經過機器人的數量為H。

3.3 蜂群算法改進

3.3.1 混沌反向學習初始化種群

為了減少算法的盲目性，增強跳出局部最優的能力，利用混沌思想和反向學習策略初始化種群。這種方法利用概率思想，將在混沌條件下的正向解和反向解進行組合，找出可能的較優解，以此擴大解空間。

1）混沌思想

混亂是不可預測的、隨機的，一個混亂的空間是離散時間的動態系統。數學描述為

此處引入混沌映射，將初始化變量轉化為混沌變量，正弦迭代公式為

3.3.2 免疫信息調節機制選擇路徑

為了隨機的擴展蜂群的數量，增加種群的多樣性，本文引入免疫信息調節機制中的濃度選擇機制對路徑進行選擇。為了避免局部最優，隨機產生一定數量的蜜源（抗體）作為新種群的一部分。第i個蜜源（抗體）的濃度公式如下：

3.3.3 獨立慣性權重調節尋優能力

為了得到理想的最優解，本文引入獨立的慣性權重調節蜜蜂的全局與局部尋優能力：

在路徑規劃過程中，需要在依據當前路徑產生的新路徑和所有初始可行路徑中進行選擇。由于機器人路徑規劃需要尋找最短路徑，則蜜源的選擇根據式（19）進行：

其中，fiti為第i 個蜜源的適應度，如果某條路徑長度越短，則其相應的fiti值越大，被選擇的可能性pi越大，就越容易將此路徑選擇為新路徑。

3.3.4 邊界變異

在跟隨蜂對雇傭蜂進行跟隨時，跟隨蜂有可能因為雇傭蜂靠近邊界導致其自身超過邊界。因此在搜索過程中，算法易陷入局部最優，導致效率不佳。所以，通過邊界變異法將越界的蜜蜂位置移動到可行解的位置。設隨機數r∈（0.2，1.0），如果蜜蜂超過上界U，則將蜜蜂的位置依據式（20）調整，如果蜜蜂超過下界L，則將蜜蜂的位置依據式（21）調整。

用適應度值評估解決方案的質量。通常，使用更大的適應值來導致算法的收斂。對于機器人路徑規劃問題，設計的適應度函數為

4 基于速度反饋的模糊控制避障行為

機器人路徑規劃的實現由于機器人在使用和操作過程中通常處于復雜的非結構化環境中，通過前面的方法規劃機器人的最優路徑后，收集機器人實際操作過程中的動態信息，并根據路徑規劃方案進行智能控制。為了更精確地控制機器人的行走路徑，避免路徑的偏差，在機器人路徑變化的過程中，及時、快速地規劃和修正機器人的行進路徑，合理規劃到達目標點，并進行障礙物檢測，本文結合具有速度反饋的模糊算法規劃機器人的避障行為，從而控制機器人在特定狀態下準確方便地改變路徑，保證其在最佳路徑狀態下運行到目標點。

本文將機器人的左側、前方、右側與障礙物的距離dl、df、dr，以及機器人當前的運動方向與目標方向的夾角ic 作為模糊控制的輸入，通過步長控制速度進行反饋，將機器人運動的角度變化cc作為模糊控制的輸出。將距離的論域取為0～1m，對應的語言變量記為｛N，F｝；機器人運動方向與目標方向夾角的論域取為-180deg～180deg，對應語言變量記為｛LB，LS，Z，RS，RB｝；機器人運動角度變化的論域取為-60deg～60deg，對應的語言變量記為｛TLB，TLS，TZ，TRS，TRB｝。本文采用曲線比較平滑的高斯隸屬函數，可以使系統更加簡潔，且具有較好的精度。下面列舉部分模糊控制規則庫，如表1 所示。

表1 模糊控制規則庫（部分）

使用較為成熟的Mamdani 推理進行推理。最后，為了得到精確的控制量，本文采用重心法求出模糊推理的最終輸出值，即

為了使機器人在轉彎時可以減速行駛，避免發生側移，本文以模糊控制算法為基礎，設計了一個速度模糊控制器。機器人的速度可以用步長來表示，即機器人在單位時間內行走的距離。步長對于機器人在行走過程中尤為重要，步長過大，會使機器人出現避讓不及而撞到障礙物的情況，步長過小則會使系統來不及處理兩次相鄰的采樣信息。同時，應該使機器人在轉彎處減小步長，防止因為慣性過大使機器人產生側移。所以，本文設計了一個速度模糊控制器，以機器人的速度方向偏差和當前運動速度為輸入變量，以下一步的運動速度為輸出變量，模糊控制規則如表2所示。

表2 速度模糊控制規則表

5 實驗仿真與結果分析

首先對傳統人工蜂群算法（ABC）和本文改進算法（IABC）在沒有障礙物的環境進行仿真驗證，仿真結果如圖2～圖4所示，從仿真結果可以看出經過改進的算法可以明顯縮短路徑長度，且收斂性良好。

圖2 ABC算法路徑規劃圖

圖3 IABC算法路徑規劃圖

圖4 收斂曲線

然后對本文的模糊避障功能進行仿真驗證，構造600*600 的地圖環境，機器人分別從不同的起點出發，繞開障礙物訪問任務點。圖5 為改進人工蜂群算法和普通模糊算法相結合（F&IABC）的避障實驗，圖6 為本文IF&IABC 算法仿真結果，路徑優化曲線如圖7 所示。從實驗結果可以看出，利用本文所提出的IF&IABC算法進行路徑規劃時，機器人可以很好地躲避障礙物并依次訪問目標點，且收斂速度較優，具有明顯優勢。

圖5 F&IABC算法路徑規劃圖

圖6 IF&IABC算法路徑規劃圖

圖7 優化曲線

為了驗證本文算法的可擴展性，建立在三維環境中機器人的實驗環境，進行實驗。仿真結果表明，本文算法同樣適用于三維空間的路徑規劃問題，能夠在三維空間很好地躲避障礙物并訪問任務點，具有很好的可擴展性。仿真結果如圖8所示。

圖8 三維路徑規劃圖

6 結語

本文為解決機器人路徑規劃問題提出了一種新的方法。結合改進的蜂群算法和改進的模糊算法規劃出機器人的最佳路徑。本文所提出的IF&IABC在效果上具有一定的優越性，為解決機器人的路徑規劃問題提出了新的思路。該方法適用于不同規模、不同任務數量的路徑規劃，具有很強的實際應用價值。未來的研究工作將集中在復雜環境和方向變化最小的多目標優化問題及對本方法進一步改進將其應用于具有復雜障礙的環境和現實生活的環境中去。