TY - GEN
T1 - Multi-agent coalition formation for distributed area coverage
T2 - 2010 3rd IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology - Workshops, WI-IAT 2010
AU - Cheng, Ke
AU - Dasgupta, Prithviraj
N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.
PY - 2010
Y1 - 2010
N2 - In the multi-robot area coverage problem, a group of mobile robots have to cover an initially unknown environment using a sensor or coverage tool attached to each robot. Multi-robot area coverage is encountered in many applications of multi-robot systems including unmanned search and rescue, aerial reconnaissance, robotic demining, automatic lawn mowing, and inspection of engineering structures. We envisage that multi-robot coverage can be performed efficiently if robots are coordinated to form small teams while covering the environment. In this paper, we use a technique from coalitional game theory called a weighted voting game that allows each robot to dynamically identify other team members and form teams so that the efficiency of the area coverage operation is improved. We propose and evaluate a novel technique of computing the weights of a weighted voting game based on each robot's coverage capability and finding the best minimal winning coalition(BMWC). Also we designed a greedy method and a heuristic method to find BMWC in O(n log n) time and O(n2) time respectively. There is a trade-off between computational time and the optimal solution.
AB - In the multi-robot area coverage problem, a group of mobile robots have to cover an initially unknown environment using a sensor or coverage tool attached to each robot. Multi-robot area coverage is encountered in many applications of multi-robot systems including unmanned search and rescue, aerial reconnaissance, robotic demining, automatic lawn mowing, and inspection of engineering structures. We envisage that multi-robot coverage can be performed efficiently if robots are coordinated to form small teams while covering the environment. In this paper, we use a technique from coalitional game theory called a weighted voting game that allows each robot to dynamically identify other team members and form teams so that the efficiency of the area coverage operation is improved. We propose and evaluate a novel technique of computing the weights of a weighted voting game based on each robot's coverage capability and finding the best minimal winning coalition(BMWC). Also we designed a greedy method and a heuristic method to find BMWC in O(n log n) time and O(n2) time respectively. There is a trade-off between computational time and the optimal solution.
KW - Area coverage
KW - Weighted voting games
KW - Winning coalitions
UR - http://www.scopus.com/inward/record.url?scp=78649820090&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78649820090&partnerID=8YFLogxK
U2 - 10.1109/WI-IAT.2010.277
DO - 10.1109/WI-IAT.2010.277
M3 - Conference contribution
AN - SCOPUS:78649820090
SN - 9780769541914
T3 - Proceedings - 2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology - Workshops, WI-IAT 2010
SP - 334
EP - 337
BT - Proceedings - 2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology - Workshops, WI-IAT 2010
Y2 - 31 August 2010 through 3 September 2010
ER -