Multi-Robot Task Allocation (MRTA)

This axis classifies whether a robot can execute only one task at a time (ST) or multiple tasks concurrently (MT).

• ST Robots: Simpler, common in delivery or inspection scenarios. Allocation is a strict assignment.
• MT Robots: More complex, enabling a single robot to service multiple waypoints or monitor several areas. Allocation becomes a scheduling problem with temporal constraints.

This axis defines whether a task requires exactly one robot (SR) or multiple robots (MR) for completion.

• SR Tasks: The standard case (e.g., 'go to location X'). Allocation is often a bipartite matching problem.
• MR Tasks: Require cooperation, such as collective transport of a large object or collaborative sensing. Allocation must form coalitions of robots with complementary capabilities.

This dimension separates allocation based on the planning horizon.

• Instantaneous Allocation (IA): Assigns all currently known tasks in a single, static episode. Assumes tasks are independent and available at time zero.
• Time-Extended Allocation (TA): Accounts for tasks that arrive dynamically over time and may have complex temporal dependencies (e.g., Task B can only start after Task A finishes). This leads to spatio-temporal planning and is significantly more complex, often requiring integrated task allocation and scheduling.

This defines the system's control and information structure.

• Centralized: A single entity has global knowledge of all robots and tasks, computes the optimal allocation (e.g., via a mixed-integer linear program), and broadcasts assignments. Optimal but suffers from a single point of failure and communication bottlenecks.
• Decentralized: Robots compute assignments locally using partial information via communication with neighbors. Methods include auction-based coordination and consensus algorithms. Offers scalability and robustness but may converge to suboptimal solutions.

The metric the allocation aims to optimize. The choice drastically alters the solution.

• Makespan: Minimize the total time until the last task is completed.
• Sum-of-Costs: Minimize the total distance traveled or energy consumed by all robots.
• Maximum Task Time: Minimize the longest time any single robot is busy (fairness).
• Number of Tasks Completed: Maximize throughput in dynamic environments.
• These are often subject to hard constraints like battery life, robot capabilities, and task deadlines.

MRTA problems are often NP-Hard, but their difficulty varies by classification.

• Simplest (ST-SR-IA): Often reducible to the Linear Sum Assignment Problem, solvable in polynomial time (O(n³)) with the Hungarian Algorithm.
• Complex (MT-MR-TA): Combines coalition formation, scheduling, and path planning. Requires sophisticated distributed optimization or market-based heuristics.
• Heterogeneous Fleets: Introducing robots with different capabilities (sensors, speed, payload) adds another layer, requiring role assignment and matching tasks to capable agents.

This is the most mature application of MRTA, where fleets of Autonomous Mobile Robots (AMRs) are coordinated to fulfill e-commerce orders. Algorithms dynamically assign tasks like order picking, inventory replenishment, and sortation to robots based on real-time location, battery level, and current workload.

• Key MRTA Problem: Online, multi-task robots (MT-MR) with precedence constraints (items must be picked before packing).
• Example: In a Kiva/Amazon Robotics system, hundreds of robots bring entire shelves to human pickers. The MRTA system minimizes total travel time and prevents gridlock.
• Impact: Reduces walk time for human workers by over 80%, enabling same-day and next-day delivery logistics.

Teams of aerial and ground robots are deployed over vast fields for crop scouting, soil sampling, and targeted spraying. MRTA algorithms partition the area efficiently among heterogeneous robots (e.g., drones for aerial imagery, UGVs for soil analysis).

• Key MRTA Problem: Single-task robots (ST), multi-robot tasks (SR) where a field is divided among agents.
• Example: A swarm of drones autonomously covers a 100-acre field, with the MRTA system ensuring complete, non-overlapping coverage while accounting for varying flight times and sensor payloads.
• Impact: Enables hyper-localized application of water and pesticides, reducing chemical use by 30-50% and improving yield.

In unstructured, hazardous environments after earthquakes or fires, teams of robots perform victim identification, mapping, and hazard assessment. MRTA is critical for prioritizing areas, allocating robots with specific sensors (thermal cameras, gas detectors), and adapting to newly discovered information.

• Key MRTA Problem: Dynamic task generation, heterogeneous capabilities, and severe communication constraints often necessitate decentralized auction-based or market-driven approaches.
• Example: Aerial drones quickly map a collapsed building, identifying potential voids. Then, ground robots are allocated to inspect those specific high-probability locations for signs of life.

In smart factories, MRTA coordinates collaborative robots (cobots) and Automated Guided Vehicles (AGVs) on flexible production lines. Tasks like part delivery, machine tending, and sub-assembly are allocated in real-time based on production schedules and machine availability.

• Key MRTA Problem: Tightly coupled tasks with temporal and spatial constraints (e.g., part A must arrive at station 5 within a 10-second window).
• Example: In a car assembly line, AGVs are dynamically rerouted to deliver different door panels to various stations based on the specific vehicle model moving down the line, optimizing flow and minimizing buffer inventory.

Fleets of autonomous underwater vehicles (AUVs) and surface vehicles (ASVs) are deployed for long-duration missions like tracking algal blooms, mapping ocean currents, or inspecting underwater infrastructure. MRTA plans persistent, energy-efficient patrols and adaptive sampling campaigns.

• Key MRTA Problem: Extended operations with severe communication latency (acoustic modems) require robust decentralized and consensus-based algorithms. Tasks often involve collecting data to reduce uncertainty in a spatial model.
• Example: A team of solar-powered ASVs is allocated to continuously monitor salinity and temperature across a marine protected area, dynamically adjusting their paths to focus on regions showing anomalous readings.

Autonomous robots transport linen, meals, laboratory samples, and medical supplies throughout hospitals. MRTA systems manage priority-based scheduling (stat lab tests vs. routine deliveries), enforce sanitization protocols, and integrate with elevator systems for multi-floor navigation.

• Key MRTA Problem: A dynamic mix of urgent and routine tasks in a human-centric, safety-critical environment. Algorithms must account for preemption (re-tasking a robot for a higher-priority delivery) and strict temporal deadlines.
• Impact: Reduces nurse walking time for logistical tasks by up to 30%, allowing more time for patient care, and reduces the risk of hospital-acquired infections via contactless transport.

A decentralized, market-inspired method for Multi-Robot Task Allocation (MRTA). Robots act as bidders, calculating a local cost (e.g., time, energy) for available tasks and submitting bids. A central or distributed auctioneer assigns each task to the robot with the best bid, optimizing a global objective like total mission time. Common auction types include sequential single-item auctions and combinatorial auctions for complex task bundles. This approach is highly scalable and naturally handles heterogeneous robot capabilities.

The computational problem of planning collision-free paths for multiple agents (robots) from start to goal locations in a shared environment. It is a critical sub-problem tightly coupled with MRTA; after tasks are allocated, robots must navigate without interfering. Algorithms optimize for makespan (total time) or sum-of-costs (total moves). Key algorithms include:

• Conflict-Based Search (CBS): A two-level optimal algorithm that resolves path conflicts by adding constraints.
• Optimal Reciprocal Collision Avoidance (ORCA): A decentralized, reactive velocity-based method for real-time collision avoidance.

A system architecture where each robot makes autonomous decisions based on local rules and neighbor information, without a central coordinator. This contrasts with centralized MRTA approaches. Benefits include improved scalability, robustness to single-point failures, and adaptability to dynamic environments. Implementation often uses consensus algorithms for agreement on shared data and distributed optimization techniques to solve global objectives through local computation and communication.

The dynamic process of allocating specific functions or responsibilities to individual robots within a team. While MRTA assigns concrete tasks, role assignment assigns abstract capabilities (e.g., scout, leader, transporter, blocker). Roles are often assigned based on robot capabilities, environmental context, and mission phase. This enables specialized heterogeneous teams where a robot's role dictates the type of tasks it is eligible for during MRTA, creating a hierarchical coordination structure.

The challenge of managing a team of robots with different capabilities, sensors, dynamics, and payloads. MRTA for heterogeneous fleets must match task requirements to robot specifications. This involves creating a capability matrix and solving a more complex assignment problem. For example, a mapping task requires a robot with a LiDAR, while a transport task requires a robot with a sufficient payload capacity. Coordination must also account for differing speeds and communication protocols.

A class of algorithms where robots collaboratively solve a global optimization problem (e.g., minimize total energy) using only local computation and communication with neighbors. This is the mathematical engine behind many decentralized MRTA and coordination schemes. Techniques include distributed gradient descent and consensus-based optimization. Each robot iteratively adjusts its planned actions based on local cost and messages from peers, converging to a globally efficient solution without sharing all data centrally.