路月潭

(安徽電子信息職業(yè)技術(shù)學(xué)院 機(jī)電工程系， 安徽 蚌埠233000)

追捕-逃避問題(Pursuit-Evasion Games)是研究如何指導(dǎo)一群追捕者相互合作去捕捉另一群運動的獵物.由于這類問題有著廣泛的應(yīng)用前景，因此受到很多學(xué)者的關(guān)注.追捕-逃避問題的關(guān)鍵技術(shù)在軍事、工業(yè)等方面有著廣泛的應(yīng)用，如機(jī)器人部隊合作包圍/捕獲入侵者[1]以及無人機(jī)和地面無人車輛協(xié)同作戰(zhàn)[2]等對抗領(lǐng)域都已經(jīng)采用追捕-逃避問題來研究.

目前，大多數(shù)追捕-逃避問題討論的是追捕單目標(biāo)問題[3]或是僅給出了移動目標(biāo)采用隨機(jī)逃跑策略而追捕者采用隨機(jī)獨立的搜索策略[4]，這一方面降低了追捕的難度，另一方面并沒有發(fā)揮多個追捕者協(xié)作式搜索的優(yōu)勢.

由于無人機(jī)擁有眾多有人駕駛飛機(jī)所不具有的優(yōu)點，使得其在軍事和民用等諸多領(lǐng)域中有著廣泛的用途和廣闊的應(yīng)用前景.本文考慮多架無人機(jī)在二維固定區(qū)域內(nèi)協(xié)同搜索多個目標(biāo)，發(fā)現(xiàn)目標(biāo)后，合作追捕的目標(biāo)，目標(biāo)采用相對于無人機(jī)相反方向逃逸的策略，最后通過仿真驗證本文協(xié)同追捕策略的正確性.

1 任務(wù)描述

系統(tǒng)中的每個無人機(jī)和移動目標(biāo)都是有智能的，我們統(tǒng)稱為智能體，它們具有感知、規(guī)劃、移動能力以及與其它智能體通信協(xié)商的能力(移動目標(biāo)暫時不考慮通信能力).每個智能體都具有三種不同的感知區(qū)域[5].如圖1所示.最里面的設(shè)置為移動智能體之間避碰的區(qū)域；中間為視覺感知范圍；最外側(cè)為無人機(jī)對外的通信范圍.每個無人機(jī)能夠通過觀察和與其它無人機(jī)的協(xié)商，規(guī)劃自己的移動方向.系統(tǒng)中假設(shè)：①移動目標(biāo)也能根據(jù)感知得到的信息規(guī)劃自己的行為，當(dāng)無人機(jī)發(fā)現(xiàn)移動目標(biāo)后，由于感知的同步性移動目標(biāo)采取與無人機(jī)之間排斥力的策略，以及移動目標(biāo)之間的避碰，也采取排斥力策略，則逃跑的方向即為這些斥力的合力方向，如圖2所示.圖中圓點為目標(biāo)，實線表示斥力，虛線為合力，即目標(biāo)逃跑的方向.②每個智能體知道自己的位置.③無人機(jī)可以在其通信范圍內(nèi)互相通信，信息共享，即通信范圍中的無人機(jī)彼此知道其位置信息以及目標(biāo)的位置和運動方向等，本文的通信范圍是整個二維固定區(qū)域.④追捕成功條件：移動目標(biāo)被4架無人機(jī)從不同的方向合圍，直到所有的無人機(jī)與移動目標(biāo)的距離小于圍捕半徑，則移動目標(biāo)被成功追捕.

圖1 無人機(jī)的三個感知范圍 圖2 目標(biāo)逃逸的合力方向

圖3 無人機(jī)移動控制規(guī)則 圖4 勢點決策圍捕圖

2 無人機(jī)行為控制

如圖3所示，為無人機(jī)跟蹤目標(biāo)的基本控制規(guī)則[6].無人機(jī)Ri受到避碰區(qū)內(nèi)無人機(jī)R1和R2的排斥力作用，同時受到感知區(qū)內(nèi)目標(biāo)T1的吸引力的作用，它們的合力F表示機(jī)器人R1的移動方向和大小，無人機(jī)R3對Ri無作用力影響，因為R3在Ri的避碰區(qū)外，所以無人機(jī)的移動總是遠(yuǎn)離其它無人機(jī)并指向目標(biāo)的移動.

在多目標(biāo)追捕任務(wù)中，每個無人機(jī)都執(zhí)行相同的算法，并且無人機(jī)的移動是同步并行進(jìn)行的.FRi表示無人機(jī)Ri所受到的感知范圍內(nèi)目標(biāo)的引力和避碰范圍內(nèi)無人機(jī)斥力的合力.

(1)

FRi，T1=?(sj-qi)

(2)

(3)

其中，F(xiàn)Ri，T1表示Ri的感知范圍內(nèi)目標(biāo)對其引力.FRi，Rl表示Ri的避碰范圍內(nèi)第l個無人機(jī)對其斥力，?、β分別是一個正的增益系數(shù)，sj、qi分別是目標(biāo)和無人機(jī)的位置，rRi表示無人機(jī)的個數(shù).

FRi=ma

(4)

其中，m=1是無人機(jī)的質(zhì)量，a是無人機(jī)的加速度，amax是無人機(jī)的最大加速度，無人機(jī)每隔Δt的時間重新計算所受到的作用力，如果Δt比較小，可以認(rèn)為下式成立：

(5)

即無人機(jī)所受作用力如果超過最大驅(qū)動力，也只能按最大驅(qū)動力計算速度.

無人機(jī)的運動模型：

(6)

(7)

θi(k+1)=θi(k)+ui(k){i=1，2，…，m}

(8)

3 目標(biāo)搜索

目標(biāo)搜索[7]是在被稱之為“伸縮式”搜索方法上改進(jìn)的.由于“伸縮式”搜索方法在擴(kuò)散搜索目標(biāo)時，收斂速度較慢.本文采用在擴(kuò)散搜索時將圓形邊界被M架無人機(jī)等分，當(dāng)無人機(jī)在收縮搜索之后，確定各無人機(jī)對應(yīng)的等分點為其子目標(biāo)并進(jìn)行路徑規(guī)劃，執(zhí)行擴(kuò)張搜索.

其收縮搜索路徑的確定方法如下：

Fx，i(m)=k×((xi-1(m)-xi(m))+
(xi+1(m)-xi(m)))

(9)

Fy，i(m)=k×((yi-1(m)-yi(m))+
(yi+1(m)-yi(m)))

(10)

Fx，i(m)，F(xiàn)y，i(m)為各無人機(jī)間的位置差異對無人機(jī)x，y方向上的影響.k是收縮系數(shù)，它的取值大小控制著收縮過程的快慢.m為收縮運算的次數(shù)，i=1，2，…，n(n為圍捕無人機(jī)個數(shù))為無人機(jī)標(biāo)號.

xi(m+1)=xi(m)+Fx，j(m)

(11)

yi(m+1)=yi(m)+Fy，j(m)

(12)

由于采用這種方法進(jìn)行搜索時，無人機(jī)總是趨于均勻分布，減小了路徑?jīng)_突的可能，從而提高了搜索的效率.每個無人機(jī)規(guī)劃自己的搜索子目標(biāo)信息(xi(m+1)，yi(m+1))做出相應(yīng)的動作控制.

其擴(kuò)張搜索路徑的確定方法如下：

若有M架無人機(jī)，可以將邊界圓等分成M份，則有M個坐標(biāo)為(x(k)，y(k)){k=1，2，…，M}，這M個坐標(biāo)位置每隔一段時間變化一次，循環(huán)變化，無人機(jī)可以將這M個坐標(biāo)作為搜索子目標(biāo)規(guī)劃自己的路徑.

4 追捕決策

設(shè)獲取到的被追捕目標(biāo)的當(dāng)前坐標(biāo)為(x，y) ，運動方向為θ，構(gòu)造基于“勢點”的追捕任務(wù)決策算法[8]，其原理如圖4所示.在圖4中，被追捕目標(biāo)的“勢點”集合為(xi，yi)，{i=1，2，3，4} ，“勢場”半徑為R，(x1，y1)為序列{(xi，yi)}中的基準(zhǔn)“勢點”，其航向與被追捕目標(biāo)的運動方向θ保持一致，有：

(13)

(14)

為保證追捕有效，需要確保一定的隊形緊密度，“勢場”半徑R需設(shè)置比圍捕半徑略小，這四個“勢點”將作為四架無人機(jī)的搜索子目標(biāo).

a初始狀態(tài) b收縮搜索狀態(tài)

c擴(kuò)張搜索狀態(tài) d所有目標(biāo)均被捕獲

5 仿真

仿真中有8架無人機(jī)和4個目標(biāo)，隨機(jī)產(chǎn)生無人機(jī)和目標(biāo)的位置坐標(biāo)、初始航向以及速度，無人機(jī)的速度比目標(biāo)的速度略大.某無人機(jī)發(fā)現(xiàn)目標(biāo)時，將組成有四個成員的團(tuán)隊，從不同方向追捕目標(biāo)，當(dāng)所有無人機(jī)均在追捕半徑內(nèi)，目標(biāo)即被捕捉.圖5為仿真試驗中得到的圖像，三角形代表無人機(jī)，圓形代表移動目標(biāo)，當(dāng)目標(biāo)被捕捉后，將變成五角星固定在被捕捉時的位置.圖a表示隨機(jī)產(chǎn)生的無人機(jī)和目標(biāo)的初始位置；圖b表示無人機(jī)正在收縮搜索目標(biāo)；圖c表示無人機(jī)正在擴(kuò)張搜索目標(biāo)；圖d表示所有目標(biāo)都被捕獲.

6 結(jié)論

本文介紹了無人機(jī)運動的控制方法、協(xié)同搜索方法以及追捕目標(biāo)模型，在簡單環(huán)境中仿真驗證了無人機(jī)追捕目標(biāo)問題，仿真中無人機(jī)可以動態(tài)避免相互之間碰撞，成功發(fā)現(xiàn)目標(biāo)，追捕目標(biāo)，直到所有目標(biāo)被捕捉完畢，體現(xiàn)了很好的整體智能性.

參考文獻(xiàn)：

[1]Yamaguchi H.A cooperative hunting behavior by mobile-robot troops [J].The International Journal of Robotics and Research (S0278-3649)，1999，20(9):93l-940.

[2]Vidal，R.，Rashid，S.，Sharp，C.etc.Pursuit-Evasion Games with Unmanned Ground and Aerial Vehicles[C]//Proceedings of the 2001 IEEIE International Conference on Robotics 8 Automation Seoul，Korea(S1050-4729)，2001，3:2948-2955.

[3]Yamaguchi H.A distributed motion coordination strategy for multiple nonholonomic mobile robots in cooperative hunting operations [J].Robotics and Autonomous Systems(S0921-8890)，2003，43(4):257-282.

[4]HesPanha J，Prandini M，Sastry S.Probabilistic pursuit-evasion games:a one-step Nash approach[C]//The 39th IEEE Conf on Decision and Control，Sydney，Australia，2002.4:56-70.

[5]李淑琴，王歡，李偉，楊靜宇.基于動態(tài)角色的多移動目標(biāo)圍捕問題算法研究[J].系統(tǒng)仿真學(xué)報，2006，18(2):362-365，390.

[6]周彤，洪炳镕，樸松昊，等.基于多機(jī)器人自組織協(xié)作的多目標(biāo)跟蹤[J].高技術(shù)通訊，2007，17(12):1250-1255.

[7]宋梅萍，顧國昌，張汝波.多移動機(jī)器人協(xié)作任務(wù)的分布式控制系統(tǒng)[J].機(jī)器人，2003，25(5):456-460.

[8]李煥全.基于“勢點”的多移動機(jī)器人協(xié)調(diào)圍捕/攔截策略[J].自動化與儀表，2007，5(1):1-4.