Abstract.
The objective of this project is to study biologically inspired algorithms
which enable a robot or group of robots to track an odor plume to its
source, with an appropriate combination of speed, efficiency, reliability,
and accuracy. Research is conducted at three levels: non-embodied point
simulations, embodied sensor-based simulations, and real robots. The
simulations use sensors and actuators which are based on the capabilities
of the real robots, and plume information is derived from empirical
data files recorded from real plumes or realistic plume simulators.
In simulation we explore the performance of various families of simple
algorithms, as well as the potential for automated parameter tuning
and on-line learning. We assess the most promising algorithms on real
robots, which are equipped with Caltech olfactory sensors, anemometric
devices, and simple communication systems.
Motivation.
Recently,
advances have been made in understanding biological and artificial odor
classification and odor localization as performed by moths and rats
in the air, and lobsters and stomatopods in water. Animals use a combination
of hardware (frequency of receptor adaptation, perhaps), software (temporal
integration and/or spatial integration), and search strategies (both
intrinsic and landmark-based) to locate odor sources. Odor localization
is in essence a behavioral problem, and for certain tasks (e.g., detecting
chemical leaks and mapping hazardous waste sites) there are engineering
advantages to combine odor sensing with mobile robots. We are interested
in developing small mobile robots that use odor tracking algorithms
and multi-sensor (e.g. odometry, anemometry, olfaction) fusion to search
out and identify sources of odor.
Research
Algorithm. The basic odor localization algorithm used in this study,
Spiral Surge (SS), is shown in Figure 1. It consists of different behaviors
related to the three different subtasks.
TABLE
I
Spiral Surge Algorithm Parameters
|
SpiralGab
1
|
Initial
spiral gap width |
| SpiralGab
2 |
Plume
reacquisition spirial gap width |
| Step
Size |
Surge
distance post odor hit |
| CastTime |
Length
of time before reverting from reacquisition to initial search spiral |
| SrcDecThresh |
Significance
threshold between separate odor hits |
| SrcDecCount |
Number
of significant differences before source declaration |
Figure
1. Spiral Surge odor localization behavior.
Plume finding is performed by an initial outward spiral search pattern
(SpiralGap1). This allows for thorough coverage of the local space if
the total search area is large and initial information can be provided
by the deployment point (an external 'best guess' as to source location).
Alternatively, if no a priori knowledge is available, a spiral with
a gap much greater than the arena size (producing essentially straight
line search paths) provides an effective, although not optimal, search
procedure. Future work will address search efficiency in greater detail.
Plume traversal
is performed using a type of surge algorithm. When an odor is encountered
during spiraling, the robot samples the wind direction and moves upwind
for a set distance (StepSize). If during the surge another odor packet
is encountered, the robot resets the surge distance but does not resample
the wind direction. After the surge distance has been reached, the robot
begins a spiral casting behavior, looking for another plume hit. The
casting spiral can be tighter than the plume finding spiral (SpiralGap2),
as post surge the robot has information about packet density and a thorough
local search is a good strategy. If the robot subsequently re-encounters
the plume, it will repeat the surging behavior, but if there is no additional
plume information for a set amount of time (CastTime), the robot will
declare the plume lost and return to the plume finding behavior (with
a wider, less local, spiral gap parameter).
Source declaration can be accomplished using the fact that a robot performing
the plume traversal behavior at the head of a plume will tend to surge
into an area where there is no plume information, and then spiral back
to the origin of the surge before receiving another odor hit. If the
robot keeps track internally of the post spiral inter-hit distances
(using odometry, for example, which is sufficient because information
must be accurate only locally), a series of small differences can indicate
that the robot has ceased progress up the plume, and must therefore
be at the source. However, because small inter-hit distances can occur
in all parts of the plume, this method is not foolproof, and tuning
the significance threshold (SrcDecThresh), as well as the number of
observed occurrences before source declaration (SrcDecCount), is required
to obtain a particular performance within a given plume. See Table I
for a summary of individual SS parameters.
SS uses only binary odor information generated from a single plume sensor.
This is motivated partially because this is the most simple and reliable
type of information that can be obtained from real hardware. However,
due to the highly stochastic nature of turbulent fluid flow and the
odor-packet nature of the plume, it is unclear that more complex sensing
-- via graded intensity information or larger sensor arrays -- would
benefit an agent when flow information is available through other means.
Real Robots. We use Moorebots, as shown in Figure 2a. The plume
traversal arena is 6.7 by 6.7 m, and the robots are 24 cm in diameter.
In addition to the basic setup, as described in [Winfield00], each robot
is equipped with four infra-red range sensors for collision avoidance,
a single odor sensor tuned to sense water vapor, and a hot wire anemometer.
An overhead camera tracking system (Figure 2b), combined with a radio
LAN among the robots and an external workstation, is used to log position
data during the trials, reposition the robots between trials, and emulate
the binary communication signals. Trials of different group size are
interleaved and inactive robots are automatically positioned at recharging
stations.
(a)
(b)
Figure
2. (a)
Moorebots in plume traversal arena. (b) Overhead camera view
The
odor sensor detects the presence of an airborne substance through a
change in the electrical resistance of a chemically sensitive carbon-doped
polymer resistor. We generate a water plume using a pan of hot water
and an array of fans. Mapping the plume using a random walk behavior
(see Figure 3a) indicates that the plume is stable. The anemometer is
enclosed in a tube that gives it unidirectional sensitivity, which,
combined with a scanning behavior, allows the robot to measure wind
direction.
(a)
(b)
Figure 3. (a) Plume hits received by 6 real robots over 1 hour
while performing a random walk behavior. (b) Plume hits received by
6 simulated robots over 1 hour. (b) Average wind direction in plume
traversal arena as measured by the real robots. Plume source at upper
right. Arrow lengths are proportional to the mean flow magnitude at
the tail of each arrow.
Embodied Simulation. In absence of a functional higher level
alternative, we used Webots, a 3D sensor-based, kinematic simulator,
originally developed for Khepera robots, to systematically investigate
the performance of SS in simulation. This embodied simulator has previously
been shown to generate data that closely matches real Khepera [Martinoli99]
and Moorebot [Hayes00] experiments, so we were confident that real robot
behavior was accurately captured.
 |
 |
|
(a)
|
(b)
|
Figure
4. (a) Webots plume traversal arena with average plume intensity
map. (b) Performance of real robot (solid) and Webots (dashed) trials
across group size. Higher values indicate better performance. SS1 and
SS2 are the SS algorithm with different parameter values. Random Walk
uses no plume information and Random Odor decouples plume hits and spatial
location. For more details see [Hayes01]
The physical arena was captured in Webots, as shown in Figure 4a. To
properly capture the plume stimulus, we incorporated a series of leaky
source 2D plume images generated in a water flume by Philip Roberts
and Donald Webster at Georgia Tech. Such 'plume movies', even though
they do not capture the influence of the agents on plume dynamics, offer
a good approximation to the discretized (packet-like) nature of odor
stimulus received in real environments. We scaled the recorded plume
data to imitate the average speed and envelope of the real plume data
(Figure 3a), and tuned the odor sensitivity threshold (higher threshold
leads to less odor information) based on performance observed in our
real arena. Flow information was taken directly from the real robot
data (as shown in Figure 3b) and introduced into the embodied simulations.
Achievements. We described a distributed algorithm for solving
the full odor localization task, and showed that group performance can
exceed that of a single robot.
We demonstrated that conducting polymer-based odor sensors possess the
combination of speed and sensitivity necessary to enable real world
odor plume tracing.
We created a stable test-bed and demonstrated that one subtask, plume
traversal, can be successfully accomplished by real robots.
We established that an embodied simulator can accurately replicate the
real robots results, and used a reinforcement learning system to optimize
system performance.
We showed that elementary communication among a group of agents can
increase the efficiency of the odor localization system performance.
References
Swarm Robotic Odor Localization. Hayes A. T., Martinoli A.,
and Goodman R. M., Proc. of the 2001 IEEE/RSJ Int. Conference on Intelligent
Robots and Systems IROS-2001, Wailea, Hawaii, October 2001, pp. 1073-1078.
Comparing Distributed Exploration Stratgeies with Simulated and
Real Autonomous Robots.Hayes A. T., Martinoli A., and Goodman R.
M., Proc. of the fifth Int. Symp. on Distributed Autonomous Robotic
Systems DARS-2000, L. E. Parker, G. Bekey, and J. Barhen, Eds., Knoxville,
Tennessee, October 2000, pp. 261-270, Springer Verlag.
An Autonomous Water Vapor Plume Tracking Robot Using Passive Resistive
Polymer Sensors. Kazadi S., Goodman R., Tsikata D., Lin H., Autonomous
Robots, 2000, Vol. 9, No. 2, pp. 175-188.
Swarm Intelligence in Autonomous Collective Robotics: From Tools
to the Analysis and Synthesis of Distributed Control Strategies.
A. Martinoli, PhD Thesis, Dept. of Computer Science, EPFL, Lausanne,
Switzerland, 1999.
The Application of Wireless Local Area Network Technology to the
Control of Mobile Robots. Winfield A. F. T. and Holland O. E., Microprocessors
and Microsystems, 2000, Vol. 23, pp. 597-607.
