@COMMENT This file was generated by bib2html.pl version 0.94
@COMMENT written by Patrick Riley
@COMMENT This file came from Gal A. Kaminka's publication pages at
@COMMENT http://www.cs.biu.ac.il/~galk/Publications/
@Article{jopha10noa,
author = {Noa Agmon and Meytal Traub and Sarit Kraus and Gal A. Kaminka},
title = {Task Reallocation in Multi-Robot Formations},
journal = JOPHA,
year = {2010},
OPTkey = {},
volume = {4},
number = {2},
pages = {1--10},
OPTmonth = {},
OPTnote = {},
abstract = { This paper considers the task reallocation problem, where $k$ robots are to be extracted
from a coordinated group of $N$ robots in order
to perform a new task. The interaction between the team members and
the cost associated with this interaction are represented by a
directed weighted graph. Consider a group of $N$ robots organized in
a formation. The graph is the monitoring graph which represents the
sensorial capabilities of the robots, i.e., which robot can sense
the other and at what cost. The team member reallocation problem
with which we deal, is the extraction of $k$ robots from the group in order to
acquire a new target while minimizing the cost of the interaction
of the remaining group, i.e., the cost of sensing amongst the
remaining robots. In general, the method proposed in our work shifts the
utility from the team member itself to the interaction between the
members, and calculates the reallocation according to this
interaction cost. We found that this can be done optimally by a
deterministic algorithm, while reducing the time complexity from $O(N^k)$ to $O(2^k)$, thus resulting in a
polynomial time complexity in the common case where a small number of robots is extracted, i.e., when $k=O(N)$. We show that our basic algorithm creates a framework that can be extended for use in more complicated cases, where more than one component should be taken into consideration when calculating the robots' utility. We describe two such extensions: one that handles prioritized components and one that handles weighted components. We describe several other non-robotic domains in which our basic method is applicable, and conclude by providing an empirical evaluation of our algorithm in a robotic simulation. },
OPTannote = {}
}