|
|
|
Overview
|
|
- 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.
|
|
Simulator
|
|
This animation shows the mars autonomy software working with
a simulated Fidorover.
[
QuickTime Streaming 11.2 M]
|
|
Framed Quadtrees
|
Framed Quadtree D*
Click for a full-size image
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.
- 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.
Details:
- 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:
- 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*.
Details:
- 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 $
|
