首页|Fast and Adaptive Multi-Agent Planning under Collaborative Temporal Logic Tasks via Poset Products

Fast and Adaptive Multi-Agent Planning under Collaborative Temporal Logic Tasks via Poset Products

扫码查看
原文链接
  • NETL
  • NSTL
  • 万方数据
Efficient coordination and planning is essential for large-scale multi-agent systems that collaborate in a shared dynamic environment.Heuristic search methods or learning-based approaches often lack the guarantee on correctness and performance.Moreover,when the collaborative tasks contain both spatial and temporal requirements,e.g.,as linear temporal logic(LTL)formulas,formal methods provide a verifiable framework for task planning.However,since the planning complexity grows exponentially with the number of agents and the length of the task formula,existing studies are mostly limited to small artificial cases.To address this issue,a new planning paradigm is proposed in this work for system-wide temporal task formulas that are released online and continually.It avoids two common bottlenecks in the traditional methods,i.e.,(a)the direct translation of the complete task formula to the associated Büchi automaton and(b)the synchronized product between the Büchi automaton and the transition models of all agents.Instead,an adaptive planning algorithm is proposed,which computes the product of relaxed partially ordered sets(R-posets)on-the-fly and assigns these subtasks to the agents subject to the ordering constraints.It is shown that the first valid plan can be derived with a polynomial time and memory complexity with respect to the system size and the formula length.Our method can take into account task formulas with a length of more than 400 and a fleet with more than 400 agents,while most existing methods fail at the formula length of 25 within a reasonable duration.The proposed method is validated on large fleets of service robots in both simulation and hardware experiments.

Zesen Liu、Meng Guo、Weimin Bao、Zhongkui Li

展开 >

Department of Mechanics and Engineering Science,College of Engineering,Peking University,Beijing 100871,China

Science and Technology Commission of China Aerospace Science and Technology Corporation,Beijing 100048,China

National Key R&D Program of ChinaNational Key R&D Program of ChinaNational Natural Science Foundation of ChinaNational Natural Science Foundation of ChinaNational Natural Science Foundation of ChinaNational Natural Science Foundation of China

2022ZD01164012022-ZD0116400U22412146237300862203017T2121002

2024

10.34133/research.0337

研究(英文)

研究(英文)

CSTPCD
ISSN：
年,卷(期)：2024.2024(2)
  • 58