Mars Autonomy Project Local Obstacle Avoidance

Mars Autonomy
    Obstacle Avoidance
Path Planning
Contact us
Related Sites
We use a local obstacle avoidance algorithm called Morphin. Morphin has the ability to recommend good steering commands to the arbiter, and also vetoes dangerous commands.

Morphin maintains a high-resolution grid based map of the traversability of the immediate vicinity. Starting with an empty map, Morphin adds new sensor data from the traversability mapper as it is obtained.

Morphin does not look for discrete obstacles. Rather, it evaluates potential steering commands by integrating the traversability and certainty of map cells along the corresponding arcs of motion.


The Morphin Map
Morphin Screen Shot


Morphin maintains a local map that integrates a number of individual stereo traversability maps provided by the traversability mapper. It adds each traversability map sensor footprint to the appropriate location in its map based on the current estimate of rover pose.

Because of the possibility of dynamic obstacles, and because the pose estimate has growing uncertainty as the rover continues to move, the certainty of old data is discounted based on the time and distance travelled since it was collected.

The Morphin map grid has high resolution and tracks only a small local area. It wraps from top to bottom and left to right, allowing the rover to move arbitrarily long distances without leaving the map.

A sample morphin map is shown above. The traversability fades from green (best) to red (worst). Certainty fades from highest (bright red or green) to lowest (black). The position of the rover is indicated by the white silhouette in the center. Note the dimmer yellows in the upper right, behind the rover, showing that this older data has had its certainty discounted. The blue arcs correspond to potential steering commands, as explained in the next section.


Steering Evaluation
Morphin has the ability to recommend good steering commands to the arbiter, and also vetoes dangerous commands.

Steering can be either left or right, over a range of turn radii. The range of radii is discretized to form about twenty possible steering commands. Each such command corresponds to a steering arc, calculated by propagating the rover pose forward in time with that command in effect.

Morphin evaluates each arc based on the average traversability and certainty of grid cells along the arc, and the worst hazard encountered on the arc. It uses these data to calculate a figure called merit. Morphin recommends high merit steering commands to the arbiter, and vetoes commands below a certain threshold as unsafe.

In the Morphin map shown above, the blue arcs are steering arcs under evaluation. In this case, Morphin will recommend that the vehicle make a left turn in order to travel through high-certainty, safe terrain.

Although Morphin is myopic and has no notion of a goal position, it complements a global path planner with the following advantages:

  • It requires little computational power, and can operate at high resolution and high frequency.
  • It does not make any assumptions about the robot having holonomic motion or omni-directional sensing.


Last modified: $Date: 1999/06/28 18:04:27 $