Academic
Publications
Multi-Robot Coalition Formation

Multi-Robot Coalition Formation,Lovekesh Vig,Julie A. Adams

Multi-Robot Coalition Formation   (Citations: 55)
BibTex | RIS | RefWorks Download
Abstract—As the community strives towards autonomous multi- robot systems, there is a need for these systems to autonomously form coalitions to complete assigned missions. Numerous coalition formation algorithms have been proposed in the software agent lit- erature. Algorithms exist that form agent coalitions in both super additive and non-super additive environments. The algorithmic techniques vary from negotiation-based protocols in multi-agent system (MAS) environments to those based on computation in distributed problem solving (DPS) environments. Coalition for- mation behaviors have also been discussed in relation to game theory. Despite the plethora of MAS coalition formation literature, to the best of our knowledge none of the proposed algorithms have been demonstrated with an actual multi-robot system. There exists a discrepancy between the multi-agent algorithms and their applicability to the multi-robot domain. This paper aims to bridge that discrepancy 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 has been studied in order to identify the necessary modifications to facili- tate its application to the multi-robot domain. This paper reports multi-robot coalition formation results based upon simulation and actual robot experiments. A multi-agent coalition formation algorithm has been demonstrated on an actual robot system. Index Terms—Coalition formation, coalition imbalance, task
Published in 2006.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The multi-agent algorithms and techniques are not directly transferable to multi-robot domains, as multi-robot domains present challenges and constraints not encountered with software agents [19]...
    • ...However, their algorithm does not apply directly to multi-robot domains[19].PreviousattemptstouseShehoryandKraus’algorithminmulti-robotdomains have added the overhead of a constraint satisfaction problem in order to enforce the physical constraints on physical robot resources [19]...
    • ...However, their algorithm does not apply directly to multi-robot domains[19].PreviousattemptstouseShehoryandKraus’algorithminmulti-robotdomains have added the overhead of a constraint satisfaction problem in order to enforce the physical constraints on physical robot resources [19]...
    • ...incurred the additional overhead of a constraint satisfaction problem [19]...
    • ...Vig and Adams [19,20] demonstrate some of the differences between general multi-agent and multirobot domains and highlight the fact that the general multi-agent algorithms and techniques are not directly transferable to multi-robot domains, as multi-robot domains present challenges and constraints not encountered with software agents...
    • ...Both Shehory and Kraus’ algorithm [16] for coalition formation in general multi-agentdomainsandVigandAdams’extensiontoShehoryandKraus’algorithm[19,20] for multi-robot domains are discussed separately...
    • ...Vig and Adams [19,20] consider the coalition formation problem in multi-robot domains...
    • ...We present algorithms that complement Shehory and Kraus’ algorithm for general multi-agent domains and improve upon Vig and Adams’ algorithm [19] in the following ways:...
    • ...time of Vig and Adams’ algorithm [19 ]t oO(n...
    • ...Previous attempts to use Shehory and Kraus’ algorithm in multi-robot domains required the addition of a constraint satisfaction problem in order to ensure that particular sets of resources reside on particular robots [19]...
    • ...The algorithmwepresentfortheservicemodelalsoscalesexceptionallywell,sincethecomputational complexity is independent of k; whereas, Vig and Adams’ extension of Shehory and Kraus’ algorithm scales exponentially with k [16,19]...
    • ...2 m) ,f or all fi xed k. Our algorithm for the service model is, thus, a vast improvement over the extensions to Shehory and Kraus’ algorithm made by Vig and Adams [19] for use in multi-robot domains...
    • ...2 m) for any fixed k. Previous attempts by Vig and Adams’ [19 ]t o...

    Travis C. Serviceet al. Coalition formation for task allocation: theory and algorithms

    • ...Other work has explicitly addressed domains where tasks require the joint efforts of multiple agents [15] [14] [12]...

    Edward Gil Joneset al. Time-extended multi-robot coordination for domains with intra-path con...

    • ...However, there are algorithms that provide approximate and near-optimal solutions [11]...
    • ...The coalition formation algorithms developed in the multi-agent community cannot be directly applied to multiple robot systems since the resources cannot be transferred from one robot to another [11]...
    • ...The same authors address the issue of balance in the coalition between the coalitional size and the resource contribution in [11]...
    • ...The algorithms developed in [12, 13], or [11] require significant amount of computation time and communication which may not be possible in UAV networks as UAVs move fast and cannot stop in mid air...

    Joel G. Manatharaet al. Multiple UAV Coalitions for a Search and Prosecute Mission

    • ...Many architectures [3], [5], [7] are proposed which aim at solving the coalition formation problem with multi-robot teams, in which each assigned task may require the cooperation of multiple robots, as individual robots may not have all the capabilities to accomplish the task...

    Yu Zhanget al. Solution space reasoning to improve IQ-ASyMTRe in tightly-coupled mult...

    • ...Multi-robot approaches have been successfully applied in similar contexts [2], [3]...

    A. Beniniet al. A simulation framework for coalition formation of Unmanned Aerial Vehi...

Sort by: