Research on multiple AUVs task allocation with energy constraints in underwater search environment

多AUV在水下搜索环境中的能量约束任务分配研究

作者: Hailin Wang, Yiping Li, Shuo Li, and Gaopeng Xu
单位： 中国科学院大学
发表期刊: Electronics, 2024.09

---

1. 概述

1.1. 研究背景

自主水下航行器（AUVs）是海洋学研究、水下监视和资源勘探等领域的重要工具。然而，水下任务环境具有独特的挑战性，特别是能量有限和通信困难。因此，如何在这些约束下高效地为多个AUV分配任务，以优化其整体性能和任务完成效率，成为了一个关键问题。

这项研究将多AUV任务分配问题（Multiple Robots Task Allocation, MRTA）定义为一个已被证明是NP-complete的容量限制车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）。在此之前，已有研究采用量子粒子群优化（QPSO）、强化学习（RL）等方法来尝试解决此类问题，旨在提高计算效率和降低能耗。

但很少有研究全面解决全局最优性、能耗优化和任务持续时间的结合问题。因此迫切需要创新的任务分配策略来确保多个AUV能够高效协同工作。

1.2. 研究贡献

论文的主要贡献在于为解决能量受限下的多AUV任务分配问题提供了一个新的理论框架和高效的求解方法。具体贡献如下：

1. 创新的建模方法： 将多AUV任务分配问题精确地建模为容量限制车辆路径问题（CVRP），旨在优化导航时间并兼顾能量消耗约束。
2. 保证全局最优解： 采用SCIP（Solving Constraint Integer Programs）求解器来解决该CVRP模型。与启发式算法相比，SCIP能够在合理时间内找到问题的全局最优解，从而显著提高解的质量。
3. 综合优化目标： 该研究全面地解决了全局最优性、能量消耗优化和任务持续时间这三个关键因素的结合，而此前的研究很少能同时兼顾这三点。
4. 实用指导价值： 研究成果不仅在理论上具有创新性，还为优化多AUV系统的任务规划和能源管理提供了实用的指导和可行的见解。

2. 研究方法

根据多机器人任务分配（MRTA）的分类法，本研究中的问题被归类为 SR-MT-IA 类型。

• SR (Single Robot Task): 每个任务都可以由单个AUV完成。
• MT (Multi-Task Robot): 每个AUV能够处理多个任务。
• IA (Instantaneous Assignment): 任务是在任务开始前被一次性分配的。

本研究的核心方法是建立一个基于CVRP的数学模型，并使用SCIP求解器进行优化求解。

2.1. 问题建模与公式化

该研究将问题公式化为一个优化问题：

• 变量定义:

  • 任务节点集合: X = { t 0 , t 1 , . . . , t n } X=\{t_{0},t_{1},...,t_{n}\} X={t0​,t1​,...,tn​}，其中 $t_0$ 是所有AUV的起始点（岸基）。
  • AUV集合: V = { v 1 , v 2 , . . . , v m } V=\{v_{1},v_{2},...,v_{m}\} V={v1​,v2​,...,vm​}。
  • 任务 $j$ 所需能量: $Pu(j)$。
  • AUV $v$ 的能量容量: $Au(v)$。
  • AUV $v$ 的速度: $Sv(v)$。
  • 节点 $i$ 和 $j$ 之间的欧氏距离: $d(x_i,x_j)$。
  • 二进制决策变量: $w_{ij}^v$，如果AUV $v$ 从节点 $i$ 移动到节点 $j$ 则为1，否则为0 。

• 目标函数:
  研究提出了两个目标函数：一个是最小化所有AUV中的最大行驶时间（min-max），另一个是最小化所有AUV的总行驶时间：

  1. 最小化最大行驶时间: $minma{x}_{v\in V}({\sum }_{i\in X}{\sum }_{j\in X}(\frac{d(x^i,x^j)}{Sv(\nu )}+Tp(i)w_{ij}^{\nu }))$
  2. 最小化总行驶时间: $min{\sum }_{v\in V}{\sum }_{i\in X}{\sum }_{j\in X}(\frac{d(x^i,x^j)}{Sv(v)}+Tp(i))w_{ij}^v$

• 约束条件:

  • 任务唯一性约束: 每个任务节点只能被访问一次：
    $$\sum _{v\in V}\sum _{j\in X}{w}_{ij}^v=1,i\in X^{\prime }$$
  • 路径归属性约束: 每个路径由同一个AUV完成：
    $$\sum _{i\in X}{w}_{ij}^v-\sum _{jk}^v{w}_{jk}^v=0,v\in V,i,j,k\in X,i\ne j\ne k$$
  • 能量容量约束: 每个AUV消耗的总能量不能超过其自身携带的能量容量：
    $$\sum _{i\in X}\sum _{j\in X}{w}_{ij}^{v}Pu(i)\le Au(v),v\in V$$
  • 最大航程约束: 每个AUV的行驶总距离不能超过其预设的最大航程：
    $$\sum _{i\in X}\sum _{j\in X}{w}_{ij}^{v}d(x_i,x_j)\le MaxPath(\vartheta ),v\in V$$
  • 路径连续性约束: 保证每个AUV的行驶路径是连续的

2.2. 算法与求解器

研究采用SCIP（Solving Constraint Integer Programs）求解器来解决上述建立的混合整数线性规划（MILP）模型。SCIP是一个先进的求解工具，它集成了分支定界算法、割平面、启发式方法和域传播等技术，能够高效处理复杂的约束整数规划问题。

SCIP-based MRTA-CVRP 算法流程:

2.2.1. 算法输入 (Input Parameters)

• X = { x i } i = 0 n X=\{x_{i}\}_{i=0}^{n} X={xi​}i=0n​: 任务节点的集合，其中 $x_0$ 是所有AUV共同的起始点（例如岸基），其余为目标任务点。
• V = { v i } i = 1 m V=\{v_{i}\}_{i=1}^{m} V={vi​}i=1m​: 可用的AUV集合。
• $P_u[j]$: 完成任务节点 $j$ 所需的能量。
• $A_u[v]$: AUV $v$ 自身携带的总能量容量。
• $dist[i,j]$: 任务节点 $i$ 和节点 $j$ 之间的距离。
• MaxPathLength[v]: AUV $v$ 的最大允许航行路径长度。

2.2.2. 算法输出 (Output)

算法成功运行后，会输出每个AUV的最优行驶路径。

2.2.3. 算法核心步骤 (Algorithm Steps)

算法的执行过程主要分为两大部分：构建约束模型和调用优化器求解。

第一步：初始化与预计算

1. 初始化能量: 为所有AUV初始化剩余能量变量。
2. 计算距离: 预先计算出每两个任务节点之间的欧氏距离，是后续路径长度和能耗计算的基础。

第二步：设定约束条件 (Set Constraints)

• 禁止立即返回 (No Immediate Return Constraint):

  • 目的: 确保AUV在完成一个节点的任务后，不会立刻返回该节点。
  • 实现: model.addCons(w[i,j,v] + w[j,i,v] <= 1)。 这条约束表示对于任意两个节点i和j，以及任意AUV v，从i到j的路径和从j到i的路径不能同时被选择，从而避免了无效的往返。

• 任务唯一性约束 (One AUV per Task Constraint):

  • 目的: 保证每一个目标任务点都仅由一个AUV服务。
  • 实现: model.addCons(sum(...) = 1, One_AUV_per_Task_)。这条约束规定，对于每一个任务节点j（起点除外），所有进入该节点的路径总和必须为1，意味着有且仅有一条路径（来自某一个AUV）指向该节点。

• 路径连续性约束 (Path Continuity Constraint):

  • 目的: 确保每个AUV的行驶路径是连续的，即进入一个节点的次数等于离开该节点的次数。
  • 实现: model.addCons(sum(w[i, j, v]) - sum(w[j, k, v]) = 0, Continuity_)。 这个“流量守恒”约束保证了对于任意AUV v和任意中间节点j，只要有路径进入j，就必须有路径从j离开，从而形成一条完整的路径链。

• 能量限制约束 (Energy Limit Constraint):

  • 目的: 确保每个AUV完成其所有分配任务所消耗的总能量，不超过其自身的能量容量。
  • 实现: model.addCons(sum(w[i, j, v] * Pu[j]) <= Au[v], Power_Limit_)。该约束将AUV v所经过的每个任务节点j所需能量 $P_u[j]$ 进行累加，并确保总和小于等于其能量上限 $A_u[v]$。

• 路径长度限制约束 (Path Length Limit Constraint):

  • 目的: 保证每个AUV的总行驶距离不超过其最大航程。
  • 实现: model.addCons(sum(w[i, j, v] * dist[i, j]) <= MaxPathLength[v], Max_Distance_Limit_) [cite: 191]。 该约束将AUV v所走的每段路径(i, j)的距离 $dist[i,j]$ 进行累加，并确保总距离不超过其最大路径长度 $MaxPathLength[v]$。

第三步：优化求解 (Optimize Solution)

1. 调用优化器: 在所有约束条件都添加到模型中之后，算法会调用SCIP优化器来求解这个构建好的约束模型。
2. 获取结果: 优化器会寻找满足所有约束条件并使目标函数（最小化总时间）最优的解。最终，求解结果以 travel_dict 的形式存储，其中包含了为每个AUV规划好的最优路径。

3. 实验

为了验证方法的有效性，研究进行了仿真实验，并与粒子群优化（PSO）算法进行了对比。

3.1. 仿真设置与结果

• 实验环境: 实验在一台配备Core i7-10750H处理器和16GB内存的Windows 10计算机上进行，SCIP求解器版本为8.0.4。
• 碰撞规避: 实验中未考虑AUV之间的碰撞问题，因为研究假设不同的AUV在预先分配的不同深度层工作，因此碰撞概率极低。

• 仿真场景: 研究模拟了6个不同的场景，涉及不同数量的AUV和任务节点。
  • 场景a (3 AUVs, 11 nodes): 成功找到最优解。
  • 场景b (4 AUVs, 8 nodes): 成功找到最优解。
  • 场景c (4 AUVs, 10 nodes): 成功找到最优解。
  • 场景d (4 AUVs, 20 nodes): 无解。结果表明，当前AUV数量和能量配置不足以完成所有任务。
  • 场景e (8 AUVs, 16 nodes): 成功找到最优解。
  • 场景f (8 AUVs, 20 nodes): 成功找到最优解。
• 求解效率: 在大多数可解的场景中，SCIP求解器在10秒内找到了最优任务分配方案，显示出很高的实用性。

3.2. 与PSO算法的对比分析

• 性能（目标值）对比:
  • 实验结果表明，尽管PSO可以提供可行的解，但SCIP求解器始终能找到更优（即目标值更低）的全局最优解。
  • 在场景a、e和f中，SCIP求解器的结果明显优于PSO算法。

• 计算时间对比:

  • 在计算速度方面，PSO算法通常更快，尤其是在小规模问题上。
  • 尽管如此，SCIP求解器的计算时间仍在可接受范围内。大多数问题实例在10秒内解决，其中一半在1秒内完成，证明了其在实际应用中的计算效率。

• 对比总结:
  该对比分析表明，虽然PSO算法在速度上有优势，但本研究提出的基于SCIP求解器的方法在解的质量上更胜一筹，能够保证全局最优性，并且计算时间合理，因此对于复杂的优化问题是更稳健的选择。

4. 结论、限制与未来方向

• 结论:
  本研究成功提出了一种基于CVRP模型和SCIP求解器的多AUV任务分配方法，该方法在处理能量约束下的导航时间优化问题时表现出色。它能够保证找到全局最优解，且计算效率高，为复杂水下环境中的多AUV系统部署提供了重要的理论和实践支持。

• 限制:

  1. 可扩展性: 对于大规模问题实例，求解器的性能可能会下降，导致处理时间变长。
  2. 动态适应性: 该方法对于参数频繁变化的实时动态环境灵活性较差，可能需要不断重新优化。
  3. 模型简化: 当前模型未考虑一些关键的现实世界因素，如三维空间问题、AUV转向时的惯性效应以及洋流的影响。

• 未来方向:

  1. 混合方法: 未来可以探索将SCIP求解器的最优性保证与PSO等启发式算法的快速性相结合的混合方法，以应对不同规模和时间要求的场景。
  2. 提升可扩展性: 采用并行化技术或分布式计算来提高算法处理大规模数据的效率。
  3. 转向分布式策略: 当前的集中式方法在仿真中有效，但实际应用需要能够在弱通信条件下运行的分布式任务分配算法。未来的工作将重点开发分布式策略，以增强系统的可扩展性、可靠性和对动态环境的适应性。