基于非合作博弈的多智能體覆蓋問題動(dòng)態(tài)規(guī)劃

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

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

1 引言

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

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

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

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

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

2.1 問題描述

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

(1)

2.2 博弈建模

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

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

2)任意第i個(gè)博弈方的策略集Si={ρi，θi}，其中：ρi為第i個(gè)智能體的步長(zhǎng)，θi∈[0，2π]為第i個(gè)智能體的方向。因此第i個(gè)博弈方在k+1時(shí)刻的位置坐標(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ù)涞闹行模允沟孟噜徶悄荏w間距離的方差盡量小)。任意第i個(gè)博弈方的得益函數(shù)為[9]

(3)

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

(4)

式中：δ為給定的小值。

3 博弈模型求解

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

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

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

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

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

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

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

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

在上述各步中，解向量si=(ρi，θi)和方差向量ξ=(ξ1，ξ2)的變異是進(jìn)化計(jì)算中最關(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個(gè)智能體，通訊半徑Rc取20，覆蓋半徑Rf取10，最大步長(zhǎng)ρmax=0.5，關(guān)鍵鄰居控制值m取1。覆蓋問題動(dòng)態(tài)規(guī)劃中的參數(shù)δ取0.005，博弈求解中參數(shù)ε取0.002，單目標(biāo)優(yōu)化的進(jìn)化算法參數(shù)設(shè)置為：種群規(guī)模L=60，最大進(jìn)化代數(shù)Tmax=50，閾值μ=0.01。多智能體的初始位置分3種情形：集中在中心、集中在角點(diǎn)和隨機(jī)分散。

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

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

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

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

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

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

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

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

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

圖6 單位個(gè)體平均覆蓋率隨移動(dòng)步的變化圖

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

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

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

5 結(jié)語

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

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

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