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

Asaf Shiloni. Of Robot Ants and Elephants. Master's Thesis, Bar Ilan University,2010.

Download

[PDF]1.2MB  

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 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 the first part of this thesis, 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. In the second part of this thesis, we investigate a specific problem involving two ants. In order to create a cooperative intelligent behavior, ants may need to get together; however, they may not know the locations of other ants. Hence, we focus on an ant variant of the rendezvous problem, in which two ants are to be brought to the same location in finite time. We introduce three algorithms that solve this problem for two ants by simulating a bidirectional search in different environment settings. Two algorithms for an environment with no obstacles and a general algorithm that handles all types of obstacles. We provide detailed discussion on the different attributes, size of pheromone required, and the performance of these algorithms.

Additional Information

BibTeX

@MastersThesis{asaf-msc,
author = {Asaf Shiloni},
title = {Of Robot Ants and Elephants},
school = {{B}ar {I}lan {U}niversity},
year = {2010},
OPTkey = {},
OPTtype = {},
OPTaddress = {},
OPTmonth = {},
OPTnote = {},
OPTannote = {},
  wwwnote = {}, 
  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 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 the first part of this thesis, 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. 
    In the second part of this thesis, we investigate a specific problem involving 
two ants. In order to create a cooperative intelligent behavior, ants may need to 
get together; however, they may not know the locations of other ants. Hence, we 
focus on an ant variant of the rendezvous problem, in which two ants are to be 
brought to the same location in finite time. We introduce three algorithms that 
solve this problem for two ants by simulating a bidirectional search in different 
environment settings. Two algorithms for an environment with no obstacles and a 
general algorithm that handles all types of obstacles. We provide detailed discussion on 
the different attributes, size of pheromone required, and the performance of these algorithms.
}
}

Generated by bib2html.pl (written by Patrick Riley ) on Sun Oct 29, 2017 21:31:22