robot interval success story from UTEP

[David G. Hough at validgh]

Date: Sat, 5 Oct 96 21:17:29 MDT
From: vladikacs.utep.edu (Vladik Kreinovich)
To: reliable_computingainterval.usl.edu
Subject: interval methods help robots

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: 
* 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
  degree turn.
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, 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. 
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. 

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
actual width. 

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 top 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.