• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Noa Agmon, Meytal Traub, Sarit Kraus, and Gal A. Kaminka. Task Reallocation in Multi-Robot Formations. Journal of Physical Agents, 4(2):1–10, 2010.
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.
Available on the the journal web page at: http://www.jopha.net/index.php/jopha/article/view/68
@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 = {}
}
Generated by bib2html.pl (written by Patrick Riley ) on Fri Aug 30, 2024 17:29:51