Dutta

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.