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

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

0 引言

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

1 相關(guān)工作

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

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

Yang等提出平均場(chǎng)強(qiáng)化學(xué)習(xí)，其中智能體之間的相互作用近似于單個(gè)智能體與總體或鄰近智能體的平均效應(yīng)之間的相互作用；兩個(gè)實(shí)體之間的相互作用是相互加強(qiáng)的，智能體的最優(yōu)學(xué)習(xí)策略依賴于種群的動(dòng)態(tài)，而種群的動(dòng)態(tài)根據(jù)個(gè)體政策的集體模式變化；Mguni等提出了一種在多智能體系中計(jì)算閉環(huán)最優(yōu)策略的方法，每個(gè)智能體只需觀察其本地狀態(tài)信息和已實(shí)現(xiàn)的獎(jiǎng)勵(lì)即可獨(dú)立于智能體數(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)航時(shí)，自發(fā)地表現(xiàn)出類似網(wǎng)格的活動(dòng)模式，這種神經(jīng)活動(dòng)模式與觀察到的哺乳動(dòng)物活動(dòng)模式非常一致。同樣，群體智能應(yīng)用于機(jī)器人領(lǐng)域，然而這些機(jī)器人大多需要某種程度上的集中控制或者依賴確定性行為。受到生物學(xué)中集體遷移現(xiàn)象啟發(fā)，松散耦合群體機(jī)器人結(jié)構(gòu)簡(jiǎn)單、容易制造，并且比中央控制的機(jī)器人系統(tǒng)更加靈活、易于拓展，還擁有很好的魯棒性，因此具有廣闊的應(yīng)用前景。

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

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

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

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

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

Multi-agent

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

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

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

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

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

2.2 群決策方法

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

δ

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

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

其中，

n

[

t

]為在t步時(shí)采取

action

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

δ

=

π

/

N

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

Rotation

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

action

+1，對(duì)于

δ

=

π

/

N

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

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

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

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

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

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

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

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

其中，

L

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

D

是網(wǎng)格(

x

，

y

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

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

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

Fig.4 Map of concentration gradient圖4 濃度梯度場(chǎng)地圖

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

3.1 實(shí)驗(yàn)方法

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

ξ

，用來體現(xiàn)系統(tǒng)的導(dǎo)航性能?？梢钥闯?，當(dāng)m=5時(shí)，

ξ

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

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

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

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

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

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

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

4 結(jié)語

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

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