Parallel multi-objective multi-robot coalition formation

Abstract

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.