Distributed algorithm design for multi-robot generalized task assignment problem

We present a provably-good distributed algorithm for generalized task assignment problem in the context of multirobot systems, where robots cooperate to complete a set of given tasks. In multi-robot generalized assignment problem (MR-GAP), each robot has its own resource constraint (e. g. , energy constraint), and needs to consume a certain amount of resource to obtain a payoff for each task. The objective is to find a maximum payoff assignment of tasks to robots such that each task is assigned to at most one robot while respecting robots' resource constraints. MR-GAP is a NP-hard problem. It is an extension of multi-robot linear assignment problem since different robots can use different amount of resource for doing a task (due to the heterogeneity of robots and tasks). We first present an auction-based iterative algorithm for MR-GAP assuming the presence of a shared memory (or centralized auctioneer), where each robot uses a knapsack algorithm as a subroutine to iteratively maximize its own objective (using a modified payoff function based on an auxiliary variable, called price of a task). Our iterative algorithm can be viewed as (an approximation of) best response assignment update rule of each robot to the assignment of other robots at that iteration. We prove that our algorithm converges to an assignment (approximately) at equilibrium under the assignment update rule, with an approximation ratio of 1+α (where α is the approximation ratio for the Knapsack problem). We also combine our algorithm with a message passing mechanism to remove the requirement of a shared memory and make our algorithm totally distributed assuming the robots' communication network is connected. Finally, we present simulation results to depict our algorithm's performance.

Authors

• Lingzhi Luo
• Nilanjan Chakraborty
• Katia P. Sycara

Keywords

• Approximation algorithms
• Approximation methods
• Algorithm design and analysis
• Robot kinematics
• Distributed algorithms
• Algorithm Design
• Distributed Algorithm
• Assignment Problem
• Performance Of Algorithm
• Resource Constraints
• Iterative Algorithm
• Communication Network
• Linear Problem
• Best Response
• Multi-agent Systems
• Auxiliary Variables
• Update Rule
• Approximate Ratio
• Knapsack Problem
• Shared Memory
• Running Time
• Estimation Algorithm
• Resource Consumption
• Open Research
• Current Price
• Approximate Equilibrium
• Theoretical Computer Science
• Task Allocation
• Performance Guarantees
• Local Communication
• Auction Mechanism
• Bid Price