oo
z
s
wKeywords:
Indoor monitoring
Gas source localization
Bio-inspired algorithm
and a new one started, based on the information acquired about gas distribution. This enables the robot
to get close to the ejecting source, without relying on airflow measurements. Results from experiments
are also described and discussed, to assess the efficiency of the proposed method.
© 2008 Elsevier B.V. All rights reserved.
1. Introduction
This paper describes the design and implementation on a
robotic autonomous agent of a biologically-inspired algorithm,
named SPIRAL (Searching Pollutant Iterative RoundingALgorithm),
which aims to localize a gas/odor source in an indoor environment
in the absence of a strong and constant airflow. Even if this
condition represents a realistic indoor scenario very well, it
presents certain difficulties to the autonomous agent to track a
plume up to its source. The lack of a strong wind exacerbates the
patchiness and intermittency of gas distribution, as it is typical
of turbulent flows in the presence of strong mean flows. Gas
dispersion is characterized by low energy, turbulent mixing and
weak convective airstreams. Therefore, gas distribution presents
high temporal variations around an average value. Gas distribution
features and the lack of possibility of using information about
wind direction to infer the position of an emitting source, make
these experimental conditions much more challenging than the
experimental setting usually used in literature for plume tracking
experiments, where a strong and constant wind is artificially
generated.
In the approach here pursued, the robot moves along a spiral
path and stops at a temporal window in some specific locations
∗ Corresponding author at: CRIM Laboratory, Scuola Superiore Sant’Anna, Viale
Rinaldo Piaggio 34, 56025 Pontedera (Pisa), Italy. Tel.: +39 050883417; fax: +39
050883497.
E-mail address: g.ferri@imtlucca.it (G. Ferri).
in order to sample the gas. Based on the features collected from
the information acquired, the robot computes an index, called
the Proximity Index (PI), to assess how close the source of the
gas is to the sampling location. The PI is computed based on the
average of the signal measured, together with a measurement
of the peaks present in the acquired signal (concentration peak
frequency and intensity seem to increase in association with
proximity to a source [3,22]). Based on considerations about the
created PIs, a spiral may be reset and, after that, a new one is
started. This movement allows the robot to approach an emitting
source without relying on any information about the airflow.
The SPIRAL algorithm was implemented on a robotic platform
developed by the authors [9,10] and experimental results are
reported here. To test the efficiency of the algorithm we also
evaluated the results of a so-called random SPIRAL, in which
the original SPIRAL algorithm was tested with randomly created
PIs. We have also compared SPIRAL with a bacterium inspired
algorithm [32], with two different sampling times, to investigate
how changes in the acquisition time may affect its behavior.
The paper is outlined as follows: the next section focuses on
the potentialities and difficulties associated with the localization
of a chemical source by using an autonomous robot. A review
follows of previous works on source localization in experimental
settings with and without a strong wind. Section 2 illustrates
sensors calibration and source characterization results. Section 3
introduces the SPIRAL algorithm. Section 4 and 5, respectively,
describe the experimental set-up and experimental results. Finally,
conclusions and recommendations for future research close the
paper.Robotics and Autonomous S
Contents lists availa
Robotics and Auto
journal homepage: www.
SPIRAL: A novel biologically-inspired alg
in an indoor environment with no strong
Gabriele Ferri a,b,∗, Emanuele Caselli a,b, Virgilio Matt
Paolo Dario b
a BioRobotic Engineering School, IMT Lucca Institute for Advanced Studies, Piazza San Pon
b CRIM Laboratory, Scuola Superiore Sant’Anna, Viale Rinaldo Piaggio 34, 56025 Pontedera
a r t i c l e i n f o
Article history:
Received 26 July 2007
Received in revised form
3 July 2008
Accepted 15 July 2008
Available online 20 July 2008
a b s t r a c t
This work describes the de
source in an indoor environm
exacerbates the patchiness
presence of strong mean flo
position of the source. In the0921-8890/$ – see front matter© 2008 Elsevier B.V. All rights reserved.
doi:10.1016/j.robot.2008.07.004ystems 57 (2009) 393–402
ble at ScienceDirect
nomous Systems
elsevier.com/locate/robot
rithm for gas/odor source localization
airflow
li b, Alessio Mondini b, Barbara Mazzolai b,
iano 6, 55110 Lucca, Italy
(Pisa), Italy
ign and experimental results of an algorithm, designed to localize a gas
ent with no strong airflow by using an autonomous agent. This condition
and intermittency of odor distribution, typical of turbulent flows in the
s. Furthermore, no information about the wind can be used to detect the
approach proposed here, the robot moves along spirals. A spiral can be reset
394 G. Ferri et al. / Robotics and Autono
1.1. Searching for a gas/odor source by using an autonomous robotic
agent
The sense of smell is widely used throughout the biological
world. Animals use odors to catch information about the environ-
ment and to appropriately react to different situations [7]. Odor is
fundamental for many animal species to localize a possible source
of food [5,13,34] a mate (like moths, which follow a pheromone
plume [2,6]), or to escape from possible predators [15]. Further-
more, odors can also be used as ameans of communication to orga-
nize complex social behaviors: bees use odor to recognize relatives
or nest-mates [14], and ants use trails of pheromone to coordinate
movements and improve the ability for the swarm to find food [8],
just to give a few examples.
The ability to smell volatile chemicals provided by these sensors
has lead researchers – from the 90s on – to investigate the use of
gas sensors for robot navigation. The ability of robots to orientate
themselves by smelling some odor has proved useful in many
scenarios. Two applications have been investigated so far: a robot
using a trail of odor marked on the ground, to follow a particular
path [30], or a robot using odor clues to localize an emitting
source. In this paper, we will focus on the second issue. Gas
source localization by using an autonomous agentwould help us to
accomplish many tasks, in either indoor or outdoor environments:
it could help to localize leaks of harmful gas in industrial or
domestic environments, to monitor a poisoned area, to detect
pipeline leakages and to search for hidden explosives or narcotics.
To localize an emitting chemical source in a rapid and reliable
way is not an easy task, because of the complex nature of gas
distribution. Gas source localization essentially involves three
different subtasks, and according to the taxonomy of [16], they
include the following: plume finding—namely detecting increased
gas concentration, plume traversal — namely following the plume
up to the source, and source declaration — namely determining
if a source has been found. Turbulent gas dispersion brings up
a few issues for autonomous agents when fulfilling the above
mentioned subtasks. At medium and high Reynolds numbers (the
situation encountered by an autonomous agent), gas dispersion
is dominated by turbulent mixing [4,33]. Odor is concentrated
in ‘‘packets’’, often with extremely low concentration measured
between immersions in an odor packet. The slow velocity of gas
molecules to diffuse (ethanol constant diffusion is 0.119 cm2/s at
25 ◦C and 1 atm with a diffusion length in one hour calculated to
be only 20.7 cm) implies that gas dispersion is totally dominated
by airflows: flow turbulence dominates the distribution of gas
molecules. As a consequence, instantaneous gradients are poorly
defined, time varying and frequently do not point towards the
source [28]. To solve these problems, most researchers test
their approaches by introducing an artificial strong airflow in
the experiment area, to minimize the effects of gas turbulent
transport. Therefore, tracking a gas plume up to its source with
no sufficiently strong airflow is a much more difficult task:
gas dispersion is dominated by low energy turbulent mixing
and weak convective flows, produced by spatial temperature
differences [35], resulting in a patchier and more fluctuant gas
distribution. Local concentration maxima and even the absolute
maximum have been observed at some distance from the source,
if the source was active for some time [24].
The two different conditions (absence and presence of a strong
and constant wind) are shown in Figs. 2 and 3, which report
our source characterization test results, namely of one source
ejecting ethanol in the presence and absence of a strong wind (see
Section 2).
Test results show the following:
• With a strong and constant wind, at least in an area close to
the source, low fluctuations around the average gas value are
noticed and a gradient is defined (Fig. 2);mous Systems 57 (2009) 393–402
• Without any wind, high fluctuations of gas concentration occur
around the average value (Fig. 3).
Therefore, introducing a constant and strong airflow provides
several benefits in localizing a chemical source. Gas concentration
is temporally less fluctuant; the plume consists of two areas, as
noticed in [12,20]: a region closer to the source and a far region.
The region closer to the source consists of a high gas concentration
odorant, which sharply falls off at the edges of the plume (and
which makes the plume finding task easier for a robot), with the
average concentration decreasing when going downwind: here a
concentration gradient can be detected. Going downstream, the
plume becomes larger and edges are less well defined. This is the
far region, where instantaneous concentration is highly variable.
Moreover, the direction and intensity of a strongwind can be easily
measured by using an anemometer, where wind direction may
help to track the plume up to its source.
In the next section, we will review the approaches proposed by
researchers in the two different scenarios.
1.2. Previous works in an indoor environment in the presence and in
the absence of a strong and constant airflow
In experimental conditions with a strong and constant air-
flow, gradient-ascent based methods have been proposed and
tested [20,26,32]. In theseworks the robot uses spatially-separated
gas sensors. It reacts to a sensed concentration gradientmoving to-
wards the direction in which it senses a higher gas intensity. Based
on this strategy, a wheeled underwater robot was also made to
move in a flume featuring an artificially generated flow [12]. Re-
sults show that the gradient can be followed if the robot moves
inside the artificially generated plume and it is not too far from
the source: here a gradient is detectable. If the robot gets outside
the well defined plume or far from the source, the information ac-
quired is misleading and the robotic agent is liable to get ‘‘stuck’’
into local maxima or to wander about.
The biological world has inspired a family of bio-inspired
algorithms aimed at reproducing the successful behaviors of
animals in localizing ejecting sources. The chemotactic behavior
of the bacterium Escherichia coli has been implemented and tested
on robots [26,27,32]. The bacterium strategy works well in a small
scale, where the chemical dispersion is characterized by diffusion.
At large scales it presents the same flaws as the gradient-ascent
based algorithms: the robot is liable to wander about if it is far
from the source or outside the well defined edges of the plume.
However, unlike the gradient-ascent techniques, it is not affected
by the difficulties of relying on differential measurements taken
with different sensors, which are often misleading because of
the intermittent nature of the plume. The most studied behavior
is no doubt the upwind flight of the male moth searching for
a female ejecting pheromone [2,6]. The behavior of the moth
consists of counterturning patterns with alternate turns to the
left and right, according to the wind direction (casting), to come
into contact with packets of odor, and then an upwind movement
(surge), to come closer to the source. This successful behavior
was theoretically studied [4] and implemented on robots [27,29,
32], showing its efficiency and reliability. Other approaches aim
at using information about wind direction and gas samplings, to
mix plume acquisition and plume following behaviors up to a
source [16,17,31].
Much less work has addressed indoor environments without
artificially created strong ventilation, despite the fact that this
condition is more realistic and common in indoor environments,
and that this is the actual situation in which robots will have to
work in real applications.
G. Ferri et al. / Robotics and Autono
As previously anticipated, without a strong and constant
airflow, gas concentration presents peaks and high variability,
with respect to the average value (see Fig. 3). The extremely
weak airflows present in a room are hardly detectable. In fact,
the classically used thermal airflow anemometers show detection
limits (5 cm/s), unable to detect weak airflows [19]. Also the more
sensible ultrasonic anemometers (detection limits of about 1 cm/s)
sometimes fail to detect wind in particular areas of a room [19].
In addition, the movement of the robot can have some significant
impact in measuring weak airflow. Finally, it is worth noting that,
also with a constant mean airflow, the presence of obstacles can
generate areas where information about the wind cannot be used
by the robot. To deal with this issue, some researchers have tried
to propose methods that either do not rely on or only partially rely
on wind measurements.
Experiments with a robot moving in a corridor are reported
in [21], to investigate the relation between gas measurements and
source location (peaks in measured concentration are observed
to be associated with a source nearby). In [18] the use of gas
sensors, together with a vision system to identify some possible
ejecting objects, is tested in a room without forced ventilation:
the information about the airflow is only used when it is
available. However, the vision can be useful only if the source is a
recognizable object, for example a bin or a bottle. If it is a leak from
a pipeline, the vision cannot help to localize the source. In [23],
a modified moth behavior is described which does not use wind
information for its peculiar upwind movement.
With no wind, gradient-ascent based techniques can improve
overall performances, but theymay be easily affected by extremely
multimodal gas distribution [22].
2. Sensor calibration and source characterization
As odor sensors, we chose TGS 800 commercial sensors
manufactured by Figaro Engineering Inc. They are metal oxide
semiconductor gas sensors, and, in the presence of alcohol vapors,
internal resistance changes, based on a logarithmic function. This
kind of sensor was chosen for its high sensitivity, usable long life
span, and comparatively high robustness to changing environment
conditions [25]. The sensors are small, cheap, and can be easily
integrated in the measurement circuit [25]. Their main drawbacks
involve the need for a high operating temperature, which causes
a high power consumption and slow recovery time after the gas
is removed. Furthermore, they include a variance of the response
characteristics between individual sensors. For this reason, at first,
some calibration sessions were carried out. Sensors (6 sensors:
5 for source characterization, 1 used on the robot) were tested
in a hermetically closed box, where a known increasing amount
of alcohol was periodically injected. A fan was also included to
accelerate alcohol vaporization and homogeneous dispersion. The
signals coming from the sensors were acquired using a DAQCard-
6024ETM, from National Instruments. Data were sampled every
1 ms, and each stored value was the mean calculated on 500
measurements. In order to calibrate the sensors, the data collected
were fittedwith the characteristic bi-logarithmic function given by
the sensors datasheet: the sensed gas concentration is proportional
to the value of the internal resistance, that is,
log(c) = f (log(R/R0)) (1)
where c is the sensed gas concentration, R is the internal resistance
and R0 is the resistance when no gas is sensed by the sensor.
We fitted this relation for all the known concentrations injected
in the box (ci) (we used 14 concentrations) using a third degree
polynomial:log(ci) = k0 + k1 log(R/R0)+ k2log(R/R0)2 + k3 log(R/R0)3 (2)mous Systems 57 (2009) 393–402 395
Fig. 1. Position of the sensors related to the ethanol source during the experiments
for source characterization. The source was a circular 8.5 cm diameter dish
containing ethanol alcohol.
where ci are the known ethanol concentrations used during
the calibration session and ki are the coefficients of the fitting
polynomial. We solved, in the least squares sense, the systems of
equations for the different sensors, to find the desired polynomial
coefficients. The coefficients of the polynomial, characteristic of
each sensor, were used to convert sensor voltage outputs into
concentrations.
In order to characterize gas dispersion, some preliminary
experiments were carried out. The source used was an 8.5 cm
diameter circular dish, containing ethanol alcohol, because of its
volatility at room temperature and no toxicity. This is the same
source used in the experiments with the robot. We used the
previously calibrated sensors to measure alcohol concentrations.
We used 5 sensors placed in a row, spaced 25 cm from each
other. The first one is at a distance of 30 cm from the source
(see Fig. 1). The acquisitions started after the ethanol had been
free to evaporate for 15 min. Two different kinds of trials were
carried out: one without the introduction of an external artificial
airflow and a second one with a fan, placed 40 cm behind the
source, generating an airflow of about 50 cm/s. We collected data
placing the sensors in four perpendicular directions to investigate
the spatial differences in gas distribution. Figs. 2 and 3 report
the results for one direction. Fig. 2 reports the results with the
sensors placed inside the limits of the well defined generated
plume.
The figures clearly show the differences between the two
conditions. With the presence of the wind, at least inside the well
defined plume and not too far from the source, gas concentration
is much smoother: a gradient is detectable, low variations around
an average value are present. There is a sharp fall in concentration
at the edges of the plume, created by the forced ventilation. The
analysis of Fig. 3, however, clearly shows a much more complex
distribution. There are high variations around an average value,
and at a distance from the source it appears more difficult to
recognize which sensor is the one closest to the source. The gas
distribution showsmuchmore spatial uniformity than for the case
with wind, in which extremely low concentrations are present on
the upwind side of the source. Fig. 3 also shows an interesting
feature of gas distribution: getting closer to the source, peaks of
gas intensity become more frequent and higher. These peaks, also
noted in [3,22], appear to be a distinctive feature of the proximity
to an emitting source. It has also been suggested that some animals
(lobsters, for example) [3] might theoretically be able to extract an
odor landscape from the shapes of the peaks of sensed odor, and
use it to move up to a food source.
3. SPIRAL algorithm
SPIRAL is an algorithm to localize a chemical source without
using any information about the airflow, so as to be able to
work reliably in an indoor environment with no strong airflow.
The SPIRAL idea involves spiral movements. During the spiral
movements the robot stops to sample gas. With the data acquired,
it figures out its proximity to the source: if it finds out it is closer
to the source in comparison with the previous measurements, the
robot starts one more spiral movement, otherwise, it continues in
the current one. Thisway, spirals are propagated to get closer to the
source (see Fig. 4). Fig. 5 shows the actual spiralmovement that the
Fig. 3. Source characterization without a predominant airflow. Sensor 0 is placed at a distance of 30 cm from the source. All sensors are spaced by 25 cm from each other,
so that the farthest sensor (Sensor 4) is at a distance of 130 cm. High fluctuations in sensor measurements around average values are noticed.
robot performs. Arm lengths have been chosen, based on the search
area dimensions. Crosses represent the sampling locations.
At this stage, it is necessary to discuss how to quantify the
proximity to a source and to describe the movements of the
propagating spiral.
3.1. Proximity to a source
Proximity to the source cannot be easily quantified by simply
referring to instantaneous gas concentrations, because of the high
signal fluctuations. The slow response time of gas sensors makes
it even more difficult for the robot to react to instantaneous gas
samplings. To solve these problems, SPIRAL uses a stop and sense
philosophy to sense the gas. An acquisition ismadewhen the robot
is not moving, and lasts 1T seconds. After each acquisition, an
index, called the Proximity Index (PI), is created.
The index is a number quantifying how close to the source
the robot is. Bearing in mind our observations throughout source
characterization experiments, we defined the PI, based on the
chemical source. PI parameters aim at mixing the intensity of the
concentration peaks measured and the mean of gas concentration
intensity in a weighted sum. The PI is defined as:
PI = Kµ · µ+ KP · P(1TP) (3)
where: Kµ, Kp are two multiplicative constant values;
- µ is the mean of the signal acquired by the gas sensor during
the fixed temporal window;
- P is defined as the sum of the number of peaks (a ‘‘peak’’
refers to a local maximum above the average value measured in
the acquisition window) of gas concentration, measured in a fixed
temporal window (1T ), each multiplied by its own intensity. The
acquisition temporal window (1T ) is divided into intervals of1Tp
seconds; for each interval, only the highest peak is considered for
the final sum;
- 1Tp is the length of the windows into which the acquisition
time is divided.
The mean (µ) is added to the PI, to catch some information on
the distance from the source, when the peaks are low.Fig. 2. Source characterization with a strong airflow. Airflow is forced by a fan placed behind the source. Sensor 0 is at a distance of 30 cm. All sensors are spaced 25 cm
from each other, so that the farthest sensor (Sensor 4) is at a distance of 130 cm. Sensors are placed inside the well defined plume created by the fan. Low fluctuations in
sensor measurements around average values are noticed.396 G. Ferri et al. / Robotics and Autonosignal average and on the measured concentration peaks, which
are a distinctive feature of gas distribution near an emittingmous Systems 57 (2009) 393–402The values for these parameters were chosen based on the
data coming from our source characterization experiments (in
G. Ferri et al. / Robotics and Autono
Fig. 4. SPIRAL algorithm basic idea. HIT indicates when the robot figures that it is
closer to the source.
Fig. 5. Actual spiral path covered by the robot. The crosses represent the sampling
locations.
the absence of wind). For each sensor, the data acquired were
divided into temporal windows of1T seconds. PIs were computed
from the different windows. The PI calculation was applied several
times, using a different set of parameters each time. The set
was generated heuristically within reasonable limit values. The
set of parameters that generated better PIs was chosen for the
implementation of the algorithm. For ‘‘better’’ we mean a set of
parameters that causes the PIs to better follow the order relation
between the sensors: that is, given two sensors, the one closer to
the source needs to have higher PIs than the one that is further.
The parameters include the following:1T (the fixed acquisition
temporal window) is a trade-off between searching algorithm
rapidity and PI creation accuracy, and it is fixed at 30 s (10 s and
20 s were also tested); 1Tp is fixed at 5 s (chosen among the
following tested values: 1 s, 2 s, 5 s, 10 s, 15 s).1Tp is a parameter
affecting spurious peaks readings. Kµ is fixed at 1 and Kp is fixed
at 0.5 (0.l, 0.2, 0.5, 0.7, 1, 1.5 were also tested) (they affect the
relative weighting of the average measure and peak intensities).
For the rare case in which no peaks are found, Kµ = 2 is used. This
correction is necessary to give more weight to the average value
in this specific case. Our experiments suggest that for this value it
is reasonable not to have so large a difference between a PI with
peaks and a PI without peaks.mous Systems 57 (2009) 393–402 397
The index seems relatively robust to different parameter
variations. The most critical parameter to choose is 1T . It was
chosen as a compromise between accuracy in PI creation and speed
in finding the source: a high1T , in fact, implies PIs that bettermeet
the order relation between the sensors, but it causes an overall
increment in the time to find the source.
3.2. SPIRAL movement strategy
Drawing inspiration from the behavior of insects, the SPIRAL
algorithm reiterates fixed searching in spiral figures. The moth, for
example, alternates fixed and repetitive movements to come into
contact with odors (casting), and then it moves upwind (surge) [6].
SPIRAL is basically a sort of casting (spiral movements) that is
sometimes restarted during the searching task. The decision to
restart the spiral movement is made on the basis of the calculated
PI values. Obviously, we cannot use a surge movement because we
cannot measure a stable and constant wind direction.
The robot moves along a spiral. At the end of each spiral arm, it
stops and performs an acquisition. With the data provided by the
acquisition, the robot calculates the Proximity Index (PI), which
takes into account the intensity of concentration peaks and the
mean value of the signal (see Section 3.1 for PI description). The
robot has a stored PI value called TPI (Threshold Proximity Index).
If the next PI is higher than or equal to the TPI , the TPI is refreshed
to the new PI value, and a new spiral is started (we call this a HIT).
Otherwise, if the new PI is lower than TPI , the TPI is not refreshed,
and the current spiral is continued (we call this a MISS).
SPIRAL presents the following additional features:
• A minimum threshold for PI: mTPI (Minimum Threshold PI).
This threshold is a minimum PI value below which the HIT
mechanism is not triggered.
The threshold was chosen based on experiments. We
calculated different PIs in different positions in the room used
for experiments with the robot, after a source had ejected
ethanol for 5min. Then, PIs calculated atmore than2m from the
source were considered not to provide sufficient information
about the proximity of the source. Their average was selected
as the minimum threshold.
• A mechanism of TPI lowering. This mechanism is activated in
two different cases:
• five consecutive MISSes; in this case, the TPI parameter is set
to the valuemTPI −∆ (where∆ is a positive constant design
parameter);
• three consecutive MISSes with measured PIs lower than
TPI/2; also in this case, TPI is set to the valuemTPI −∆.
• The first mechanism aims at solving the problem of a robot
moving about in a gas low-concentration area, and the second
one aims at preventing spurious high gas measurements (high
PIs), which could compromise the SPIRAL efficiency.
An escaping (ESCAPE) movement. When a spiral has ended
and no HIT has occurred during the spiral, the robot resets the
TPI , and then it rotates through a randomly generated angle (45◦
granularity). Afterwards, the robot goes forward covering some
distance (this distance is a design parameter depending on the
geometry of the environment). These movements are intended
to explore the environment randomly, when considerable PIs are
not produced. Even if this mechanism was rarely triggered in
our experiments, it is designed for an application in large indoor
environments where areas of low PIs can be found.
An obstacle-collision handling behavior has also been studied
and added to SPIRAL. In the case of an obstacle collision, the robot
performs a pre-defined sequence of movements, to avoid future
obstacle collisions. The obstacle-collision handling behavior is very
simple: the robot goes backwards, then rotates, and finally goes
fMOMO robotic platform, supplied with a TGS 800, manufactured
by Figaro Engineering Inc., a sensor for alcohol detection.
The MOMO platform was developed and presented in previous
works of the authors [9,10] to easily test gas-finding algorithms.
In our experiments we use one single-agent robot (see Fig. 7),
based on the RoboDesigner Kit, manufactured by Japan Robotech
Ltd, and a PC. The PC tracks the robot position (via a web-cam)
and communicates with the robot, checking its state (through an
FM communication channel — an AUR EL XTR-434H from AUREL
spa Inc. transceiver is used either with the PC or the robot), and
collecting the data produced by the robot’s actions. The robot,
17 cm long and 17 cm wide, is provided with two encoders on its
wheels for rough odometry, a main micro controller that manages
movement (PIC 184F52 from Microchip Technology Inc.), two sets
of high capacity rechargeable Ni-MH batteries (assuring at least
two hours of autonomy), two bumper whiskers as touch sensors,
and a TGS 800 gas sensor.
Fig. 8 shows a drawing of the roomwhere the experimentswith
the robot and preliminary tests with sensors were carried out. The
room contained a 3 m × 2.1 m arena where the robot was able
to move. The arena was delimited by polystyrene walls on the
north and south sides. Humidity and temperature conditions were
assessed so as not to vary remarkably when compared with those
reported in the sensor datasheet, and not to affect measurements
significantly. During the experiments, the doors and windows of
the roomwere kept shut. In the PC location, two persons were free
Fig. 7. The MOMO platform overview with one robot.
moved with a speed of about 20 cm/s. During each acquisition,
the robot sampled gas concentration every 1 ms, and it stored
averages calculated on 500ms. A third degree polynomialwas used
to convert sensor voltage outputs into concentrations during the
experiments, and its coefficients were calculated during the sensor
calibration experiments (see Section 2).
5. Experimental results
This section reports and discusses the experimental results
obtained from SPIRAL implementation on aMOMOplatform robot.
To evaluate the viability of the proposed SPIRAL algorithm,
sets of trials were carried out also implementing other algorithms
for the robot movement. Different sets of trials were carried out
for each algorithm, for two different starting conditions: 150 cm
and 180 cm robot-source start distance. A trial was considered
completed (stop condition) when the robot reached a 20 cm ×
20 cm square containing the source. The trials were divided into
sessions: four trials were carried out for each session. Each trial
session started five minutes after the opening of the gas source. At
the end of each trial session, windows were opened and the air of398 G. Ferri et al. / Robotics and Autono
Fig. 6. State diagram o
forward to cover the remaining distance it had to cover before the
collision. The sense of rotation (clockwise or counter-clockwise) is
chosen by taking into account either the task to continue the spiral
movement or the possibility of exploring places with higher PIs.
The obstacle collision handling appears to be a fundamental issue
above all in an indoor environmentwith obstacles, or characterized
by relatively small dimensions, where possible collisions with the
borders of the area may occur.
Fig. 6 reports the state diagram of the SPIRAL algorithm.
4. Experimental set-up
The SPIRAL algorithm was implemented on one robot of theto move. Fig. 9 shows a picture of the experiment area with the
robot searching for the source. During the experiments, the robotmous Systems 57 (2009) 393–402
the SPIRAL algorithm.the room changed. The experiment area is divided into nine sectors
(see Fig. 8). The source was placed in sector 6. The robot starting
G. Ferri et al. / Robotics and Autono
Fig. 8. A drawing of the experiment room. The position of the source (circle in
sector 6) and the starting position of the robot (arrow in sector 4) are showed.
Fig. 9. Experiment areawith the robotmoving around, with cardboard forwebcam
tracking.
position was placed in sector 4: the robot is oriented with its nose
heading at 90◦ to the source. The robot positions were tracked by
a webcam, so that searching paths could be easily displayed and
post-processed. A typical tracked trial of the SPIRAL algorithm is
reported in Fig. 10.
The SPIRAL algorithm functionalities have been compared with
two other algorithms: a bacterium-inspired algorithm (BA) [32]
and a random SPIRAL algorithm.
The behavior of E. coli bacterium [1] consists of straight runs
and occasional turns (tumbling). The angles of the turns depend on
the sensed chemical spatial gradient computed through successive
chemical samplings: if the gradient is positive, the bacterium
tends to go straight, otherwise it turns randomly. This behavior
has inspired robotic researchers and it has been implemented
on robots. We chose this behavior as a comparison with SPIRAL
because it is the only algorithm in literature, to the best of the
authors’ knowledge, which uses only one gas sensor and does not
require any information about the wind to work. In this paper, for
the first time, we present the results of the bacterium-inspired
algorithm application, in an environment with no strong and
constant airflow. We adopt the version used in [32]. Descriptionmous Systems 57 (2009) 393–402 399
Fig. 10. Webcam tracking of a trial. HIT indicates the condition when the new
computed PI is greater than or equal to the stored one. MISS indicates the situation
in which the new computed PI is lower than the stored one.
Table 1
Pseudo code of Escherichia coli bacterium algorithm
The E. coli algorithm:
l = 25 cm
repeat {
if current sensor reading is greater than previous sensor reading
rotate± random (5◦) and move forward l± random (0.05 l)
else
rotate± random (180◦) and move forward l± random (0.05 l)
}
of the implemented E. coli algorithm is given in Table 1. The
acquisition time for the BA is set at 3 s [26,32] which seems to be a
suitable time to achieve reliable gas measurements. We also tried
to investigate the behavior of BA with an acquisition time of 30 s,
the same time as used by SPIRAL.
The random SPIRAL algorithm is implemented in the same way
as SPIRAL, but using random values instead of computed Proximity
Indices. The SPIRAL random walk was used to assess whether the
room dimensions are large enough to avoid a particular kind of
random walk can find the source with a number of acquisitions
comparable to SPIRAL.
The results (means and standard deviations) of the trials carried
out using the three different algorithms are reported in Table 2. The
comparison between SPIRAL and random SPIRAL shows clearly the
superior efficiency of the proposed method (on average, SPIRAL
reaches the source using less than one third of the acquisitions
needed by the random SPIRAL algorithm). This assesses that the
experimental area is large enough for a ‘‘smart’’ randommovement
to be unable to achieve comparable results.
SPIRAL works better than the bacterium-inspired algorithm
(both with 3 s and 30 s acquisition times). The results of our
trials with the BA (30 s acquisition time) suggest that, even if
the bacterium-inspired algorithm (30 s acquisition time) finds the
source with fewer acquisitions than BA (3 s acquisition time), it is
much slower. This is due to the nature itself of bacterium-inspired
algorithm. The robot needs to perform a remarkable number of
acquisitions, in order to orientate itself using the random nature of
the bacterium algorithm. Issues come up when the robot moves in
areaswith low gas concentrations: the high number of acquisitions
purpose of localizing a gas source in an indoor environment in
the absence of strong airflows. Turbulence and weak convective
flows strongly characterize the dispersion process. Gas is present in
‘‘packets’’, and high fluctuations around amean value are observed
(see Fig. 3). These problems decrease with the introduction of a
strong wind. A strong and constant wind increases the energy of
turbulent mixing producing an area relatively close to the source
where a gradient is detectable and low fluctuations around amean
value are present (see Fig. 2). Without a strong wind, information
about airflow direction cannot be used to infer the position of the
ejecting source. Therefore, searching an odor source in a windless
room becomes a harder task. In this paper, we focused on this
environment for two different reasons: it can well represent a
realistic indoor scenario, and these conditions may be peculiar to
areas behind obstacles also when a strong mean flow is present in
the searching area.
To perform gas source localization in these experiment
conditions, we proposed the SPIRAL algorithm, which consists of
measurements with spatially separated sensors might be
misleading, because of gas concentration high fluctuations;
• it works without a constant forced airflow and without the
necessity of acquiring information about the wind (measuring
wind direction in the environment described may be hard to
accomplish [19]).
In the literature, only a few works address the gas source
localization issue in the environment analysed in this paper. The
only other method showing the same features, to the best of the
authors’ knowledge, is the bacterium-inspired algorithm. Fromour
experiments SPIRAL appears to bemore robust than the bacterium-
inspired method.
If we take the time used to find a source as a merit factor,
SPIRAL needs more time if compared with the time necessary
for the algorithms available in the literature, which use the
wind information. However, the time used is comparable and
of the same order of magnitude. Similar results achieved in a
more difficult experiment setting show the viability of SPIRAL400 G. Ferri et al. / Robotics and Autono
Table 2
Results of the trials with different algorithms
Algorithm Starting distance from the source (cm) Num
SPIRAL µ = 180 15
µ = 150 15
E. COLI (acquisition time= 3 s) µ = 180 15
µ = 150 15
E.COLI (acquisition time= 30 s) µ = 180 4
µ = 150 4
SPIRAL RANDOM µ = 180 10
µ = 150 10
needed to approach areas closer to the source where the algorithm
can work better make the task of moving towards areas with
higher concentrations too time consuming. Time to find the source
drastically decreases reducing the sampling time. The BA (3 s
acquisition time version) produces times to find the source that are
comparable with SPIRAL times. However, SPIRALworks better. It is
worth noting that the obstacle handling behavior becomes above
all fundamental in BA experiments. In fact, BA (3 s acquisition
time version) is more easily affected than SPIRAL by turbulent
effects, and it tends to wander about hitting the borders of the
experimental area. The many collisions with the borders and the
consequent collision handling behavior help the robot to explore
the experimental area andmakes it able to reach areas with higher
gas concentrations (closer to the source), where the BA algorithm
is more effective. In the trials in which SPIRAL was used, a few
collisions against the borders were observed (see for example
Fig. 10). This suggests that enlarging the experimental area would
not change SPIRAL results significantly, whereas it would decrease
BA efficiency: the robotmightmove in low gas concentration areas
and it could come closer to the source only after a long time. SPIRAL
balances its greater robustness against turbulent effects with a
longer acquisition window.
6. Conclusions and future works
This paper focuses on the design and implementation of a
biologically-inspired algorithm on a robotic platform, with thespiral movements and stop and acquisition steps, after which a
Proximity Index is created. The Proximity Index aims at expressingmous Systems 57 (2009) 393–402
ber of trials Time to find the source (s) Steps(acquisitions) to find the source
µ = 398.2 µ = 11.5
σ = 151.5 σ = 4.3
µ = 306.3 µ = 9.2
σ = 91.2 σ = 2.7
µ = 463.3 µ = 67.8
σ = 93 σ = 14.7
µ = 353.1 µ = 50.3
σ = 73.2 σ = 11.3
µ = 1671.2 µ = 49.3
σ = 134.9 σ = 4.1
µ = 1184.1 µ = 35.7
σ = 158.1 σ = 5.1
µ = 1351 µ = 38.6
σ = 291 σ = 8.1
µ = 991 µ = 28.3
σ = 193 σ = 5.2
proximity to the source with a numerical value. The index
includes the measured gas peak intensity and the signal average
as well. SPIRAL allows the robot to move towards higher and
higher Proximity Index locations, which correspond, on average,
to locations closer to the source.
The SPIRAL algorithm was implemented on the MOMO robotic
platform [9,10] and tested by means of experiments with one
robot. The validity of the SPIRAL approach was assessed by
comparing it with an E. coli bacterium algorithm (the only other
method available in the literature, to the best of the authors’
knowledge, which presents the same features as SPIRAL: single
and not differential gas measurements and no use of information
about the wind) and a SPIRAL random-walk. The results are very
encouraging and show that the algorithm is robust and reliable
in finding the source. The SPIRAL algorithm main features can be
summarized as follows:
• the robot moves spirally towards high Proximity Index
locations;
• the spiral movements make the algorithm intrinsically robust,
which means that wrong measurements (low measurements
near the source) do not compromise its effectiveness. If no
trigger occurs, the spiral movement, in fact, allows the agent
to pass again in a location closer to the source, where the robot
has another possibility to trigger;
• no differential measurements are needed. There is no necessity
to calibrate more than one sensor: to calibrate different gas
sensors is not an easy task. More importantly, differentialas an algorithm to be used in an indoor environment, when the
airflow is so weak or unsettled that a state-of-the-art anemometer
G. Ferri et al. / Robotics and Autono
cannot measure it reliably. It could also be used together with
traditional algorithms in areas (above all behind obstacles) where
traditional algorithms fail because of the difficulty of measuring
wind direction.
In future works, further experiments in larger areas will be
carried out, to investigate the efficiency of SPIRAL. In addition,
we will use SPIRAL in a multi-source and windless environment,
together with a probabilistic mapping algorithm [11]. Once the
presence of a source in an area has been most likely detected, the
spiral movements of SPIRAL may be used to localize the ejecting
source.
References
[1] J. Adler, The sensing of chemicals by bacteria, Scientific American 234 (4)
(1976) 40–47.
[2] A. Arbas, M.A. Willis, R. Kanzaki, Organization of goal-oriented locomotion:
Pheromone-modulated flight behavior of moths, in: R.D. Beer, R.E. Ritzmann,
T. McKenna (Eds.), Biological Neural Networks in Invertebrate Neuroethology
and Robotics, Academic Press, San Diego, 1993, pp. 159–198.
[3] J. Atema, Eddy chemotaxis and odor landscapes exploration of nature with
animals sensors, Biological Bulletin 191 (1996) 129–138.
[4] E. Balkovsky, B.I. Shraiman, Olfactory search at high Reynolds number,
Proceedings of the National Academy of Science 99 (20) (2002) 12589–12593.
[5] J. Basil, J. Atema, Lobster orientation in turbulent odor plumes: Simultaneous
measurements of tracking behavior and temporal odor patterns, Biological
Bulletin 187 (1994) 272–273.
[6] J.H. Belanger, M.A. Willis, Biologically-inspired search algorithms for locating
unseen odor sources, in: Proceedings of the IEEE ISIC/CIRA/ISAS Joint
Conference Galthersburg, MD, USA, 1998, pp. 265–270.
[7] D.B. Dusenbery, Sensory Ecology: How Organisms Acquire and Respond to
Information, Freeman, New York, 1992.
[8] L. Edelstein-Keshet, J. Watmough, G.B. Ermentrout, Trail following in ants:
Individual properties determine population behaviour, Behavioral Ecology
and Sociobiology 36 (2) (1995) 119–133.
[9] G. Ferri, E. Caselli, V. Mattoli, A Mondini, B. Mazzolai, P. Dario, A biologically-
inspired algorithm implemented on a new highly flexible multi-agent
platform for gas source localization, in: Proceedings of the IEEE RAS-EMBS
International Conference on Biomedical Robotics and Biomechatronics -
Biorob 2006, Pisa, Italy, 2006, pp. 573–578.
[10] G. Ferri, E. Caselli, V. Mattoli, A. Mondini, B. Mazzolai, P. Dario, A biologically-
inspired algorithm for gas/odor source localization in an indoor environment
with no strong airflow: First experimental results, in: Proceedings of
Workshop on Robotic Olfaction of IEEE International Conference on Robotics
and Automation, ICRA 2007, Rome, Italy, 2007.
[11] G. Ferri, M.V. Jakuba, E. Caselli, V. Mattoli, B. Mazzolai, D.R. Yoerger, P. Dario,
Localizingmultiple gas/odor sources in an indoor environment using Bayesian
occupancy grid mapping, in: Proceedings of the IEEE/RSJ International
Conference on Intelligent Robots and Systems, IROS 2007, San Diego, CA, USA,
2007.
[12] F.W. Grasso, T.R. Consi, D.C. Mountain, J. Atema, Biomimetic robot lobster
performs chemo-orientation in turbulence using a pair of spatially separated
sensors: Progress and challenges, Robotics and Autonomous Systems 30
(2000) 115–131.
[13] F.W. Grasso, J.A. Basil, How lobsters, crayfishes, and crabs locate sources
of odor current perspectives and future directions, Current Opinion in
Neurobiology 12 (2002) 721–727.
[14] L. Greenberg, Genetic component of bee odor in kin recognition, Science 30
206 (4422) (1979) 1095–1097.
[15] E. Hancock, A primer on smell, John Hopkins Magazine 9 (September) (1996)
(Electronic Edition — A Special Issue on the Senses).
[16] A.T. Hayes, A. Martinoli, R.M. Goodman, Distributed odor source localization,
IEEE Sensors Journal 2 (3) (2002) 260–271.
[17] H. Ishida, G. Nakayama, T. Nakamoto, T. Moriizumi, Controlling a gas/odor
plume-tracking robot on transient responses of gas sensors, IEEE Sensors
Journal 5 (3) (2005) 537–545.
[18] H. Ishida, H. Tanaka, H. Taniguchi, T. Moriizumi, Mobile robot navigation using
vision and olfaction to search for a gas/odor source, Autonomous Robots 20
(2006) 231–238.
[19] H. Ishida, Robotic systems for gas/odor source localization: Gap between
experiments and real-life situations, in: Proceedings of Workshop on Robotic
Olfaction of IEEE International Conference on Robotics and Automation, ICRA
2007, Rome, Italy, 2007.
[20] S. Kazadi, R. Goodman, D. Tsikata, D. Green, H. Lin, An autonomouswater vapor
plume tracking robot using passive resistive polymer sensors, Autonomous
Robots 9 (2000) 175–188.mous Systems 57 (2009) 393–402 401
[21] A. Lilienthal,M. Zell, U.Wandel, Sensing odour sources in indoor environments
without a constant airflow by a mobile robot, in: Proceedings of the 2001
IEEE International Conference on Robotics and Automation, ICRA 2001, Seoul,
Korea, 2001, pp. 4005–4010.
[22] A. Lilienthal, T. Duckett, Experimental analysis of smelling Braitenberg
vehicles, in: Proceedings of the IEEE International Conference on Advanced
Robotics, ICAR 2003, Coimbra, Portugal, 2003, pp. 375–380.
[23] A. Lilienthal, D. Reiman, A. Zell, Gas source tracing with a mobile robot
using an adapted moth strategy, Autonome Mobile Systeme (AMS) Karlsruhe,
December 4–5, (2003) 150–160.
[24] A. Lilienthal, T. Ducket, Building gas concentration gridmaps with a mobile
robot, Robotics and Autonomous Systems 48 (2004) 3–16.
[25] A. Lilienthal, A. Loutfi, T. Duckett, Airborne chemical sensing with mobile
robots, Sensors 6 (2006) 1616–1678.
[26] C. Lytridis, E.E. Kadar, G.S. Virk, A systematic approach to the problem of odour
source localization, Autonomous Robots 20 (2006) 261–276.
[27] L. Marques, U. Nunes, A. de Almeida, Olfaction-based mobile robot navigation,
Thin Solid Films 418 (2002) 51–58.
[28] J. Murlis, J.S. Elkinton, R.T. Cardè, Odor plumes and how insects use them,
Annual Review of Entomology 37 (1992) 505–532.
[29] P. Pyk, S. Bermudez i Badia, U. Bernardet, P. Knusel,M. Carlsson, J. Gu, E. Chanie,
B.S. Hansson, T.C. Pearce, P.F.M.J. Verschure, An artificial moth: Chemical
source localization using a robot based neuronal model of moth optomotor
anemotactic search, Autonomous Robots 20 (2006) 197–213.
[30] R.A. Russell, Laying and sensing odor markings as a strategy for assisting
mobile robot navigation trasks, IEEE Robotics and Automation Magazine 2
(1995) 3–9.
[31] R.A. Russell, D. Thiel, R. Deveza, A. Mackay-Sim, A robotic system to locate
hazardous chemical leaks, in: Proceedings of International Conference on
Robotics and Automation, ICRA 1995, 1, Nagoya, Japan, 1995, pp. 556–561.
[32] R.A. Russell, A. Bab-Hadiashar, R.L. Scheffer, G. Wallace, A comparison of
reactive chemotaxis algorithms, Robotics and Autonomous Systems 45 (2003)
83–97.
[33] B.I. Shraiman, B.I. Siggia, Scalar turbulence, Nature 405 (6787) (2000) 639–646.
[34] N.J. Vickers, Mechanisms of animal navigation in odor plumes, Biological
Bulletin 198 (2) (2000) 203–212.
[35] M.R. Wandel, A. Lilienthal, T. Duckett, U. Weimar, A. Zell, Gas distribution
in unventilated indoor environments inspected by a mobile robot, in:
Proceedings of the IEEE International Conference on Advanced Robotics, ICAR
2003, Coimbra, Portugal, 2003, pp. 507–512.
Gabriele Ferri received the Laurea degree (M.S.) in
Computer Engineering (with Honors) from the University
of Pisa, Italy, in 2003. From 2003 to 2005, he worked as a
Software/System Consultant Engineer for WASS company
(a Finmeccanica group company) in Livorno, Italy, working
on the design of a new System of Control and Guidance for
a light-weighted torpedo. He is currently a Ph.D. candidate
in Biorobotic Science and Engineering at IMT Advanced
Studies in Lucca, Italy, an inter-university consortium
formed also by Scuola Superiore S.Anna. From November
2006 he has been a visiting researcher at Woods Hole
Oceanographic Institution, Woods Hole, Massachusetts, USA. His research interests
include robotic systems for environmental monitoring/exploration, control theory
and robot navigation issues.
Emanuele Caselli received his Laurea degree (M.S.) in
Electronic Engineering from the University of Modena,
Italy in 2004.He is currently a Ph.D. candidate in Biorobotic
Science and Engineering at IMTAdvanced Studies Institute
in Lucca, Italy. From 2005 he worked in collaboration with
Scuola Superiore Sant’Anna, Italy. His research interests
include the implementation of robotic swarms systems
for environmental monitoring and exploration, sensors
integration, intra-robot communication and developing of
swarm behaviour.
Virgilio Mattoli received his Laurea degree in chemistry
(with Honors) from the University of Pisa and the Diploma
in Chemistry (with Honors) from the Scuola Normale
Superiore of Pisa in 2000. He joined the CRIM Lab of Scuola
Superiore Sant’Anna in 2001 with a research program
focused on the control and integration of miniaturized
devices for environmental and biomedical application.
He received his Ph.D. in bio-engineering (with Honors)
in 2005. He has been a visiting researcher at Stanford
University, California, USA, and at Waseda University,
Tokyo, Japan. His main research interests include: thin
film sensor microfabrication, sensor conditioning, miniaturized acquisition system,
wireless sensor networks, mechatronics and biorobotics. He is currently involved
in several research projects on these topics.
402 G. Ferri et al. / Robotics and Autono
Alessio Mondini received is Laurea degree in electronic
engineering from the University of Pisa, Italy in 2002.
In 2003, he worked in the national energy company
(ENEL) with a stage program focused on data acquisition
system and sensor conditioning for physicalmeasures into
the geothermal wells. From May 2004, he is working at
CRIM Laboratory of Scuola Superiore Sant’Anna. His main
research interests include microsystems technologies,
microelectronics andminiaturizeddata acquisition system
for sensor networks.
Barbara Mazzolai received her Laurea degree in Biology
(with Honors) from the University of Pisa, Italy, in 1995.
From 1994 to 1998, she worked at the Institute of Bio-
physics of the National Research Council on environmen-
tal topics and in particular, on mercury pollution. In 1998,
she received her Master’s degree in Eco-Management and
Audit Schemes (EMAS) from Scuola Superiore Sant’Anna
(SSSA), Pisa, Italy. Then, she had a research assistant po-
sition at Center for Research in Microengineering (CRIM)
Laboratory of SSSA from February 1999 until June 2004.
From July 2004, she obtained a temporary position of as-
sistant professor in bioengineering at SSSA. Her current research interests include
robotics, autonomous robots, microsystems and sensors for environmental, agro-
food and biomedical applications. She is currentlyworking on several European and
international projects focused on these fields.mous Systems 57 (2009) 393–402
Paolo Dario received the Dr. Eng. degree in mechanical
engineering from the University of Pisa, Pisa, Italy, in 1977.
He is currently a Professor of Biomedical Robotics at the
Scuola Superiore Sant’Anna, Pisa, Italy. He also teaches
courses at the School of Engineering of the University
of Pisa, and at the Campus Biomedico University, Rome,
Italy. He has been a Visiting Professor at Brown University,
Providence, RI, at the Ecole Polytechnique Federale de
Lausanne (EPFL), Lausanne, Switzerland, and at Waseda
University, Tokyo, Japan. He was the founder of the
Advanced Robotics Technologies and Systems (ARTS)
Laboratory and is currently the co-cordinator of the Center for Research in
Microengineering (CRIM) Laboratory of the Scuola Superiore Sant’Anna, where he
supervises a team of about 70 researchers and Ph.D. students. He is also the Director
of the Polo Sant’AnnaValdera and aVice-Director of the Scuola Superiore Sant’Anna.
His main research interests are in the fields of medical robotics, mechatronics,
and micro/nanoengineering, and specifically in sensors and actuators for the above
applications. He is the coordinator of many national and European projects, the
editor of two books on the subject of robotics, and the author of more than 200
scientific papers (75 in ISI journals). He is Editor-in-Chief, Associate Editor, and
Member of the Editorial Board of many international journals. Prof. Dario served
as President of the IEEE Robotics and Automation Society during 2002–2003, and
he is currently Co-Chair of the Technical Committees on Bio-robotics and of Robo-
ethics of the same society. He is a Fellow of the European Society on Medical and
Biological Engineering, and a recipient of many honors and awards, such as the
Joseph Engelberger Award. He is also a Member of the Board of the International
Foundation of Robotics Research (IFRR).