Coordinating Multi-Robot Teams Under Strict Temporal Constraints

This direction is merged into another direction: multi-agent temporal logic coordination. Its last version stays readable and citable here.

Version 1 of 115 papers17 conceptsfrozen 2026-10-04

In traditional multi-robot task allocation, the primary question is often spatial: "Which robot is closest to the goal?" However, in real-world logistics and manufacturing, space is only half the battle. Tasks come with strict time windows, deadlines, and complex ordering requirements. A robot might be physically near a task, but if it cannot arrive within a specific ten-second window without violating its existing commitments, it is the wrong choice for the job.

The research direction emerging from these challenges focuses on the tight coupling of task allocation (who does what) and temporal scheduling (when they do it).

The Coupling Problem

The core insight shared by researchers like Maria L. Gini is that in constrained environments, allocation and scheduling cannot be solved sequentially. In Multi-Robot Allocation of Tasks with Temporal and Ordering Constraints, Gini argues that an agent's availability is not a static property; it is a dynamic function of its current itinerary.

When a new task arrives, the system must evaluate if any robot can "fit" the new task into its schedule without causing a cascade of delays for its previously assigned duties. This creates a search space where every new assignment potentially reshuffles the timing of every subsequent task for that robot.

Modeling Time as a Network

To manage this complexity, researchers use graph-based representations to maintain "temporal feasibility." Ernesto Nunes and Maria L. Gini introduced TeSSI (Temporal Sequential Single-Item auction), which utilizes Simple Temporal Networks (STNs).

An STN treats tasks as nodes and temporal constraints (like "Task B must start at least 5 minutes after Task A ends") as edges. By using these networks during the auction process, robots can quickly determine if a new task is feasible by checking if the graph remains consistent. This allows for Multi-Robot Auctions for Allocation of Tasks with Temporal Constraints that are far more flexible than static assignments, as robots can dynamically reschedule their internal timelines to accommodate high-priority requests.

Balancing Spatial and Temporal Constraints

As the number of robots increases, the problem shifts from simple timing to a dual-constraint problem: satisfying temporal deadlines while avoiding physical collisions. Matthew C. Gombolay and his team address this by Learning to Dynamically Coordinate Multi-Robot Teams in Graph Attention Networks.

The intuition here is that spatial conflicts (two robots trying to occupy the same hallway) are often just temporal conflicts in disguise. By using Graph Attention Networks (GATs), the system learns to attend to the most critical constraints—whether they are a tight deadline or a narrow corridor—allowing the team to coordinate without the computational explosion of traditional hand-crafted heuristics.

Handling Uncertainty and Long Horizons

In dynamic environments, tasks often arrive asynchronously, and execution times are rarely certain. Shushman Choudhury and Mykel J. Kochenderfer developed SCoBA (Stochastic Conflict-Based Allocation) to address this. As detailed in Dynamic multi-robot task allocation under uncertainty and temporal constraints, SCoBA decouples high-level coordination from low-level planning. This allows the system to remain performant even when the probability of task success is uncertain, ensuring that the team doesn't commit to a schedule that is likely to fail.

This coordination extends even to complex hardware like dual-arm robots. In RoboPARA, Shiying Duan and colleagues demonstrate that the same temporal scheduling principles apply to end-effectors. By enforcing "object-arm affinity"—ensuring the same arm handles a specific object across a sequence—the scheduler maintains physical consistency while maximizing the parallel utilization of both arms.

Finally, for long-horizon tasks where robots have limited visibility, frameworks like LLaMAR, proposed by Siddharth Nayak in Long-Horizon Planning for Multi-Agent Robots in Partially Observable Environments, show that temporal synchronization is the key to collaborative maneuvers. Whether lifting a heavy object together or navigating a warehouse, the robots must align their internal clocks to ensure that individual actions contribute to a coherent, time-sensitive collective goal.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_coordinating_multi_robot_teams_under_str_04997dc3,
  title = {Coordinating Multi-Robot Teams Under Strict Temporal Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/coordinating-multi-robot-teams-under-strict-temporal-constraints/rdr_04997dc3c5d54a2f9c7c8642a45cc802},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_coordinating_multi_robot_teams_under_str_04997dc3_v1,
  title = {Coordinating Multi-Robot Teams Under Strict Temporal Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/coordinating-multi-robot-teams-under-strict-temporal-constraints/rdr_04997dc3c5d54a2f9c7c8642a45cc802/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}