一种基于动态蚁群劳动分工模型的多AUV任务分配方法

摘要

本发明公开了一种基于动态蚁群劳动分工模型的多AUV任务分配方法，首先建立异构多AUV动态任务分配问题数学模型，然后采用动态蚁群劳动分工模型，将AUV对应为蚂蚁；根据动态蚁群劳动分工模型的刺激—响应原理，将动态蚁群劳动分工的环境刺激模型、响应阈值模型及转移概率模型在异构多AUV系统动态任务分配问题上进行一一映射；最后采用循环竞争方案，解决任务冲突问题，为每个AUV分配任务。本发明方法能高效地完成任务分配过程，与传统的群智能任务分配方法相比，具有很好的自组织性、鲁棒性及快速性且能得出无冲突的任务分配方案。

说明书

技术领域

本发明属于水下航行器技术领域，具体涉及一种多AUV任务分配方法。

背景技术

AUV任务分配通过构建科学健壮的数学模型，设计优化算法完成任务配置，使个体的资源得到充分利用，高效地完成任务，体现了多AUV系统的高层组织形式与运行机制。因此，针对异构多AUV系统和海洋环境的特殊性，为提升多AUV系统的智能化水平，开展多AUV系统协同任务分配方法的研究具有重要的意义。

传统的任务分配方法如数学规划法、遗传算法(GA)、蚁群算法(ACO)、粒子群算法(PSO)通过不断的扩展和改进已经成功应用于多旅行商问题、车间调度问题、多处理器资源分配问题、车辆路径问题等。如曾文权通过设置PSO算法中速度惯性权重和加速度系数的自动调整，以及引入GA中的变异操作，实现了对PSO算法的改进，运用改进的PSO算法解决虚拟企业中的任务分配问题。秦新立针对传统ACO求解多机器人任务分配收敛速度慢且易陷入局部最优问题,引入局部优化变异算子和改进模拟退火算法来解决多机器人任务分配问题。这类集中式算法虽然易于理解，理论上可以获得任务分配的最优方案，但巨大的计算复杂性对于中心节点来说是一个巨大的挑战，不适合大规模的任务分配系统。另外，战场具有高度的不确定性和动态性，在没有充分利用智能体自适应和协同特性的情况下，很难处理任务重新分配，集中式方法获得的结果具有非常普通的实时性能。

为了充分利用智能体的协同特性，许多分布式算法如面向协商的熟人网和合同网分配方式，对策论联盟形成策略，依据价格的市场拍卖，面向结构的自组织方法等是动态环境中常采用的任务分配方法。如Cheng Q研究了一种用于多AUV系统的基于拍卖的多约束任务分配算法，提出一种多层成本计算方法，其中根据四种类型的约束将成本的计算分为四层，解决了多个约束问题。Lee考虑到机器人的资源问题，提出了一种面向资源的分布式拍卖算法，在拍卖过程中具有有限通信范围的客户代理和机器人构建一个自组网络树，并以分散的方式相互协商进行任务分配。然而这类分布式算法过度依赖于系统中的信息交换和共享，对时延要求较高。故寻找一种具有良好的自组织性、鲁棒性以及快速性的任务分配方法在水下动态任务分配问题上尤为迫切。

群集智能是指众多行为简单的个体相互作用过程中涌现产生的整体智能行为。蚁群作为一类社会性群体，其劳动分工行为具有明显的自适应的特征。令人惊奇的是，蚂蚁是在并不知晓任何关于群体需求的全局信息的情况下，自动地对群体内的个体进行分工，并达到相对平衡，其结果不但使得每个蚂蚁都在忙碌地工作，而且任务的分工又恰好符合群体对各项任务的要求。这体现了蚁群劳动分工的一个显著特点就是由个体行为柔性产生群体分工的可塑性，即执行各项任务的蚂蚁的比率在内部繁衍生息的压力和外部侵略挑战的作用下是可以变化的。这种自下而上的机制强调个体对环境的动态响应，并通过个体的本地意识和响应交互来产生全局自组织行为。蚁群劳动分工在解决任务分配过程中有很好的柔性。在没有集中控制且不提供全局模型的前提下，蚁群劳动分工模型为寻找复杂的分布式问题的解决方案提供了基础。

发明内容

为了克服现有技术的不足，本发明提供了一种基于动态蚁群劳动分工模型的多AUV任务分配方法，首先建立异构多AUV动态任务分配问题数学模型，然后采用动态蚁群劳动分工模型，将AUV对应为蚂蚁；根据动态蚁群劳动分工模型的刺激-响应原理，将动态蚁群劳动分工的环境刺激模型、响应阈值模型及转移概率模型在异构多AUV系统动态任务分配问题上进行一一映射；最后采用循环竞争方案，解决任务冲突问题，为每个AUV分配任务。本发明方法能高效地完成任务分配过程，与传统的群智能任务分配方法相比，具有很好的自组织性、鲁棒性及快速性且能得出无冲突的任务分配方案。

本发明解决其技术问题所采用的技术方案包括以下步骤：

步骤1：建立异构多AUV动态任务分配问题数学模型；

步骤1-1：异构多AUV系统动态任务分配问题定义为在一定区域内，有N个异构AUV执行M个不同特性的任务，且在执行过程中，任务的数量和状态会发生变化，为保证任务执行的效率，需要异构多AUV系统实时进行动态任务分配；

步骤1-2：N个不同参数的AUV组成AUV群体，表示为AUV＝{AUV

将AUV的参数用集合进行描述，即：

{AUV_State AUV_Position AUV_Resource AUV_Speed AUV_Ability AUV_Scope}其中，AUV_State代表AUV的状态，指空闲或执行任务；AUV_Position代表AUV所处的位置；AUV_Resource代表AUV携带的资源总量，简化表示为RC；AUV_Speed代表AUV的航行速度；AUV_Ability代表AUV执行任务的能力；AUV_Scope代表AUV执行任务的范围；

步骤1-3：被AUV执行的不同任务集合表示为TASK＝{TASK

{TASK_State TASK_Position TASK_Resource TASK_Value}

其中，TASK_State代表任务的状态，指任务是否被完成；TASK_Position代表任务所处的位置；TASK_Resource代表任务的需求资源数量，简化表示为RT；TASK_Value代表任务的价值；

步骤1-4：将异构多AUV系统动态任务分配问题表示为集合{TASK，AUV，U

步骤1-5：建立异构多AUV系统动态任务分配问题的约束条件：

其中，决策变量x

式(1)中第1个条件表示同一时刻，一个任务能被多个AUV执行；

式(1)中第2个条件表示同一时刻，任意一个AUV只能执行一个任务；

式(1)中第3个条件表示同一AUV对于同一任务只能执行一次；

式(1)中第4个条件表示单个AUV或多AUV自行组成的联盟执行任务时，其携带的资源总量RC

步骤2：采用动态蚁群劳动分工模型，将AUV对应为蚂蚁；根据动态蚁群劳动分工模型的刺激-响应原理，将动态蚁群劳动分工的环境刺激模型、响应阈值模型及转移概率模型在异构多AUV系统动态任务分配问题上进行一一映射：

步骤2-1：环境刺激模型映射；

用s

其中，TASK_Value(j)表示第j个任务的价值；

各个AUV结合任务的环境刺激值与自身对任务的响应阈值决定是否执行该项任务，如果该项任务没有被执行，则该项任务的环境刺激值随时间变化而变化，其变化规则为：

s

其中，s

用

当AUV

s

其中，s

步骤2-2：响应阈值模型映射；

用ξ

其中，

φ

其中，N

其中，RC

ψ

用

AUV

ξ

其中，ξ

步骤2-3：转移概率模型映射；

用p

步骤3：采用循环竞争方案，解决任务冲突问题，为每个AUV分配任务；

步骤3-1：如果存在AUV

当所有AUV均被分配任务时，分配过程结束，结束循环竞争方案；

步骤3-2：所有AUV

步骤3-3：当存在任务被多个AUV选择，则执行步骤3-4至步骤3-13；

当每个任务都被N个AUV中的一个选择时，则结束循环；

步骤3-4：如果任务TASK

步骤3-5：提取已被分配任务TASK

步骤3-6：如果任务TASK

步骤3-7：分配ξ

步骤3-8：如果min(RC

步骤3-9：在满足RC

步骤3-10：如果max(RC

步骤3-11：将参与竞争的AUV按其对TASK

步骤3-12：将所有AUV分配去执行任务TASK

步骤3-13：将竞争中淘汰的AUV对应的p

步骤3-14：如果存在AUV

本发明的有益效果如下：

本发明引入动态蚁群劳动分工中的刺激-响应原理，将任务的状态预测纳入响应阈值，建立了动态蚁群劳动分工与多AUV任务分配问题之间的映射关系，同时针对任务分配过程中可能出现的任务冲突现象，提出了新的循环竞争方案以实现最大限度地利用AUV资源。本发明提出的方法能高效地完成任务分配过程，与传统的群智能任务分配方法相比，具有很好的自组织性、鲁棒性及快速性且能得出无冲突的任务分配方案。

附图说明

图1为本发明方法流程图。

图2为本发明方法循环竞争方案流程图。

图3为本发明实施例DACLD的相对运动结果图。

图4为本发明实施例DACLD的动态任务分配结果图。

图5为本发明实施例任务所需资源变化图(与ACO、PSO及GA相比)。

具体实施方式

下面结合附图和实施例对本发明进一步说明。

本发明态蚁群劳动分工模型方法进行改进并将其应用于多AUV动态任务分配中，根据动态蚁群劳动分工中的刺激-响应原理，将动态蚁群劳动分工中的响应阈值模型、环境刺激模型及转移概率模型在多AUV任务分配问题上进行一一映射，从而实现动态任务分配。为了避免在解决任务冲突问题时AUV资源被闲置，提出了一种循环竞争方案以实现最大限度地利用AUV资源，同时确保了每一分配结果的任务完成效率最高。

如图1所示，一种基于动态蚁群劳动分工模型的多AUV任务分配方法，包括以下步骤：

步骤1：建立异构多AUV动态任务分配问题数学模型；

步骤1-1：异构多AUV系统动态任务分配问题定义为在一定区域内，有N个异构AUV执行M个不同特性的任务，且在执行过程中，任务的数量和状态会发生变化，为保证任务执行的效率，需要异构多AUV系统实时进行动态任务分配；

步骤1-2：N个不同参数的AUV组成AUV群体，表示为AUV＝{AUV

将AUV的参数用集合进行描述，即：

{AUV_State AUV_Position AUV_Resource AUV_Speed AUV_Ability AUV_Scope}其中，AUV_State代表AUV的状态，指空闲或执行任务；AUV_Position代表AUV所处的位置；AUV_Resource代表AUV携带的资源总量，简化表示为RC；AUV_Speed代表AUV的航行速度；AUV_Ability代表AUV执行任务的能力；AUV_Scope代表AUV执行任务的范围；

步骤1-3：被AUV执行的不同任务集合表示为TASK＝{TASK

{TASK_State TASK_Position TASK_Resource TASK_Value}

其中，TASK_State代表任务的状态，指任务是否被完成；TASK_Position代表任务所处的位置；TASK_Resource代表任务的需求资源数量，简化表示为RT；TASK_Value代表任务的价值；

步骤1-4：将异构多AUV系统动态任务分配问题表示为集合{TASK，AUV，U

对于传统的任务分配方法(如蚁群算法)，U

步骤1-5：异构多AUV系统的任务分配是一个多输入，多输出，多约束以及多目标的优化问题。输入包括各AUV参数、各任务参数，输出包括任务与AUV的分配关系，面向任务的AUV之间资源分配关系。建立异构多AUV系统动态任务分配问题的约束条件：

其中，决策变量x

式(1)中第1个条件表示同一时刻，一个任务能被多个AUV执行；

式(1)中第2个条件表示同一时刻，任意一个AUV只能执行一个任务；

式(1)中第3个条件表示同一AUV对于同一任务只能执行一次；

式(1)中第4个条件表示单个AUV或多AUV自行组成的联盟执行任务时，其携带的资源总量RC

步骤2：采用动态蚁群劳动分工模型，将AUV对应为蚂蚁；根据动态蚁群劳动分工模型的刺激-响应原理，将动态蚁群劳动分工的环境刺激模型、响应阈值模型及转移概率模型在异构多AUV系统动态任务分配问题上进行一一映射：

步骤2-1：环境刺激模型映射；

用s

其中，TASK_Value(j)表示第j个任务的价值；

任务环境刺激值大小反应任务的紧迫程度，刺激值越大，任务越紧迫，则越容易吸引蚂蚁(AUV)执行该项任务。各个AUV结合任务的环境刺激值与自身对任务的响应阈值决定是否执行该项任务，如果该项任务没有被执行，则该项任务的环境刺激值随时间变化而变化，其变化规则为：

s

其中，s

用

当AUV

s

其中，s

步骤2-2：响应阈值模型映射；

用ξ

其中，

φ

其中，N

其中，RC

ψ

用

AUV

ξ

其中，ξ

步骤2-3：转移概率模型映射；

用p

步骤3：如图2所示，采用循环竞争方案，解决任务冲突问题，为每个AUV分配任务；

一般情况下，AUV选择p

以往的冲突解决方案大多只进行一次竞争，而被淘汰的智能体便不再参与此次任务分配，处于空闲状态。这种分配方案会造成AUV资源的浪费，且任务执行效率不高。因此针对以上问题提出如下冲突解决方案：

步骤3-1：如果存在AUV

当所有AUV均被分配任务时，分配过程结束，结束循环竞争方案；这样做既保证了AUV资源的合理利用，又保证了AUV群执行任务的高效性；

步骤3-2：所有AUV

步骤3-3：当存在任务被多个AUV选择，则执行步骤3-4至步骤3-13；

在一次循环中会解决所有组对任务有冲突的AUV间的竞争，而在竞争中落败的AUV会依p

当每个任务都被N个AUV中的一个选择时，则结束循环；

步骤3-4：如果任务TASK

步骤3-5：提取已被分配任务TASK

步骤3-6：如果任务TASK

步骤3-7：分配ξ

当多个AUV均依转移概率选择某个任务时，优先选用AUV资源满足任务所需资源的AUV而不采取合作方案。此外，由于AUV的响应阈值ξ

步骤3-8：如果min(RC

步骤3-9：在满足RC

步骤3-10：如果max(RC

步骤3-11：将参与竞争的AUV按其对TASK

步骤3-13：将竞争中淘汰的AUV对应的p

步骤3-14：如果存在AUV

当任务执行过程中剩余待执行的任务个数小于RC

具体实施例：

1、假设初始时刻有3个异构AUV和5个动态任务，每个AUV根据动态任务分配结果向所分配的任务移动，任务进入AUV的执行范围便会被执行，直到所有任务被完成，仿真结束。

AUV和任务的初始信息分别示于下表1和2中。

表1 AUV参数设置

表2 TASK参数设置

通过与基于ACO、PSO及GA的任务分配方法的结果进行对比，分析本文所提出的基于DACLD的任务分配方法的自组织性、鲁棒性和快速性。ACO、PSO及GA中的个体数目k为30只，每得到一次任务分配结果的迭代次数Nc为100次，目标函数是尽可能地使AUV群执行任务所需的时间及航程最小。本文所提DACLD中的公式(6)中，w

2、图3为多AUV依据DACLD去自主分配跟踪目标而产生的相对运动结果图。图4为DACLD整个过程中的动态任务分配结果图。

结合两图分析可知，t＝24s时AUV

3、图5为采用不同算法的总的TASK所需资源变化图。在任务执行过程中，总的TASK所需资源会随着任务被执行而不断降低直至变为0。

由图5可知，基于ACO的任务分配方法执行完成所有任务用时51s，基于PSO的任务分配方法执行完成所有任务用时53s，基于PSO的任务分配方法执行完成所有任务用时52s，而基于DACLD任务分配方法执行完成所有任务用时45s且所有任务均于基于三种任务分配方法之前完成，表明所提出的DACLD任务分配方法具有更高的执行效率。

4、表3反应了不同算法在计算机中运行的仿真时间对比。仿真环境为MATLAB2018a，计算机配置为2.2GHz Intel(R)Core(TM)i5-5200U处理器，12G RAM，WIN10家庭中文版。

表3 算法仿真时间对比表

算法时间效率可表示为每一步得到一个任务分配结果计算机所需要运行的时间。由表3可知，本文所提方法的算法时间效率要远大于ACO等群智能搜索算法的时间效率。这是由于ACO、PSO及GA为了保证算法结果收敛，需完成Nc*k次任务分配才得到一次最终的任务分配结果，而DACLD只需要完成一次任务分配即可，因而算法复杂度要远小于ACO等群智能搜索算法。