21-09-2008, 11:24 AM
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.
