Mars Autonomy Project Path Planning

Mars Autonomy
Technology
	Obstacle Avoidance
	Path Planning
	Integration
	Perception
Publications
Movies
People
Contact us
Related Sites
Internal

Overview
A rover navigating between observation points on the surface of Mars encounters two types of uncertainty: Its environment will be unknown or partially-known. If any data is available, it is likely to be at a coarse resolution (e.g., from descent imagery or orbital flyby). Its position on the surface will be known only approximately (e.g., from star tracking or terrain landmarks) given the absence of GPS. Nonetheless, the rover must reach its goal. Presently, we use the D* algorithm to plan paths to the goal in an unknown or partially-known environment.
The D* Algorithm
D* starts with a map containing all known, assumed, and estimated mobility cost data for the environment. The map is an eight-connected two-dimensional grid. Using this map, an initial path is planned from the rover's starting location to the goal. As the robot drives the path, its sensors discover discrepancies between the initial map and environment. The map is updated, and the rover's path is replanned from its current location to the goal. This process repeats until the rover reaches the goal or discovers that it cannot. The D* algorithm is a dynamic version of the A* algorithm. For large environments, it can replan paths many times faster than A*. See also Path Planning Publications.
Dealing with Positional Uncertainty
The D* algorithm assumes that the rover's position is known. If the position is unknown, two problems result: D* does not know what part of the map to update. D* does not know the starting location for planning a path. In this program, we have extended D* to address this problem. Instead of using a flat map structure, D* uses a network of local terrain maps (LTMs). Every time the rover takes an image of its terrain, the data is stored in a new LTM. Each LTM holds mobility data for a local region around the rover at the time the data was collected. LTMs are connected to each other via sets of geometric transformations. Deadreckoning and landmark matching constrain the possible transformations. For example, assume the rover collects range data at two locations, separated by five meters. Two LTMs are created, LTM1 and LTM2. The transformation from LTM1 to LTM2 is bounded by the deadreckoning drift as the robot drives the five meters. Additionally, it is further constrained by the region of overlap between the two LTMs. When a new LTM is created, it is added to the network and connected to the other LTMs, as constrained by deadreckoning and landmark matching. This addition to the network constitutes a change to the map for D*, and a new path is planned from the current location to the goal. The paths both cross the cells in a given LTM and "hop" between LTMs. Each time a path "hops", it implicitly selects a possible transformation between the LTMs. Since the transformation links are assigned a cost of zero, the planner finds the optimistic path to the goal, that is, the lowest-cost path to the goal assuming all positioning error is favorable to the rover. The planner is complete in the sense that it will deliver the rover to the goal to within the deadreckoning error accrued during the traverse (worst case), assuming a path to the goal exists.
A Sample Run
Figure 1 Click for full-size image Figure 2 Click for full-size image	Figures 1 and 2 show the planner in action. Figure 1 shows a path planning environment. The starting location is the middle of the left wall, and the goal location is the middle of the right wall. The blue regions are large, known obstacles, likely to be seen from space or during a descent. The yellow regions are small, unknown obstacles, to be seen by the rover during its traverse. The traverse taken by the rover is shown in Figure 2. The rover has a radial field of view sensor. As it detects the yellow obstacles, it paints them blue. The green line shows the actual location of the rover during the traverse. The white line shows its assumed location, given its optimistic assumptions. Note that the two lines diverge initially, due to the dead reckoning error (set at 5% of distance travelled). As the rover approaches the large, known obstacle, it gets a global fix on its location, and the two lines become coincident. Thereafter, the lines diverge again as the rover heads to the goal. The rover misses the goal by the amount of the accrued dead reckoning error. A movie showing intermediate stages of D* progress on this run is also available. [QuickTime 348K]
Future Work
Future work includes employing better positioning constraints and providing guarantees against getting lost.

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