路月潭

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

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

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

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

1 任務(wù)描述

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

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

圖3 無(wú)人機(jī)移動(dòng)控制規(guī)則 圖4 勢(shì)點(diǎn)決策圍捕圖

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

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

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

(1)

FRi，T1=?(sj-qi)

(2)

(3)

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

FRi=ma

(4)

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

(5)

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

無(wú)人機(jī)的運(yùn)動(dòng)模型：

(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)時(shí)，收斂速度較慢.本文采用在擴(kuò)散搜索時(shí)將圓形邊界被M架無(wú)人機(jī)等分，當(dāng)無(wú)人機(jī)在收縮搜索之后，確定各無(wú)人機(jī)對(duì)應(yīng)的等分點(diǎn)為其子目標(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)為各無(wú)人機(jī)間的位置差異對(duì)無(wú)人機(jī)x，y方向上的影響.k是收縮系數(shù)，它的取值大小控制著收縮過程的快慢.m為收縮運(yùn)算的次數(shù)，i=1，2，…，n(n為圍捕無(wú)人機(jī)個(gè)數(shù))為無(wú)人機(jī)標(biāo)號(hào).

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

(11)

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

(12)

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

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

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

4 追捕決策

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

(13)

(14)

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

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

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

5 仿真

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

6 結(jié)論

本文介紹了無(wú)人機(jī)運(yùn)動(dòng)的控制方法、協(xié)同搜索方法以及追捕目標(biāo)模型，在簡(jiǎn)單環(huán)境中仿真驗(yàn)證了無(wú)人機(jī)追捕目標(biāo)問題，仿真中無(wú)人機(jī)可以動(dòng)態(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]李淑琴，王歡，李偉，楊靜宇.基于動(dòng)態(tài)角色的多移動(dòng)目標(biāo)圍捕問題算法研究[J].系統(tǒng)仿真學(xué)報(bào)，2006，18(2):362-365，390.

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

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

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