謝晨輝，謝能剛，王 璐，暴 偉

(1.安徽工業(yè)大學(xué)機械工程學(xué)院，安徽 馬鞍山 243002；2.安徽工業(yè)大學(xué)管理科學(xué)與工程學(xué)院，安徽 馬鞍山，243002)

1 引言

多智能體覆蓋問題主要研究的是：針對具備一定范圍內(nèi)感知、通信和分辨能力以及分布計算性能的多個智能體，通過自組織的方式運動，使得多智能體系統(tǒng)在保持連通的同時，最終形成的網(wǎng)絡(luò)狀態(tài)能實現(xiàn)對特定環(huán)境的最大覆蓋[1]。目前多智能體覆蓋在很多實際任務(wù)中都有應(yīng)用，如監(jiān)視、搜救[2]、無線通信[3]、耕種等方面。多智能體覆蓋問題中的關(guān)鍵是智能體的移動策略，一些初始位置隨機的智能體在確定了策略后，經(jīng)過多次移動，最后達到最理想的覆蓋，獲得最終的拓?fù)浣Y(jié)構(gòu)。因此，多智能體覆蓋控制就是路徑規(guī)劃問題。此問題的評價指標(biāo)主要有覆蓋度與一致性，文獻[4]就將一致性結(jié)合多智能體覆蓋控制進行了研究，并在一維空間內(nèi)進行了仿真，證明了算法的有效性。

目前計算動態(tài)路徑的算法主要分為集中式和分布式兩種。文獻[5]描述了一種通過集中配置靜態(tài)節(jié)點位置的算法，使整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)滿足全部連通和最大覆蓋。但這種集中式算法要求環(huán)境已知且不夠魯棒?？紤]到對環(huán)境的適應(yīng)性，分布式算法就更加靈活可行。文獻[6]提出了一種基于柵格法的集中式全覆蓋路徑規(guī)劃算法，該算法有效地減少了柵格的密度，使得覆蓋路徑大大減少。Koenig等[7]提出了一種分布式的仿生覆蓋算法，通過模仿螞蟻在經(jīng)過路程上釋放信息素這一行為，利用提醒機制避免其它螞蟻在該路程范圍內(nèi)(一定信息素濃度的區(qū)域)進行重復(fù)覆蓋并最終達到最大覆蓋。Batalin[8]等設(shè)計了一種智能體之間通過信息交換來互相排斥，并實現(xiàn)覆蓋目標(biāo)最大的分布式算法。

由于博弈論在多智能體協(xié)作問題上的廣泛應(yīng)用和良好表現(xiàn)，目前也被應(yīng)用到多智能體覆蓋問題中。Xu M[9]提出了一種基于非合作博弈的無線傳感系統(tǒng)輔助拓?fù)淇刂扑惴?，但算法仍有較大的冗余。錢凌[10]等將順序博弈應(yīng)用到覆蓋控制當(dāng)中，提出一種分布式算法，實現(xiàn)了無線傳感網(wǎng)絡(luò)中節(jié)點能量的均衡。劉昊然[11]等針對冗余造成能量效率低的問題，綜合考慮網(wǎng)絡(luò)節(jié)點覆蓋率和節(jié)點剩余能量，提出了一種基于非合作博弈的無線傳感器覆蓋控制算法，增加了網(wǎng)絡(luò)利用率和網(wǎng)絡(luò)生命周期。Xin Ai[12]等基于非合作博弈模型，使用交互式算法來尋找博弈均衡解，利用多智能體之間重疊的感知面積最小化，來實現(xiàn)系統(tǒng)對環(huán)境的最大覆蓋。丁曉燕[13]將非合作博弈引入到多智能體覆蓋問題中，利用非合作博弈的個體理性來尋找最優(yōu)解，每個智能體通過預(yù)測鄰居智能體的行動來確定自己的最優(yōu)移動策略，所有智能體的最優(yōu)策略組合就構(gòu)成系統(tǒng)的Nash均衡，經(jīng)過多次移動后，整個系統(tǒng)就會達到一種平衡并實現(xiàn)最大的覆蓋。但文獻[13]只將智能體的移動方向作為博弈模型中的策略變量，通過多智能體博弈確定最佳方向后，再通過計算出最大可行步長的方式來保證多智能體系統(tǒng)的連通性。這種分兩步走的方法不僅使計算量增加，同時無法解決智能體移動步長和移動方向之間可能出現(xiàn)的不協(xié)調(diào)問題，例如在第一步已經(jīng)確定的各智能體最佳方向的基礎(chǔ)上，在第二步各智能體移動步長的計算中，可能出現(xiàn)沒有維持系統(tǒng)連通性的可行解的情形。

本文將多智能體系統(tǒng)對環(huán)境實現(xiàn)最優(yōu)覆蓋的任務(wù)視為分布式的動態(tài)規(guī)劃問題，并針對動態(tài)規(guī)劃過程進行博弈建模，同時針對文獻[13]的不足，在非合作博弈模型中將智能體的移動步長和移動方向同時作為博弈的策略變量，將維持系統(tǒng)連通性作為博弈模型的約束條件，采用進化算法進行各個博弈方的策略尋優(yōu)，通過談判算法獲得博弈均衡解，實現(xiàn)各個智能體在當(dāng)前步下的最佳移動。智能體系統(tǒng)經(jīng)過多次移動并達到穩(wěn)定后，系統(tǒng)的網(wǎng)絡(luò)拓?fù)浼扔羞B通性又可實現(xiàn)最佳覆蓋度。本文算法的分布式控制模式可以克服魯棒性不足的缺點。

2 多智能體覆蓋控制問題描述與建模

2.1 問題描述

已知二維環(huán)境中有n個智能體，n個智能體的初始位置為(x1(0)，y1(0))、…、(xi(0)，yi(0))、…、(xn(0)，yn(0))，智能體之間的通信半徑為Rc(與鄰居交流半徑)，智能體移動的最大可行步長為ρmax，智能體覆蓋半徑為Rf(智能體實際覆蓋區(qū)域)；所有智能體已知鄰居與自己的距離與方向。研究的問題是：在保持多智能體系統(tǒng)連通性的條件下(每個智能體至少有m個鄰居)，對多智能體的移動路徑進行規(guī)劃，并使最終的分布狀態(tài)實現(xiàn)對環(huán)境的最大覆蓋，其中環(huán)境覆蓋的評價指標(biāo)為單位個體平均覆蓋率λ，定義為

(1)

2.2 博弈建模

針對上述多智能體移動路徑的動態(tài)規(guī)劃問題，即已知k時刻(k=0，1，2，…)的n個智能體的位置(x1(k)，y1(k))、…、(xi(k)，yi(k))、…、(xn(k)，yn(k))，規(guī)劃k+1時刻n個智能體的位置，本文建立非合作博弈模型進行求解。對任意k+1時刻：

1)n個智能體視為n個博弈方；

2)任意第i個博弈方的策略集Si={ρi，θi}，其中：ρi為第i個智能體的步長，θi∈[0，2π]為第i個智能體的方向。因此第i個博弈方在k+1時刻的位置坐標(biāo)(xi(k+1)，yi(k+1))可表示為

xi(k+1)=xi(k)+ρicosθi

yi(k+1)=yi(k)+ρisinθi

(2)

3)在智能體的博弈得益上不僅考慮該智能體的覆蓋性能，讓其與鄰居智能體之間的距離保持足夠遠(yuǎn)以覆蓋盡可能大的范圍(減少冗余面積)，還考慮該智能體和鄰居智能體之間的一致性指標(biāo)(即該智能體盡量處于由其所有鄰居組成的網(wǎng)絡(luò)拓?fù)涞闹行?，以使得相鄰智能體間距離的方差盡量小)。任意第i個博弈方的得益函數(shù)為[9]

(3)

利用上述模型對k=0，1，2，…逐步進行博弈求解，以此獲得所有智能體在每個移動步的坐標(biāo)，完成多智能體移動路徑的動態(tài)規(guī)劃，覆蓋問題規(guī)劃成功的收斂判據(jù)為

(4)

式中：δ為給定的小值。

3 博弈模型求解

3.1 博弈均衡解的談判求解算法

博弈均衡解的談判求解算法步驟如下：

1)在各博弈方的策略空間S1，…，Sn中隨機生成(或給定)初始可行策略，形成策略組合s0={s10，s20，…，sn0}；其中任意si0=(ρi0，θi0)。

3.2 單目標(biāo)優(yōu)化算法

對于3.1節(jié)中博弈均衡解求解算法的步驟2)，其中第i個(i=1，2，…，n)博弈方的單目標(biāo)優(yōu)化問題，基于進化算法[11]進行求解計算，具體計算步驟如下：

1)輸入初始種群規(guī)模L，最大進化代數(shù)Tmax。置初始進化代t=0，隨機產(chǎn)生L個初始設(shè)計變量的向量

2)取目標(biāo)函數(shù)Fi為適應(yīng)函數(shù)，值越大適應(yīng)性越好。

3)調(diào)整方差向量ξ，讓第tl代父本變異并選擇個體進入第tl+1代。

在上述各步中，解向量si=(ρi，θi)和方差向量ξ=(ξ1，ξ2)的變異是進化計算中最關(guān)鍵的步驟，(si，ξ)變異的后代(s′i，ξ′)為

ξ′h=ξhexp(φ′·N(0，1)+φ·Nh(0，1))(h=1，2)，

ρ′i=ρi+N(0，ξ′1)，θ′i=θi+N(0，ξ′2)

4 仿真結(jié)果及分析

4.1 有界環(huán)境的仿真分析

有界環(huán)境取50×50的矩形區(qū)域，取7個智能體，通訊半徑Rc取20，覆蓋半徑Rf取10，最大步長ρmax=0.5，關(guān)鍵鄰居控制值m取1。覆蓋問題動態(tài)規(guī)劃中的參數(shù)δ取0.005，博弈求解中參數(shù)ε取0.002，單目標(biāo)優(yōu)化的進化算法參數(shù)設(shè)置為：種群規(guī)模L=60，最大進化代數(shù)Tmax=50，閾值μ=0.01。多智能體的初始位置分3種情形：集中在中心、集中在角點和隨機分散。

圖1-圖3為不同初始位置時多智能體系統(tǒng)覆蓋控制結(jié)果，圖4為不同初始位置時系統(tǒng)覆蓋度隨移動步的變化情況，其中覆蓋度定義為：覆蓋度=系統(tǒng)已覆蓋面積/環(huán)境總面積。從結(jié)果可以看出，不同初始位置的多智能體系統(tǒng)在本文博弈算法的動態(tài)規(guī)劃下，最終都能達到一種穩(wěn)定的較優(yōu)的覆蓋。從集中在中心、集中在角點和隨機分散等3種初始位置出發(fā)，最終狀態(tài)的系統(tǒng)覆蓋度分別為：81.298%、80.402%和80.260%，均高于80%。同時，從圖1-圖3也可看出，多智能體之間存在重疊的覆蓋面積(圖中的陰影部分)以及超出環(huán)境邊界的區(qū)域，定義：冗余度=(n×單個智能體覆蓋面積-系統(tǒng)已覆蓋面積)/n×單個智能體覆蓋面積)，冗余度指標(biāo)越小，表示多智能體系統(tǒng)的覆蓋效率越高，經(jīng)計算，從集中在中心、集中在角點和隨機分散等3種初始位置出發(fā)，最終狀態(tài)的系統(tǒng)冗余度分別為：8.616%、9.774%和9.957%，均在10%以下，說明系統(tǒng)效率較高。

圖1 初始位置集中在中心時多智能體系統(tǒng)覆蓋控制結(jié)果

圖2 初始位置集中在角點時多智能體系統(tǒng)覆蓋控制結(jié)果

圖3 初始位置隨機分散時多智能體系統(tǒng)覆蓋控制結(jié)果

圖4 系統(tǒng)覆蓋度隨移動步的變化情況

4.2 無界環(huán)境的仿真分析

取無界環(huán)境，智能體數(shù)取20，通訊半徑Rc取20，覆蓋半徑Rf取20。初始位置為隨機分布在一定區(qū)域內(nèi)(如圖5所示)，其它計算條件和參數(shù)同有界環(huán)境。

圖5給出了終態(tài)時的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。圓點為智能體，點與點之間的線為鄰居之間的連線，可以看出整個網(wǎng)絡(luò)是連通的。圖6給出了單位個體平均覆蓋率隨移動步的變化情況，可以看出單位個體平均覆蓋率在多智能體移動初期迅速上升，隨后波動逐漸減小并漸趨穩(wěn)定，最終達到最大覆蓋48.6%。圖7給出了系統(tǒng)中單個智能體的平均鄰居數(shù)隨移動步的變化情形，從中可看出，初始位置時每個智能體都有19個鄰居(這個從圖5也可得到，因為所有智能體初始集中在一個較小的通訊半徑可以覆蓋的區(qū)域內(nèi))，隨著智能體逐漸移動，平均鄰居數(shù)開始下降(智能體分散開，使得相互之間逐漸脫離通訊半徑)，大約350步后平均鄰居數(shù)目趨于小幅波動并逐漸穩(wěn)定，基本維持在1.5左右。圖8和圖9顯示了智能體系統(tǒng)中所有鄰居對(互為鄰居的兩個智能體)之間距離的平均值和方差隨移動步的變化情況，可以看出，隨著智能體的移動，系統(tǒng)中鄰居距離的平均值一直呈現(xiàn)單調(diào)上升的趨勢，并逐漸趨向以通訊半徑20為上限的值；同時，系統(tǒng)中鄰居距離的方差隨著智能體從初始位置分散開，首先呈現(xiàn)迅速增長的趨勢(即不同鄰居對之間的距離相差較大，此時對應(yīng)圖8中平均值迅速上升的階段)，隨著智能體系統(tǒng)的繼續(xù)移動，一些距離超過通訊半徑的鄰居對解體，并且不同鄰居對之間的距離也得到了一定的調(diào)整，使得差距變小，方差呈現(xiàn)為緩慢的下降趨勢(對應(yīng)圖8中平均值平穩(wěn)上升的階段)，在240步以后，隨著鄰居對解體進程和不同鄰居對之間的距離調(diào)整進程的加快(即不同鄰居對之間的距離都逐漸趨向20，對應(yīng)圖8中平均值再次較快上升的階段)，方差迅速下降并逐步趨向于0。

圖5 智能體系統(tǒng)的初始位置和終態(tài)時的網(wǎng)絡(luò)拓?fù)?/p>

圖6 單位個體平均覆蓋率隨移動步的變化圖

圖7 平均鄰居數(shù)隨移動步的變化圖

圖8 系統(tǒng)中鄰居距離的平均值隨移動步的變化圖

圖9 系統(tǒng)中鄰居距離的方差隨移動步的變化圖

5 結(jié)語

1)針對多智能體覆蓋問題，基于第三代系統(tǒng)觀(即復(fù)雜適應(yīng)系統(tǒng))，突破把系統(tǒng)元素看成“死”的、被動對象的觀念，引進具有競爭能力的博弈方主體，將多智能體系統(tǒng)實現(xiàn)對環(huán)境覆蓋的移動過程視為具有自組織能力的多個博弈方之間的動態(tài)規(guī)劃。針對每一個動態(tài)規(guī)劃步(所有智能體在每一動態(tài)規(guī)劃步的移動都是同步的)，將n個智能體視為n個博弈方，將每個智能體的移動步長和移動方向作為該博弈方的策略變量，同時將維持系統(tǒng)連通性作為博弈模型的約束條件，每個博弈方通過預(yù)測鄰居博弈方的行動來確定自己的最優(yōu)移動策略(包括移動方向和移動步長)，通過各博弈方之間的多輪談判以達到最優(yōu)策略組合，獲得系統(tǒng)中每個智能體在當(dāng)前步的最佳移動方向和最佳移動步長，并得到下一步位置坐標(biāo)，完成多智能體移動路徑的動態(tài)規(guī)劃，并最終實現(xiàn)對環(huán)境的最大覆蓋。

2)利用本文算法對有界環(huán)境和無界環(huán)境下的多智能體覆蓋問題進行了仿真分析，結(jié)果表明，本算法不僅能保證多智能體系統(tǒng)整體移動時的連通性，而且系統(tǒng)的最終位置狀態(tài)可實現(xiàn)對環(huán)境的最大覆蓋。在有界環(huán)境下，分析了不同初始位置對覆蓋效果的影響，結(jié)果表明，無論是系統(tǒng)覆蓋度指標(biāo)還是冗余度指標(biāo)，都是從集中在中心的初始位置出發(fā)，系統(tǒng)的最終狀態(tài)最佳。表1顯示了無界環(huán)境下本文計算結(jié)果與文獻[13]的計算結(jié)果在性能指標(biāo)上的對比。根據(jù)表1，可以發(fā)現(xiàn)，在同樣的計算工況下，文獻[13]經(jīng)過500次的移動步，單位個體平均覆蓋率為45.9%，本文算法經(jīng)過370次左右的移動步，單位個體平均覆蓋率為48.6%；文獻[13]最終平均鄰居數(shù)在2.2-2.5的區(qū)間內(nèi)，而本文算法的最終平均鄰居數(shù)在1.5左右，體現(xiàn)出更大的分散度。因此通過本文算法最終形成的多智能體系統(tǒng)拓?fù)渚W(wǎng)絡(luò)能在保持整體連通的同時，實現(xiàn)對環(huán)境的更好覆蓋，且算法效率更高。

表1 性能指標(biāo)對比