BIOLOGICAL INSPIRATION FOR COMPUTING 257
chemical spills lead to chemical concentration gradients in the soil and/or water; ecosystems host
gradients of light, salinity, and pH. In many cases, the source intensity of these gradients varies with
time (e.g., because of movement of the source), and there may be multiple sources for any given
characteristic (e.g., two fires causing a complex temperature gradient).
Autonomous detection, location, and tracking of gradient sources would be very helpful for those
trying to study or respond to the environment. Using robots, an environmental scientist might need to
find the source(s) of a given toxic chemical, whereas a firefighter might need to locate the source(s) of a
fire in order to extinguish it.
Noting that other approaches for locating and tracking gradient sources were primarily useful in
static or quasi-static environments, and inspired by biological studies of how bacteria are attracted to
gradient sources of nutrition, Dhariwal et al.^28 sought to develop a strategy for finding gradient sources
that worked well with sources that are small, weak, mobile, or time-varying in intensity. Specifically,
their algorithm is based on the repetition of a straight-line run for a certain time, followed by a random
change in direction that sets up the direction for a new run. If the bacterium senses a higher concentra-
tion in its immediate environment, the run length is longer. Thus, although the bacterium still under-
goes a random walk, it is a random walk biased in the direction of the gradient source.
This algorithm is also well suited for implementation in a simple robot. That is, only the last sensor
reading must be stored, and so memory requirements are lower. Because only one computation has to
be done (a comparison between the present and the previous sensor reading), processing requirements
are minimal.
Dhariwal et al. compared the performance of this algorithm with a simple gradient descent algo-
rithm. They found that for single, weak sources, the simple gradient algorithm displayed better perfor-
mance. However, the bacterium-inspired algorithm displayed better performance in locating and track-
ing multiple and/or dissipative sources and in covering the entire area in which the gradient can be
found.
8.2.4 Self-healing Systems
In the past few years, the term “self-healing” has become a fashionable object of study and interest
in the academic and research computer science communities^29 and in the marketing materials of infor-
mation technology (IT) companies such as IBM,^30 Microsoft,^31 Sun,^32 and HP.^33 Despite (or because
of?) this level of interest, there is no commonly accepted definition of “self-healing” or agreement of
what functionality it encompasses or requires.
(^28) A. Dhariwal, G.S. Sukhatme, and A.A.G. Requicha, “Bacterium-inspired Robots for Environmental Monitoring,” IEEE Inter-
national Conference on Robotics and Automation, New Orleans, LA, April 25-30, 2004, available at http://www-lmr.usc.edu/~lmr/
publications/Icra04bact.pdf.
(^29) Workshop on Self-healing, Adaptive and Self-managed Systems (SHAMAN), June 23, 2002, available at http://www.cse.
psu.edu/~yyzhang/shaman/proc.html; ICSE 2003 Workshop on Software Architectures for Dependable Systems, May 2003 (for
more information, see http://www.cs.kent.ac.uk/events/conf/2003/wads/);;) David Garlan, Self-healing Systems Course, #17-
811, Carnegie Mellon University seminar, Spring 2003 (for more information see http://www-2.cs.cmu.edu/~garlan/17811/);;)
D. Garlan, J. Kramer, and A. Wolf, eds., Proceedings of the First Workshop on Self-healing Systems, ACM Press, New York, 2002.
(^30) M. Hamblen, “IBM to Boost Self-healing Capabilities in Tivoli Line,” Computerworld, April 4, 2003, available at http://
http://www.computerworld.com/softwaretopics/software/story/0,10801,80050,00.html.
(^31) "Windows 2000 Professional: Most Reliable Windows Ever,” December 5, 2000, available at http://www.microsoft.com/
windows2000/professional/evaluation/business/overview/reliable/default.asp.
(^32) "Sun and Raytheon Create Open, Adaptive, Self-healing Architecture for DD 21,” available at http://wwws.sun.com/
software/jini/news/Jini-Raytheon.pdf.
(^33) "HP Delivers Self-healing and Virtual Server Software to Advance the Adaptive Enterprise,” press release, May 6, 2003,
available at http://www.hp.com/hpinfo/newsroom/press/2003/030506c.html.