機器人導航路徑的多種群博弈蟻群規劃策略

陳銀燕 ，高安邦

（1.江蘇電子產品裝備制造工程技術研究開發中心，江蘇 淮安 223003；2.淮安信息職業技術學院，江蘇 淮安 223003；3.哈爾濱理工大學，黑龍江 哈爾濱 150080）

1 引言

移動機器人在國民生產生活中應用領域越來越廣，發揮作用也越來越大，移動機器人的行走路徑直接決定了其工作效率和自身安全，是進行其他生產活動或服務活動的基礎[1]。因此，研究機器人導航路徑規劃問題具有明顯的經濟意義和安全意義。

機器人路徑規劃的核心要求是在滿足約束條件下，規劃一條從起始點到目標點的無碰路徑，且此路徑滿足某種評價標準下的最優。根據對環境的掌握程度和環境中障礙物動態特性，一般將路徑規劃分為全局規劃和局部規劃[2]。對于靜態的、全局已知的環境，使用全局規劃方法；對于動態的、未知的環境使用局部規劃方法。從規劃方法的提出時間劃分，可以分為傳統規劃方法和智能仿生規劃方法。傳統規劃方法包括Dijkstra 算法[3]、人工勢場法[4]、模糊邏輯法、柵格法[5]等。智能仿生規劃方法包括遺傳算法[6]、神經網絡[7]、蟻群算法和粒子群算法[8]等，此類方法的特點是模擬生物的某種生理現象或發揮群體智慧對工作路徑尋優。由于智能仿生算法的整體尋優水平較好，因此規劃的路徑質量相對較高，因此成了當前路徑規劃研究的熱點。當前機器人工作場景多種多樣，使得單一固定的機器人路徑規劃方法難以滿足要求。總的來講，機器人路徑規劃研究趨勢為：（1）全局規劃與局部規劃相結合；（2）傳統規劃方法與智能規劃方法融合發展；（3）新型智能規劃算法不斷提出。

研究了靜態柵格環境下導航路徑規劃問題，提出了多種群博弈蟻群算法的規劃方法。將博弈論應用于多種群協同與配合中，有效增加了算法在整個迭代過程中的路徑多樣性，達到了降低工作路徑長度、減少迭代次數、增加路徑平滑性的目的。

2 機器人工作環境模型

2.1 柵格模型

常用的環境建模方法包括可視圖法、極坐標法、Voronoi 圖法、單元樹法和柵格法等，其中柵格法具有原理簡單、易于存儲、柵格大小可調等諸多優點，因此選擇建立工作環境的柵格模型。

柵格法是使用固定大小的柵格將工作區域進行分割，柵格內含有障礙物的柵格稱為障礙物柵格，不含有障礙物的柵格稱為非障礙物柵格。若障礙物沒有占滿一個柵格，則使用膨脹法使其占滿柵格，而后根據柵格內含有障礙物情況進行屬性賦值。一般將非障礙物柵格賦值為0，將障礙物柵格賦值為1。至此柵格建模法將虛擬的二維工作環境轉化為二維矩陣，非常易于建立和存儲。

圖1 某環境柵格模型Fig.1 Grid Model of Some Environment

某工作環境的柵格模型，如圖1 所示。對應的二維矩陣模型為。

2.2 柵格編碼

柵格編碼方法有兩種，分別為順序編碼法和直角坐標法。順序編碼法是從上至下，由左到右依次編碼；直角坐標法是第i 行第j 列的柵格坐標記為（xi，yj）。則順序編碼為k 的柵格與直角坐標法（xi，yj）轉換關系為：

式中：Nh—每一行的柵格數；mod—取余函數；int—舍余取整函數。

另外在此說明的是，柵格法包括四叉樹法和八叉樹法。四叉樹法是指機器人可選柵格限定在當前柵格的上下左右等4 個柵格，八叉樹法是指機器人可選柵格為當前柵格的上、下、左、右、左上、左下、右上、右下等8 個柵格。使用的是八叉樹柵格法。

3 算法改進相關知識

為了在柵格環境下規劃出機器人最優路徑，提出了多種群博弈蟻群算法，設計了一個主種群和若干個從種群，使用博弈論實現主從種群間合作和從種群間協調，同時使用信息熵作為不同博弈策略的激發條件。為了下節更加清晰的構造多種群博弈算法，本節首先介紹算法改進的相關知識。

3.1 蟻群系統與最大最小螞蟻系統

常用的蟻群算法有蟻群系統和最大最小螞蟻系統兩種，兩種蟻群算法的最大區別體現在信息素更新方面。

蟻群系統的信息素更新包括局部更新和全局更新兩個方面。局部更新方法為螞蟻從節點i 運動至節點j 后，則在路徑ij 上進行信息素更新，方法為：

式中：λ—局部信息素揮發系數；τ0—信息素初值。

蟻群系統的全局信息素更新在完成一次迭代后，只針對全局最優路徑進行，方法為：

式中：ρ—全局信息素揮發系數；Vτij—信息素增量；Lgb—一次迭代后全局最優路徑長度。

最大最小螞蟻系統的信息素更新強調兩個方面：一是只進行全局信息素更新，即在完成一次迭代后，對本次迭代最優路徑進行信息素更新，信息素更新公式同式（3）一致；二是為了平衡收斂性和多樣性，對路徑信息素濃度設置上下限。

3.2 博弈論

博弈論也稱為對策論，是研究具有對抗或競爭行為的理論[9]。在博弈論中，參加斗爭或競爭的各方具有各自的利益或目標，各方需充分考慮其他個體所有的可能行動方案，選擇對自身最有利的行動方案。下面介紹博弈論中重要的三個概念：Nash 均衡、帕累托最優和夏普里值。

3.2.1 Nash 均衡

Nash 均衡是指所有參與者這樣的組合策略，在此組合策略下，任何參與者單方面改變策略都得不到好處。Nash 均衡是一種非合作博弈狀態。

數學定義為，對于博弈G=｛N，Ai，ui｝，式中N 為博弈參與者數量，Ai=｛aij｝為博弈參與者i 行動策略集合，ui為參與者i 基于行動 Ai的收益。如果在某個策略組合中，任一參與者的行動策略a*i都是其余參與者行動策略組合的最佳對策，也即ui對于任意aij∈Ai都成立，則稱為博弈 G 的一個 Nash 平衡。

3.2.2 帕累托最優

帕累托最優是一種理想的資源分配狀態。對于博弈G=｛N，Ai，ui｝，從一種策略組合改變為另一種策略組合時′時，在沒有任何參與者收益ui減小的前提下，至少使一個參與者收益變大，此過程為帕累托改進。帕累托最優是指不存在帕累托改進的余地，即資源分配達到了最理想的收益狀態。達到帕累托最優的渠道是帕累托改進。

3.2.3 夏普里值

夏普里值是一種分配方式，分配原則是所得與自己貢獻相等。博弈參與者i 的利益分配函數或期望貢獻為：

式中：N—所有參與者組成的大聯盟；S—任意參與者組成的小聯盟；n—大聯盟參與者數量；k—小聯盟S 參與者數量：v（S）-v（S-｛i｝）—參與者 i 對聯盟 S 的決策影響度。

3.3 信息熵

信息熵可用于描述隨機事件發生的不確定性，或者可用于描述隨機變量的隨機性。對于某一隨機變量X，其信息熵定義[10]為：

式中：H（X）—信息熵；x—隨機變量 X 的取值；p（x）—事件的發生概率。

在隨機事件或隨機變量中，每個可能事件發生的概率越均衡，則隨機事件或隨機變量的信息熵越大。因此在后文中，使用信息熵描述算法路徑多樣性，信息熵越大說明路徑多樣性越好。

4 多種群博弈蟻群算法

4.1 多種群博弈算法框架

算法多樣性決定了算法對工作區域的搜索廣度，同時也決定了最優路徑的搜索概率，因此提高算法多樣性可以極大程度提高算法的搜索性能。鑒于這一思想，提出了多種群博弈蟻群算法，旨在平衡算法的多樣性和收斂性。

設計的多種群博弈蟻群算法原理框架，如圖2 所示。

圖2 多種群博弈蟻群算法原理Fig.2 Principle of Multi-population Game Ant Colony Algorithm

由1 個主種群和2 個從種群組成，為了實現種群之間的信息交流與協作配合，提出了4 種機制，分別為合作博弈機制、獎懲機制、協調博弈機制、針鋒相對機制。主種群與從種群之間使用合作博弈機制進行交流與配合，使主種群自適應進化；獎懲機制是主種群對從種群的單方向作用機制，可以強調優化從種群的作用，對較差從種群對主種群的影響減小。從種群的信息交流與合作機制為協調博弈機制和針鋒相對機制，這兩種機制為并行機制，協調博弈機制是為了提高所有從種群的路徑質量，達到帕累托最優狀態；針鋒相對機制為了提高較差種群的影響力，將較差種群的信息素重新分布。兩種并行機制相互配合從而提高整個從種群群體的路徑質量和多樣性。

不同機制之間的切換條件以本次迭代路徑的信息熵為依據，在介紹不同機制時會一一給出。

4.2 合作博弈機制

合作博弈機制是主種群與從種群之間的博弈機制，是從種群根據自身搜索結果向主種群反饋的最佳信息，也可以理解為從種群將自身的搜索經驗匯報給主種群，從而提高主種群搜索效率和收斂性。

由經驗可知，同一路徑規劃問題，多數次優解或類似最優解都有相同的路徑片段，而此路徑片段也是最優解的必經路段。基于這一經驗，從從種群規劃的多數類似最優解中提取出重復路段，然后傳遞給主種群，從而減少主種群路徑規劃的任務量，實現了從種群對路徑的預處理或預挑選。

合作博弈機制需要一個觸發條件，使用信息加權熵進行構造，信息加權熵體現了從種群對主種群的影響力，當影響力足夠大時才能夠觸發合作博弈機制。因此設定一個閾值，當信息加權熵大于此閾值時實施合作博弈機制。信息加權熵計算方法為：

式中：HW—信息加權熵；Hk—從種群k 的信息熵；wk—從種群k 的權值，使用夏普里值法確定，即權值與貢獻相等。

4.3 獎懲機制

獎懲機制是主種群對從種群的單方向作用機制，對表現優的從種群進行獎勵，對表現差的從種群進行懲罰，這一機制類似于博弈論中的拍賣模型。主種群對從種群的獎懲作用于算法的信息素上，信息素獎懲方式為：

式中：Vτi—從種群i 產生的信息素增量，當從種群i 被獎勵時則信息素增量增加1.2 倍，被懲罰時則減小1.2 倍。

通過式（7）給出的信息素獎懲機制，表現好的從種群就能夠留下更強濃度的信息素供主種群參考，使主種群向表現好的從種群學習，吸取較優從種群的搜索經驗，有利于提高算法搜索速度和精度。獎懲機制貫穿在整個算法執行過程中，無需觸發條件。

4.4 針鋒相對機制

針鋒相對是一種博弈策略，它是指當有從種群對當前狀態不滿時，要求重新進行利益分配的策略，也即由一個Nash 平衡轉化為另一個Nash 平衡。使用針鋒相對機制是為了防止路徑較為單一的從種群出現，從而提高從種群的路徑多樣性。

針鋒相對機制觸發條件為至少一個從種群的信息熵較小，超過了設定閾值。

當滿足觸發條件時，對較差的從種群信息素執行融合操作，為：

式中：n—從種群數量；Pk—從種群k 當前的信息素矩陣；wk—從種群k 對較差從種群的影響系數，取值為（0，1），另外將自身種群對自身影響力設定為0，即自身的信息素矩陣不參與計算。

4.5 協調博弈機制

協調博弈機制是跟隨者之間的博弈機制，旨在提高所有從種群的路徑質量，操作方法為在沒有任何從種群性能變差的前提下，至少使一個從種群的性能提高，也即通過不斷帕累托改進，提高從種群整體性能。從種群性能的評判標準使用信息熵、路徑質量和迭代次數構造，為：

式中：Vi—算法性能指標；Si—當前信息熵與歷史最大信息熵比值；Ai—當前最優解與理論最優解的反比；Ci—當前迭代最小收斂次數與本子群收斂次數的比值。通過式（9）可以看出，Vi取值為（0，1）之間，其值越大則說明算法性能越好。

針鋒相對機制觸發條件為兩個從種群的信息熵之差超過設定閾值。閾值根據當前從種群整體協同狀態自適應調整，方法為：

式中：T—觸發閾值；VT—增量。式（10）表示，當經過帕累托改進得到優化時，則閾值保持不變；當經過帕累托改進沒有得到優化時，說明整體協同狀態已經處于較高水平，難以再進行提高，此時提高閾值減少協調博弈觸發次數。

4.6 多種群博弈蟻群算法流程

圖3 多種群博弈蟻群算法流程Fig.3 Flow of Multi-population Game Ant Colony Algorithm

在多種群博弈蟻群算法中，主蟻群使用蟻群系統，2 個從種群分別使用蟻群系統和最大最小螞蟻系統。將合作博弈機制、獎懲機制、針鋒相對機制和協調博弈機制融入到多種群博弈算法中，得到算法流程，如圖3 所示。

5 仿真驗證與分析

5.1 算法多樣性驗證

使用博弈論實現多種群蟻群算法間的信息交流與合作，通過增加路徑多樣性提高路徑遍歷性和最優路徑被搜索概率，因此本節對算法多樣性進行驗證。

蟻群算法參數設置為：最大迭代次數為2000，螞蟻數量為20，局部信息素揮發因子為0.1，全局信息素揮發因子為0.1，啟發式因子為2，信息素因子為1，信息素強度為1。

圖4 不同算法迭代過程中路徑多樣性Fig.4 Path Diversity in Iteration Process of Different Algorithm

以TSP 測試庫中中等規模的測試函數pr107 為算例進行驗證，為了形成對比效果，分別使用蟻群系統（Ant Colony System，ACS）、最大最小螞蟻系統（Max Min Ant System，MMAS）、多種群博弈蟻群算法（Multi-population Game Ant Colony Algorithm，MP－GAC）進行路徑規劃，每個算法各自獨立運行10 次，選擇規劃的最優路徑統計結果進行展示，三種算法在迭代過程中路徑多樣性，如圖4 所示。

從圖中可以看出，蟻群系統和最大最小螞蟻系統在迭代初期由于信息素分別較為均勻，因此路徑多樣性較好；但是隨著算法的迭代和信息素集中分布于若干路徑，路徑多樣性急劇下降。多種群博弈蟻群算法的路徑多樣性在整個迭代過程中均保持較高水平，提高了路徑遍歷性和最優路徑被搜索概率。

5.2 路徑規劃仿真分析

圖5 路徑長度迭代曲線Fig.5 Path Length Iteration Curve

圖6 兩種算法規劃的最優路徑Fig.6 Optimal Path Planned by the Two Algorithms

為了驗證多種群博弈蟻群算法在柵格環境下的路徑規劃性能，同時使用最大最小螞蟻系統、多種群博弈蟻群算法在柵格環境下進行路徑規劃，算法最大迭代次數設置為100，其余參數設置與5.1 節不變，迭代過程中最優路徑長度隨迭代次數變化曲線，如圖5 所示。兩種算法規劃的最優路徑，如圖6 所示。

從圖5 中可以看出，多種群博弈蟻群算法規劃的路徑長度隨迭代次數下降極快，且在迭代12 次時搜索到最優路徑。而最大最小螞蟻系統規劃路徑長度下降速度相對較慢，在迭代至44 次時路徑長度不再下降。從最優路徑長度來看，多種群博弈蟻群算法規劃的路徑長度明顯小于最大最小螞蟻系統。

從圖6 可以看出，多種群博弈蟻群算法規劃的最優路徑長度和平滑度明顯優于最大最小螞蟻系統。經計算，最大最小螞蟻系統規劃的最優路徑長度為46.113，搜索到最優路徑時迭代次數為44 次，路徑拐點數量為19 個；多種群博弈蟻群算法規劃的最優路徑長度為43.355，比最大最小蟻群算法減少了5.98%；搜索到最優路徑時迭代次數為12 次，遠遠小于最大最小螞蟻算法；路徑拐點數量為10 個，是最大最小螞蟻算法規劃路徑的約一半，說明算法規劃路徑平滑度遠遠優于最大最小螞蟻算法。綜上所述，多種群博弈蟻群算法的最優路徑長度、迭代次數、路徑平滑度均優于最大最小螞蟻算法，這是因為從種群之間的協調博弈機制和針鋒相對機制有效協調了從種群之間的配合和共同進步，主從種群之間的合作博弈機制使從種群將自身搜索經驗和路徑片段傳遞給主種群，極大地提高了主種群路徑質量和搜索效率，使多種群博弈蟻群算法的路徑規劃結果更優。

6 結論

研究了柵格環境下機器人路徑導航算法，提出了多種群博弈蟻群算法的路徑規劃方法。經過研究，得出以下結論：（1）協調博弈機制和針鋒相對機制可以提高從種群整體的路徑多樣性和路徑質量；（2）合作博弈機制能夠有效將從種群搜索經驗和較優片段傳遞給主種群，降低主種群搜索工作量，提高搜索效率；（3）多種群博弈可以有效提高蟻群算法的多樣性，從而提高搜索性能和路徑規劃質量。