Multi-robot coalition formation problem: Task allocation with adaptive immigrants based genetic algorithms

Abstract

Multi-robot coalition formation (MRCF) problem deals with the formation of subsets of robotic to handle a particular task. In such a system, every task is executed by multiple robots. Thus, cooperation and coordination among the robots is very important. One of the key issues to be investigated for smooth operation of a multi-robot systems is finding an optimal task allocation among the suitably formed robot groups (sub sets). Considering the complete execution of available tasks, the problem of assigning available resources (robot features) to the tasks is computationally complex, which may further increase as number of tasks increases. Genetic algorithms (GA) have been found quite efficient in solving such complex computational problems. There are several algorithms based on GA to solve MRCF problems but none of them have considered the dynamic variants. Thus we apply immigrants based GAs viz. RIGA (random immigrants genetic algorithm) and EIGA (elitism based immigrants genetic algorithm) to optimal task allocation in MRCF problem. Comparative performance evaluation has been made with respect to SGA (standard genetic algorithm). Finally, we report a novel use of these algorithms making them adaptive with certain modification in their traditional attributes by adaptively choosing the parameters of genetic operators. We name them as aRIGA (adaptive RIGA) and aEIGA (adaptive EIGA). Simulations experiments have demonstrated that RIGA and EIGA produces better solutions then SGA in both the cases (with fixed and adaptive genetic operators). Among them, EIGA and aEIGA outperforms RIGA and aRIGA respectively.