Multi-Robot Coalition Formation

Abstract

As the multi-robot community strives towards greater autonomy, there is a need for systems that allow robots to autonomously form teams and cooperatively complete assigned missions. The corresponding problem with software agents has received considerable attention from the multi-agent community and is also known as the 'coalition formation problem'. Numerous coalition formation algorithms have been proposed that allow software agents to coalesce and perform tasks that would otherwise be too burdensome for a single agent. Coalition formation behaviors have also been discussed in relation to game theory.

Despite the plethora of coalition formation algorithms in the literature, to the best of our knowledge none of the proposed algorithms have been demonstrated with an actual multiple robot system. Currently, there exists a divide between the software-agent coalition formation algorithms and their applicability to the multi-robot domain. This dissertation aims to bridge that divide by unearthing the issues that arise while attempting to tailor these algorithms to the multi-robot domain. A well-known multi-agent coalition formation algorithm was studied in order to identify the necessary modifications to facilitate its application to the multi-robot domain. The modified algorithm was then demonstrated on a set of real world robot tasks.

The notion of coalition imbalance was introduced and its implications with respect to team performance and fault tolerance were studied both for the multi-robot foraging and soccer domains. Results suggest an interesting correlation between performance and balance across both the foraging and soccer domains. Balance information was also utilized to improve overall team performance in these domains. The balance coefficient metric was devised for quantifying balance in multi-robot teams.

Finally, this dissertation introduces RACHNA, a market-based coalition formation system that leverages the inherent redundancy in robot sensory capabilities to enable a more tractable formulation of the coalition formation problem. The system allows individual sensors to be valued on the basis of demand and supply, by allowing for competition between the tasks. RACHNA's superiority over simple task allocation techniques was demonstrated in simulation experiments and the idea of preempting complex multi-robot tasks was explored.