Game-Theoretical Approach to Multi-Robot Task Allocation Using a Bio-Inspired Optimization Strategy

Abstract

This paper introduces a game-theoretical approach to the multi-robot task allocation problem, where each robot is considered as self-interested and cannot share its personal utility functions. We consider the case where each robot can execute multiple tasks and each task requires only one robot. For real-world applications with mobile robots, we design a utility function that includes both assignment conflict penalties and path-dependent execution cost. For a robot to maximize its own utility, it needs to select a subset of conflict-free tasks that minimizes its total travel distance. Our approaches utilize a consensus communication scheme to share robots' task selection and the Speeding-Up and Slowing-Down (SUSD) strategy to search in a combinatorial action (task selection) space for a subset of tasks that can achieve a higher utility at each iteration. The SUSD strategy can perform a gradient-like search without calculating the derivatives, which allows robots to improve upon their current task selections. Simulation results show that robots using the proposed algorithms can successfully find Nash equilibria for effective coordination.