Department of Computer Science
Technion City, Haifa 32000, Israel
Israel A. Wagner
Prof. Alfred M. Bruckstein
Dr. Michael Lindenbaum
Submitted to the Senate of the Technion - Israel Institute of Technology
Haifa, August, 1998
Ant-robots are simple physical or virtual creatures designed to cooperate
in order to achieve a common goal. They are assumed to have very limited
resources of energy, sensing and computing, and to communicate via traces
left in the workspace or on the ground, like many insects naturally do.
This paradigm is shown to sometimes lead to efficient cooperation in the domains of search and exploration;
performance is investigated via mathematical analysis and computer simulations.
The distribution of work among multiple a(ge)nts can be made by either
a central controller
who sends orders to the agents, or by an a-priori agreement on a certain partitioning that,
if obeyed by the agents, eventually leads to a completion of the given mission.
A third way, used throughout the current work, is to design the behavior of individuals such that cooperation
will naturally emerge in the course of their work, without making a-priori decisions
on the structure of the cooperation. The specific application that we address is covering,
which is also known as exploring or searching. This variety of names hints to the many
applications this problem might have: from cleaning the floor of a house to mapping an unknown planet or
demining a mine field. A goal of our work is to make the agents as simple as possible,
in order to enable rigorous mathematical analysis and to increase the reliability of the group.
The first problem we address is that of many simple robots cooperating
to clean the dirty floor of a non-convex region over the integer grid,
using the dirt on the floor as the main means of inter-robot communication.
We show an upper bound on the cover time, depending on the number of robots and the geometrical
properties of the region to be cleaned.
Next we consider the more general problem of covering a graph
by a group of robots that communicate by
leaving chemical odor traces that evaporate with time, and are able to evaluate the strength of smell at every
point they reach, with some measurement error.
We describe three methods of cooperatively covering a graph,
using smell traces that gradually vanish with time, and show that they all result in eventual task completion,
in a time polynomial in the number of vertices. As opposed to existing traversal methods,
our algorithms are adaptive: they complete the traversal of the graph even if
some of the agents die or the graph changes (edges/vertices added or deleted)
during the execution, as long as the graph stays connected.
Another advantage of our agent interaction processes is the
ability of agents to use noisy information at the cost of longer cover time.
The third issue investigated in this work is that of exploring a continuous
unknown planar region
by a group of robots having limited sensors and no explicit communication.
A lower bound is shown on the length of any covering path,
and two methods are described for solving the problem on-line.
One is the deterministic ``mark and cover'' algorithm that uses short-lived
navigational markers as means of navigation and
indirect communication. The convergence of
the algorithm is proved, and its cover time is shown to be
the asymptotically optimal O(A/a), A being the total area and a -
the area covered by the robot in a single step.
The algorithm is tested against an alternative randomized
probabilistic method, which does not rely on markers
but is still able to cover an unknown region in an expected
time O(n rho log n), where n=O(A/a) and rho is the electrical resistance of the region, if made
of a uniform material with unit sheet-resistance.
Both algorithms enable cooperation of several robots to achieve faster coverage, as shown by simulations.
We then show that the two methods can be combined to yield a third, hybrid algorithm with a better tradeoff
between performance and robustness.
Finally we investigate the geometrical evolution of a probabilistic
based on local ant-inspired rule of motion that eventually leads to the straightening of the path of
a sequence of agents.
Our analysis and simulation results, although simple, seem to give a
first approximation of the
potential benefits to be gained from solving a typical robotic problem by means of a decentralized
multi-agent/multi-robot system, and to suggest various interesting problems for future research.