受生物啟發(fā)的多智能體導(dǎo)航模型

劉鵬元，蘇先創(chuàng)，張惠凱

（浙江理工大學(xué)信息學(xué)院，浙江杭州 310018）

0 引言

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

1 相關(guān)工作

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

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

Yang等提出平均場強(qiáng)化學(xué)習(xí)，其中智能體之間的相互作用近似于單個智能體與總體或鄰近智能體的平均效應(yīng)之間的相互作用；兩個實體之間的相互作用是相互加強(qiáng)的，智能體的最優(yōu)學(xué)習(xí)策略依賴于種群的動態(tài)，而種群的動態(tài)根據(jù)個體政策的集體模式變化；Mguni等提出了一種在多智能體系中計算閉環(huán)最優(yōu)策略的方法，每個智能體只需觀察其本地狀態(tài)信息和已實現(xiàn)的獎勵即可獨立于智能體數(shù)量進(jìn)行擴(kuò)展。

分散式系統(tǒng)比集中式控制系統(tǒng)在極端環(huán)境下?lián)碛懈鼜?qiáng)的魯棒性。此外，研究發(fā)現(xiàn)群體智能算法訓(xùn)練的人工神經(jīng)網(wǎng)絡(luò)在模擬環(huán)境中進(jìn)行導(dǎo)航時，自發(fā)地表現(xiàn)出類似網(wǎng)格的活動模式，這種神經(jīng)活動模式與觀察到的哺乳動物活動模式非常一致。同樣，群體智能應(yīng)用于機(jī)器人領(lǐng)域，然而這些機(jī)器人大多需要某種程度上的集中控制或者依賴確定性行為。受到生物學(xué)中集體遷移現(xiàn)象啟發(fā)，松散耦合群體機(jī)器人結(jié)構(gòu)簡單、容易制造，并且比中央控制的機(jī)器人系統(tǒng)更加靈活、易于拓展，還擁有很好的魯棒性，因此具有廣闊的應(yīng)用前景。

果蠅幼蟲由于腹部和胸部細(xì)胞的綜合動作能夠執(zhí)行探索程序，平衡前進(jìn)任務(wù)和轉(zhuǎn)向任務(wù)，表現(xiàn)出類似于智能體的自主性。分散的細(xì)菌菌落（例如大腸桿菌），在覓食時表現(xiàn)出與食物以及生存相關(guān)的氣味驅(qū)動趨化行為。受這些行為啟發(fā)，Manrique等提出了基于果蠅幼蟲的分散導(dǎo)航模型，表明分散式系統(tǒng)在部分能力不足時能更有效地到達(dá)目標(biāo)。

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

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

2 多智能體導(dǎo)航模型

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

Multi-agent

）導(dǎo)航模型，并針對復(fù)雜環(huán)境提出基于嗅覺和視覺的導(dǎo)航算法，調(diào)整嗅覺和視覺導(dǎo)航方式占比，使模型中能力不足的個體盡可能越過障礙完成導(dǎo)航任務(wù)。

2.1 模型基本構(gòu)成

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

Fig.1 Multi-agent navigation model圖1 多智能體導(dǎo)航模型

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

2.2 群決策方法

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

δ

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

系統(tǒng)會在每一步根據(jù)N個智能體的集體決策來選擇一個新的速度方向并前進(jìn)單位距離1，旋轉(zhuǎn)角度如下：

其中，

n

[

t

]為在t步時采取

action

±1的智能體個數(shù)，

δ

=

π

/

N

，是一個與智能體個數(shù)N有關(guān)的常數(shù)，

Rotation

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

action

+1，對于

δ

=

π

/

N

，實體逆時針旋轉(zhuǎn)180°。

2.3 最優(yōu)決策算法

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

Fig.2 Best-performing algorithm圖2 最優(yōu)決策算法

Fig.3 Step trajectory圖3 步進(jìn)軌跡

每個智能體都有其對應(yīng)的s條策略，每次決策時選取最優(yōu)策略。在本文中為每個策略設(shè)定分?jǐn)?shù)屬性（初始時分?jǐn)?shù)為0），如果當(dāng)前智能體的行為有利，則當(dāng)前策略分?jǐn)?shù)加1，否則分?jǐn)?shù)減1。因此，每次選取分?jǐn)?shù)最高的一條策略，如果多個策略有相同的最高分?jǐn)?shù)，則隨機(jī)選取擁有最高分?jǐn)?shù)的多條策略。

2.4 基于濃度梯度場的地圖構(gòu)建

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

其中，

L

是目標(biāo)點的發(fā)光強(qiáng)度，

D

是網(wǎng)格(

x

，

y

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

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

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

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

2.5 基于嗅覺和視覺的導(dǎo)航算法

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

（3）根據(jù)當(dāng)前坐標(biāo)以及運動的方向計算出下一個坐標(biāo)。

（4）多智能系統(tǒng)中所有智能體根據(jù)這個運動的結(jié)果做出反饋，更新自身數(shù)據(jù)，為下次決策做準(zhǔn)備。

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

3 實驗分析

本文針對無障礙、簡單障礙以及復(fù)雜障礙環(huán)境進(jìn)行仿真模擬實驗，并考察多智能體系統(tǒng)采用嗅覺導(dǎo)航方式、視覺導(dǎo)航方式以及嗅覺和視覺導(dǎo)航相結(jié)合時的表現(xiàn)能力。

3.1 實驗方法

3.2 實驗結(jié)果

⑴當(dāng)活動環(huán)境變得略微復(fù)雜一些時，實體依舊能夠只憑借視覺導(dǎo)航到達(dá)目標(biāo)點，見圖5（a）。

Fig.5 Navigation perfor mancein different environments圖5 不同環(huán)境下的導(dǎo)航性能

⑵將環(huán)境變得更加復(fù)雜，僅靠視覺進(jìn)行導(dǎo)航會不斷碰壁，導(dǎo)致無法尋找到終點食物，形成一個死局，運行結(jié)果見圖5（b）。

⑶根據(jù)上一環(huán)境可以看出，僅憑視覺無法適應(yīng)更為復(fù)雜的環(huán)境，圖5（c）為憑借嗅覺導(dǎo)航方式運動的軌跡，實體成功到達(dá)終點。

圖6（a）為多智能體模型在無障礙環(huán)境下的統(tǒng)計結(jié)果，其中橫坐標(biāo)為個體能力m，縱坐標(biāo)為到達(dá)目標(biāo)點使用的步長

ξ

，用來體現(xiàn)系統(tǒng)的導(dǎo)航性能。可以看出，當(dāng)m=5時，

ξ

取得最小值，即導(dǎo)航性能最佳。在最簡單的無障礙環(huán)境下，得出與文獻(xiàn)［23］］研究相同的結(jié)論；如圖6（b）所示，在個體能力剛剛好的時候?qū)嶓w表現(xiàn)最佳，增大的記憶（memory）反而表現(xiàn)得不那么機(jī)智。

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

Fig.6 Navigation performance statistics in barrier free environment圖6 無障礙環(huán)境下導(dǎo)航性能統(tǒng)計結(jié)果

Fig.7 Visual navigation performanceunder simpleobstacles圖7 簡單障礙下視覺導(dǎo)航性能

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

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

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

4 結(jié)語

本文的多智能體導(dǎo)航模型首先實現(xiàn)了在簡單環(huán)境下的目標(biāo)導(dǎo)航，并且在單個智能體能力恰好時多智能體系統(tǒng)表現(xiàn)最佳。在此基礎(chǔ)上，進(jìn)一步設(shè)計復(fù)雜障礙考察多智能體系統(tǒng)在迷宮環(huán)境下的表現(xiàn)能力，結(jié)果顯示多智能體系統(tǒng)先前的導(dǎo)航算法在實現(xiàn)導(dǎo)航任務(wù)時優(yōu)勢不明顯。因此，本文參照生物學(xué)中動物的嗅覺導(dǎo)航和視覺導(dǎo)航方式，設(shè)計了相應(yīng)的群決策算法，其目的是使得分散式的實體在復(fù)雜環(huán)境下利用嗅覺和視覺導(dǎo)航盡可能到達(dá)目標(biāo)，尋找導(dǎo)航模型的最優(yōu)解。

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