Temporal Logic Task Allocation in Heterogeneous Multirobot Systems

Xusheng Luo

doi:10.1109/TRO.2022.3181948

2022-12-01

Xusheng Luo *

Michael M. Zavlanos

DOI：10.1109/TRO.2022.3181948

原文链接

原文求助

摘要

En 中文

We consider the problem of optimally allocating tasks, expressed as global linear temporal logic (LTL) specifications, to teams of heterogeneous mobile robots of different types. Each task may require robots of multiple types. To obtain a scalable solution, we propose a hierarchical approach that first allocates specific robots to tasks using the information about the tasks contained in the nondeterministic B ii chi automaton (NBA) that captures the LTL specification and then designs low-level paths for robots that respect the high-level assignment. Specifically, motivated by lazy collision checking methods in robotics, we first prune and relax the NBA by removing all negative atomic propositions, which simplifies the planning problem by checking constraint satisfaction only when needed. Then, we extract sequences of subtasks from the relaxed NBA along with their temporal orders and formulate a mixed integer linear program to allocate these subtasks to robots. Finally, we define generalized multirobot path planning problems to obtain low-level paths that satisfy both the high-level task allocation and the constraints captured by the negative atomic propositions in the original NBA. We show that our method is complete for a subclass of LTL that covers a broad range of tasks and present numerical simulations demonstrating that it can generate paths with lower cast, considerably faster than existing methods.

Keyword:

Formal methods in robotics and automation

motion and path planning

path planning for multiple mobile robots or agents

task planning