Interval Methods Help a Robot Succeed
Interval methods helped a robot designed by the University of Texas at
El Paso (UTEP) team win a prestigious third place world-wide in the robot
competition held during the American Association of Artificial Intelligence
conference in Portland, Oregon, August 6-7, 1996.
Robots have to deal with two types of uncertainty:
Traditionally, statistical methods have been used to deal with these
two types of uncertainty. There are, however, two major problems related
to these methods:
- first, their sensors are not absolutely accurate; as a result, they
measure, e.g., distances to obstacles only approximately;
- second, their actuators are not absolutely precise; as a result,
e.g., a command to turn 90 degrees can actually leads to an 85 or 95
The team leaders of the UTEP team, graduate students David Morales
and Tran Son and their supervisor Chitta Baral, decided to abandon
statistical methods and use interval-based methods instead.
- first, they are very computationally intensive: for every pixel,
at any moment of time, we need to compute and store the probability
that the corresponding point contains an obstacle; in a mobile robot,
it is desirable to have computational methods that are
as simple as possible;
- second, even more importantly, these methods require that we know
the probabilities of errors for different sensors and actuators, and
we usually do not know the exact values of these probabilities.
Instead, we only know the intervals of possible error values.
We can try to guesstimate the probabilities, but:
- if we wrongly guess the probabilities of sensor errors,
we may erroneously hit an obstacle;
- if we wrongly guess the probabilities of actuator errors,
and use these wrong probabilities in some filtering-type
correction, we may worsen the position error instead of
compensating for it.
To take sensor errors d into consideration, their robot assumes that any
pixel that could be (within this error) inside an obstacle has to be
avoided. As a result, e.g., when going in a corridor, the robot actually
follows the "virtual corridor" whose width is 2d smaller than the
To compensate for the actuator errors, with unknown probabilities, the
robot does not attempt any statistical filter-type corrections;
instead, it uses the sensor feedback to periodically
adjusts its position and orientation.
Several other novel ideas have been used. The resulting algorithms
turned out to be computationally simpler and more reliable than the
previously known ones. In the robot competition, the robot Diablo
implementing these algorithms won the third place in complicated office
navigation competition where robots had to navigate in a realistic
office environment. Diablo proved to be 100% reliable, always staying
on track and never hitting any obstacle. The only points it lost were
due to speed.
Due to novel algorithms, UTEP's commercially built robot outperformed
more than 20 much more technologically sophisticated robots from all
over the world, including teams from prestigious
institutions long involved in world-class robotic research
such as Carnegie-Mellon University and the
Universities of Stuttgart and Bonn.
In addition to D. Morales and T. Son, the main team included Luis
Floriano and Monica Nogueira. Support team members who assisted with
the robot's programming were Alfredo Gabaldon, Richard Watson, Glen
Hutton, and Dara Morgenstein.
Back to the Honors Received by Interval
Back to the Applications of Interval
Back to the main menu of the Interval