基于弹性平衡与动态规划的多机器人覆盖路径规划

《International Journal of Advanced Robotic Systems》：Multi-robot coverage path planning based on elastic balance and dynamic programming

　　

覆盖路径规划（Coverage Path Planning, CPP）是多种实际机器人应用的基础。多机器人的使用能够显著提升覆盖效率并增强系统鲁棒性。然而，大多数多机器人覆盖路径规划（Multi-robot CPP, MCPP）方法面临着任务分配不均衡以及冗余无效路径导致的效率降低等挑战。为解决上述问题，本文提出了一种融合弹性平衡（Elastic Balance, EB）机制与动态规划（Dynamic Programming, DP）机制的启发式MCPP方法。EB机制将回路的路径分割问题建模为弹性调整过程，通过识别弹性平衡状态确定最优分割点，从而有效平衡各机器人间的工作负载。DP机制将往返充电成本最小化问题建模为动态规划问题，通过搜索整个解空间以最小化非工作路径的成本。对比实验表明，所提方法在仿真环境和真实场景中均取得了最短的覆盖时间。

论文主体内容总结

1. 引言

论文指出覆盖路径规划（CPP）是军事、农业、工业、商业、救灾及城市生活等多个领域的基础性技术。随着问题规模扩大与多机器人技术发展，多机器人系统在CPP领域得到日益广泛的应用，相比单机器人具有更高的运行效率和更强的鲁棒性。然而，多机器人覆盖路径规划（MCPP）已被证明是NP难问题。从优化视角看，现有方法可分为两类：一类聚焦于任务平衡优化，从多机器人系统内部协调角度提升效率，具体又可分为区域优先分解法和路径优先分割法；另一类聚焦于冗余路径最小化，从单机器人视角优化个体路径效率。区域优先分解法将目标区域划分为多个子区域，每个子区域对应一台机器人的任务，虽然降低了问题复杂度，但忽略了区域分解与路径规划之间的耦合关系，可能导致覆盖路径不均衡。路径优先分割法先生成覆盖全部目标点的覆盖路径，再将该路径分割为多个子路径，但受机器人运动学及环境因素约束，常面临等成本分割失败、路径最优性受损及计算复杂度增加等挑战。无效路径最小化方法通过最小化不贡献覆盖的路径成本来提升效率，已有工作通常通过最小化转弯成本或优化充电位置来降低无效路径比例，但同样面临计算复杂度增加和部署困难等问题。本研究在已知环境中解决MCPP问题，综合考虑目标区域布局、机器人运动学约束、续航限制及充电站位置等实际约束，主要目标是通过平衡各机器人工作负载并最小化每台机器人的无效路径来提升整体覆盖效率。

2. 相关工作

2.1 基于任务平衡优化的MCPP

与单机器人相比，多机器人通过并行任务执行实现更高效率，实现多机器人覆盖工作负载的均衡是提升MCPP效率的关键因素，但该问题已被证明是NP难的。MCPP通常涉及任务分配和路径规划两个子问题。区域优先分解法将目标区域划分为N个分区，并对每个分区调用单机器人CPP算法生成对应覆盖路径。例如，Karapetyan等人使用聚类进行分解并在各子区域调用单机器人CPP；Zhou等人将MCPP问题建模为BCP_q并采用遗传算法进行均匀分解；Chen等人针对异构多机器人系统应用自适应聚类；Gao等人采用拍卖机制构建生成树以生成路径；Li等人基于机器人能力的信用模型对目标区域进行划分。这类方法将多目标优化的MCPP问题分解为一系列单目标优化的CPP子问题，降低了复杂度并提升了效率，但往往忽略区域分解与路径规划之间的耦合，可能导致覆盖工作负载不均衡。路径优先分割法先生成访问目标区域所有点的覆盖路径，再将该路径切割为K个片段，每个片段对应一台机器人。Karapetyan等人将高效覆盖路径发现问题定义为MinMax k-中国邮递员问题，并采用k-邮递员近似算法将路径划分为k条回路。Tang等人通过划分拓扑回路并将各片段分配给特定机器人来解决MCPP问题，通过迭代最小化所有片段的最大权重来生成长度均衡的片段。Lu等人提出了一种新颖的转弯最小化MSTC算法（TMSTC*），将转弯时间成本纳入路径权重。这类方法的关键优势在于能够充分利用现有单机器人CPP算法获得初始最优解，但对单机器人覆盖路径的分割可能损害全局最优性，且常忽略从起点到各子路径及返回起点的行程成本，可能导致机器人间工作负载不均衡。

2.2 最小化无效路径的MCPP

影响覆盖效率的关键因素之一是无效路径的存在，即不贡献实际覆盖的运动，包括转弯和往返充电站的行程。CPP方法通常分为两类：减少转弯成本和最小化充电时间。减少转弯成本的工作分为两类：第一类以转弯次数最少为目标，通过优化区域分解和选择高效行进方向实现；第二类聚焦于最小化累计转弯成本，考虑不同运动学约束的机器人对相同转弯产生不同成本，通过优化子区域访问顺序和区域内轨迹遍历顺序，或动态调整转弯速度和半径来降低成本。最小化充电成本的工作假设机器人电池寿命有限，可分为两类：第一类聚焦于优化充电站布置，如在线增量优化站点位置或调度备用无人机替换需充电的无人机；第二类直接最小化与充电相关的路径成本，如结合Dijkstra算法与果蝇优化缩短清洁机器人返回充电点的路径，或提出整数线性规划模型优化机器人初始充电状态以提升充电站利用效率。

3. 问题陈述

论文假设目标区域为包含多个障碍物的二维地图，所有障碍物形状和位置已知。生成对应的二值栅格地图，其中障碍物以黑色表示、自由空间以白色表示。每个栅格宽度为2×d，内部包含四个宽度为d的小方格。基于该栅格地图生成覆盖图G和生成图H。使用N台同构机器人执行覆盖任务，每台机器人从各自起点出发，完成分配的覆盖任务后返回起点。每台机器人配备能够覆盖宽度为d方格的传感器，具有相同的前进速度、加速度和续航时间T。若电量不足，机器人需返回对应起点完成充电。MCPP的目标是使用N台机器人覆盖栅格地图中所有自由空间，同时满足避障、最小时间成本和有限电池时间等要求。

4. 所提方法

本文提出一种基于弹性平衡与动态规划（EDM）的新颖MCPP方法，包含两个关键机制：基于弹性平衡（EB）的MCPP机制和利用动态规划（DP）的单机器人机制。EB接收目标环境、多机器人系统和任务需求信息，生成单机器人覆盖回路，并利用弹性力模型将该回路分割为N个负载均衡的初始子回路。随后，DP接收这N个子回路，通过动态规划最小化其往返充电成本。EB和DP按顺序单次执行，无需迭代反馈。

4.1 基于弹性平衡的MCPP机制（EB）

现有MCPP方法通过贪心策略将覆盖全部点的单机器人回路分割为N个子路径，但存在两个关键局限：当两个选定的子路径不相邻时，任务无法直接转移，必须通过中间子路径顺序传播；且这些方法虽旨在均匀分割单机器人回路，但未考虑各机器人从起点到分配子路径及返回的行程距离差异，可能导致总行程成本显著不均衡。为解决这些问题，EB算法首先构建初始回路并将其分割为N个片段，将第n个子回路Π_n的时间成本T_n建模为理想弹簧，其自然长度为T_min。T_n的变化产生不同的弹性力E_n，弹性力越大表示对应子回路的时间成本越高。当N个子回路的弹性力大小相等时，所有子回路的时间成本一致，表明N台机器人的工作负载达到均衡。EB选择与相邻子回路弹性力差异最大的子回路Π_m，在Π_m与其左右相邻子回路之间进行弹性力交换，使三者达到弹性力平衡。与MSTC*算法不同，EB不需要链式任务转移。通过多轮弹性力交换，N个子回路对应的弹性力逐渐趋于平衡，最终获得时间成本均衡的N个子回路。EB算法的每轮迭代计算复杂度为O(N)，设最大迭代次数为T，则整体计算复杂度为O(T·N)。

4.2 利用动态规划的单机器人机制（DP）

现有MCPP算法在有限续航条件下表现良好，但仍面临两个关键挑战：一是初始划分的子回路数量K不一定是机器人数量N的整数倍，导致部分机器人被分配显著更多的子回路，造成工作负载不均衡；二是对于分配固定任务集的机器人，其总运行时间包含任务执行时间和往返充电站的行进时间，而现有方法未显式优化充电行程造成的时间开销。DP算法确定最优的返回充电坐标，在平衡任务分配的同时最小化机器人往返的充电时间。假设机器人r_n在执行子回路Π_n时需要执行q_n次充电行程，则需在π_n上找到q_n个分割点。前一次充电行程会影响后续充电行程的选择，因此将子回路分解为多次充电行程构成多阶段决策问题。为此建立动态规划模型，定义状态变量dp[i]为机器人在给定充电结构下完成前i个点访问所需的最小总行程时间，状态转移方程为dp[i] = min(dp[i], dp[j] + f(j, i))，其中f(j, i)表示机器人从充电点s_n出发到达位置j+1，再到达位置i，最后返回充电点的总时间，且需满足续航约束f(j+1, i) ≤ T。通过回溯Parent表确定分割点，最终生成优化路径Π′及其总时间成本dp[N_p]。

5. 实验与讨论

实验部分将EDM与现有算法TMSTC和MSTC进行对比，在ROS Melodic和Gazebo仿真环境中使用TurtleBot Kobuki模型实现。性能评估采用两个指标：最大覆盖时间和最大无效覆盖比。最大覆盖时间衡量任务效率和多机器人间的任务平衡程度；最大无效覆盖比量化往返充电时间成本与总覆盖成本的比值。

5.1 模拟室外场景对比实验

实验采用具有随机放置障碍物的规则室外地图，机器人续航时间统一设为200秒，机器人团队规模从1到5变化。结果表明，EDM在大多数情况下能提供最少的最大覆盖时间；与两种对比算法相比，EDM的最大无效覆盖比最多可降低22.4%。在路径规划结果中，EDM在所有机器人中实现了最低的往返充电操作次数。

5.2 基于实际建筑和道路数据的场景对比实验

实验在丹佛市和纽约市两个实际街道地图上进行，地图尺寸分别为51.2×51.2 m²和102.4×102.4 m²。小地图中机器人数量设为1、3、5、7、9和11，续航时间设为400秒；大地图中机器人数量为2、4、6、8、10、12、14和16，续航时间设为2000秒。结果表明，在真实场景中，随着机器人数量和目标区域尺寸逐渐增加，EDM在大多数情况下始终提供最短的最大覆盖时间和最低的无效覆盖比，且表现出更低的充电往返频率。

5.3 不同续航时间的可扩展性验证

实验测试不同机器人续航时间下的最大覆盖时间和最大无效覆盖比，机器人数量设为11。当续航时间从300秒增加到700秒时，最大覆盖时间从1434秒降至920秒，无效覆盖比从45.68%降至15.33%。当续航时间达到500秒及以上时，无效覆盖比稳定在约15%–16%，表明进一步延长续航时间仅能带来边际改善。

6. 结论

本文在有限续航时间约束下解决MCPP问题，从单机器人和多机器人两个视角优化任务。首先，建立新颖的弹性模型以平衡多机器人间的覆盖工作负载；其次，提出动态规划模型以最小化单机器人无效路径的总成本。通过对比实验和可扩展性实验验证了所提方法的有效性。本文工作仍存在若干局限：所有机器人假设在速度和续航方面完全相同，未考虑异构多机器人系统；方法在测试规模之外的可扩展性尚未验证；仅在仿真中验证，尚未进行物理实验；未考虑传感器读数、定位及偏差。未来工作将扩展到异构机器人团队的覆盖路径规划。