论文标题
在协作时间任务下，多代理系统的时间最小化和在线同步
Time Minimization and Online Synchronization for Multi-agent Systems under Collaborative Temporal Tasks
论文作者
论文摘要
在以并发方式解决团队范围的任务时，多代理系统可能非常有效。但是，如果没有适当的同步，则很难保证合并行为的正确性，例如遵循子任务的特定顺序或同时协作。这项工作解决了复杂的全球任务中的多代理系统的最低时间任务计划问题，称为线性时间逻辑（LTL）公式。这些任务包括独立本地动作和直接子团队合作的时间和空间要求。提出的解决方案是一种随时随地的算法，结合了对任务分解的基础任务自动机的部分顺序分析，以及用于任务分配的分支和绑定（BNB）搜索方法。提供最小的完成时间的合理性，完整性和最佳性分析。还表明，在搜索范围内持续在时间预算之内，很快就能达到可行且近乎最佳的解决方案。此外，为了处理在线执行期间任务持续时间和代理失败的波动，提出了一种适应算法来同步执行状态并动态地重新分配未完成的子任务以保持正确性和最佳性。两种算法通过数值模拟和硬件实验在大规模系统上进行了严格的验证，这些算法都针对多个强大的基准进行了验证。
Multi-agent systems can be extremely efficient when solving a team-wide task in a concurrent manner. However, without proper synchronization, the correctness of the combined behavior is hard to guarantee, such as to follow a specific ordering of sub-tasks or to perform a simultaneous collaboration. This work addresses the minimum-time task planning problem for multi-agent systems under complex global tasks stated as Linear Temporal Logic (LTL) formulas. These tasks include the temporal and spatial requirements on both independent local actions and direct sub-team collaborations. The proposed solution is an anytime algorithm that combines the partial-ordering analysis of the underlying task automaton for task decomposition, and the branch and bound (BnB) search method for task assignment. Analyses of its soundness, completeness and optimality as the minimal completion time are provided. It is also shown that a feasible and near-optimal solution is quickly reached while the search continues within the time budget. Furthermore, to handle fluctuations in task duration and agent failures during online execution, an adaptation algorithm is proposed to synchronize execution status and re-assign unfinished subtasks dynamically to maintain correctness and optimality. Both algorithms are validated rigorously over large-scale systems via numerical simulations and hardware experiments, against several strong baselines.
