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.

(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

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

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.

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.

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.

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

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

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.

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