The Virtual Force Field (VFF) and the Vector Field Histogram (VFH) Methods -- Fast Obstacle Avoidance for Mobile Robots

Obstacle avoidance methods based on ultrasonic sensors must account for the sensors' shortcomings, such as inaccuracies, crosstalk, and spurious readings. In our work this is accomplished with the histogram grid world model that is updated by rapidly firing 24 sensors around the robot during motion.

Fig. 1.1.1:The Histogram Grid

(a) For each range reading, the cell that lies on the acoustic axis and corresponds to the measured distance d is incremented, increasing the certainty value (CV) of the cell.

(b) A histogramic pseudo-probability distribution is obtained by continuous and rapid sampling of the sensors while the robot is moving.

Our earlier obstacle avoidance method combined the histogram grid world model with the concept of potential fields, or force fields. We named this method the virtual force field (VFF). The VFF method worked as follows:

  1. A virtual window moves with the vehicle and overlays a square region of the histogram grid. We call this the active window, and cells that are momentarily covered by the active window are called active cells. In our current implementation, the active window covers an area of w_s w_s cells in the histogram grid.
  2. Each active cell applies a virtual repulsive force F_i,j toward the vehicle. The magnitude of this force is proportional to the CV of the cell, and inversely proportional to r^2, where r is the distance between the cell and the vehicle.
  3. Next, all virtual repulsive force vectors F_i,j from the active cells are added up to yield the resultant repulsive force vector F_r.
  4. A constant-magnitude virtual attractive force F_t is applied to the vehicle by the target. The summation of F_r and F_t yields the resulting force vector R.
  5. The steering of the robot is aligned with R to avoid the obstacle.

Fig. 1.1.2: The Virtual Force Field (VFF) concept: Occupied cells exert repulsive forces onto the robot; the magnitude is proportional to the certainty value c_i,j of the cell and inversely proportional to r^2.

Problems with Potential Field Methods

In the course of our experimental work with the VFF algorithm, we identified a number of significant problems that are inherent to potential field methods and independent of the particular implementation. One of the most severe of these problems is the tendency of the robot to oscillate in narrow corridors.

A narrow corridor is defined as a passage in which the robot experiences repulsive forces simultaneously from opposite sides. Under steady state conditions, the repulsive forces from both sides balance the robot on an equilibrium line, which is usually on or close to the center of the corridor. If, however, the robot strays slightly to either side of the center-line, it experiences a strong virtual repulsive force from the near wall, while the repulsive force from the far wall decreases. As a result, the robot will turn to the far wall, overshoot the equilibrium line and consequently experience a strong repulsive force in the opposite direction. This effect may result in oscillatory and unstable motion.

Fig. 1.1.3: Instability With Potential Field Methods

Figures (a) and (b) show the path resulting from an actual robot run, along a wide and a narrow corridor, respectively. In the wide corridor, the robot adjusts its path smoothly in response to a sudden change in the width of the corridor. In the narrow corridor, however, the sudden change excites unstable oscillations and eventually causes a collision.

The Vector Field Histogram (VFH) Method

Careful analysis of the shortcomings of the VFF method reveals its inherent problem: excessively drastic data reduction that occurs when the individual repulsive forces from histogram grid cells are added up to calculate the resultant force vector F_r. Hundreds of data points are reduced in one drastic step to only two items: direction and magnitude of F_r . Consequently, detailed information about the local obstacle distribution is lost.

To remedy this shortcoming, we have developed a new method called the vector field histogram (VFH). The VFH method uses an intermediate data structure, called the polar histogram H. H is an array of 72 (5-deg wide) angular sectors. To account for the robot's changing position and new sensor readings, the polar histogram is completely rebuilt once during each 30 msec sampling interval. This works as follows:

A window moves with the robot, overlying a square region of w_s w_s (e.g., 33x33) cells in the histogram grid. The contents of each active cell in the histogram grid is mapped into the corresponding sector of the polar histogram (see Fig. 1.1.4), resulting in each sector k holding a value h_k. Thus, h_k is higher if there are many cells with high CVs in one sector. Intuitively, this value can be interpreted as the polar obstacle density in the direction of sector k.

Fig. 1.1.4: The heart of the VFH method: Mapping active cells onto the polar histogram.

Fig. 1.1.5: A Typical Experimental Run

(a) Typical obstacle setup in our lab. Note that the gap between obstacles B and C is only 1.2m and that A is a thin pole of 3/4" diameter. (b) The histogram grid obtained after partially traversing this obstacle course.

Fig. 1.1.6: The Polar Histogram

(a) The polar histogram corresponding to the momentary position of the robot at point O. The directions in the polar histogram correspond to directions measured counterclockwise from the positive x-axis of the histogram grid. The peaks A, B, and C in the polar histogram result from obstacle clusters A, B, and C in the histogram grid.

(b) The polar form of the exact same polar histogram as Fig. 1.1.6a, overlaying part of the histogram grid of Fig. 1.1.5b. Polar obstacle density represented in the polar histogram H(k) -- relative to the robot's position at O.

Selecting a Direction of Motion

A threshold on the polar histogram determines the candidate directions for subsequent travel. Candidate directions are shown as lightly shaded sectors in Fig. 1.1.7, while unsafe directions (i.e., those with polar obstacle densities (PODs) above the threshold) are shown in darker shades. Usually there are several candidate directions and the VFH algorithm selects the one that most closely matches the direction to the target.

Fig. 1.1.7: Candidate directions match free space in the actual environment: a fine-tuned threshold is not required.

Experimental Results

We implemented and tested the VFH method on our mobile robot CARMEL. CARMEL is based on a commercially available mobile platform; it has a maximum travel speed of 0.78 m/sec and weighs about 125 kg. The platform has a hexagonal structure and a unique three-wheel drive (synchro-drive) that permits omnidirectional steering. A Z-80 on-board computer serves as the low-level controller of the vehicle. We added two computers: a PC-compatible single-board computer to control the sensors, and a 20 MHz, 80386-based AT-compatible that runs the VFH algorithm. We ahve also equipped CARMEL with a ring of 24 ultrasonic sensors.

Fig. 1.1.8: Fast Motion in Cluttered Environments

Histogram grid representation of an actual run through a field of densely spaced, 3/4"-diameter vertical poles. The poles were spaced at a distance of about 1.4 m from each other. The actual location of the poles is indicated by (+) symbols. It should be noted that none of the obstacle locations were known to the robot in advance: the CV-clusters gradually appeared on the operator's screen while CARMEL was moving. The average speed in this run was V_avrg = 0.58 m/sec.

Click here for Project History

For more details on the VFF method see paper 10

For more details on the VFH method see papers 16,17

For more details on Histogrammic In-motion Mapping (HIMM) see papers 18,19