Gal A. Kaminka's Publications

Sorted by DateClassified by Publication TypeClassified by TopicGrouped by Student (current)Grouped by Former Students

Task Reallocation in Multi-Robot Formations

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.

Download

[PDF]305.6kB  

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.

Additional Information

Available on the the journal web page at: http://www.jopha.net/index.php/jopha/article/view/68

BibTeX

@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 Sun Oct 29, 2017 21:31:22