Gal A. Kaminka's Publications

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

Of Robot Ants and Elephants: A Computational Comparison

Asaf Shiloni, Noa Agmon, and Gal A. Kaminka. Of Robot Ants and Elephants: A Computational Comparison. Theoretical Computer Science, 412(41):5771–5788, 2011.

Download

[PDF]662.5kB  

Abstract

In the robotics community, there exist implicit assumptions concerning the computational capabilities of robots. Two computational classes of robots emerge as focal points of recent research: Robot Ants and robot 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 elephants, 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 conclusions regarding the computational power of both models.

BibTeX

@Article{tcs11,
 author={Asaf Shiloni and Noa Agmon and Gal A. Kaminka},
 title = {Of Robot Ants and Elephants: A Computational Comparison},
 journal = {Theoretical Computer Science},
 year = {2011},
OPTkey = {},
volume = {412},
number = {41},
pages = {5771--5788},
OPTmonth = {},
  wwwnote = {}, 
  OPTnote = {},
OPTannote = {},
 abstract =  { In the robotics community, there exist implicit assumptions 
 concerning the computational capabilities of robots. Two \emph{computational 
 classes} of robots emerge as 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 elephants, 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 conclusions 
  regarding the computational power of both models. }
}

Generated by bib2html.pl (written by Patrick Riley ) on Sun Jul 23, 2017 22:08:49