受生物啟發的多智能體導航模型

劉鵬元，蘇先創，張惠凱

（浙江理工大學信息學院，浙江杭州 310018）

0 引言

群體智能（Swarm Intelligence，SI）領域正逐步從強調中心的集中式系統走向去中心化的分散式系統。群智能體（Agent）遵循非常簡單的規則，盡管沒有集中的控制結構來指示單個智能體應如何行動，但此類智能體之間的相互作用會使群體展現出不同于個體的智能行為。與傳統的人工智能思想不同，群體智能是從去中心化的角度理解和把握智能思想，將群體智能與復雜適應系統相結合，研究自然界生命個體、群體機制，建立模擬這些機制的仿真模型與計算方法。本文模型受果蠅幼蟲啟發，并基于動物視覺和嗅覺導航，使用群決策方法（Group Decision-making）構建多智能體模型，考察模擬生物在迷宮環境下的巡航能力，并對視覺和嗅覺共同導航的不同占比所產生的導航效果進行探索。

1 相關工作

1992年Lewis等討論利用群體智能來控制體內的納米機器人以殺死癌癥腫瘤的可能性；2003年，何小賢等提出群體智能本質和個體智能是一致的，而群體智能在復雜環境中表現出很好的魯棒性；2005年，康琦等分別對人工生命和群體智能進行了綜述，分析了兩者的區別與聯系，并對其未來發展趨勢進行了展望。群體智能算法的優化改進一直備受關注，群體智能算法可對神經網絡結構進行優化，群體智能方法為解決復雜的軟件工程問題提供了新思路；基于SI技術的應用越來越多，盡管如此，與經典的人工智能技術相比，SI還是一個相對年輕的領域。

許多動物無需地圖或儀器就可準確找到自己的路，不同的動物可以整合不同類型的線索以使自己定向并有效導航。科研人員從動物導航視角進行研究，其中以嗅覺和視覺最為大眾所知。嗅覺線索是由受體蛋白檢測到空氣中的揮發性化學物質或水中的可溶性化學物質，它在動物歸巢中起著非常重要的作用。而研究昆蟲中的視覺歸巢也很有趣，因為昆蟲可以在自然條件下進行實驗和重建視點，并且昆蟲可能已經進化出了對歸巢問題的簡化而魯棒的解決方案。

Yang等提出平均場強化學習，其中智能體之間的相互作用近似于單個智能體與總體或鄰近智能體的平均效應之間的相互作用；兩個實體之間的相互作用是相互加強的，智能體的最優學習策略依賴于種群的動態，而種群的動態根據個體政策的集體模式變化；Mguni等提出了一種在多智能體系中計算閉環最優策略的方法，每個智能體只需觀察其本地狀態信息和已實現的獎勵即可獨立于智能體數量進行擴展。

分散式系統比集中式控制系統在極端環境下擁有更強的魯棒性。此外，研究發現群體智能算法訓練的人工神經網絡在模擬環境中進行導航時，自發地表現出類似網格的活動模式，這種神經活動模式與觀察到的哺乳動物活動模式非常一致。同樣，群體智能應用于機器人領域，然而這些機器人大多需要某種程度上的集中控制或者依賴確定性行為。受到生物學中集體遷移現象啟發，松散耦合群體機器人結構簡單、容易制造，并且比中央控制的機器人系統更加靈活、易于拓展，還擁有很好的魯棒性，因此具有廣闊的應用前景。

果蠅幼蟲由于腹部和胸部細胞的綜合動作能夠執行探索程序，平衡前進任務和轉向任務，表現出類似于智能體的自主性。分散的細菌菌落（例如大腸桿菌），在覓食時表現出與食物以及生存相關的氣味驅動趨化行為。受這些行為啟發，Manrique等提出了基于果蠅幼蟲的分散導航模型，表明分散式系統在部分能力不足時能更有效地到達目標。

然而，以上研究僅針對最簡單的平面空間進行抽象，表明了簡單環境下去中心化模型的有效性。生物真實生存環境往往復雜得多，各種人類活動的產物對生物生存提出了新的挑戰，例如玻璃建筑物威脅鳥類生命。在這些類似于玻璃的透明障礙下，生物是否有能力越過障礙尋找到食物是個難題。

本文基于以上相關工作，從生物啟發角度出發，基于生物嗅覺與視覺導航方式，通過分散式的群決策方法對如迷宮一樣的復雜環境進行研究，提出一種在復雜環境下導航的可解決方案。對導航方法進行改進，模擬生物面對較復雜環境時使用嗅覺和視覺導航尋找目標的能力。實驗結果表明，本文方法可使多智能體模型完成復雜環境下的導航任務。

2 多智能體導航模型

本文基于群決策行為模擬生物的嗅覺和視覺導航方式，研究多智能體（

Multi-agent

）導航模型，并針對復雜環境提出基于嗅覺和視覺的導航算法，調整嗅覺和視覺導航方式占比，使模型中能力不足的個體盡可能越過障礙完成導航任務。

2.1 模型基本構成

多智能體導航模型如圖1所示。提供一個簡單實體（Entity），該實體由任意數目的N個智能體組成，每個智能體接收外部信息（即傳感器）的能力有限，存儲和處理該信息的能力有限，通過嘗試向左或向右推動系統來執行操作（即執行器）的能力有限。然而，這些有限能力的智能體組合卻能夠使導航系統向左或向右轉動并前進，最終使整體向目標前進。

Fig.1 Multi-agent navigation model圖1 多智能體導航模型

對每個智能體存儲系統過去m個結果進行歷史記錄，其中，結果用0/1表示，將整數m定義為智能體能力。在多智能體系統中，每個時間步智能體單獨決策，所有智能體的操作綜合作用影響實體的決策結果。如果智能體的決策使得實體與目標方向更接近，則記此時間步結果為1，如果該實體方向變得遠離目標，則記為0。

2.2 群決策方法

能力為m的智能體存在著2個可能的歷史結果，如對于m＝2，智能體過去2個時間步可能的歷史為00、01、10和11，即使在任意給定的時間步中智能體存儲相同的歷史記錄，依舊有兩個可選擇操作：嘗試將系統順時針（action-1）或逆時針旋轉角度

δ

（action+1）。因此，存在一個如圖1右下所示的查找表，其中每一行實際上都是一種信息處理算法（稱為“策略”），用于在給出2種可能的歷史輸入之一的情況下預測最佳操作，所以有2種可能的策略。每個智能體最初隨機從2個可能的策略中獲取s（s＞1）個策略，從而引入異質性，完成策略初始化。

系統會在每一步根據N個智能體的集體決策來選擇一個新的速度方向并前進單位距離1，旋轉角度如下：

其中，

n

[

t

]為在t步時采取

action

±1的智能體個數，

δ

=

π

/

N

，是一個與智能體個數N有關的常數，

Rotation

的值為正則逆時針旋轉，否則為順時針旋轉。如果所有智能體都采取了相同的

action

+1，對于

δ

=

π

/

N

，實體逆時針旋轉180°。

2.3 最優決策算法

為了使有限智能體組合的實體表現良好，本文為每個智能體增加一定的適應性，即每個智能體在任何給定時間步選取其s個策略中的最優策略。需要對策略進行評分，在每個時間步判斷智能體所作出的行為是否對集體有利，并作出相應的獎勵與懲罰。最優決策算法如圖2所示。

Fig.2 Best-performing algorithm圖2 最優決策算法

Fig.3 Step trajectory圖3 步進軌跡

每個智能體都有其對應的s條策略，每次決策時選取最優策略。在本文中為每個策略設定分數屬性（初始時分數為0），如果當前智能體的行為有利，則當前策略分數加1，否則分數減1。因此，每次選取分數最高的一條策略，如果多個策略有相同的最高分數，則隨機選取擁有最高分數的多條策略。

2.4 基于濃度梯度場的地圖構建

由于引入了復雜的迷宮環境，本文將地圖離散化成一定數量的方格（grid，作為地圖的最小單位）。就嗅覺導航而言，需要表達出目標點在迷宮中所處的位置以及其散發出的氣味，使模擬幼蟲可以感知到周圍的食物氣味濃度。因此在地圖中引入濃度梯度場，每個時間步濃度梯度下降最快的方向即為指向目標點的最優方向。用地圖中小方格的濃度概括地表示該方格內所有位置的濃度，從而簡化地表示每一個點的濃度，當方格足夠小時能在一定程度上近似地表達這個地圖上每一個點的濃度。在模型中，當目標被視為光源時，強度定義為單個柵格位置處的照度級別。進一步假設濃度隨著距離的增加而衰減，并遵循反定律，可用式（2）計算：

其中，

L

是目標點的發光強度，

D

是網格(

x

，

y

)到目標點的距離。模型中任何位置的濃度值均由單個值給出。本文將目標點的濃度值設置為1，地圖其他位置的濃度值隨著距離增加而衰減。

同時，地圖離散化之后，障礙物的位置以及實體當前是否遇到障礙也就變得容易處理。本文在平面坐標上加入迷宮障礙，障礙的基本組成單位是方格。當實體撞向障礙的時候會反彈，即改變一定的方向。所有障礙都為透明玻璃障礙，即光線可以穿透障礙，模擬生物使用視覺導航時可以直接看到食物。多智能體系統有一個直接向食物前進的強烈感知牽引，而嗅覺導航所依賴的氣味無法穿透透明障礙直線傳播，所以模擬生物嗅覺導航下沿著濃度梯度下降最快的路線前進。

為方便可視化，用顏色深淺來表示濃度高低。地圖中的格子濃度越高，顏色會越深，反之越淺。地圖中存在一些屏障，屏障是透明的但是會阻擋氣味的散發，即實體可以看到迷宮對面的食物，同時也能聞到食物散發的味道。具體迷宮如圖4所示。

Fig.4 Map of concentration gradient圖4 濃度梯度場地圖

2.5 基于嗅覺和視覺的導航算法

本文研究了嗅覺組件和視覺組件的比例對分散實體導航能力的影響。受嗅覺導航啟發，實體在根據嗅覺覓食時能獲得周圍濃度梯度信息，并沿著濃度梯度上升最快的方向前進，即需要獲得實體周圍一定范圍內濃度梯度相差最大的點。同樣，僅受視覺導航影響時，實體直接朝著看得見的目標點運動。具體導航算法步驟如下：

（3）根據當前坐標以及運動的方向計算出下一個坐標。

（4）多智能系統中所有智能體根據這個運動的結果做出反饋，更新自身數據，為下次決策做準備。

（5）建立碰壁機制，使得實體在碰到迷宮障礙時改變運動方向，實現類似反彈的效果。

3 實驗分析

本文針對無障礙、簡單障礙以及復雜障礙環境進行仿真模擬實驗，并考察多智能體系統采用嗅覺導航方式、視覺導航方式以及嗅覺和視覺導航相結合時的表現能力。

3.1 實驗方法

3.2 實驗結果

⑴當活動環境變得略微復雜一些時，實體依舊能夠只憑借視覺導航到達目標點，見圖5（a）。

Fig.5 Navigation perfor mancein different environments圖5 不同環境下的導航性能

⑵將環境變得更加復雜，僅靠視覺進行導航會不斷碰壁，導致無法尋找到終點食物，形成一個死局，運行結果見圖5（b）。

⑶根據上一環境可以看出，僅憑視覺無法適應更為復雜的環境，圖5（c）為憑借嗅覺導航方式運動的軌跡，實體成功到達終點。

圖6（a）為多智能體模型在無障礙環境下的統計結果，其中橫坐標為個體能力m，縱坐標為到達目標點使用的步長

ξ

，用來體現系統的導航性能。可以看出，當m=5時，

ξ

取得最小值，即導航性能最佳。在最簡單的無障礙環境下，得出與文獻［23］］研究相同的結論；如圖6（b）所示，在個體能力剛剛好的時候實體表現最佳，增大的記憶（memory）反而表現得不那么機智。

然而，在簡單障礙下，智能體能力的增大會在實體尋找食物的過程中起到積極作用。從圖7可以看出當m＞9之后積極作用有限，但在有障礙的環境下需要個體組件有更強的能力。

Fig.6 Navigation performance statistics in barrier free environment圖6 無障礙環境下導航性能統計結果

Fig.7 Visual navigation performanceunder simpleobstacles圖7 簡單障礙下視覺導航性能

為了跨越障礙成功尋找到食物，本文研究嗅覺與視覺在模型尋找食物中的影響占比，以及地圖的變化是否會改變這個影響。如圖8所示，所處環境為復雜障礙，其中不同標記的折線代表中間那個障礙頂端到地圖上方的距離與整個地圖的高度比值，本文稱為間隙?。圖中橫坐標為嗅覺所占比重，嗅覺與視覺總共為1。從圖中可以看出，在同一環境下嗅覺的比值在0.5～0.55之間出現突變，并且地圖間隙越狹小就越依賴嗅覺來尋找食物，細微的嗅覺影響增加會顯著地提升實體找到食物的幾率。

若嗅覺與視覺的比例不變，則間隙?從0.1增加到0.7的過程中，隨著間隙?的增大曲線逐漸遠離x軸，即實體的表現能力呈下降趨勢，而間隙?為0.8和0.9時表現能力有所回升。當間隙?越來越大時，原本作為誤導因素的視覺系統反而正向影響實體完成導航任務；當間隙?越來越小時，嗅覺起到了減少步數的關鍵作用。

Fig.8 Olfactory and visual navigation performance of multi-agent under complex obstacles圖8 復雜障礙下多智能體的嗅覺和視覺導航性能

4 結語

本文的多智能體導航模型首先實現了在簡單環境下的目標導航，并且在單個智能體能力恰好時多智能體系統表現最佳。在此基礎上，進一步設計復雜障礙考察多智能體系統在迷宮環境下的表現能力，結果顯示多智能體系統先前的導航算法在實現導航任務時優勢不明顯。因此，本文參照生物學中動物的嗅覺導航和視覺導航方式，設計了相應的群決策算法，其目的是使得分散式的實體在復雜環境下利用嗅覺和視覺導航盡可能到達目標，尋找導航模型的最優解。

通過仿真實驗研究發現，當分散式實體處于復雜環境時，僅憑借視覺導航可以跨越一些簡單障礙完成導航任務。然而在障礙變得復雜時，實體需要借助嗅覺導航才能到達目標。本文模擬果蠅幼蟲的導航模型討論了復雜環境下受嗅覺和視覺導航啟發的多智能體系統導航能力，具有一定的代表性，為后續多智能體系統探索復雜環境提供參考。