孙金龙，李大辉，吴鹏，陶伟，陈昂

基于拍卖算法的多智能体围捕编队控制

孙金龙，李大辉，吴鹏，陶伟，陈昂

（齐齐哈尔大学 计算机与控制工程学院，黑龙江 齐齐哈尔 161006）

随着高新技术的快速发展，多智能体的协同控制成为研究热点．在多智能体协同控制的基础上，设计了多智能体的围捕编队，能够在给定被围捕目标具体位姿信息的情况下，对目标进行围追堵截．使用经典的拍卖算法解决了智能体在围捕队形中的任务分配问题，使各智能体能够以相对较快的时间形成标准的围捕编队队形．此外，还提出运用双向拍卖算法解决队形形成过程中的位置点分配问题，能够以相对较小的代价完成队形的控制，进而完成对目标的围捕．

智能体编队；任务分配；双向拍卖算法；队形控制

近年来，无人集群协同控制的研究受到研究人员越来越多的关注．无人集群协同控制系统，即无人操控的多智能体智能性任务执行系统．多智能体是无人机、无人艇、无人车等智能无人设备的总称．这些设备都具有一定的自主性，能够实现自我路径规划、动态任务分配以及实时协同避障等[1-2]．无人集群协同控制涉及运动控制、数据融合和人工智能等多领域、多学科的交叉融合，无人系统的发展趋势由半自主向全自主方向发展[3-5]．

在多智能体编队队形形成的问题中，李强[6]提出了目标位置优化选择法，按照智能体与队形点之间的距离进行队形点的分配优化，这种算法能够较好地解决队形形成过程中点分配的冲突问题，但忽略了智能体方向角的问题，无法保证结果在实验上的最优．陈梅[7]等在目标位置优化选择法的基础上，提出了改进

的目标点优化分配法，解决了智能体与队形点数量一致时的队形点分配，整体上队形点的分配均匀，能够在较短的时间内形成期望队形，但缺少了对智能体与队形点数量不一致时的非对称任务点分配的讨论．

本文基于拍卖算法研究了智能体编队的围捕队形形成问题，运用双向拍卖算法对目标点与智能体数量不对称的情况进行了研究．仿真结果表明，该算法能够较好地减轻智能体集群在任务分配过程中的负载不均衡问题，完成目标围捕队形的形成与保持．

1 基于拍卖算法的任务分配

在多智能体编队的控制中，首要解决的问题是如何划分编队中智能体的角色（包括领航者和跟随者2种角色），各个智能体如何确定自身在目标队形中的理想位置，并且使各个智能体能够安全快速地到达其理想位置点．

当目标队形中的位置点数目和智能体的数量一致时，采用经典的拍卖算法进行任务点的分配，当目标队形中的位置点数目与智能体的数量不一致或目标队形中位置点数目动态变化时，采用兼顾任务负载平衡的双向拍卖算法．根据不同的编队队形需求，能够实施不同的任务分配方案，达到更高的分配时效．

1.1 对称任务分配

经典的对称拍卖[8]中包含了拍卖师、竞拍方和拍卖品几种角色．在编队队形的形成过程中，由首先获得目标位置点的智能体担任拍卖师，编队中的所有智能体作为竞拍方，拍卖品为全体目标点[9]．拍卖算法见算法1.

算法1 拍卖算法

第1步：获得目标位置点的智能体广播信息标物信息，并附加时间戳；

第2步：竞拍方根据获得的广播信息，提交竞价向量，点对点传输至拍卖师；

第4步：拍卖方进行初次任务分配或依据条件判断，决定是否对任务进行再次竞价或者重新分配；

第5步：重复第4～5步，直到所有智能体均获得目标位置点．

经典拍卖算法对队形理想位置点的分配结果见图1．各智能体能够通过拍卖算法获得相应的目标位置点．经典拍卖算法在应对理想位置点数量与智能体数量不对称的情况时，采取增加虚拟智能体或者增加虚拟任务的方法，这种方法增加了计算的负载[10]．本文设计一种双向拍卖算法来解决数量不对称的目标点位置分配问题．

图1 经典拍卖算法分配结果

1.2 非对称任务分配

图2 目标点较少时的分配结果

表1 各智能体的任务分配结果

算法2正向拍卖算法

第2步：while 总任务未执行完毕；

第3步：if判断条件；

第4步：拍卖师执行主拍卖算法；

目标待分配除首轮拍卖外，收集未完成首批目标的智能体竞价，运行正向拍卖主程序；

第6步：各智能体根据拍卖后的任务分配映射更新任务序列；

第7步：各智能体根据更新后的任务序列执行任务；

第10步：end while．

在反向拍卖中，首艘完成首批目标的智能体作为拍卖师，全体智能体作为竞拍方，反向目标作为拍卖品．反向拍卖算法设计见算法3．

算法 3 反向拍卖算法

第2步：while 总任务未执行完毕；

第3步：if判断条件；

第4步：拍卖师执行主拍卖算法；

第5步：收集所有智能体对第２批目标的反向竞价；

第7步：运行反向拍卖主程序；

第8步：拍卖师广播竞拍结果，并附加时间戳timestamp；

第9步：完成首批目标的智能体，更新任务序列，未完成的继续执行原任务，不更新任务序列；

第10步：各智能体根据更新后的任务序列执行任务；

第13步：end while．

首批目标位置点分配示意图见图3，其中蓝色目标为首批分配的目标位置点，绿色为第2批待分配的目标．首批目标分配的智能体任务序列见表2.

图3　初次任务分配结果

表2 初次任务分配时刻各智能体任务序列

表3 某时刻智能体任务序列

智能体7和5，分别为正向和反向拍卖的拍卖师．智能体状态分为3种：1代表执行正向拍卖目标中；2代表正向拍卖目标未执行完毕，预分配反向拍卖目标；3代表正向拍卖目标执行完毕，执行反向拍卖目标中（见表4）．

表4 任务完成时刻各智能体各自完成的任务汇总

由表4的对比结果可知，双向拍卖算法极大地减轻了智能体集群的负载不均衡问题．同时，虽然有一些性能损失（总任务完成时长延长了6.91%，总收益减少了4.81%），但是均衡的任务负载，隐性地增加了整个智能体集群的巡航时间．

2 多智能体围捕编队

2.1 围捕队形设计

围捕队形结构的基本描述见图4．其中红色点表示被围捕目标，绿色点表示围捕队形中各无人艇个体的目标点，黑色点表示某无人艇的当前位置．

图4 围捕队形的基本描述

根据围捕目标的具体坐标位置设计各个无人艇的期望坐标，被围捕目标在无人艇个体坐标系下的坐标

各无人艇期望位置在无人艇个体坐标系下的位姿

算法 4 围捕编队算法

输入：各智能体的当前位置，智能体的理想位置；

输出：智能体的最终位置；

第3步：以被围捕目标为坐标原点，计算智能体的目标位置在围捕队形中的相对坐标；

第4步：以各智能体的中心为坐标原点，计算各智能体的目标位置在各智能体坐标系中的坐标；

2.2 具有失效节点的围捕队形设计

多智能体围捕队形中的节点可分为主节点和次节点．主节点位于被围捕目标航向的正前方，能够对被围捕目标形成正面拦截；次节点则均匀地分布在以被围捕目标为圆心的圆周上，形成对目标的闭环围捕．在多智能体集群执行围捕过程中，由于外力环境因素或智能体自身故障，可能出现编队中节点失效的情景．初始为4个智能体节点参与围捕任务时，其中一个智能体将被分配在围捕队形的主节点位置上，其余节点则均匀地分列在其他次节点位置上（见图5a）．当智能体节点中的其中一个失效时，分配算法应能够首先保证围捕队形的主节点位置上分配到活跃节点，其余活跃节点均匀地分列在围捕队形的其他位置点上（见图5b）．

在围捕过程中，队形的主节点能够分配到活跃节点，即能对围捕目标形成拦截，则视为围捕成功．同样，在形成围捕队形后，也可能面临节点失效的情况．此时，需要通过队形中次节点位置上的活跃节点向前递补，保证围捕队形主节点位置上分配到活跃节点，从而完成对目标的围捕．

图5 围捕队形失效情况

3 运用任务分配算法的围捕队形仿真

多智能体仿真控制系统以Qt C++为主进行开发，使用在线地图API对智能体的位置进行展示，使用在线地图对智能体的轨迹进行描绘．此外，多智能体集群仿真控制系统能够获取被围捕目标的坐标位置点，进而实时计算编队中每一个智能体的理想位置，控制围捕编队队形的形成．

3.1 基础围捕队形实验仿真

多智能体围捕队形的仿真效果见图6．其中红色轨迹节点作为被围捕目标，蓝色轨迹节点作为智能体节点执行围捕任务．任务分配中的经典拍卖算法能够对围捕编队中的队形点进行优化分配，为每一个智能体分配其在队形位置中的最优目标点，达到以最小代价到达围捕队形目标位置点的目的．智能体能够朝着被围捕目标的方向迅速移动，对被围捕目标节点形成围势．

3.2 具有失效节点的围捕队形实验仿真

对具有失效节点的围捕编队队形进行仿真，结果见图7．其中红色轨迹节点作为被围捕目标，其他节点作为智能体节点执行围捕任务．运用任务分配模块中的双向拍卖算法，对失效后的围捕编队位置点做出调整，使各智能体能够通过任务重分配得到代价最小的目标位置点，进而对被围捕目标形成围势．

图6 围捕队形仿真

图7 具有失效节点的围捕队形

通过40次独立的含失效节点的围捕仿真测试，运用任务分配中的双向拍卖算法对活跃节点进行队形点位置重分配，在４个智能体对目标进行围捕时，失效一个节点的情形下，围捕成功的概率可达85%．

4 结语

本文提出了运用双向拍卖算法解决编队队形形成过程中的任务点分配问题．该方法较好地解决了任务点分配过程中的负载不均衡问题，有效地延长了智能体在形成编队之后的巡航时间．对具有失效节点的围捕队形进行设计，通过使用双向拍卖算法，能够较好地分配智能体在围捕队形中的目标位置点，在部分节点失效后仍能对被围捕目标进行有效围捕.

[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，Fossen T I．Ship Formation Control：A Guided Leader-Follower Approach[J]．IFAC Proceedings

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

[6] 李强．基于多智能体系统的机器人队形控制与协作研究[D]．无锡：江南大学，2011．

[7] 陈梅，梅乐，陈艳燕．基于改进分配法的多智能体队形形成[J]．合肥工业大学学报（自然科学版），2016，39（10）：1336-1340．

[8] 赵辉，郝梦雅，王红君，等．基于资源拍卖的农业多机器人任务分配[J]．计算机应用与软件，2021，38（12）：286-290，313．

[9] 孙延标，黄润才．基于拍卖算法的多机器人编队时间优化[J]．制造业自动化，2021，43（12）：82-86．

[10] 李鑫滨，郭力争，韩松．一种分布式异构多AUV任务分配鲁棒拍卖算法[J]．北京航空航天大学学报，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

齐齐哈尔大学研究生创新项目（YJSCX2021077）

孙金龙（1995-），男，河北张家口人，在读硕士研究生，从事多智能体协同控制研究．E-mail：sjinlong_1025@163.com

李大辉（1968-），男，黑龙江齐齐哈尔人，教授，博士，从事多智能体协同控制研究．E-mail：1125073174@qq.com