A joint project of the Graduate School, Peabody College, and the Jean & Alexander Heard Library

Title page for ETD etd-09152006-140914

Type of Document Dissertation
Author Vig, Lovekesh
Author's Email Address lovekesh.vig@vanderbilt.edu
URN etd-09152006-140914
Title Multi-Robot Coalition Formation
Degree PhD
Department Computer Science
Advisory Committee
Advisor Name Title
Julie A. Adams Committee Chair
David Noelle Committee Member
Douglas Fisher Committee Member
Lynne E. Parker Committee Member
Nilanjan Sarkar Committee Member
  • Multi-Robot
  • market-based
  • Coalition
  • Robots--Programming
  • Intelligent agents (Computer software)
Date of Defense 2006-08-22
Availability unrestricted
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


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.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  dissertation.pdf 2.32 Mb 00:10:44 00:05:31 00:04:49 00:02:24 00:00:12

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact LITS.