基于Voronoi分区实现多智能体集群的动态任务分配与多目标整体包围
《Mathematics and Computers in Simulation》:Dynamic Task Allocation and Whole-Group Encirclement of Multiple Targets in Multi-Agent Swarms via Voronoi Partitioning
【字体:
大
中
小
】
时间:2026年08月29日
来源:Mathematics and Computers in Simulation 4.0
编辑推荐:
**摘要**
多目标包围是多智能体系统中的一个基本问题。在现有研究中,实现对多个移动目标的整群包围仍然充满挑战,并且在包围过程中智能体资源往往分配不均。针对这些问题,本文提出了一种基于Voronoi划分的多目标动态任务分配与整群包围策略。具体而言,将多个目标建模为一个整合的
**摘要**
多目标包围是多智能体系统中的一个基本问题。在现有研究中,实现对多个移动目标的整群包围仍然充满挑战,并且在包围过程中智能体资源往往分配不均。针对这些问题,本文提出了一种基于Voronoi划分的多目标动态任务分配与整群包围策略。具体而言,将多个目标建模为一个整合的目标群,识别最外层目标并生成包围点。这些包围点引导智能体逐步约束群体边界,最终在整个目标群周围形成包围。随后,这些包围点作为Voronoi生成点,对二维工作空间进行划分。基于该划分,设计了一种根据区域负载进行动态调度的机制,使智能体能够根据每个区域内的智能体数量自适应地调整其分配的包围点,从而避免区域空缺和目标逃脱。为减少对目标运动的干扰并保持群体完整性,将连接最外层目标所形成的多边形定义为限制区域,并引入排斥势以防智能体穿越群体内部。此外,进一步设计了势修正项,以解决限制区域约束与调度机制相互作用导致的死锁问题。通过Lyapunov分析建立了所提出控制策略的稳定性,并通过大量仿真实验验证了其有效性。结果表明,所提出的策略提高了包围效率和资源利用率,同时在目标数量变化和智能体初始分布不均的情况下仍能保持鲁棒的性能。
**引言**
近年来,无人系统、分布式机器人和自主系统的快速发展激发了人们对群体智能和多智能体系统执行复杂任务的日益浓厚的兴趣。与单智能体系统相比,多智能体群体在自主性、分布式决策、鲁棒性和可扩展性方面具有显著优势[1]。受自然系统中集体行为的启发,群体协同依赖于自组织和分布式控制,以实现复杂环境中的灵活响应[2]、[3]、[4]。通过局部交互和合作控制,群体智能体能够在无集中监控的情况下完成复杂任务,同时对个体故障、通信约束和环境不确定性保持韧性[5]、[6]、[7]。这些能力使多智能体群体在目标搜索与跟踪[8]、[9]、环境监测[10]、协作运输[11]、[12]和包围控制[13]等领域得到了广泛应用。
群体协同的早期研究可以追溯到1987年,Reynolds根据对鸟类群体行为的观察提出了Boids模型[14]。该模型总结了协调运动的三个基本规则,即聚合、分离和对齐,为后续的集体运动研究奠定了基础。1995年,Vicsek等人[15]研究了受随机噪声影响的自驱动粒子系统,证明有序集体运动仍可通过局部交互涌现,展示了集体秩序的鲁棒性。Toner等人[16]随后对鸟群运动动力学进行了系统的理论分析,强调了方向对齐在维持集体秩序中的核心作用。他们进一步指出,仅靠局部感知可能不足以维持稳定的群体结构。为表征智能体间的交互,Gazi和Passino[17]提出了一种吸引-排斥交互模型,个体在远距离处相互吸引、在近距离处相互排斥,从而实现自组织聚集并避免碰撞。在此基础上,Olfati-Saber等人[18]建立了多智能体群体的系统协调控制框架,该框架结合了虚拟领导者引导、速度一致性和基于势的避障排斥。该框架为多智能体协调控制和群体行为分析提供了重要的理论基础。
在多智能体群体的各种协同任务中,包围是一个备受关注的代表性空间合作控制问题。其主要目标是引导多个智能体在目标周围形成稳定的包围结构,从而实现目标禁锢、监视或捕获[19]。因此,人们开发了各种包围控制方法,包括人工势场法、领航员-跟随者法[20]、[21]、[22]、[23]、基于行为的方法[28]、[29]、[30]、虚拟结构法[31]、[32]、[33]和博弈论方法[34]、[35]、[36]。
人工势场法构建与目标相关的势函数,其负梯度引导智能体向期望的包围构型运动。由于其直观的公式化和易于实现的特点,这些方法在早期的包围研究中被广泛使用。然而,人工势场通常包含多个局部极小值,在复杂环境中尤其如此,导致智能体陷入不期望的平衡状态。这可能导致包围失败或阵型不稳定。虽然势整形或辅助机制可以缓解这一局限性,但势场方法在复杂包围场景中的适用性仍然有限。因此,近期的研究越来越多地关注将势场思想与其他方法相结合,或进一步提升该方法。
领航员-跟随者方法通常在目标周围引入虚拟或物理领导者,其余智能体则被引导收敛于领导者或接近目标邻域,从而实现协同包围。在领航员-跟随者框架下,Luo等人[20]提出了一种基于距离的多目标跟踪和包围方法。在该方法中,每个智能体评估其到不同目标的距离,并优先选择较近的目标进行包围。然而,这种最近目标选择策略可能导致多目标场景中的智能体分配不均。某些智能体可能陷入决策死锁,导致某些目标的包围智能体过少或完全没有。Pei等人[21]通过开发一种局部聚集算法解决了这一问题,使智能体能够在局部信息约束下更均匀地跟踪和包围多个目标。Zhao等人[22]为非完整多智能体系统开发了一种基于仿生神经动力学的编队跟踪控制器。通过将分布式自适应估计器与受饱和约束的回溯控制器相结合,他们的方法在有限的领导者信息下实现了编队跟踪。此外,Mo等人[23]研究了领航员-跟随者分数阶多智能体系统的包围控制,设计了具有分离状态估计器的控制协议,使跟随者在不完全信息下形成稳定的包围。相关研究还探讨了轨迹跟踪和优化,以改善自主系统中的跟踪精度、约束满足和运动效率[24]、[25]。这些研究为实际运动约束下的编队跟踪控制提供了有用的参考。然而,这些研究主要处理规定轨迹跟踪或编队维持,因此不能直接应用于动态包围。Li等人[26]将每个目标建模为领导者并分配其影响区域,通过调节每个区域内的智能体数量实现速度收敛,同时排斥势使个体能够捕获每个目标。然而,由于所采用的包围规则,智能体只能对每个目标进行独立包围。因此,调度过程需要相当长的时间,降低了包围效率。
基于行为的方法通常赋予所有智能体平等的决策和控制权限。群体级协同从预定义的行为规则或偏好机制中涌现,引导个体行动朝向目标包围[27]。这些方法强调个体自主决策与集体行为涌现之间的关系,因此具有很强的直观性和灵活性。Huang等人[28]提出了一种基于松散偏好规则的自组织包围方法,使机器人能够根据局部行为规则自主移动,在无集中协调的情况下包围目标。此外,Xu等人[29]、[30]开发了一种基于吸引线段的行为规划方法,将目标吸引从传统的点扩展到线段,从而提高了路径规划中的运动安全性和合理性。然而,在大规模群体中直接组合多种行为规则会削弱智能体间的协调,使得难以维持稳定的整群包围结构,并可能导致局部冲突或结构碎片化。总体而言,基于行为的方法通常依赖全局或近似全局信息进行群体级协同设计,其控制策略难以用精确的数学模型刻画。同时,多条规则的叠加和调参也会增加计算复杂度。这些局限性影响了基于行为的方法在大规模多智能体包围任务中的可扩展性和实用性。
虚拟结构法从多个虚拟节点构建刚性或半刚性包围几何结构,并引导智能体到达这些结构上的预定位置。由于编队是由集体定义的而非由单一领导者定义,因此与领航员-跟随者方法相比,这类方法通常对领导者故障和通信中断更具容忍性。Yu等人[31]、[32]研究了多智能体系统的时间变化刚性编队,并采用分布式跟踪控制使智能体跟随目标轨迹同时形成包围链。Zhang等人[33]提出了一种基于径向基隐式函数的柔性形状生成算法,使包围结构能够在多种几何形态之间切换并扩展到多目标场景。然而,虚拟结构法的性能可能对智能体的初始分布敏感。当初始分布与期望结构偏差较大时,智能体可能需要较大的重新定位,从而增加收敛时间并降低资源利用效率。
博弈论方法通常将包围表述为追捕者与逃逸目标之间的对抗性交互。Li等人[34]将追捕者与目标的交互建模为动态博弈过程,分析了重复交互过程中个体策略的演化,使智能体能够发展出完成任务的协同行为。然而,在多目标包围场景中,状态和策略空间可能迅速增长,大幅增加计算复杂度。此外,这些方法可能也难以根据智能体的空间分布适应性地调整资源分配。Zhan等人[35]和Chi等人[36]设计了收益函数和策略更新机制,使多智能体系统在与目标的重复交互中逐步形成包围构型。然而,这些方法并未明确纳入包围点的几何构建或整群包围的结构要求,限制了它们随着空间构型变化而自适应重新分配智能体的能力。
Voronoi划分在多智能体协同中被广泛使用,因为它提供了一种根据空间邻近性分解任务空间的简单实用的方法。具体而言,在覆盖和部署应用中,Yasuda等人[37]利用局部Voronoi反馈实现了卫星群体的弹性分布式覆盖控制,而Faghihi等人[38]研究了已知和未知环境中的分布式最优覆盖控制,展示了基于Voronoi的空间分解在覆盖优化中的适用性。在探索和避障方面,Zhao等人[39]将动态Voronoi划分与强化学习相结合,支持未知环境中的多机器人探索和避障,而Zhu等人[40]开发了缓冲的不确定性感知Voronoi单元,用于定位和感知不确定性下的去中心化概率避障。在捕猎应用中,Dong等人[41]将Voronoi图纳入协作接力跟踪,以实现在监控区域内的目标捕获。Zhou等人[42]进一步将不确定性感知Voronoi单元扩展到具有任务分配和位置不确定性下避障的多机器人捕猎。总之,这些研究展示了Voronoi划分在多智能体覆盖、探索、避障、跟踪和捕猎任务中的实用性和适应性。然而,大多数研究使用Voronoi区域进行空间覆盖、导航或局部目标跟踪,未考虑种子点之间的动态资源平衡。
对以上研究[20]、[21]、[23]、[26]、[27]、[28]、[29]、[30]、[34]、[35]、[36]的综述表明,现有的包围研究大多聚焦于单目标场景或各目标独立处理的多目标场景。在多目标包围任务中,智能体通常被分配为对每个目标执行局部包围。当目标数量较少时,这类方法可以有效。然而,当目标密集分布或任务规模较大时,这些方法往往导致智能体分配不均、包围结构碎片化和全局协调减弱。此外,传统方法通常缺乏对多目标整体几何结构的统一建模框架,难以系统地保持包围结构的稳定性和完整性。因此,实现对多个目标的整群包围构成本文的第一个动机。
此外,大多数现有研究预先分配智能体到每个目标[26]、[31]、[33]、[34]、[35]、[36]或采用静态分配方案。这些方法未充分考虑包围过程中智能体分布、区域负载和任务动态的变化。随着目标分布的改变,固定分配策略可能无法维持平衡的包围资源,导致区域过载、空缺或资源浪费。
因此,使智能体能够根据目标运动进行动态重新分配构成了本文的第二个动机。此外,在许多多目标包围研究中,智能体不可避免地会影响目标运动,导致目标群体分散,使包围变得更加困难[26]、[31]、[32]、[33]。与此同时,智能体在选择目标和运动过程中也可能陷入僵局或局部极小值。因此,需要开发一种能够减少目标运动干扰并避免死锁的包围策略,这构成了本文的第三个动机。综上所述,本文的主要贡献如下:(1) 与现有的将多目标包围分解为几个独立的单目标任务或依赖预设编队结构的包围方法不同,本文提出的方法将多个目标建模为一个整体群体。基于最外层目标的空间分布,提出了一种整体群体的包围点生成方法。这种设计使智能体能够在整个目标群体周围构建包围圈,而不是独立包围单个目标,从而减少了冗余的包围行为,保留了全局包围结构。(2) 与固定分配和最近点分配方法不同,这些方法可能会产生过载或空缺区域,并低效地利用智能体资源,本文提出的方法采用动态生成的包围点作为Voronoi生成器,并将区域负载纳入调度机制。因此,智能体可以动态调整其分配的包围点,并向负载较轻的区域重新分布,从而提高分配平衡性,降低区域空缺和目标逃逸的风险。(3) 许多现有方法并未明确考虑智能体进入目标群体内部所造成的干扰。此外,运动约束与任务分配项之间的交互可能产生局部极小值或僵局。因此,为了在包围过程中保持目标群体的完整性,本文提出的方法将最外层目标形成的多边形定义为限制区域,并引入相应的排斥项以防止智能体穿过其内部。还进一步引入了一个势函数修正项,以解决限制区域排斥项与区域调度项之间交互所导致的不良平衡问题。这两个组件改善了包围过程的结构一致性和稳定性。本文其余部分组织如下:第2节介绍图论初步知识、Voronoi划分以及多智能体包围问题的建模。第3节提出所设计的整体群体包围策略,包括包围点的生成和基于Voronoi区域的动态控制方法。第4节通过Lyapunov分析建立所提出控制方法的稳定性。第5节呈现仿真结果、参数分析和对比研究,以验证所提方法的有效性。最后,第6节对本文进行总结。各章节概述 初步知识与问题建模:本节建立了所提包围策略的理论基础和数学框架。首先介绍图论初步知识,以描述智能体和目标的局部交互拓扑。接下来回顾Voronoi划分,作为任务分配的空间分解工具。最后,对智能体和目标动力学进行建模,为后续控制器设计奠定基础。多目标整体群体包围策略:本节提出了针对多个移动目标的整体群体包围策略,解释如何将目标建模为整合的目标群体,以及如何动态引导智能体在群体周围形成稳定的包围圈。首先识别最外层目标以生成包围点,这些点随后作为Voronoi生成器划分任务空间,并建立动态任务分配的基础。基于此划分,智能体...稳定性分析:本节对所提包围策略进行稳定性分析,旨在证明所设计的控制方法能够防止碰撞、促进连通组件内的速度一致性,并引导智能体和目标趋向稳定的群体结构。分析分为两部分,4.1节证明智能体控制输入的稳定性属性,4.2节分析目标控制输入的稳定性。仿真结果与讨论:本节呈现所提包围策略的仿真结果,设计三种不同目标数量和不同初始智能体分布的仿真场景,以评估所提方法的有效性和适应性,并与现有方法进行对比以进一步展示所提策略在多目标整体群体包围和动态调度方面的优势。此外,讨论了关键参数的选择标准...结论:本文解决了多目标包围中的几个关键挑战,包括整体协调不足和智能体分配不平衡问题。为应对这些挑战,本文提出了一种基于Voronoi划分的动态任务分配和面向多智能体集群的整体群体包围策略。该方法识别目标群体的最外层目标并动态生成相应的包围点,使多个目标能够被建模为...利益冲突声明:作者声明不存在可能影响本文工作的已知经济利益竞争或个人关系。致谢:本研究部分由国家自然科学基金(编号71571091和71771112)资助。数据可用性:数据可根据要求提供。李晨阳 | 杨永辉 | 韩一林 | 陈雪波 | 赵天新
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号