Temporal Logic Task Allocation in Heterogeneous Multi-Robot Systems

Xusheng Luo, Michael M. ZavlanosarXiv 2021 · OpenReview

TL;DR

This paper tackles the complex problem of assigning tasks, defined by temporal logic specifications, to teams of diverse robots. They introduce a novel hierarchical approach that breaks down the problem into high-level task allocation and low-level path planning, significantly improving scalability and efficiency compared to existing methods.

What Problem Does This Paper Address?

Coordinating multiple robots to achieve complex goals, especially when those goals involve sequences of actions, timing constraints, and specific robot capabilities, is a significant challenge in robotics. Traditional approaches often struggle with scalability as the number of robots, tasks, or the complexity of the goals increases. Specifically, this paper addresses the Multi-Robot Task Allocation (MRTA) problem under Linear Temporal Logic (LTL) specifications (LTL-MRTA). The core difficulty lies in assigning tasks, expressed as LTL formulas, to a team of heterogeneous robots (robots with different capabilities) in a way that satisfies the global specification while minimizing cost and ensuring feasibility. Existing methods that build large "product automata" become computationally intractable for realistic scenarios.

Methods

The authors propose a hierarchical approach to tackle LTL-MRTA:

  1. NBA Pruning and Relaxation: They start by processing the Nondeterministic Büchi Automaton (NBA) that represents the LTL specification. This involves removing infeasible transitions and, crucially, relaxing negative atomic propositions. This "lazy collision checking" inspired step simplifies the problem by deferring constraint satisfaction to the execution phase.
  2. Subtask Extraction and Temporal Ordering: From the relaxed NBA, they extract sequences of subtasks and infer their temporal order using partially ordered sets (posets).
  3. High-Level Task Allocation (MILP): A Mixed Integer Linear Program (MILP), inspired by the vehicle routing problem, is formulated to assign these subtasks to robots and determine time-stamped waypoints. This step effectively creates a high-level plan.
  4. Low-Level Path Planning (GMRPP): Finally, generalized multi-robot path planning (GMRPP) problems are solved to generate executable robot paths that respect the high-level plan and reintroduce the negative constraints that were initially relaxed.

Datasets

Not discussed in the paper. The evaluation is performed using simulated workspaces and task specifications.

Key Insights and Ideas

  • "Lazy" Temporal Logic Planning: The core innovation is the "lazy collision checking" inspired relaxation of negative atomic propositions in the NBA. This significantly simplifies the high-level planning problem by deferring complex constraint satisfaction to the low-level path execution, leading to better scalability.
  • Hierarchical Decomposition: Breaking the complex LTL-MRTA problem into distinct high-level (task allocation) and low-level (path planning) stages is key to managing complexity.
  • MILP for Task Allocation: Leveraging MILP, inspired by established routing problems, provides a structured way to allocate subtasks and generate time-stamped plans.
  • Completeness for a Subclass of LTL: The method is proven to be complete for a significant subclass of LTL that covers many practical robotic tasks, offering theoretical guarantees.

Key Results

  • Scalability: The proposed method can handle LTL-MRTA problems with up to $10^{90}$ states in the product graph, significantly outperforming existing methods.
  • Optimality: The method generates paths with lower cost compared to existing feasibility-focused approaches.
  • Efficiency: Numerical simulations demonstrate considerably faster path generation times.
  • Comparison to BMC: In a case study with a 30x30 grid and up to 30 robots, their method achieved about half the runtime and one-third the cost of a Bounded Model Checking (BMC) based approach.
  • Completeness: The method is proven to be complete for a subclass of LTL specifications.

Limitations and Future Work

  • Completeness for LTL vs. LTLX: The theoretical completeness result is primarily for LTL specifications, with extensions to LTLX (which includes induced atomic propositions) being complete for finite-horizon tasks.
  • Assumption of Feasible Paths: The framework relies on the assumption that feasible paths exist for the given specifications and workspace.
  • Suboptimality: While the method aims for lower cost, it's not guaranteed to find the absolute optimal solution, especially when multiple posets (representing different task orderings) are possible.
  • Future Work: The paper suggests exploring extensions to the MILP formulation for more complex constraints, such as managing the number of participating robots or prohibiting the use of the same robots for different tasks. Further investigation into the impact of partial execution in GMRPP for large workspaces is also mentioned.

Summary updated

Abstract

In this paper, we consider the problem of optimally allocating tasks, expressed as global Linear Temporal Logic (LTL) specifications, to teams of heterogeneous mobile robots. The robots are classified in different types that capture their different capabilities, and each task may require robots of multiple types. The specific robots assigned to each task are immaterial, as long as they are of the desired type. Given a discrete workspace, our goal is to design paths, i.e., sequences of discrete states, for the robots so that the LTL specification is satisfied. To obtain a scalable solution to this complex temporal logic task allocation problem, we propose a hierarchical approach that first allocates specific robots to tasks using the information about the tasks contained in the Nondeterministic Buchi Automaton (NBA) that captures the LTL specification, and then designs low-level executable plans for the robots that respect the high-level assignment. Specifically, we first prune and relax the NBA by removing all negative atomic propositions. This step is motivated by "lazy collision checking" methods in robotics and allows to simplify 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 (MILP) to allocate these subtasks to the robots. Finally, we define generalized multi-robot path planning problems to obtain low-level executable robot plans that satisfy both the high-level task allocation and the temporal 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 cost, considerably faster than existing methods.
BibTeX
@misc{luo2021temporal,
  author = {Xusheng Luo and Michael M. Zavlanos},
  title = {{Temporal Logic Task Allocation in Heterogeneous Multi-Robot Systems}},
  year = {2021},
  eprint = {2101.05694},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.05694},
}

Loading related content...

Figure