基于仿生狼群法的无人机群任务分配算法 |
您所在的位置:网站首页 › 无人机u1 › 基于仿生狼群法的无人机群任务分配算法 |
A task allocation algorithm for a swarm ofunmanned aerial vehicles based on bionic wolfpack method https://doi.org/10.1016/j.knosys.2022.109072 A task allocation algorithm for a swarm ofunmanned aerial vehiclesbased on bionic wolfpack method摘要 任务分配是 UAV 集群中一个非常重要的过程,但目前面临着大规模、实时性等约束,如何有效地进行任务分配具有一定的挑战性。因此,对狼群在自然环境中的行为特征进行建模,并利用其来解决复杂场景下 UAV 集群动态任务分配问题。具体而言,所提出的方法考虑非平衡任务分配问题,并利用任务调度算法使分配结果满足任务性能约束。提出了一种适用于复杂场景下 UAV 集群的路径规划算法和覆盖搜索算法。针对不同目标数量和随机目标位置的仿真实验表明,该算法具有较高的任务完成率,并能平衡无人机的负载,为复杂场景提供了一种合适的解决方案。 文章目录 A task allocation algorithm for a swarm ofunmanned aerial vehiclesbased on bionic wolfpack method一、介绍二、相关工作三、问题建模1. 对象定义1、无人机2、目标与任务3、障碍物 2.任务分配模型 四、 任务分配算法1.任务分配和调度任务分配任务调度重分配算法 总结 一、介绍仿生狼群特征:狼发现猎物后,猎物的信息会与狼群共享,然后狼决定是否等待其他狼合作猎杀猎物。狼群中的每只狼都能管理和执行捕猎任务。狼既是管理者又是执行者。打猎时,任务是被分配的,攻击是由个人组织的,这个人不一定是领导者,也不是固定的。为了防止群体中个体能力的分化和损失,狼注重任务分配的平衡,这有利于群体的发展。 本文研究的 UAV 集群具有以下特点:UAV 集群内信息共享,每架 UAV 可以分配任务并执行。UAV 集群中领导者和执行者之间没有固定的划分,求解算法还需要平衡和协调任务分配问题。 本文分别提出了一种适用于本文所研究的复杂场景的任务分配、路径规划和覆盖搜索方法。 任务分配:将其转化为非平衡分配,并通过改进的匈牙利算法进行求解。此外,提出了一种重分配算法来平衡任务负载。路径规划:受 Theta*算法的启发,提出了一种适用于动态环境治理下的无人机集群的路径规划方法。覆盖搜索:提出了一种基于动态人工势场的无人机集群覆盖搜索算法。后一种算法解决了无人机在复杂场景中进行并行搜索时,难以定位的问题。 二、相关工作离线任务分配问题可以转化为组合优化问题并集中求解,但通常需要大量时间来计算最优解。 在线任务分配算法常用于解决动态任务分配问题,同时适用于集中式和分散式多智能体系统架构。 将任务分配过程分为三个子过程 :任务分配、路径规划和覆盖搜索。 最初,无人机集群需要搜索地图上的目标。然后,无人机集群为搜索目标生成任务并计算执行任务的代价。根据代价值进行任务分配,无人机集群根据任务分配结果执行设计的路径规划并执行任务。 1. 对象定义 1、无人机
为了描述任务分配过程,为每个UAV对象ui定义了costi,waiti和donei三个列表。 – 搜索任务时,每个无人机计算任务的成本并将其保存在costi列表中 – 任务分配后,每个无人机接受一些任务并将其保存在waiti列表中 – 每次UAV执行任务后,它都会将任务保存在donei列表中,以评估最终结果 2、目标与任务![]() 值得注意的是,每个目标都分为三个需要顺序执行但不能连续执行的任务。这些任务类型表示为A,B和C,此约束称为任务顺序约束。其中,只有任务B可能需要多个无人机的配合,而A和C则可以由单个无人机来完成。
为了方便路径规划和覆盖范围搜索过程,定义了地图中障碍物的对象。在不失去一般性的情况下,障碍物可以表示为矩形的组合 ![]() 所有无人机和任务的成本矩阵和成本函数 在某个时刻,假设有nτ任务要分配,并且nµ的uav可以参与任务分配过程
损失函数L 涉及两个方面: 飞行距离和威胁 利润函数P考虑群体利润和个体利润两个方面
本文将任务分配问题考虑为一个带约束的组合优化问题,其中定义Xik为无人机UI对任务τk的决策变量,即如果任务τk被分配给无人机Ui,则它变成1。 否则为零。 任务分配问题模型: 对于本文实现的动态任务分配过程,下面列出了一些主要假设: 场景图是所有无人机事先知道的。每架无人机都可以与任何其他无人机共享信息。每架无人机的尺寸都可以忽略不计。执行任务的持续时间可以忽略不计,即任务开始后立即完成。每架无人机在一定时间间隔内的步长是相同的,即每架无人机具有相同的速度。 四、 任务分配算法动态任务分配问题包括任务分配、路径规划和覆盖搜索三个子问题。将任务分配问题视为任务分配的核心问题,而将路径规划和覆盖搜索视为两个独立的子问题。 任务动态分配框架 在本工作中,任务分配被认为是非平衡分配问题,因为它得到了比平衡分配问题更好的解。 对于非平衡指派问题,采用改进的匈牙利算法,在满足以下方程的条件下提供了代价最小的指派方案: 改进的匈牙利算法的步骤如下 步骤1:对于成本矩阵的每一列,每个数字减去该列的最小值。 然后对每一行重复此过程。 一旦此过程结束,每行和每列至少有一个零。步骤2:用最少的水平线和垂直线的数目代替所有的零。 如果行数等于行数,则转到步骤4。 否则,请执行步骤3。步骤3:找出第二步中画出的线没有覆盖的位置的最小值。 从线条未覆盖的值中减去最小值,将最小值添加到线条交叉点处的值,删除所有线条,跳回步骤2。步骤4:对于只有一个零的每一行,查找零所在的列。 将列号对应的任务分配给行号对应的无人机。 然后,删除此列中的其他零,因为每个任务只能分配给一架无人机。步骤5:对于多个零的行,根据原始成本矩阵,将这些零所代表的任务分配给成本最低的无人机。 然后,删除零所在列中的其他零。步骤6:重复第4步和第5步,直到分配完所有任务。 任务调度解决分配问题可以为每架无人机提供一组任务。 为了满足任务顺序和协作约束,需要进行任务调度。 在此过程中,对每个无人机任务集中的任务进行判断。 如果任务满足约束条件,则将其放置在无人机任务序列中,并从任务集中删除。 如果任务不符合约束条件,将由另一架无人机进行判断。 最终不能满足约束的任务将被放回列表T中,并从任务集中删除。 判断过程继续进行,直到所有集合都为空。 在这项工作中,假设执行任务的持续时间可以忽略不计,即任务开始后立即完成。 一个任务调度示例涉及表2所示的无人机和任务,其中任务必须按照A→B→C的顺序执行。 在任务调度过程中,首先判断U1的任务集中的B1任务。 给定不满足任务顺序约束,U1应该等待,判断U2的A1任务。 该任务满足约束条件,被添加到U2的任务序列中。 但是U2的C1任务不满足约束条件,因为B1还没有完成。 因此判断U3的B2任务,不符合约束条件,因此U3应该等待。 然后返回U1的任务集,判断B1和A2满足约束条件,将其加入U1的任务序列中。 任务B2满足任务顺序约束,但需要三架无人机协同执行。 因此,它首先被放入U1的任务序列中,必要时根据另一个无人机的任务序列进行调整 。现在U2的C1任务满足约束条件,因为U2可以在U1完成B1后立即执行C1。 此后,U2需要等待U1协同执行B2,对于U3也是如此。 最后,U3的C2任务被添加到任务序列中。 实例的最终结果在图得到了说明 3. 仿生狼群无人机群在任务分配过程中要平衡任务负载。 然而,在实验过程中,发现非平衡分配算法偶尔会导致负载不平衡。 因此,使用比平衡分配方案提供更好结果的再分配算法。 这是因为非平衡分配比平衡分配获得了更好的解,而重新分配算法在改变解的同时保持了这一优势。 具体结果将在仿真实验中给出,而算法1中介绍了重分配算法。 考虑到再分配算法,它首先对无人机群的负载进行平均,然后负载高于平均值的无人机按照成本值从高到低的顺序将其部分任务发送到任务列表中,使得无人机的任务负载不超过平均值。 最后,任务负载低于平均值的无人机根据成本值接收列表中的任务。 所接收的任务的顺序被适当地安排,以最小化执行它们的额外成本。 为了使新的任务序列满足约束条件,只考虑不需要协作且指向同一目标的任务。 提示:这里对文章进行总结: 总体来说就是用改进的匈牙利算法做任务分配,然后再根据约束条件进行任务调度,最后再进行重新分配任务。 将任务分配问题看作一个非平衡分配问题,利用改进的匈牙利算法进行求解,从而降低了无人机群体任务的执行成本。 那么,在保持高净利润的基础上, 提出了一种任务重分配算法,增加了任务负载的均衡性,有利于群体的发展。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |