A global planner determines the best path for the robot to take to reach its human-commanded destination, taking into account not only the shape of the terrain but also the robot's own constraints, such as steering and climbing ability, and ground clearance. The global planner has the unique capability to change its planned path at any moment, according to new problems posed by the terrain.

The robot's local path planner, Ranger, guides the robot over the immediate terrain, using data from both the global planner and the perception system. The local planner uses techniques developed in ARPA's Unmanned Ground Vehicle (UGV) program for cross-country navigation [Kelly 1994a]. The basic idea is to evaluate the hazards along a discrete number of paths (corresponding to a set of steering commands) that the rover could possibly follow in the next few seconds of travel. The evaluation produces a set of "votes" for each path/steering angle, including "vetoes" for paths that are deemed too hazardous to traverse. In this way, the rover steers itself away from obstacles, such as craters or mounds, that it cannot cross or surmount.

The obstacle avoidance planner first merges individual elevation maps produced by the stereo system to produce a more complete terrain map of the area up to seven meters in front of the rover. Map merging is necessary because the limited fields of view of the cameras do not allow a single image to view sufficient terrain; map merging is desirable because it provides the robot with the most up-to-date information with which to make planning decisions. To make the stereo computation tractable, a small segment of the stereo image is requested, at reduced resolution, (typically only about 2% of the total available image). The planner dynamically chooses which portion of the image that the stereo system should process, based on the current vehicle speed, stopping distance, and expected cycle time of the perception/planning/control loop.

To evaluate the potential steering commands, the planner uses a detailed model of the vehicle's kinematics and dynamics to project forward in time the expected path of the rover on the terrain. This produces a set of paths, one for each potential steering direction. The planner then evaluates, at each point along the path, the robot's roll and the pitch of each body segment. If the roll or pitches exceed an allowable threshold, or if the path crosses a significant area that has not yet been imaged by the cameras, then the path is vetoed. Otherwise, the value assigned to that path depends on how level is the overall traverse, and how known is the underlying terrain. The path evaluations are then sent to the arbiter, along with the pose of the robot at the time of the evaluation. Currently, on a SPARC 10, the obstacle avoidance planner takes about 500 msec per cycle (map merging and path evaluation).

LRD Navigation Group - (last updated in March 1995)
Comments? Suggestions? Requests? Please send e-mail to!