Research Thesis

Department of Computer Science

Technion City, Haifa 32000, Israel

**Israel A. Wagner**

Advisors:

Prof. Alfred M. Bruckstein

Dr. Michael Lindenbaum

Submitted to the Senate of the Technion - Israel Institute of Technology

AV, 5758

Haifa, August, 1998

**Abstract**

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)**,

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

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
pursuit process

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.