Non-additive multi-objective robot coalition formation 

 Abstract

 Manifold increase in the complexity of robotic tasks has mandated the use 
 of robotic teams called coalitions that collaborate to perform complex tasks. 
 In this scenario, the problem of allocating tasks to teams of robots (also 
 known as the coalition formation problem) assumes significance. So far, 
 solutions to this NP-hard problem have focused on optimizing a single utility 
 function such as resource utilization or the number of tasks completed. We have 
 modeled the multi-robot coalition formation problem as a multi-objective optimization 
 problem with conflicting objectives. This paper extends our recent work in multi-objective 
 approaches to robot coalition formation, and proposes the application of the Pareto 
 Archived Evolution Strategy (PAES) algorithm to the coalition formation problem, 
 resulting in more efficient solutions. Simulations were carried out to demonstrate the 
 relative diversity in the solution sets generated by PAES as compared to previously 
 studied methods. Experiments also demonstrate the relative scalability of PAES. Finally, 
 three different selection strategies were implemented to choose solutions from the 
 Pareto optimal set. Impact of the selection strategies on the final coalitions formed 
 has been shown using Player/Stage.