Temporal Logic Task Allocation in Heterogeneous Multirobot Systems

Xusheng Luo, Michael M. ZavlanosIEEE Trans. Robotics 2022 · OpenReview

TL;DR

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

What Problem Does This Paper Address?

Coordinating multiple robots to perform complex tasks, especially when those tasks involve specific sequences of actions or conditions over time, is a significant challenge in robotics. Traditionally, these tasks are described using formal languages like Linear Temporal Logic (LTL). However, existing methods for assigning these LTL tasks to a team of robots (Multi-Robot Task Allocation or MRTA) often struggle with scalability. This is because they typically build a massive "product automaton" that combines the robot's capabilities with the task's logic, leading to an exponential increase in complexity with more robots or more intricate tasks. Furthermore, when robots have different capabilities (heterogeneous), the problem becomes even harder. This paper addresses the need for a more scalable and efficient method to handle LTL-MRTA for heterogeneous robot teams, aiming to find optimal or near-optimal task assignments and robot paths.

Methods

The authors propose a hierarchical approach to solve the LTL-MRTA problem. The core idea is to decompose the problem into two main stages:

  1. High-Level Task Allocation:
    • NBA Relaxation and Pruning: They start by processing the Nondeterministic Büchi Automaton (NBA) that represents the LTL task. Crucially, they "prune" and "relax" the NBA by removing negative atomic propositions. This is inspired by "lazy collision checking" in robotics and simplifies the problem by deferring constraint satisfaction to the low-level planning stage.
  2. Subtask Extraction and Temporal Ordering: Sequences of subtasks and their temporal dependencies are extracted from the relaxed NBA.
  3. Mixed Integer Linear Programming (MILP): An MILP, similar to those used in vehicle routing problems, is formulated to assign these subtasks to specific robots and determine time-stamped waypoints for each robot. This MILP effectively creates a high-level plan.
  4. Low-Level Path Planning:
    • Generalized Multi-Robot Path Planning (GMRPP): For each subtask in the high-level plan, a GMRPP is formulated. This stage reintroduces the negative constraints (removed earlier) and generates executable robot paths that respect the high-level assignment and temporal logic. The GMRPP considers factors like travel time, collision avoidance, and robot capabilities.

This hierarchical structure allows them to tackle complex LTL tasks by first making high-level decisions and then refining them with detailed path planning, avoiding the exponential complexity of traditional product automaton methods.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and demonstrates its effectiveness through simulations on custom-designed workspaces and tasks, rather than using pre-existing datasets.

Key Insights and Ideas

  • "Lazy" Constraint Checking for High-Level Planning: The idea of removing negative atomic propositions from the NBA during high-level planning and reintroducing them during low-level path planning is a key innovation. This significantly simplifies the MILP formulation for task allocation.
  • Hierarchical Decomposition: Breaking the problem into distinct high-level (task assignment) and low-level (path planning) stages is crucial for scalability. This allows for optimization at each level independently.
  • MILP for Task Allocation: Leveraging MILP, inspired by the Vehicle Routing Problem, provides a powerful way to model and solve the complex combinatorial problem of assigning subtasks to heterogeneous robots while respecting temporal constraints.
  • Completeness for a Subclass of LTL: The authors demonstrate that their method is complete for a significant subclass of LTL that covers many practical robotic tasks, offering theoretical guarantees.

Key Results

  • Scalability: The proposed method significantly outperforms existing approaches in handling larger problems, demonstrated by successfully solving LTL-MRTA problems with up to $10^{90}$ states in the product graph, a feat intractable for prior methods.
  • Efficiency: Numerical simulations show that their method generates paths considerably faster than existing methods.
  • Optimality: While not theoretically optimal in all cases, the method generates paths with lower costs compared to existing methods that often focus solely on feasibility. For instance, in Case Study I, their method achieved costs close to optimal, and in 35 out of 50 trials for task (i), it found the exact optimal solutions without collision avoidance.
  • Robustness: The method handles heterogeneous robots and complex temporal logic specifications, including those requiring synchronization and temporal ordering.

Limitations and Future Work

  • Assumptions: The method relies on certain assumptions about the NBA structure (e.g., existence of restricted accepting runs and satisfying paths) and the workspace (disjoint regions). While these assumptions are stated to be mild and satisfied by many practical tasks, they do represent limitations.
  • Suboptimality: While the method aims for low-cost solutions, it doesn't guarantee theoretical optimality in all scenarios. The hierarchical nature might lead to locally optimal decisions at each stage.
  • LTL vs. LTLX: The completeness proof is primarily for LTL specifications, though it extends to LTLX for finite-horizon tasks.
  • Future Work: The paper suggests extensions to the MILP formulation to handle more complex constraints, such as requiring specific robots to participate in tasks, managing the number of participating robots, prohibiting the use of the same robots for different tasks, and incorporating more sophisticated collision avoidance strategies. The authors also mention the possibility of exploring partial execution in GMRPP for better efficiency in large workspaces.

Summary updated

Abstract

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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ddot{\text{u}}$</tex-math></inline-formula> 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 cost, considerably faster than existing methods.
BibTeX
@article{luo2022temporal,
  author = {Xusheng Luo and Michael M. Zavlanos},
  title = {{Temporal Logic Task Allocation in Heterogeneous Multirobot Systems}},
  journal = {IEEE Trans. Robotics},
  year = {2022},
  url = {https://openreview.net/forum?id=GLkovdWsVx0},
}
Figure