Abstract
In 1992, the University of Michigan’s CARMEL robot secured first place at the inaugural AAAI mobile robot competition. This paper details the architectural choices that led to its success, specifically the implementation of the Vector Field Histogram (VFH) for real-time obstacle avoidance and a lightweight, barcode-based vision system. By offloading complex spatial reasoning to a 1D polar representation and utilizing a finite state machine for object recognition, CARMEL achieved unprecedented speeds and reliability in a dynamic, cluttered environment, proving that autonomous robots could navigate complex spaces using entirely on-board processing.
Introduction
In the early 1990s, autonomous mobile robotics was transitioning from laboratory theory to real-world application. The AAAI-92 robot competition was established to benchmark the state-of-the-art in a 22m x 22m arena filled with cardboard boxes, wandering human judges, and specific target objects (ten-foot poles). The challenge required robots to demonstrate robust navigation, target acquisition, and high-speed efficiency under a strict 20-minute time limit.
At the time, many autonomous systems struggled with two primary issues: "crosstalk" (interference between sonar sensors) and the heavy computational load of image processing. These bottlenecks often forced robots to move at a snail's pace or rely on off-board computers for decision-making. The University of Michigan team addressed these challenges with CARMEL (Computer-Aided Robotics for Maintenance, Evaluation, and Localization), a Cybermotion K2A platform equipped with 24 sonar sensors and a single black-and-white CCD camera.
System Architecture and Methods
1. Obstacle Avoidance: VFH and EERUF
To handle the noise inherent in ultrasonic sensors, the team implemented EERUF (Error Eliminating Rapid Ultrasonic Firing) to reject crosstalk. For navigation, they employed the Vector Field Histogram (VFH) method, which allowed for high-speed movement without the need for frequent stops to process data.
The VFH method operates through a two-stage data reduction process:
- The Histogram Grid: A 2D Cartesian map where each cell stores a "certainty value" representing the probability of an obstacle's presence based on sonar returns.
- The Polar Histogram: This grid is compressed into a 1D polar representation centered on the robot. The authors describe this as a "mountainous panorama" where peaks represent obstacles and valleys represent safe travel directions.
By steering toward the valley closest to its target trajectory, CARMEL could maintain continuous motion. This abstraction allowed the robot to make steering decisions extremely quickly, enabling speeds of up to 780 mm/sec—a significant achievement for autonomous robots of that era.
2. Vision and Object Recognition
Rather than employing computationally expensive general-purpose computer vision, the team utilized a specialized approach for identifying the ten-foot poles. Each target was tagged with omni-directional barcodes consisting of black and white stripes on PVC tubing.
The vision algorithm was designed for maximum efficiency, scanning columns of pixels for white-to-black transitions in a single pass. A Finite State Machine (FSM) tracked the spacing of these bands to identify specific tags. This required zero image preprocessing, allowing the robot to detect and identify targets at distances of up to 19 meters in real-time. This simplicity ensured that the robot did not need to pause to "think" or process complex edge detections.
Experimental Results
CARMEL was the clear winner of the AAAI-92 competition, demonstrating a level of reliability and speed that other entries lacked. The competition was divided into three stages:
- Stage 1 (Roaming): CARMEL placed 3rd, demonstrating stable navigation in a cluttered environment.
- Stage 2 (Search and Visit): CARMEL placed 1st. It successfully found and visited all ten objects in under ten minutes. Notably, it was the only robot in the competition to find all ten objects within the 20-minute limit.
- Stage 3 (The Race): CARMEL placed 1st, completing a timed race to three specific objects and back to the starting point in just under three minutes.
Discussion and Limitations
The success of CARMEL was rooted in the synergy between its hardware and software. The system used three separate processors to parallelize tasks: one for motor control, one for sonar firing, and one for high-level logic (avoidance and recognition). This parallel architecture, combined with the algorithmic simplicity of the VFH and barcode recognition, allowed for real-time performance that outpaced competitors relying on more complex, slower models.
However, the approach had inherent limitations. The vision system was entirely dependent on artificial markers; it would not have functioned in a "natural" environment without the specific barcode tags. Additionally, while EERUF mitigated crosstalk, the sonar-based navigation remained susceptible to "specular reflection," where sound waves bounce off smooth surfaces at an angle, rendering them invisible to the sensors.
Conclusion
CARMEL’s victory at AAAI-92 proved that abstraction and simplicity are powerful tools in robotics. By reducing complex 2D environments into 1D histograms and using specialized markers for vision, the Michigan team created a robot capable of operating at human-like speeds in dynamic environments. This work laid the groundwork for future research into real-time reactive navigation and efficient sensor fusion.
Summary updated