面向地毯式搜索的多机器人两阶段自适应采样与滚动任务重分配方法

《Egyptian Informatics Journal》：A multi-robot two-stage adaptive sampling and rolling task reallocation method for carpet-like search

　　

在野外生态监测、搜救以及防灾任务中，通常采用地毯式搜索策略。任务的重要性和数量往往会动态变化，因此要求多机器人系统具备对动态变化进行灵活响应的能力。然而，传统任务分配方法大多面向静态小规模环境设计，难以满足大规模动态任务场景的需求，也未针对地毯式搜索策略进行优化。为解决这一问题，本文将地毯式搜索建模为狭长区域内多个任务的序贯执行过程，并提出一种两阶段自适应采样滚动任务重分配方法（TASRTRA）。在TASRTRA中，为解决随机概率采样导致高重要性任务被忽略的问题，研究人员构建了自适应概率采样机制，通过动态调整采样概率分布来提高高重要性任务的采样概率，从而在任务价值最大化与计算效率之间实现平衡。考虑到任务执行过程中任务重要性具有时变特征，研究人员通过引入动态重要性变化因子，改进了边际代价计算方法，使多机器人系统能够实时感知任务重要性的演化并动态重构任务分配方案。此外，为缓解任务路径相交所导致的碰撞风险升高，研究人员引入了相交路径交换策略，在提升系统整体性能的同时降低碰撞概率。实验结果表明，TASRTRA在动态场景及不同任务规模条件下均表现出更优性能。与传统方法相比，该方法平均奖励提升7.62%，平均运行时间降低15.15%。该方法能够有效适应多种动态任务条件，表现出较强鲁棒性，并显著优化任务分配效率。

本文发表于《Egyptian Informatics Journal》。Wan Xu、Ao Nie、Rupeng Chen、Wei Zhou、Yi Yu围绕地毯式搜索场景下的多机器人任务分配问题展开研究。文章首先指出，在野外生态监测、防灾与搜救等任务中，目标区域往往需要连续、无遗漏的全面覆盖，因而通常采用地毯式搜索（carpet search，一种强调完整覆盖的连续搜索模式）。这类任务具有明显的工程复杂性：一方面，野外山地峡谷环境地形崎岖、气候多变、灾害现场不确定性强，导致人工巡查、固定监测站和卫星遥感均存在覆盖不足、实时性差或成本较高等局限；另一方面，任务本身并非静态不变，任务的重要性会随时间升降，新任务也会不断出现，使得传统面向静态、小规模环境的任务分配方法难以适应。尤其是地毯式搜索具有狭长连续空间、任务顺序性强、覆盖完整性要求高等特点，进一步加剧了任务分配的复杂性。因此，开展针对该类场景的动态多机器人任务分配研究，核心目的在于同时兼顾任务收益、实时响应、路径安全与系统鲁棒性。

针对上述问题，研究人员将地毯式搜索抽象为狭长区域内多个任务的序贯执行过程，构建了两阶段自适应采样滚动任务重分配方法（TASRTRA）。该方法旨在解决三类关键矛盾：其一，面对大规模任务时，若对所有任务全量求解会显著增加计算负担，但随机采样又可能遗漏高价值任务；其二，任务重要性在执行过程中持续变化，静态分配结果会迅速偏离最优；其三，多机器人独立竞拍任务虽然能够快速得到分配结果，但可能引发路径交叉，增加碰撞风险并降低覆盖效率。为此，文章分别从初始采样、动态重分配与路径平滑三个层面提出改进机制。结果表明，TASRTRA能够在不同规模和不同动态条件下获得较高总体收益，并保持毫秒级计算效率，显示出较好的工程应用潜力。

研究人员采用的关键技术方法可概括如下：首先，将任务区域建模为沿长边展开的狭长子区域，并建立以总收益最大化为目标的数学模型，引入任务重要性变化项与时间折扣项；其次，在初始阶段采用基于任务重要性的自适应概率采样，在执行阶段采用基于子区域的滚动确定性采样与重分配；再次，通过引入动态重要性变化因子改进边际代价计算，并以相交路径交换策略优化机器人路径。全部验证基于仿真实验完成，包括Gurobi 10.0约束可行性验证及100次Monte Carlo仿真比较。

从建模层面看，文章将复杂山地峡谷环境简化为二维狭长区域，以矩形表示任务区域、点表示任务点，任务可随机分布于区域内部，并允许在执行期间出现重要性变化与新任务到达。系统运行框架为：中央控制中心下发初始任务，信号站向多机器人系统广播；机器人在执行任务过程中持续上报任务完成状态及任务状态信息；一旦感知到任务重要性变化或新任务出现，即触发动态任务重分配。该问题被形式化为一个收益最大化模型：目标函数综合任务重要性、时间折扣和执行时序影响，以归一化方式评估每个任务的收益；约束条件则确保每个任务仅分配给一个机器人、每个机器人至少执行一个任务、所有机器人从统一入口出发，并通过路径一致性、累计距离、累计时间等公式描述执行过程。模型中还通过E_j(t)=E_0j+β_jsin(t?t_start)u_j表达任务重要性的动态变化，体现出本文对时变任务属性的显式刻画。

在方法设计方面，TASRTRA的核心是一种“先全局、后局部”的两阶段机制。第一阶段为初始全局任务分配。由于大规模任务下全量求解代价较高，文章提出自适应概率采样机制，根据任务当前重要性动态调整采样概率。具体而言，先对任务重要性进行归一化，再引入扰动项δ₀e以保留一定随机性，最终得到与任务重要性正相关的采样概率。该策略的意义在于，相比传统随机采样或固定概率采样，它显著提高了高重要性任务被纳入候选集的机会，从而在计算代价受控的前提下，减少关键任务被漏采样造成的收益损失。

第二阶段为子区域滚动任务重分配。文章注意到，地毯式搜索场景中的任务具有“沿长边连续展开”的空间分布特点，因此将任务区域按x方向划分为多个子区域，并依据任务密度自适应调整子区域长度Δx。研究人员以全局平均密度作为阈值Δρ，若当前子区域密度低于平均水平，则适当扩展窗口；若密度较高，则缩短窗口，以此获得更均衡的子区域划分。机器人在执行当前子区域任务的同时，开始生成并优化下一子区域的分配结果，从而形成滚动式更新机制。这种设计使系统无需对全局任务反复重算，而是仅在受影响的局部区域进行确定性采样与任务重排，因此更适合动态环境中的实时响应。

为使重分配能够真实反映任务状态变化，研究人员进一步改进了边际代价模型。传统基于任务插入收益的竞拍式分配方法，通常只依据静态任务价值进行边际收益评估，难以处理任务重要性随时间波动的情况。本文将动态因子λ_jE_j(t)纳入总收益函数S_k^p_k(t)，使机器人在计算某任务插入路径不同位置后的边际得分时，不仅考虑路径长度和时间折扣，也同时考虑任务价值的时变性。这样一来，当某任务的重要性升高时，其竞拍吸引力会及时增强；当重要性降为零时，则可自然从待执行集合中移除。这一改进直接支撑了动态环境中的在线重构能力。

除收益优化外，文章还考虑了多机器人协同中的路径安全问题。由于基于拍卖或竞价的任务分配往往强调“谁出价高谁得任务”，却不保证最终路径在空间上最优，机器人之间可能出现大量路径交叉，不仅带来碰撞风险，也可能造成重复覆盖。为此，研究人员提出相交路径交换策略。该方法首先基于向量叉积判断不同机器人路径段是否相交；若相交，则尝试交换相应任务点之后的路径片段，并重新计算整体收益；只有当交换后收益提高时，才更新路径。该策略并不改变任务分配框架的基本结构，而是在结果后处理中对路径进行平滑优化，因此能够在保持或提升总收益的同时降低路径交叉。

以下结合论文结果部分的小标题对主要发现进行概括。

4.1. Parameter sensitivity analysis
这一部分通过灵敏度实验确定TASRTRA的关键参数。针对扰动系数δ₀，研究结果表明，当δ₀接近0.1时，总奖励最高；若δ₀过大，随机性增强将引发不必要的任务切换，导致奖励下降、运行时间上升。针对初始采样概率p₀，总奖励随p₀先快速提升后趋于平稳，运行时间呈U形变化，说明过低概率导致初始解缺失、过高概率则扩大搜索空间，最终选取p₀=0.65作为较优基线。针对误差系数ξ，结果显示其决定了环境适应性与计算代价之间的平衡：ξ过小时系统过度敏感、重分配频繁；ξ过大则削弱局部密集区域的精细调整能力，最终确定ξ=0.045较为合适。该部分结果说明，TASRTRA的性能提升并非源于任意参数设置，而是建立在系统性的参数校准基础上。

4.2. Validation of the effectiveness of TASRTRA
这一部分在3000 m × 12 000 m二维区域中，以15台机器人和100个任务为例，验证算法有效性。研究人员先用Gurobi 10.0验证模型约束可行性，再将TASRTRA与HMTA算法进行对比。结果显示，HMTA的分配路径存在较大任务跨越与明显交叉，而TASRTRA通过分层自适应采样、滚动优化和交叉路径交换，形成了更紧凑、更平滑的任务路径。收益上，TASRTRA达到0.97254，高于HMTA的0.93859；尽管TASRTRA由于引入动态重分配机制而增加了一定计算量，但整体仍处于毫秒级，满足实时性要求。该部分证明了本文方法不仅在收益指标上优于对照算法，也在路径可执行性方面更符合实际协同搜索需求。

4.3. Performance analysis of dynamic task allocation TASRTRA
这一部分专门考察TASRTRA在动态子区域中的在线重分配能力。

4.3.1. Verification of time-varying importance
研究人员在第三个子区域中人为设置任务T21、T28重要性显著升高，T19重要性降为0，T9轻微上升，以模拟真实环境中任务优先级突变的情形。结果表明，TASRTRA能够根据新的重要性状态实时调整任务序列：对变化较小且边际收益不足以触发重分配的T9，算法保持原分配不变；对重要性显著变化的T19、T21、T28，则重构多个机器人的路径序列，移除已失效任务并重新分配高价值任务。该结果说明，动态重要性变化因子被有效嵌入了边际收益计算，能够驱动系统实现有选择的、收益导向的重分配，而非无差别地全局重算。

4.3.2. Changes in the number of tasks
在这一小节中，研究人员通过随机生成T30至T34五个新任务，模拟执行过程中子区域内的新任务到达。结果显示，重分配后新任务主要被插入到负载较低、且原路径跨度较大的机器人序列中，如机器人5、8和12获得新增任务，从而改善了原有路径中的大跨度问题，也体现出任务负载均衡效果。与此同时，新任务被“自然嵌入”原任务序列，没有造成大范围路径震荡，说明TASRTRA在动态插入任务时兼顾了局部响应速度与全局方案稳定性。进一步地，文章还在100次Monte Carlo实验中将该方法与No reset、Full reset、Single reset、Heuristic full reset、PR with fixed reset、PR with team reset以及CBBA等多种重置机制比较。结果显示，TASRTRA在面对持续到达的新任务或重要性波动时获得了更高的重分配收益，表明其自适应采样与滚动策略更善于定位受影响区域并快速恢复全局收益。

4.4. Comparison and analysis of different algorithms
这一部分将TASRTRA与CBBA、DSTA、MOSFLA-GA和HGA四类代表性方法进行系统比较，场景规模从10台机器人/30个任务扩展到60台机器人/150个任务，并采用100次Monte Carlo仿真以降低随机性影响。结果显示，在六种环境下，TASRTRA的总体收益均为最高，平均收益从0.90257到0.94103不等，整体明显优于其他算法；箱线图还显示其四分位间距较小，说明稳定性较好。时间方面，TASRTRA虽然略慢于HGA，但显著快于CBBA和DSTA，也优于MOSFLA-GA，且全程保持毫秒级运行。随着任务规模增大，TASRTRA的计算时间逐渐上升、在极端复杂场景下收益略有回落，但总体仍展现出较强的可扩展性与实时适应能力。这一部分从横向比较角度确认了TASRTRA在收益—效率综合表现上的优势。

从讨论意义上看，本文的贡献主要体现在三个层面。第一，它针对地毯式搜索这一具有连续覆盖与狭长空间特征的特殊任务形态，构建了更贴合场景本质的任务分配表述方式，而不是直接套用一般MRTA（multi-robot task allocation，多机器人任务分配）框架。第二，它通过两阶段采样、动态边际收益与路径交换三种机制的耦合，实现了“全局规划—局部自适应—路径安全优化”的一体化设计，在保证较高收益的同时兼顾实时性。第三，仿真结果表明，该方法在重要性波动和新任务到达两类关键动态扰动下均可稳定工作，因而对野外监测、灾害搜救等任务具有较强参考价值。

论文结论部分可译述如下：本文研究了地毯式搜索作业中的多机器人任务分配问题。针对这类具有特殊实际约束的任务分配需求，研究人员设计了TASRTRA算法。自适应采样策略平衡了任务重要性与计算效率之间的关系，滚动任务重分配方法能够妥善处理动态任务分配问题。改进后的边际代价计算模型充分考虑了任务重要性的时变特征，进一步增强了算法适应性。此外，相交路径交换策略通过降低机器人之间的碰撞风险提升了系统安全性，同时提高了总体收益并优化了任务分配方案。有效性实验表明，TASRTRA能够改善任务分配结果；动态响应实验表明，TASRTRA能够主动应对多种突发情况，并依据实际状态高效地重新分配任务；比较实验表明，TASRTRA在多种任务规模场景中均表现良好，相较其他算法取得了更优的任务分配结果与更高效率。