Game-Theoretic Cooperative Task Allocation for Multiple-Mobile-Robot Systems

This study investigates the task allocation problem for multiple mobile robots in complex real-world scenarios. To address this challenge, a distributed game-theoretic approach is proposed to enable collaborative decision-making. First, the task allocation problem for multiple mobile robots is formulated to optimize the resource utilization. The formulation also takes into account comprehensive constraints related to robot positioning and task timing. Second, a game model is established for the proposed problem, which is proved to be an exact potential game. Furthermore, we introduce a novel utility function for the tasks to maximize the resource utilization. Based on this formulation, we develop a game-theoretic coalition formation algorithm to seek the Nash equilibrium. Finally, the algorithm is evaluated via simulation experiments. Another six algorithms are used for comparative studies. When the problem scale is small, the proposed algorithm can achieve solution quality comparable to that of the benchmark algorithms. In contrast, under larger and more complex problem instances, the proposed algorithm can achieve up to a 50% performance improvement over the benchmarks. This further confirms the effectiveness and superiority of the proposed method. In addition, we evaluate the solution quality and response time of the algorithm, as well as its sensitivity to initial conditions. Finally, the proposed algorithm is applied to a post-disaster rescue scenario, where the task allocation results further demonstrate its superior performance.