Mars Autonomy Project Movies

Mars Autonomy
    Obstacle Avoidance
Path Planning
Contact us
Related Sites
Simulator Movie Frame


  • Rover Movies show various kinds of data collected during a run on the Bullwinkle rover in outdoor terrain and in a mars yard on the CMU campus.

  • Simulator Movies show runs using a simulated FIDO rover.


Rover Movies
About the runs:
  • May 00: Run at 20 cm/sec at the FRC marsyard. [QuickTime Streaming 15.1MB].

  • May 00: Run at 30 cm/sec at the FRC marsyard. [QuickTime Streaming 7.6MB ].

  • Aug 99 The vehicle was tethered for this run (the tether only carried debugging information back to our laptop). The rover
    • Runs into a cul-de-sac and explores it thoroughly until it finds a way around.
    • Moves up to an overgrown hill and eventually discovers the one clear path over the hill.
    • Reaches the goal, which is just past the hill.

    [QuickTime 40 K]. Shows the process of filling in the empty map of the global path planner as new sensor data becomes available during run 1. In the map, black represents unknown or clear area, blue indicates obstacles, and green indicates difficult areas (usually around obstacles). The red X at the right is the goal, and the rover's path is also shown in red.

  • Aug 99: The same start and goal positions, this time untethered. The sequence of events is roughly the same, but this time the rover fails to find the path over the hill and instead goes around it to the right, zig-zagging through the vegetation.

    Path Planner Map Growth [QuickTime 34 K]. Same information as for the above. The later parts of the run are missing from the movie.



This animation shows the mars autonomy software working with a simulated Fidorover.
[ QuickTime Streaming 11.2 M]
Framed Quadtrees

Framed Quadtree D*
Framed Quadtree D*
Click for a full-size image

Regular D*
Regular D*
Click for a full-size image

These movies show the performance advantage of Framed Quadtree D* over regular D*. Framed quadtree D* replaces the grid of regular D* with a quadtree, a data structure which hierarchically breaks down a 2D map, devoting more map cells to areas which have higher complexity. It plans a path through a large quadtree cell by discretizing the edge of the cell into a frame and selecting two points of the frame to travel between.

Framed quadtree D* has three principal advantages over normal D*:

  • Its map requires less memory for unknown terrain and simple areas like large open fields.
  • It saves time by planning the path through a large cell in one step.
  • Regular D* on an 8-connected grid tends to choose paths that line up along the connections (at integer multiples of 45 degrees). Framed quadtree D* will favor paths with more optimal slope.


The last advantage above is the one emphasized by the following movies (which show a 3D view of the rover in simulation) and the images above. In the images, the green curve is the path followed by the rover, and yellow and red areas represent increasingly impassable terrain discovered during the traverse. Notice the more direct path chosen by Framed Quadtree D*.

The movies:

D* versus A*
There are two pairs of simulator movies comparing D* and A*. For more information about D* visit our Path Planning page.

  1. The first pair of movies are meant to highlight the utility of using D* search over the standard A* graph search for path planning. D* and A* always return the same plan when presented with the same information, but since D* requires significantly less computation, it can run more often and revise its plan based on more recent information.

    These movies directly compare D* and A*. The terrain, start, and goal positions remain the same. You can observe D* making smooth curving trajectories, nicely skirting the obstacles. By the time A* takes an obstacle into account the rover is almost on top of it, and will more likely be forced to waste time turning in place in order to move around it.


    • Hardware/OS: Sparc 20, 96 MB RAM, Solaris
    • Other processes: Other system modules ran on another machine, so system load was light.
    • World size: 60 x 60 meter map with a grid cell resolution of 0.25 meters.
    • Speed: Simulator time was running at about 1/3 the rate of wall-clock time, with a rover speed 15 cm/s in the simulator.
    • Update frequency: D*, ~ 1 Hz; A*, ~ 0.25 Hz

    The movies:

  2. The second pair runs D* at full speed against a version that has been purposefully slowed down so that it only sends an update every fourth time one is generated. Again, the terrain, start, and goal positions are the same. Notice that D* run intermittently shows behavior similar to that of A*.


    • Hardware/OS: SGI Octane, 64 MB RAM, IRIX 6.2
    • Other processes: The entire system was on one machine; heavy load.
    • World size: 60 x 60 meter map with a grid cell resolution of 0.25 meters.
    • Speed: Simulator time was running at about 1/3 the rate of wall-clock time, with a rover speed 15 cm/s in the simulator.
    • Update frequency: D* Always, ~ 1 Hz; D* Intermittent, ~ 0.25 Hz

    The movies:


Last modified: $Date: 1999/07/19 22:59:38 $