| [back]
Distributed
Exploration and Coverage
Nikolaus Correll, Kjerstin Easton, Alcherio Martinoli, and Joel Burdick
Collaborators: Jonathan Witt, Edmond Wong (NASA Glenn Center)
Abstract.
The aim of this project is to formulate an efficient exploration and
coverage algorithm for a swarm of mobile agents. We present a completely
distributed algorithm relying on agents endowed with identical controllers.
The controller for the individual agent is realized through a hybrid
approach using deliberative planning together with reactive behavior
for collision avoidance. To exchange information about task progress
the agents exploit a cellular decomposition of the environment. Coverage
is performed using a grid-based algorithm (the Spanning Tree Coverage
algorithm). Interaction between the agents is constrained to decentralized
line-of-sight communication with limited range. The algorithm has been
proved regarding completeness and its performance has been systematically
investigated using an embodied simulator.
Motivation. Classical tasks in robotics, such as mapping and
coverage, and their applications, for example, lawn mowing, surveillance,
cleaning and maintenance, might be completed more efficiently by multiple
agents than by a single agent. By increasing the number of agents, communication
and centralized control pose complex problems. Moreover, depending on
the application, a certain degree of miniaturization may be required,
a constraint that limits the amount of energy available on board and,
in turn, the agent’s computational and communicational capabilities.
A decentralized approach not only minimizes long-range, energy-consuming
communication among agents but also achieves scalability to any number
of agents and robustness to possible failures of a central or single
unit.
Research. The single agent coverage algorithm is based on the
Spanning Tree Coverage (STC) algorithm, proposed by Gabriely and Rimon
[Gabriely and Rimon, 2001]. STC is a grid-based algorithm that assures
complete coverage by recursively exploring the spanning tree of the
occupancy grid. To divide labor among the agents, we divide the environment
into cells using a cellular decomposition. The agents use STC to cover
single cells while communicating with their teammates about task progress.
For path planning and navigation, we represent the decomposed environment
with an acyclic, directed graph with nodes representing the cells and
edges expressing connectivity. We call this graph a topological map.
We present an exploration strategy based on a depth-first search of
the topological map, the Single Exploration and Coverage (SEC) algorithm.
To achieve collaboration, the SEC algorithm is extended with a communication
protocol and renamed the Collaborative Exploration and Coverage (CEC)
algorithm. We use only line-of-sight communication with limited range
to assure scalability and low-power characteristics of the algorithm.
For collision avoidance we use a behavioral controller, which is transparent
to the high-level deliberative planner.
Achievements. The CEC algorithm was implemented in Webots, an
embodied, sensor-based, kinematic simulator of miniature robots [Michel
1998]. The cellular decomposition was hereby contrived for rectilinear
environments. We considered two different metrics to measure the performance
of various team sizes in randomly generated environments: the amount
of coverage over time and the amount of redundancy in coverage. We observed
a few intriguing trends by increasing team size. While in general the
rate of coverage improved by increasing the number of agents, an optimum
of three agents was observed for the environmental and agent parameters
we used. For more than three agents, this performance became worse due
to the increased communication load. On the other hand, we observed
a maximum in the redundancy of coverage with four agents while with
five agents, redundancy decreased. We conclude that, for these specific
experimental conditions, although in teams of five robots the communication
channel is more overloaded than in smaller teams, the opportunity to
exchange topological maps is also increased leading, in turn, to a reduction
of the redundant coverage.
|
