Introduction
Multi-robot task allocation (MRTA) is a fundamental coordination problem in robotics. It becomes significantly more complex when tasks are bound by temporal constraints, such as specific time windows for start and completion. This paper introduces TeSSI (Temporal Sequential Single-Item auction), an algorithm designed to handle overlapping time windows by integrating sequential auctions with Simple Temporal Networks (STNs). By allowing robots to dynamically reschedule their existing commitments, TeSSI achieves higher task completion rates and faster computation compared to existing methods like CBBA.
Problem Formulation
In many real-world applications like drone surveillance or logistics, tasks have "earliest start" and "latest finish" constraints. Traditional auction-based methods often struggle in these scenarios because they lack the flexibility to reschedule existing commitments when a new task is added. This often leads to "fragmented" schedules where robots have idle time they cannot utilize, resulting in fewer tasks being completed overall.
The TeSSI Algorithm
TeSSI addresses these challenges through a decentralized auction process. Each robot maintains its schedule as a Simple Temporal Network (STN), which allows for flexible start times within defined bounds.
When a new task is auctioned, a robot evaluates every possible insertion point in its current schedule. It uses the Floyd-Warshall algorithm to ensure temporal consistency, checking for negative cycles that would indicate an invalid schedule. Unlike methods that "lock in" task times, TeSSI allows previously assigned tasks to shift within their allowed windows to accommodate new ones. Bidding is typically based on minimizing the makespan, though dual-objective functions (TeSSIduo) can also incorporate travel distance.
Experimental Evaluation
The algorithm was tested across three distinct scenarios to ensure robustness:
- Synthetic Grid Data: Randomly generated tasks on a 60x60 grid with fixed durations.
- Dynamic Arrival: Tasks arriving in batches to simulate real-time operations.
- Solomon’s VRP Benchmark: Standard datasets for the Vehicle Routing Problem with clustered (C), random (R), and mixed (RC) spatial distributions.
Key Results
TeSSI demonstrates significant improvements over baseline greedy algorithms and the Consensus-Based Bundle Auction (CBBA) across all metrics.
- Higher Allocation Rates: As shown in the figure above, TeSSI consistently allocates more tasks than competing methods, especially as task density increases. It effectively "packs" schedules more tightly by leveraging temporal flexibility.
- Robot Efficiency: TeSSI requires fewer robots to achieve full task coverage. For a 100-task set, TeSSI reached 100% allocation with 30 robots, whereas CBBA required 40 and the greedy baseline required 50.
- Computational Speed: TeSSI is orders of magnitude faster than CBBA. In benchmark tests (Solomon C2), it allocated 100 tasks in 0.43 seconds, compared to nearly 99 seconds for CBBA.
- Spatial Synergy: The algorithm naturally groups geographically close and temporally compatible tasks, particularly excelling in clustered datasets where it can visit entire clusters before moving on.
Conclusion and Future Work
TeSSI provides a highly efficient and flexible framework for MRTA with temporal constraints. By leveraging the polynomial-time consistency checking of STNs, it achieves superior performance and scalability. Future research will focus on handling execution uncertainty—such as varying travel times—and developing decentralized auction clearing mechanisms to remove the single point of failure represented by a central auctioneer.
Summary updated