Page 317 - Introduction to Autonomous Mobile Robots

302

Path planning Chapter 6
Global Local
knowledge, map knowledge
Executive

Real-time controller
behavior 1 behavior 2 behavior 3
PID motion control

Robot Hardware

Figure 6.25
A three-tiered episodic planning architecture.

tationally intensive, and therefore planning too frequently would have serious disadvan-
tages. But the executive is in an excellent position to identify when it has encountered
enough information (e.g., through feature extraction) to warrant a significant change in
strategic direction. At such points, the executive will invoke the planner to generate, for
example, a new path to the goal.
Perhaps the most obvious condition that triggers replanning is detection of a blockage
on the intended travel path. For example, in [129] the path-following behavior returns fail-
ure if it fails to make progress for a number of seconds. The executive receives this failure
notification, modifies the short-term occupancy grid representation of the robot’s surround-
ings, and launches the path planner in view of this change to the local environment map.
A common technique to delay planning until more information has been acquired is
called deferred planning. This technique is particularly useful in mobile robots with
dynamic maps that become more accurate as the robot moves. For example, the commer-
cially available Cye robot can be given a set of goal locations. Using its grassfire breadth-
first planning algorithm, this robot will plot a detailed path to the closest goal location only
and will execute this plan. Upon reaching this goal location, its map will have changed
based on the perceptual information extracted during motion. Only then will Cye’s execu-
tive trigger the path planner to generate a path from its new location to the next goal loca-
tion.
The robot Pygmalion implements an episodic planning architecture along with a more
sophisticated strategy when encountering unforeseen obstacles in its way [36, 122]. When
the lowest-level behavior fails to make progress, the executive attempts to find a way past
the obstacle by turning the robot 90 degrees and trying again. This is valuable because the