Parallel multi-objective multi-robot coalition formation

In the quest for greater autonomy, there is an increasing need for solutions that would enable a large set of robots to coalesce and perform complicated multi-robot tasks. This problem, also known as the multi-robot coalition formation problem has been traditionally approached as a single objective optimization problem. However, robots in the real world have to optimize multiple conflicting criteria such as battery life, number of completed tasks, and distance traveled. Researchers have only recently addressed the robot coalition formation problem as a multi-objective optimization problem, however the proposed solutions have computational bottlenecks that make them unsuitable for real time robotic applications. In this paper we address the issue of scalability by proposing parallelized algorithms in the CUDA programming framework. NSGA-II and PAES algorithm have been parallelized due to their suitability to the coalition formation domain as outlined in our previous work. The parallelized versions of these algorithms have been applied to both the additive and non-additive coalition formation environments. Simulations have been performed in the player/stage environment to validate the applicability of our approach to real robot situations. Results establish that the multi-point PAES parallel variant yields significant performance gains in terms of running time and solution quality when the problem is scaled to deal with large inputs. This suggests that the algorithm may be viable for real time robotic applications. Experiments demonstrate significant speedup when the proposed parallel algorithms were compared with the serial solutions proposed earlier.