💻 computer science

Reactive Replanning Using a Target-State-Driven Strategy for Heterogeneous Multi-Robot Systems under Counting LTL Constraints

本文提出了 TRRS，一种目标状态驱动的反应式重规划策略，该策略利用后向时界混合整数线性规划公式，在计数线性时序逻辑（LTL）约束下的异构多机器人系统中，动态处理位置偏移和优先级更新，并通过仿真和物理实验证明了其性能优于静态和贪婪基准方法。

原作者： Ting Jiao, Mengge Wang, Yuwei Wang, Rong Zhang, Huanrong Ren

发布于 2026-09-23

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Ting Jiao, Mengge Wang, Yuwei Wang, Rong Zhang, Huanrong Ren

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一支被派往灾难现场寻找幸存者的救援机器人队伍。在一个完美的世界里，地图会保持静止，幸存者会留在原地，而机器人会遵循一个预先写好的单一脚本直到终点。但现实世界是混乱的。一名幸存者可能会爬到一个更安全的地方，或者一个来自不同位置的更紧急的求救信号可能会传来。如果机器人固守着执行原始脚本，它们可能会浪费宝贵的时间前往一个已经移动的人那里，或者因为它们的清单是几小时前编写的，从而忽略了一个关键的新任务。这就是必须在变化环境中协作工作的机器团队所面临的核心挑战：如何让你在上一秒还完美的计划，不至于在下一秒就变得毫无用处？

解决方案在于一个概念，叫做反应式重规划（reactive replanning）。系统不再是在开始时计算一个巨大的、不可更改的路径，而是不断观察世界，检测变化，并即时重新计算最佳行动方案。当团队由不同类型的机器人组成（每种机器人都有其自身的能力），且任务对发生顺序和内容有严格规则时，这会变得尤为困难。研究人员早已知道你不能简单地忽略这些规则，但寻找一种能够足够快地更新计划以满足实时需求的方法，一直是一个主要的障碍。

来自山西大学的一个研究小组开发了一种新方法来解决这个问题，专门针对在复杂规则下工作的混合机器人团队。他们将该系统称为 TRRS，即“目标状态驱动的反应式重规划策略”（Target-State-Driven Reactive Replanning Strategy）。其核心思想是将机器人的任务视为一个需要不断调整的“生命体状态”，而非一份固定的待办事项清单。研究人员构建了一个数学框架，使机器人能够处理两种特定类型的变化：一是目标移动到了新位置，二是目标的紧迫程度发生了变化。

在许多之前的系统中，这两类变化被同等对待，或者由软件中两个相互独立的模块分别处理。而这种新方法认识到它们本质上是不同的。如果一个目标移动了，机器人的当前路径在物理上就被中断了；机器人必须停止手头的工作，立即前往新地点。然而，如果仅仅是目标的优先级发生了变化——即任务变得更重要但位置没变——系统则会表现得更加谨慎。它允许机器人完成当前的作业，然后再转向那个新的紧急任务。这种区分防止了机器人因为频繁中止即将完成的任务而浪费能量，同时也确保了在物理世界发生位移时，它们能够做出即时反应。

为了做出这些决策，该系统使用了一种称为“混合整数线性规划”（Mixed-Integer Linear Programming）的方法。通俗地说，这是一种解决包含许多变量和严格规则的谜题的强大方式。研究人员设置了问题，使计算机必须为每台机器人找到一条既能满足任务规则、又能避免碰撞，同时又尊重每种机器人类型不同能力的路径。由于一次性为一整天的作业求解时间过长，团队采用了“收缩视界”（receding horizon）方法。这意味着计算机只规划一个较短的时间窗口，求解该窗口内的谜题，然后仅执行第一步。随着时间的推移和新信息的到来，窗口会向前滑动，计算机随后求解一个全新的、略微更新后的谜题。这使得思考时间足够短，能够在机器人实际移动的同时进行。

研究人员在两种截然不同的环境中测试了该系统。首先，他们在开放空间进行了模拟，要求机器人在遵循访问区域并返回安全区等复杂规则的同时进行操作。其次，他们在狭窄的走廊中进行了测试，这是一个机器人极易卡住或互相阻挡的狭小空间。在这两种情况下，他们都将新方法与两种旧方法进行了对比：一种是无论发生什么都坚持静态计划的方法，另一种是机器人仅仅抓取最近可用任务而不与其他成员协调的方法。

结果非常明确。静态计划在两种场景下都完全失败了，因为它无法适应移动的目标。简单的“抓取最近任务”的方法在开放空间表现尚可，但在狭窄走廊中却崩溃了，因为缺乏协调导致机器人互相阻塞并陷入僵局。然而，新系统在每一次测试中都取得了成功。即使在目标移动和优先级变化的条件下，它也能完成开放空间和狭窄走廊中的所有任务。该系统也足够快，足以用于实际应用；每次需要重新计算计划时，耗时不到十分之一秒。

为了证明该概念在计算机模拟之外也有效，团队构建了一个由两台小型轮式机器人组成的物理测试。他们设定了一个场景：机器人需要将一个背包和一个书本搬运到一个储物箱中。在任务进行到一半时，一名人类将书移动到了一个新位置，并引入了一个新的高优先级任务：递送水。系统立即检测到了这两种变化。它暂停了优先级较低的书本任务，派遣一台机器人先去递送水，然后恢复书本任务，引导机器人前往书本的新位置。机器人实现了无缝衔接，证明了该逻辑在物理世界中同样成立。

这项工作表明，赋予多样化机器人团队在不失去全局视野的情况下“随机应变”的能力是可能的。通过区分“目标已移动”和“任务仅是变得更紧急”这两种情况，该系统避免了不必要的混乱。它确保了机器人在面对不可预测的环境时，依然能够保持高效和协作。虽然目前版本的系统在处理少量机器人时效果最好，但研究人员认为，这是向在真实灾难区部署规模更大、能力更强的机器人团队迈出的至关重要的一步，因为在那些地方，刚性的计划与灵活的响应之间的区别，往往决定了成功与失败。

技术摘要：针对异构多机器人系统在计数 LTL 约束下的目标状态驱动型反应式重规划策略

1. 问题陈述

在动态异构多机器人系统（HMRS）中，由于执行过程中目标属性的意外变化，静态规划往往会失效。具体而言，目标可能会发生位置偏移（空间坐标变化）或优先级更新（紧迫程度变化）。现有方法通常将这些变化视为独立因素，或者将重规划与任务分配及优先级仲裁解耦。此外，标准的线性时序逻辑（LTL）规划难以处理异构团队所需的定量资源约束（例如，“区域 $S$ 内必须至少有 $N$ 台 $j$ 型机器人”）。

本文解决的核心挑战是如何在一个统一的混合整数线性规划（MILP）框架内，针对异构团队同时整合位置偏移和优先级更新，并保持在线执行的可行性。该系统必须在满足**计数 LTL（cLTL）**约束的情况下（即同时强制执行时序逻辑和特定类型的定量资源限制），在目标动态变化时仍不违反任务约束。

2. 方法论：TRRS 框架

作者提出了 TRRS（目标状态驱动的反应式重规划策略），这是一个旨在响应目标状态变化以反应式重规划轨迹的框架。该方法由三个集成组件组成：

2.1 统一 MILP 编码

协作规划问题被表述为一个联合优化任务分配与轨迹生成的 MILP。

系统模型： 工作空间是一个离散网格图 $G=(V, E)$ 。机器人团队由异构类型 $j \in [m]$ 组成，其中每种类型 $j$ 拥有一组机器人 $K_j$ 。目标 $P(t)$ 是随时间变化的，具有空间坐标 $\hat{p}_k(t)$ 和优先级水平 $pri_k(t)$ 。
约束：
- 运动学与碰撞： 机器人可以在相邻顶点之间移动或保持静止。顶点互斥确保不同机器人不会同时占据同一个单元格。
- cLTL 规范： 任务使用 cLTL 进行规范，它扩展了标准 LTL 并引入了计数谓词（例如， $tp(S, N^j)$ ）。这些谓词通过 big-M 重构技术进行线性化，以强制执行诸如“至少 $N$ 台 $j$ 型机器人在区域 $S$ 内”之类的约束。
- 目标函数： 在满足运动学、碰撞和 cLTL 约束的前提下，最小化总行驶成本（欧几里得网格距离）。

2.2 状态感知触发机制

TRRS 采用了一种差异化的触发机制，区分两种类型的目标变化，并应用特定的抢占规则：

位置偏移 ( $E_{pos}$ )： 如果目标的当前位置发生变化，现有的轨迹在物理上变得过时。系统会触发立即抢占，中止当前任务并立即将机器人重新分配给新目标。
优先级更新 ( $E_{pri}$ )： 如果仅优先级发生变化，系统不一定会中止当前任务。相反，它会重新排序任务队列。机器人被指示在切换到新分配的高优先级目标之前，先完成当前任务，除非优先级变化伴随着位置偏移。
耦合事件： 如果两者同时发生，则执行全量刷新并进行立即抢占。

2.3 滚动时界控制

为了确保 MILP 在在线执行中保持计算可行性，TRRS 采用了滚动时界（滚动窗口）方法：

全局时界 $T$ 被划分为若干个固定长度为 $h$ 的短窗口（实验中设置为 $h=7$ ）。
在每一轮中，MILP 仅针对当前的窗口进行求解。当前窗口的终止状态作为下一窗口的初始条件。
重规划由检测到目标变化（通过触发机制）或当前时间窗口到期所触发。

3. 核心贡献

面向异构团队的统一 cLTL 框架： 本文构建了一个 MILP 公式，能够在单一约束框架内捕捉目标位置和优先级的变化，克服了以往基于 LTL 规划中常见的解耦处理方式。
差异化抢占逻辑： 与将所有变化视为同类情况的现有方法不同，TRRS 区分了位置偏移和优先级更新。它对空间变化应用立即抢占，但允许对仅优先级变化的情况完成当前任务，从而有效地减少了不必要的在线重计算和任务放弃。
通过滚动时界实现在线可行性： 通过采用短滚动窗口，该框架确保了 MILP 解能在适合实时部署的有界计算时间内返回。
验证： 该方法通过蒙特卡洛模拟和物理机器人实验得到了验证，证明其性能优于静态和贪婪基准方案。

4. 实验结果

作者在开阔空间环境和狭窄走廊环境中评估了 TRRS，并将其与静态 MILP (S-MILP) 和事件触发贪婪 (ET-Greedy) 再分配算法进行了对比。

仿真性能（每个场景 30 次蒙特卡洛运行）：
- 成功率： 由于无法适应变化，S-MILP 在两种场景中均完全失败（0.0% 成功率）。ET-Greedy 在开阔空间中达到了 99.3% 的成功率，但在狭窄走廊中由于拥堵和死锁，成功率降至 29.3%。TRRS 在两种场景中均实现了 100% 成功率。
- 任务完成度： TRRS 在两种环境中均保持了 100% 的完成度。ET-Greedy 在开阔空间中达到 99.8%，但在狭窄走廊中仅为 50.9%。
- 效率： 在开阔空间中，TRRS 将平均执行步数从 101.6 步（ET-Greedy）降低至 94.6 步。在狭窄走廊中，TRRS 需要 59.4 步，而基准方案则出现了截断或失败运行。
计算开销： 触发重规划轮次的 MILP 平均求解时间为 0.111 秒。在一次任务中大约有 9.8 次重规划轮次，累计求解时间约为 1.09 秒，证实了其适用于在线执行。
物理验证： 通过两台差速驱动机器人的物理实验验证了该策略。当一个目标（一本书）被手动移动且一个新的高优先级任务（送水）被引入时，系统成功地重新排序了任务，暂停了低优先级采集任务，执行了高优先级递送任务，随后恢复了采集任务。

5. 重要性与主张

本文声称 TRRS 解决了动态多机器人协作中的一个关键空白：即在形式化 cLTL 约束下如何同时处理位置和优先级变化。作者指出，其差异化触发机制有效地平衡了响应能力与计算效率，避免了将所有变化都视为立即抢占的“过度反应”。

这项工作的意义在于其能够在动态、受限的环境中维持任务满意度（cLTL 约束）和高任务完成率，而在这些环境中，静态规划会失效且贪婪启发式算法会导致死锁。作者指出，虽然目前的集中式 MILP 公式对于测试的规模有效的队规模是有效的，但无法扩展到极大规模的集群。因此，他们将分布式 MILP 分解和基于学习的启发式算法确定为实现规模化扩展的必要后续步骤，同时也包括将基于网格的表示扩展到连续工作空间以及处理动态障碍物。