Page 287 - Introduction to Autonomous Mobile Robots

Chapter 6
272
freedom nonholonomics) and, particularly, as environment dynamics becomes more signif-
icant, then the path-planning techniques described above become inadequate for grappling
with the full scope of the problem. However, for robots moving in largely flat terrain, the
mobility decision-making techniques roboticists use often fall under one of the above cat-
egories.
But a path planner can only take into consideration the environment obstacles that are
known to the robot in advance. During path execution the robot’s actual sensor values may
disagree with expected values due to map inaccuracy or a dynamic environment. Therefore,
it is critical that the robot modify its path in real time based on actual sensor values. This is
the competence of obstacle avoidance which we discuss below.

6.2.2 Obstacle avoidance
Local obstacle avoidance focuses on changing the robot’s trajectory as informed by its sen-
sors during robot motion. The resulting robot motion is both a function of the robot’s cur-
rent or recent sensor readings and its goal position and relative location to the goal position.
The obstacle avoidance algorithms presented below depend to varying degrees on the exist-
ence of a global map and on the robot’s precise knowledge of its location relative to the
map. Despite their differences, all of the algorithms below can be termed obstacle avoid-
ance algorithms because the robot’s local sensor readings play an important role in the
robot’s future trajectory. We first present the simplest obstacle avoidance systems that are
used successfully in mobile robotics. The Bug algorithm represents such a technique in that
only the most recent robot sensor values are used, and the robot needs, in addition to current
sensor values, only approximate information regarding the direction of the goal. More
sophisticated algorithms are presented afterward, taking into account recent sensor history,
robot kinematics, and even dynamics.

6.2.2.1 Bug algorithm
The Bug algorithm [101, 102] is perhaps the simplest obstacle avoidance algorithm one
could imagine. The basic idea is to follow the contour of each obstacle in the robot’s way
and thus circumnavigate it.
With Bug1, the robot fully circles the object first, then departs from the point with the
shortest distance toward the goal (figure 6.7). This approach is, of course, very inefficient
but guarantees that the robot will reach any reachable goal.
With Bug2 the robot begins to follow the object’s contour, but departs immediately
when it is able to move directly toward the goal. In general this improved Bug algorithm
will have significantly shorter total robot travel, as shown in figure 6.8. However, one can
still construct situations in which Bug2 is arbitrarily inefficient (i.e., nonoptimal).
A number of variations and extensions of the Bug algorithm exist. We mention one
more, the Tangent Bug [82], which adds range sensing and a local environmental represen-