Distributed Coalition Formation with Heterogeneous Agents for Task Allocation

In this paper, we study the problem of forming coalitions with heterogeneous agents for allocating them to tasks. Several agents work together to complete a given task. Due to the inherent complexity of real-world tasks and limited capabilities of a particular type of a physical agent such as a robot, it is imperative to form a team consisting of different types of robots to complete the tasks. Our work in this paper proposes a distributed bipartite graph partitioning approach along with a region growing strategy for coalition formation with heterogeneous agents such as humans and/or robots for instantaneous allocation to tasks (ST-MR-IA). We also extend this approach to apply in the scenarios where the tasks might have dependencies among each other (ST-MR-TD).We have implemented the proposed algorithms within theWebots simulator. The proposed strategy allocates near-optimal (up to 98%) agent coalitions to tasks. Results also show that our proposed approach can easily handle as many as 100 agents and 10 tasks while spending an almost negligible amount of time.