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 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 Researchers webpage

[<--] Back to the Applications of Interval Computations webpage

[<--] Back to the main menu of the Interval Computations website