A game-theoretical approach to heterogeneous multi-robot task assignment problem with minimum workload requirements

Abstract

This paper addresses a multi-robot task assignment problem with heterogeneous agents and tasks. Each task has a different type of minimum workload requirement to be accomplished by multiple agents, and the agents have different work capacities and costs depending on the tasks. The objective is to find an assignment that minimises the total cost of assigned agents while satisfying the requirements of the tasks. We formulate this problem as the minimisation version of the generalised assignment problem with minimum requirements (MinGAP-MR). We propose a distributed game-theoretical approach in which each selfish player (i.e., robot) wants to join a task-specific coalition that minimises its own cost as possible. We adopt tabu-learning heuristics where a player penalises its previously chosen coalition, and thereby a Nash-stable partition is always guaranteed to be determined. Experimental results present the properties of our proposed approach in terms of suboptimality and algorithmic complexity.