Gal A. Kaminka's Publications

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

On Ants and Elephants

Asaf Shiloni, Noa Agmon, and Gal A. Kaminka. On Ants and Elephants. In Proceedings of the AAMAS-08 Workshop on Formal Models and Methods for Multi-Robot Systems , 2008.

Abstract

Investigations of multi-robot systems often make implicitassumptions concerning the computational capabilities of the robots.Despite the lack of explicit attention to the computational capabilities ofrobots,two computational classes of robots emerge as the focal points ofrecent research: Robot Ants and robot Elephants. Ants havepoor memory and communication capabilities,but are able to communicate using pheromones, in effect turning their workarea into a shared memory. By comparison, Elephants are computationallystronger, have large memory, and are equipped with strong sensing andcommunication capabilities. Unfortunately, not much is known about therelation betweenthe capabilities of these models in terms of the tasks they can address.In this paper, we present formal models of both Ants and Elephant, andinvestigate if one dominates the other. We present two algorithms:$\anteater$, which allows Elephant robots to execute ant algorithms; and$\elephantgun$, which converts elephant algorithms---specified as Turingmachines---into ant algorithms. By exploring the computational capabilitiesof these algorithms, we reach interesting preliminary results regarding thecomputational power of both models.

BibTeX

@InProceedings{mrs08,
author = 	 {Asaf Shiloni and Noa Agmon and Gal A. Kaminka},
title = 	 {On Ants and Elephants},
OPTcrossref =  {},
OPTkey = 	 {},
booktitle = {Proceedings of the AAMAS-08 Workshop on Formal Models and Methods for Multi-Robot Systems },
OPTpages = 	 {},
year = 	 {2008},
abstract = { Investigations of multi-robot systems often make implicit
assumptions concerning the computational capabilities of the robots.
Despite the lack of explicit attention to the computational capabilities of
robots,
two \emph{computational classes} of robots emerge as the focal points of
recent research: Robot \emph{Ants} and robot \emph{Elephants}. Ants have
poor memory and communication capabilities,
but are able to communicate using pheromones, in effect turning their work
area into a shared memory. By comparison, Elephants are computationally
stronger, have large memory, and are equipped with strong sensing and
communication capabilities.  Unfortunately, not much is known about the
relation between
the capabilities of these models in terms of the tasks they can address.
In this paper, we present formal models of both Ants and Elephant, and
investigate if one dominates the other.  We present two algorithms:
$\anteater$, which allows Elephant robots to execute ant algorithms; and
$\elephantgun$, which converts elephant algorithms---specified as Turing
machines---into ant algorithms.  By exploring the computational capabilities
of these algorithms, we reach interesting preliminary results regarding the
computational power of both models. },
wwwnote = {},
OPTeditor = 	 {},
OPTvolume = 	 {},
OPTnumber = 	 {},
OPTseries = 	 {},