SSC Pacific
Man-Portable Robotic Systems (MPRS)



The obstacle-avoidance algorithm developed for the URBOT is loosely based on the CMU Morphin algorithm, a behavior-based navigation architecture where various behaviors vote on a discrete set of actions.6 As applied here a number of arcs are projected in front of the vehicle over the obstacle map (Fig. 8). The number of arcs considered is a function of the map size and grid spacing with the arcs spaced such that one arc passes through each of the outer cells. This guarantees that each cell in the grid is covered by at least one arc. For a 7x7m grid with 41x41 cells, this results in a total of 160 arcs, 80 on each side of center. The arcs to the left of center are considered positive because a left turn has a positive turn rate (right-hand rule with Z up). Each of those arcs is related to the vehicle velocity and turn rate by where R is the radius of the arc, V is the vehicle velocity and Theta is the vehicle turn rate.

Each arc is given a weight or vote based on the distance the robot could travel along that arc before it encountered an obstacle. The longer arcs are weighted more favorably than the shorter arcs or arcs that are blocked near the robot. The votes are scaled from 1 to -1 so that they can be combined with votes from other behaviors by the arbiter (Fig. 10, top right).

Prior to running the OA routines the obstacles in the OA are expanded or grown. Growing obstacles is a common method used to compensate for the simplification of describing the robot as a point rather than a polygon. The obstacles are generally grown by half the length of the longest dimension of the vehicle, assuming that the vehicle’s coordinate system origin is in the center of the vehicle.

Obstacle Grid
Figure 8. Obstacle grid with arcs shown.

The votes for each arc from the OA algorithm are passed to the navigation arbiter where they are combined with votes from other navigation behaviors. The primary navigation behavior is waypoint navigation or route following. The waypoint navigation function produces a commanded turn rate and velocity based on the heading error between the robot’s current heading and the heading toward the goal point along the path (Fig. 9). At each cycle these turn-rate and velocity commands from the waypoint navigation function are converted into an arc. To form votes for the entire array of arcs, the primary arc is given the maximum value and votes for arcs on either side of it are linearly decreased until they reach a value of zero (the path following behavior does not vote against any arcs) (Fig. 10, top left).

Heading Error
Figure 9. Depiction of heading error between robot’s heading and heading to the goal point (Kelly, 1997).

Other arc-voting behaviors have also been added to help navigate around obstacles. These include a free-space behavior that votes (from 1 to 0) for large continuous sections of arcs that are unblocked, essentially open areas in the obstacle map (Fig. 10, bottom left). This behavior also votes for open arcs that fall between obstacles so that the robot won’t always favor going around groups of obstacles. An additional behavior was added that favors the arcs with the greatest radius, or in other words favors the current vehicle heading, which helps prevent sudden changes or oscillations in the vehicle heading.

Weighting factors are applied to the votes from each of the behaviors prior to combining them so that some behaviors contribute more to the final outcome than others. In the current implementation the OA behavior is weighted almost three times heavier than any of the other behaviors. The combined votes are shown in the bottom right plot in Figure 10.

Votes From Behavior
Figure 10. Example votes from behaviors.

Bookmark and Share
Updated: 11/7/2011 10:34 AM EST   Published (1.0)