Algorithm for Multi-Robot Chance-Constrained Generalized Assignment Problem with Stochastic Resource Consumption

We present a novel algorithm for the multi-robot generalized assignment problem (GAP) with stochastic resource consumption. In this problem, each robot has a resource (e. g. , battery life) constraint and it consumes a certain amount of resource to perform a task. In practice, the resource consumed for performing a task can be uncertain. Therefore, we assume that the resource consumption is a random variable with known mean and variance. The objective is to find an assignment of the robots to tasks that maximizes the team payoff. Each task is assigned to at most one robot and the resource constraint for each robot has to be satisfied with very high probability. We formulate the problem as a chance-constrained combinatorial optimization problem and call it the chance-constrained generalized assignment problem (CC-GAP). This problem is an extension of the deterministic generalized assignment problem, which is a NP-hard problem. We design an iterative algorithm for solving CC-GAP in which each robot maximizes its own objective by solving a chance-constrained knapsack problem in an iterative manner. The approximation ratio of our algorithm is (1+α), assuming that the deterministic knapsack problem is solved by an α-approximation algorithm. We present simulation results to demonstrate that our algorithm is scalable with the number of robots and tasks.

Authors

• Fan Yang
• Nilanjan Chakraborty

Keywords

• NP-hard problem
• Simulation
• Approximation algorithms
• Random variables
• Task analysis
• Robots
• Optimization
• Resource Consumption
• Assignment Problem
• Generalized Assignment Problem
• Scalable
• Resource Constraints
• Combinatorial Optimization Problem
• Approximate Ratio
• Deterministic Problem
• Knapsack Problem
• Straight Line
• Feasible Solution
• Sources Of Uncertainty
• Feasible Set
• Uniform Density
• Final Design
• Y-intercept
• Nonempty Set
• Resource Capacity
• Parabola
• Horizontal Coordinates
• Single Robot
• Storage Location
• Task Allocation
• Intersection Region
• Swarm Robotics