基于拍賣算法的多智能體圍捕編隊(duì)控制

孫金龍，李大輝，吳鵬，陶偉，陳昂

基于拍賣算法的多智能體圍捕編隊(duì)控制

孫金龍，李大輝，吳鵬，陶偉，陳昂

（齊齊哈爾大學(xué) 計算機(jī)與控制工程學(xué)院，黑龍江 齊齊哈爾 161006）

隨著高新技術(shù)的快速發(fā)展，多智能體的協(xié)同控制成為研究熱點(diǎn)．在多智能體協(xié)同控制的基礎(chǔ)上，設(shè)計了多智能體的圍捕編隊(duì)，能夠在給定被圍捕目標(biāo)具體位姿信息的情況下，對目標(biāo)進(jìn)行圍追堵截．使用經(jīng)典的拍賣算法解決了智能體在圍捕隊(duì)形中的任務(wù)分配問題，使各智能體能夠以相對較快的時間形成標(biāo)準(zhǔn)的圍捕編隊(duì)隊(duì)形．此外，還提出運(yùn)用雙向拍賣算法解決隊(duì)形形成過程中的位置點(diǎn)分配問題，能夠以相對較小的代價完成隊(duì)形的控制，進(jìn)而完成對目標(biāo)的圍捕．

智能體編隊(duì)；任務(wù)分配；雙向拍賣算法；隊(duì)形控制

近年來，無人集群協(xié)同控制的研究受到研究人員越來越多的關(guān)注．無人集群協(xié)同控制系統(tǒng)，即無人操控的多智能體智能性任務(wù)執(zhí)行系統(tǒng)．多智能體是無人機(jī)、無人艇、無人車等智能無人設(shè)備的總稱．這些設(shè)備都具有一定的自主性，能夠?qū)崿F(xiàn)自我路徑規(guī)劃、動態(tài)任務(wù)分配以及實(shí)時協(xié)同避障等[1-2]．無人集群協(xié)同控制涉及運(yùn)動控制、數(shù)據(jù)融合和人工智能等多領(lǐng)域、多學(xué)科的交叉融合，無人系統(tǒng)的發(fā)展趨勢由半自主向全自主方向發(fā)展[3-5]．

在多智能體編隊(duì)隊(duì)形形成的問題中，李強(qiáng)[6]提出了目標(biāo)位置優(yōu)化選擇法，按照智能體與隊(duì)形點(diǎn)之間的距離進(jìn)行隊(duì)形點(diǎn)的分配優(yōu)化，這種算法能夠較好地解決隊(duì)形形成過程中點(diǎn)分配的沖突問題，但忽略了智能體方向角的問題，無法保證結(jié)果在實(shí)驗(yàn)上的最優(yōu)．陳梅[7]等在目標(biāo)位置優(yōu)化選擇法的基礎(chǔ)上，提出了改進(jìn)

的目標(biāo)點(diǎn)優(yōu)化分配法，解決了智能體與隊(duì)形點(diǎn)數(shù)量一致時的隊(duì)形點(diǎn)分配，整體上隊(duì)形點(diǎn)的分配均勻，能夠在較短的時間內(nèi)形成期望隊(duì)形，但缺少了對智能體與隊(duì)形點(diǎn)數(shù)量不一致時的非對稱任務(wù)點(diǎn)分配的討論．

本文基于拍賣算法研究了智能體編隊(duì)的圍捕隊(duì)形形成問題，運(yùn)用雙向拍賣算法對目標(biāo)點(diǎn)與智能體數(shù)量不對稱的情況進(jìn)行了研究．仿真結(jié)果表明，該算法能夠較好地減輕智能體集群在任務(wù)分配過程中的負(fù)載不均衡問題，完成目標(biāo)圍捕隊(duì)形的形成與保持．

1 基于拍賣算法的任務(wù)分配

在多智能體編隊(duì)的控制中，首要解決的問題是如何劃分編隊(duì)中智能體的角色（包括領(lǐng)航者和跟隨者2種角色），各個智能體如何確定自身在目標(biāo)隊(duì)形中的理想位置，并且使各個智能體能夠安全快速地到達(dá)其理想位置點(diǎn)．

當(dāng)目標(biāo)隊(duì)形中的位置點(diǎn)數(shù)目和智能體的數(shù)量一致時，采用經(jīng)典的拍賣算法進(jìn)行任務(wù)點(diǎn)的分配，當(dāng)目標(biāo)隊(duì)形中的位置點(diǎn)數(shù)目與智能體的數(shù)量不一致或目標(biāo)隊(duì)形中位置點(diǎn)數(shù)目動態(tài)變化時，采用兼顧任務(wù)負(fù)載平衡的雙向拍賣算法．根據(jù)不同的編隊(duì)隊(duì)形需求，能夠?qū)嵤┎煌娜蝿?wù)分配方案，達(dá)到更高的分配時效．

1.1 對稱任務(wù)分配

經(jīng)典的對稱拍賣[8]中包含了拍賣師、競拍方和拍賣品幾種角色．在編隊(duì)隊(duì)形的形成過程中，由首先獲得目標(biāo)位置點(diǎn)的智能體擔(dān)任拍賣師，編隊(duì)中的所有智能體作為競拍方，拍賣品為全體目標(biāo)點(diǎn)[9]．拍賣算法見算法1.

算法1 拍賣算法

第1步：獲得目標(biāo)位置點(diǎn)的智能體廣播信息標(biāo)物信息，并附加時間戳；

第2步：競拍方根據(jù)獲得的廣播信息，提交競價向量，點(diǎn)對點(diǎn)傳輸至拍賣師；

第4步：拍賣方進(jìn)行初次任務(wù)分配或依據(jù)條件判斷，決定是否對任務(wù)進(jìn)行再次競價或者重新分配；

第5步：重復(fù)第4～5步，直到所有智能體均獲得目標(biāo)位置點(diǎn)．

經(jīng)典拍賣算法對隊(duì)形理想位置點(diǎn)的分配結(jié)果見圖1．各智能體能夠通過拍賣算法獲得相應(yīng)的目標(biāo)位置點(diǎn)．經(jīng)典拍賣算法在應(yīng)對理想位置點(diǎn)數(shù)量與智能體數(shù)量不對稱的情況時，采取增加虛擬智能體或者增加虛擬任務(wù)的方法，這種方法增加了計算的負(fù)載[10]．本文設(shè)計一種雙向拍賣算法來解決數(shù)量不對稱的目標(biāo)點(diǎn)位置分配問題．

圖1 經(jīng)典拍賣算法分配結(jié)果

1.2 非對稱任務(wù)分配

圖2 目標(biāo)點(diǎn)較少時的分配結(jié)果

表1 各智能體的任務(wù)分配結(jié)果

算法2正向拍賣算法

第2步：while 總?cè)蝿?wù)未執(zhí)行完畢；

第3步：if判斷條件；

第4步：拍賣師執(zhí)行主拍賣算法；

目標(biāo)待分配除首輪拍賣外，收集未完成首批目標(biāo)的智能體競價，運(yùn)行正向拍賣主程序；

第6步：各智能體根據(jù)拍賣后的任務(wù)分配映射更新任務(wù)序列；

第7步：各智能體根據(jù)更新后的任務(wù)序列執(zhí)行任務(wù)；

第10步：end while．

在反向拍賣中，首艘完成首批目標(biāo)的智能體作為拍賣師，全體智能體作為競拍方，反向目標(biāo)作為拍賣品．反向拍賣算法設(shè)計見算法3．

算法 3 反向拍賣算法

第2步：while 總?cè)蝿?wù)未執(zhí)行完畢；

第3步：if判斷條件；

第4步：拍賣師執(zhí)行主拍賣算法；

第5步：收集所有智能體對第２批目標(biāo)的反向競價；

第7步：運(yùn)行反向拍賣主程序；

第8步：拍賣師廣播競拍結(jié)果，并附加時間戳timestamp；

第9步：完成首批目標(biāo)的智能體，更新任務(wù)序列，未完成的繼續(xù)執(zhí)行原任務(wù)，不更新任務(wù)序列；

第10步：各智能體根據(jù)更新后的任務(wù)序列執(zhí)行任務(wù)；

第13步：end while．

首批目標(biāo)位置點(diǎn)分配示意圖見圖3，其中藍(lán)色目標(biāo)為首批分配的目標(biāo)位置點(diǎn)，綠色為第2批待分配的目標(biāo)．首批目標(biāo)分配的智能體任務(wù)序列見表2.

圖3　初次任務(wù)分配結(jié)果

表2 初次任務(wù)分配時刻各智能體任務(wù)序列

表3 某時刻智能體任務(wù)序列

智能體7和5，分別為正向和反向拍賣的拍賣師．智能體狀態(tài)分為3種：1代表執(zhí)行正向拍賣目標(biāo)中；2代表正向拍賣目標(biāo)未執(zhí)行完畢，預(yù)分配反向拍賣目標(biāo)；3代表正向拍賣目標(biāo)執(zhí)行完畢，執(zhí)行反向拍賣目標(biāo)中（見表4）．

表4 任務(wù)完成時刻各智能體各自完成的任務(wù)匯總

由表4的對比結(jié)果可知，雙向拍賣算法極大地減輕了智能體集群的負(fù)載不均衡問題．同時，雖然有一些性能損失（總?cè)蝿?wù)完成時長延長了6.91%，總收益減少了4.81%），但是均衡的任務(wù)負(fù)載，隱性地增加了整個智能體集群的巡航時間．

2 多智能體圍捕編隊(duì)

2.1 圍捕隊(duì)形設(shè)計

圍捕隊(duì)形結(jié)構(gòu)的基本描述見圖4．其中紅色點(diǎn)表示被圍捕目標(biāo)，綠色點(diǎn)表示圍捕隊(duì)形中各無人艇個體的目標(biāo)點(diǎn)，黑色點(diǎn)表示某無人艇的當(dāng)前位置．

圖4 圍捕隊(duì)形的基本描述

根據(jù)圍捕目標(biāo)的具體坐標(biāo)位置設(shè)計各個無人艇的期望坐標(biāo)，被圍捕目標(biāo)在無人艇個體坐標(biāo)系下的坐標(biāo)

各無人艇期望位置在無人艇個體坐標(biāo)系下的位姿

算法 4 圍捕編隊(duì)算法

輸入：各智能體的當(dāng)前位置，智能體的理想位置；

輸出：智能體的最終位置；

第3步：以被圍捕目標(biāo)為坐標(biāo)原點(diǎn)，計算智能體的目標(biāo)位置在圍捕隊(duì)形中的相對坐標(biāo)；

第4步：以各智能體的中心為坐標(biāo)原點(diǎn)，計算各智能體的目標(biāo)位置在各智能體坐標(biāo)系中的坐標(biāo)；

2.2 具有失效節(jié)點(diǎn)的圍捕隊(duì)形設(shè)計

多智能體圍捕隊(duì)形中的節(jié)點(diǎn)可分為主節(jié)點(diǎn)和次節(jié)點(diǎn)．主節(jié)點(diǎn)位于被圍捕目標(biāo)航向的正前方，能夠?qū)Ρ粐赌繕?biāo)形成正面攔截；次節(jié)點(diǎn)則均勻地分布在以被圍捕目標(biāo)為圓心的圓周上，形成對目標(biāo)的閉環(huán)圍捕．在多智能體集群執(zhí)行圍捕過程中，由于外力環(huán)境因素或智能體自身故障，可能出現(xiàn)編隊(duì)中節(jié)點(diǎn)失效的情景．初始為4個智能體節(jié)點(diǎn)參與圍捕任務(wù)時，其中一個智能體將被分配在圍捕隊(duì)形的主節(jié)點(diǎn)位置上，其余節(jié)點(diǎn)則均勻地分列在其他次節(jié)點(diǎn)位置上（見圖5a）．當(dāng)智能體節(jié)點(diǎn)中的其中一個失效時，分配算法應(yīng)能夠首先保證圍捕隊(duì)形的主節(jié)點(diǎn)位置上分配到活躍節(jié)點(diǎn)，其余活躍節(jié)點(diǎn)均勻地分列在圍捕隊(duì)形的其他位置點(diǎn)上（見圖5b）．

在圍捕過程中，隊(duì)形的主節(jié)點(diǎn)能夠分配到活躍節(jié)點(diǎn)，即能對圍捕目標(biāo)形成攔截，則視為圍捕成功．同樣，在形成圍捕隊(duì)形后，也可能面臨節(jié)點(diǎn)失效的情況．此時，需要通過隊(duì)形中次節(jié)點(diǎn)位置上的活躍節(jié)點(diǎn)向前遞補(bǔ)，保證圍捕隊(duì)形主節(jié)點(diǎn)位置上分配到活躍節(jié)點(diǎn)，從而完成對目標(biāo)的圍捕．

圖5 圍捕隊(duì)形失效情況

3 運(yùn)用任務(wù)分配算法的圍捕隊(duì)形仿真

多智能體仿真控制系統(tǒng)以Qt C++為主進(jìn)行開發(fā)，使用在線地圖API對智能體的位置進(jìn)行展示，使用在線地圖對智能體的軌跡進(jìn)行描繪．此外，多智能體集群仿真控制系統(tǒng)能夠獲取被圍捕目標(biāo)的坐標(biāo)位置點(diǎn)，進(jìn)而實(shí)時計算編隊(duì)中每一個智能體的理想位置，控制圍捕編隊(duì)隊(duì)形的形成．

3.1 基礎(chǔ)圍捕隊(duì)形實(shí)驗(yàn)仿真

多智能體圍捕隊(duì)形的仿真效果見圖6．其中紅色軌跡節(jié)點(diǎn)作為被圍捕目標(biāo)，藍(lán)色軌跡節(jié)點(diǎn)作為智能體節(jié)點(diǎn)執(zhí)行圍捕任務(wù)．任務(wù)分配中的經(jīng)典拍賣算法能夠?qū)毒庩?duì)中的隊(duì)形點(diǎn)進(jìn)行優(yōu)化分配，為每一個智能體分配其在隊(duì)形位置中的最優(yōu)目標(biāo)點(diǎn)，達(dá)到以最小代價到達(dá)圍捕隊(duì)形目標(biāo)位置點(diǎn)的目的．智能體能夠朝著被圍捕目標(biāo)的方向迅速移動，對被圍捕目標(biāo)節(jié)點(diǎn)形成圍勢．

3.2 具有失效節(jié)點(diǎn)的圍捕隊(duì)形實(shí)驗(yàn)仿真

對具有失效節(jié)點(diǎn)的圍捕編隊(duì)隊(duì)形進(jìn)行仿真，結(jié)果見圖7．其中紅色軌跡節(jié)點(diǎn)作為被圍捕目標(biāo)，其他節(jié)點(diǎn)作為智能體節(jié)點(diǎn)執(zhí)行圍捕任務(wù)．運(yùn)用任務(wù)分配模塊中的雙向拍賣算法，對失效后的圍捕編隊(duì)位置點(diǎn)做出調(diào)整，使各智能體能夠通過任務(wù)重分配得到代價最小的目標(biāo)位置點(diǎn)，進(jìn)而對被圍捕目標(biāo)形成圍勢．

圖6 圍捕隊(duì)形仿真

圖7 具有失效節(jié)點(diǎn)的圍捕隊(duì)形

通過40次獨(dú)立的含失效節(jié)點(diǎn)的圍捕仿真測試，運(yùn)用任務(wù)分配中的雙向拍賣算法對活躍節(jié)點(diǎn)進(jìn)行隊(duì)形點(diǎn)位置重分配，在４個智能體對目標(biāo)進(jìn)行圍捕時，失效一個節(jié)點(diǎn)的情形下，圍捕成功的概率可達(dá)85%．

4 結(jié)語

本文提出了運(yùn)用雙向拍賣算法解決編隊(duì)隊(duì)形形成過程中的任務(wù)點(diǎn)分配問題．該方法較好地解決了任務(wù)點(diǎn)分配過程中的負(fù)載不均衡問題，有效地延長了智能體在形成編隊(duì)之后的巡航時間．對具有失效節(jié)點(diǎn)的圍捕隊(duì)形進(jìn)行設(shè)計，通過使用雙向拍賣算法，能夠較好地分配智能體在圍捕隊(duì)形中的目標(biāo)位置點(diǎn)，在部分節(jié)點(diǎn)失效后仍能對被圍捕目標(biāo)進(jìn)行有效圍捕.

[1] Xiong T，Gu Z．Observer-based adaptive fixed-time formation control for multi-agent systems with unknown uncertainties[J]．

Neurocomputing，2021，423：506-517．

[2] Guo G，Gao Z，Dong K．Prescribed-time formation control of surface vessels with asymmetric constraints on LOS range and bearing angles[J]．Nonlinear Dynamics，2021，104（4）：3701-3712．

[3] Guo G，Zhang P．Asymptotic stabilization of USVs with actuator dead-zones and yaw constraints based on fixed-time disturbance observer[J]．IEEE Transactions on Vehicular Technology，2019，69（1）：302-316．

[4] Yin S，Yang H，Kaynak O．Coordination Task Triggered Formation Control Algorithm for Multiple Marine Vessels[J]．IEEE Transactions on Industrial Electronics，2017，64（6）：4984-4993．

[5] Breivik M，Hovstein V E，F(xiàn)ossen T I．Ship Formation Control：A Guided Leader-Follower Approach[J]．IFAC Proceedings

Volumes，2018，41（2）：16008-16014．

[6] 李強(qiáng)．基于多智能體系統(tǒng)的機(jī)器人隊(duì)形控制與協(xié)作研究[D]．無錫：江南大學(xué)，2011．

[7] 陳梅，梅樂，陳艷燕．基于改進(jìn)分配法的多智能體隊(duì)形形成[J]．合肥工業(yè)大學(xué)學(xué)報（自然科學(xué)版），2016，39（10）：1336-1340．

[8] 趙輝，郝夢雅，王紅君，等．基于資源拍賣的農(nóng)業(yè)多機(jī)器人任務(wù)分配[J]．計算機(jī)應(yīng)用與軟件，2021，38（12）：286-290，313．

[9] 孫延標(biāo)，黃潤才．基于拍賣算法的多機(jī)器人編隊(duì)時間優(yōu)化[J]．制造業(yè)自動化，2021，43（12）：82-86．

[10] 李鑫濱，郭力爭，韓松．一種分布式異構(gòu)多AUV任務(wù)分配魯棒拍賣算法[J]．北京航空航天大學(xué)學(xué)報，2022，48（5）：736-746．

Multi-agent rounding up formation control based on auction algorithm

SUN Jinlong，LI Dahui，WU Peng，TAO Wei，CHEN Ang

（School of Computer and Control Engineer，Qiqihar University，Qiqihar 161006，China）

With the rapid development of high and new technology，cooperative control of multi-agents has become a hot topic．Based on the cooperative control of multi-agents，a multi-agent rounding up formation is designed，which can encircle and intercept the target given the specific position and pose of the target being rounded up．The classical auction algorithm is used to solve the task assignment problem of agents in the rounding up formation，so that each agent can form a standard rounding up formation in a relatively fast time．In addition，the bidirectional auction algorithm is also proposed to solve the problem of position allocation in formation process，which can complete formation control with relatively small cost，and then complete the target rounding up．

agent formation；task allocation；double-side auction algorithm；formation control

1007-9831（2022）09-0026-07

TP242

A

10.3969/j.issn.1007-9831.2022.09.007

2022-04-15

齊齊哈爾大學(xué)研究生創(chuàng)新項(xiàng)目（YJSCX2021077）

孫金龍（1995-），男，河北張家口人，在讀碩士研究生，從事多智能體協(xié)同控制研究．E-mail：sjinlong_1025@163.com

李大輝（1968-），男，黑龍江齊齊哈爾人，教授，博士，從事多智能體協(xié)同控制研究．E-mail：1125073174@qq.com