Introduction Real-time
obstacle avoidance is one of the key issues to successful applications of mobile
robot systems. All mobile robots feature some kind of collision avoidance, ranging
from primitive algorithms that detect an obstacle and stop the robot short of
it in order to avoid a collision, through sophisticated algorithms, that enable
the robot to detour obstacles. The latter algorithms are much more complex, since
they involve not only the detection of an obstacle, but also some kind of quantitative
measurements concerning the obstacle's dimensions. Once these have been determined,
the obstacle avoidance algorithm needs to steer the robot around the obstacle
and resume motion toward the original target.
Autonomous
navigation represents a higher level of performance, since it applies obstacle
avoidance simultaneously with the robot steering toward a given target. Autonomous
navigation, in general, assumes an environment with known and unknown obstacles,
and it includes global path planning algorithms [3] to plan the robot's path among
the known obstacles, as well as local path planning for real-time obstacle avoidance.
This article, however, assumes motion in the presence of unknown obstacles, and
therefore One approach to autonomous navigation is the wall-following method Here
the robot navigation is based on moving alongside walls at a predefined distance.
If an obstacle is encountered, the robot regards the obstacle as just another
wall, following the obstacle's contour until it may resume its original course.
This kind of navigation is technologically less demanding, since one major problem
of mobile robots) the determination of their own position) is largely facilitated.
Naturally, robot navigation by
the wall-following method is less versatile and is suitable only for very specific
applications. One recently introduced commercial system uses this method on a
floor-cleaning robot for long hallways A more general and commonly employed method
for obstacle avoidance is based on edge detection. In this method, the algorithm
tries to determine the position of the vertical edges of the obstacle and consequently
attempts to steer the robot around either edge. The line connecting the two edges
is considered to represent one of the obstacle's boundaries. This method was used
in our own previous research, as well as in several other research projects, such
as. A disadvantage with obstacle avoidance based on edge detecting is the need
of the robot to stop in front of an obstacle in order to allow for a more accurate
measurement.
A further drawback
of edge-detection methods is their sensitivity to sensor accuracy. Unfortunately,
ultrasonic sensors, which are mostly used in mobile robot applications, offer
many shortcomings in this respect:
1.
Poor directionality that limits the accuracy in determination of the spatial position
of an edge to 10-50 cm, depending on the distance to the obstacle and the angle
between the obstacle surface and acoustic beam. 2. Frequent misreading that
is caused by either ultrasonic noise from external sources or stray reflections
from neighboring sensors ("cross talk"). Misreading cannot always be
filtered out and they cause the algorithm to "see" nonexistent edges. 3.
Specular reflections, which occur when the angle between the wave front and the
normal to a smooth surface is too large. In this case the surface reflects the
incoming ultra-sound waves away from the sensor, and the obstacle is either not
detected at all, or (since only part of the surface is detected) "seen"
much smaller than it is in reality.
To
reduce the effects listed above we have decided to represent obstacles with the
Certainty Grid method. This method of obstacle representation allows adding and
retrieving data on the fly and enables easy integration of multiple sensors. The
representation of obstacles by certainty levels in a grid model has been suggested
by Elfes, who used the Certainty Grid for off-line global path planning. Moravec
and Elfes , and Moravec also describe the use of Certainty Grids for map building.
Since the obstacle avoidance approach makes use of this method, the basic idea
of the Certainty Grid will be described briefly.
In
order to create a Certainty Grid, the robot's work area is divided into many square
elements (denoted as cells), which form a grid (in our implementation the cell
size is 10 cm by 10 cm). Each cell (i,j) contains a Certainty Value C(i,j) that
indicates the measure of confidence that an obstacle exists within the cell area.
The greater C(i,j), the greater the level of confidence that the cell is occupied
by an obstacle.