Back
to indexJ. Borenstein and Y. Koren
Summary
This paper describes an algorithm for developing a vector field histogram, using sonar sensors, to describe a field of force vectors. Each force vector is a value representing the repulsive force toward the robot at each grid location. A surface of repulsive vectors is developed, where the robot traverses between the "free sectors" of lower repulsion. The authors point out that sonar is the bottleneck limitation of the algorithm, due to its low scanning rates. Under certain conditions, such as narrow doorways, the robot would be unable to pass through the doorway, since the repulsive fields from either side of the doorway would push it away from that region.
A comparison to edge detection algorithms is explored. Edge detection algorithms are sensitive to sonar accuracy, where minor deviations in readings from the edges of obstacles could affect the robot's path drastically. The authors conclude that edge detection alone is insufficient for fast obstacle avoidance.
Methods
The virtual force field (VFF) method is described as the precursor to the vector field histogram. This method uses a 2D cartesian histogram grid for obstacle representation. Each grid value is a certainty measure of the existence of an obstacle at that location. The cells taken together generate a histogram probability distribution, where high certainty values are generally close to the actual obstacle's position. As the robot moves along, it is able to refine its certainty measurements. Active cells are defined to be the region locally around the robot, which individually generate a repulsive force. At each step, the repulsive forces of the obstacles vary inversely with the attractive forces of the free regions in the active cells. The robot navigates along these regions. The authors point out this algorithm's weakness, which is the "doorway" problem described above, the discrete nature of the cartesian histogram causing drastic changes as the robot moves along, and the robot's swaggering behavior if it is unable to navigate along a straight corridor.
The second method, the vector field histogram (VFH), addressed these shortcomings while still remaining true to the real time goals. In this model, a 2 stage data reduction technique was employed. The first stage is mapping the active region onto a polar histogram, where the vehicle's center point determined the polar degrees. Each cell was a repulsive vector that was generated as a combination of the certainty value multiplied by the obstacle vector at each point. Occupied cells maintain their large repulsive vectors, allowing the polar obstacle density to be calculated. This model has an advantage over its cartesian cousin because it is cleanly "smoothed" with the robots vision sensors. The second stage reduces the data flow and produces steering control. The smoothed grid produces peaks and valleys in its surface "Candidate valleys" in the data are noted, and the robot selects the valley that is closest to its target. This method is fast, and reacts quickly to unexpected obstacles. Optimizations are performed with adaptive threshold to determine speed based on the width of the valleys, and reduce cyclic behavior of the robot.
Keywords
sonar sensors, vector field histogram, candidate valleys, certainty grid, repulsive vectors
Rating
7
Bibtex Entry
@article{ borenstein91vector,
author = "J. Borenstein and Y. Koren",
title = "The Vector Field Histogram - Fast Obstacle Avoidance for Mobile Robots",
journal = "IEEE Transactions on Robotics and Automation",
volume = "7",
number = "3",
pages = "278--288",
year = "1991",
url = "citeseer.nj.nec.com/borenstein91vector.html"
}