Distributed algorithm design for multi-robot task assignment with deadlines for tasks

In this paper, we present provably-good algorithms for multi-robot task assignment, where each task has to be completed within its deadline. Each robot has a upper limit on the maximum number of tasks that it can perform due to its limited battery life, and each task takes the same amount of time to complete. Each robot has a different payoff (or cost) for the tasks and the objective is to assign the tasks to the robots such that the total payoff (cost) is maximized (minimized) while respecting the task deadline constraints. This problem is an extension of a special generalized assignment problem (where each task consumes the same time resource and must be finished), with additional deadline constraints for the time resource assignment. We show that the problem can be reduced to a problem of assigning tasks to robots, where the tasks are organized in overlapping sets, and each robot has a limit on the number of tasks it can perform from each set, which is a variant of multi-robot assignment problem with set precedence constraint (SPC-MAP) discussed in [1]. We present a distributed auction-based algorithm for this problem and prove that the solution is almost-optimal. We also present simulation results to depict the performance of our algorithm.

Authors

• Lingzhi Luo
• Nilanjan Chakraborty
• Katia P. Sycara

Keywords

• Nickel
• Distributed algorithms
• Robot kinematics
• Algorithm design and analysis
• Job shop scheduling
• Algorithm Design
• Distributed Algorithm
• Multi-robot Task
• Distributed Algorithm Design
• Assignment Problem
• Total Return
• Variant Of Problem
• Form Of Equation
• Feasible Solution
• Linear Problem
• Time Slot
• Convergence Of Algorithm
• Solution Quality
• Net Value
• Convergence Time
• Current Price
• Real Price
• Task Value
• Task Allocation
• Local Price
• Linear Programming Relaxation
• Performance Guarantees
• Auction Mechanism
• Extension Of Problem