Task Allocation With Minimum Requirements for Multiple Mobile Robot Systems: A Game-Theoretical Approach

Mobile robots are increasingly being deployed to replace humans in hazardous environments, and optimizing the task assignment among robots can produce satisfactory performances. This article develops a distributed task allocation scheme for a multiple mobile robot system where each task has a minimum requirement on the number of required robots for its completion.For robots, they must form task-specific coalitions to cooperatively perform the tasks. A coalition formation game (CFG) model is developed to analyze and study the interactions among the robots, and the altruistic preference order is employed to mitigate the negative effects caused by letting robots act selfishly. Meanwhile, the design of dummy utility enables every robot to prefer a task whose minimum requirement is not fulfilled, which avoids the occurrence of task failure. It is strictly proven that the CFG is equivalent to an exact potential game (EPG), and thus the existence of Nash stable partition is guaranteed. We also demonstrate that the proposed coalition formation algorithm can converge to Nash stable partition within finite iterations. The validity of our proposed scheme is verified through in-depth numerical simulations.