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

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

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

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

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

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

近年來，無人集群協(xié)同控制的研究受到研究人員越來越多的關(guān)注．無人集群協(xié)同控制系統(tǒng)，即無人操控的多智能體智能性任務(wù)執(zhí)行系統(tǒng)．多智能體是無人機(jī)、無人艇、無人車等智能無人設(shè)備的總稱．這些設(shè)備都具有一定的自主性，能夠?qū)崿F(xiàn)自我路徑規(guī)劃、動(dòng)態(tài)任務(wù)分配以及實(shí)時(shí)協(xié)同避障等[1-2]．無人集群協(xié)同控制涉及運(yùn)動(dòng)控制、數(shù)據(jù)融合和人工智能等多領(lǐng)域、多學(xué)科的交叉融合，無人系統(tǒng)的發(fā)展趨勢(shì)由半自主向全自主方向發(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ù)量一致時(shí)的隊(duì)形點(diǎn)分配，整體上隊(duì)形點(diǎn)的分配均勻，能夠在較短的時(shí)間內(nèi)形成期望隊(duì)形，但缺少了對(duì)智能體與隊(duì)形點(diǎn)數(shù)量不一致時(shí)的非對(duì)稱任務(wù)點(diǎn)分配的討論．

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

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

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

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

1.1 對(duì)稱任務(wù)分配

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

算法1 拍賣算法

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

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

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

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

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

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

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

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

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

算法2正向拍賣算法

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

第3步：if判斷條件；

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

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

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

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

第10步：end while．

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

算法 3 反向拍賣算法

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

第3步：if判斷條件；

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

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

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

第8步：拍賣師廣播競(jìng)拍結(jié)果，并附加時(shí)間戳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ù)分配時(shí)刻各智能體任務(wù)序列

表3 某時(shí)刻智能體任務(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ù)完成時(shí)刻各智能體各自完成的任務(wù)匯總

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

多智能體仿真控制系統(tǒng)以Qt C++為主進(jìn)行開發(fā)，使用在線地圖API對(duì)智能體的位置進(jìn)行展示，使用在線地圖對(duì)智能體的軌跡進(jìn)行描繪．此外，多智能體集群仿真控制系統(tǒng)能夠獲取被圍捕目標(biāo)的坐標(biāo)位置點(diǎn)，進(jìn)而實(shí)時(shí)計(jì)算編隊(duì)中每一個(gè)智能體的理想位置，控制圍捕編隊(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)化分配，為每一個(gè)智能體分配其在隊(duì)形位置中的最優(yōu)目標(biāo)點(diǎn)，達(dá)到以最小代價(jià)到達(dá)圍捕隊(duì)形目標(biāo)位置點(diǎn)的目的．智能體能夠朝著被圍捕目標(biāo)的方向迅速移動(dòng)，對(duì)被圍捕目標(biāo)節(jié)點(diǎn)形成圍勢(shì)．

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

對(duì)具有失效節(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ì)失效后的圍捕編隊(duì)位置點(diǎn)做出調(diào)整，使各智能體能夠通過任務(wù)重分配得到代價(jià)最小的目標(biāo)位置點(diǎn)，進(jìn)而對(duì)被圍捕目標(biāo)形成圍勢(shì)．

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

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

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

4 結(jié)語

本文提出了運(yùn)用雙向拍賣算法解決編隊(duì)隊(duì)形形成過程中的任務(wù)點(diǎn)分配問題．該方法較好地解決了任務(wù)點(diǎn)分配過程中的負(fù)載不均衡問題，有效地延長了智能體在形成編隊(duì)之后的巡航時(shí)間．對(duì)具有失效節(jié)點(diǎn)的圍捕隊(duì)形進(jìn)行設(shè)計(jì)，通過使用雙向拍賣算法，能夠較好地分配智能體在圍捕隊(duì)形中的目標(biāo)位置點(diǎn)，在部分節(jié)點(diǎn)失效后仍能對(duì)被圍捕目標(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é)報(bào)（自然科學(xué)版），2016，39（10）：1336-1340．

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

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

[10] 李鑫濱，郭力爭(zhēng)，韓松．一種分布式異構(gòu)多AUV任務(wù)分配魯棒拍賣算法[J]．北京航空航天大學(xué)學(xué)報(bào)，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