«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
Using cameras and laser stripers, Sojourner executed “Go To Waypoint” commands by periodically assessing the difficulty of terrain ahead of the rover, and performing scripted avoidance maneuvers to circumnavigate obstacles. The rover avoided pursuing unreachable goals by abiding by a timeout clock that prevented travel after a set number of hours. Sojourner managed its resources during execution - it measured solar array current as a means of determining whether sufficient power was available for various activities. It also periodically checked its communications link with the lander, and executed a path reversal contingency action if communications were lost. Sols, or Martian days, were typically devoted to one type of activity - either traverse, or one of many possible science or engineering activities. Using this general approach, Sojourner covered more than 100 meters, all within 12 meters of the Pathfinder lander (see Figure 1-1), over 83 sols.
Summary of Pathfinder Observations:
• Human operators relied on a global model derived from Pathfinder lander stereo imagery for waypoint selection.
• Terrain traversability and communications line-of-sight geometric constraints were critical in selecting waypoints.
• Traverse activities were largely isolated from other focussed rover activities (e.g. science measurements), allowing waypoint selection and activity sequencing to occur mostly independently.
• Terrain, time, resources and communications remained a consideration in deciding the next course of action during traverse execution.
• Simple terrain sensing and scripted obstacle avoidance behaviors, combined with human operators’ strong a priori knowledge of the terrain, enabled Sojourner to navigate confidently immediately around the lander.
Sojourner’s reliance on the lander for obstacle avoidance, state estimation and communications prevented it from travelling well beyond the landing site.
1.1.2 Mars Exploration Rovers: Spirit and Opportunity The Mars Exploration Rover (MER) missions have far surpassed Pathfinder in autonomous operations on a planet.
Spirit and Opportunity are independent of their landing vehicles, allowing them to traverse far from their landing sites. The MER rovers produce their own stereo imagery, both from hazard cameras (mounted at fixed angles on the rover) and the Pancam instrument (mounted on a mast pan/tilt mechanism). As with Sojourner, MER operators use a graphical user interface to assess the terrain around the rover, and hand-select waypoints that avoid hazardous terrain on the way to long-distance goals. Distant goals are selected using imagery collected from orbit. During the Martian winter months, when the sun was lowest on the horizon, rover operators were also forced to find paths and loiter points that maximized the solar array’s exposure to sunlight. Travel favored sun-facing slopes, and slopes facing away from the sun were often removed from consideration.
Human operators must designate the navigation mode of the traverse - either “blind” whereby the rover drives in a straight path between waypoints without visual sensing, or in “autonomous navigation” mode that enables autonomous closed-loop driving. In a conservative strategy, blind mode driving is favored for the portion of a traverse nearest the rover where a priori stereo data is most reliable, and autonomous navigation mode is used to safeguard the rover from hazards where a priori data is least reliable.
Earth-based MER planning incorporates substantial autonomy. The MAPGEN system  combines a plan editing system called APGEN and automated reasoning derived from the EUROPA constraint-based planner . Though plans remain largely hand-edited, EUROPA enables active constraint enforcement during the edit process, completes partial plans and repairs plans that violate constraints or resources, and provides operators with explanations for why certain edits are illegal.
During a traverse in autonomous navigation mode, the MER rovers create three-dimensional maps of the terrain at periodic intervals, and automatically segment the maps into traversability “goodness” levels. The GESTALT algorithm  evaluates the drive arcs available in the next move, and picks the best arc in terms of the goodness traversability index. At the time of publication of this document, Opportunity achieved a maximum autonomous drive segment of 85 meters on Sol 82 (the 82nd Martian day of operations), and Spirit, a segment of 78 meters on its Sol 133 .
Figure 1-2: Spirit Traverse Route, Sol 1 to Sol 160. MER demonstrates the scientific interest in regional exploration. These distances might be traversed in a fraction of the time spent by Spirit, using greater levels of navigational autonomy.
Summary of MER Observations:
• Human operators use orbital imagery and local models derived from rover stereo imagery to manually select waypoints.
• Terrain traversability and sun, solar array and terrain geometry data are used to manually estimate the best path.
• Loosely interleaved traverse and science activities force a greater consideration of activity interaction than for Pathfinder. Activity planning is conducted on Earth, but with elements of autonomy. Traverse segments are inserted into activity plans using distance measurements between waypoints to estimate the duration and energy allocations for mobility segments.
• Spirit and Opportunity achieve waypoint goals autonomously, using local terrain evaluation. However, beyond consideration of the next drive arc, the rovers do not conduct planning to optimize travel to the next waypoint.
The MER missions illustrate the current state-of-art in flight rover operations. As of this writing, Spirit and Opportunity have operated for over three times their baseline lifetime of 90 sols. In 270 sols, they had covered a total of 3641 m and 1664 m, respectively and continue to operate productively. Yet mission planning remains a very labor-intensive activity, requiring extended support from large teams of experts.
1.1.3 Experimental State of the Art: CLEaR High levels of autonomy have been achieved on orbiting spacecraft, as demonstrated by the Deep Space 1 Remote Agent Experiment . However, the surface operations environment is far less predictable and, as described above, has historically required far more human oversight.
Recent Earth-based experiments have demonstrated limited autonomous surface science operations. As an example, Estlin et al. have developed a system for planning and execution of position-distributed science measurements .
The system comprises CASPER, a constraint-based iterative-repair planner , the TDL task-based executive , and a simple global path planner. The system processes are coordinated under the CLEaR framework, which delegates responsibilities between the planner and executive for plan repair in response to new data. Rover experiments on the Rocky 7 and 8 rovers in the JPL Mars Yard demonstrated the system’s ability to devise plans given a set of high-level measurement goals distributed over several locations in rocky terrain. The planner decomposed the highlevel goals into low-level activities, and selected the feasible subset of goals that maximized expected science return and respected resource constraints. In planning motion between measurement sites, CASPER called on the global path planner to estimate the distance of travel. Using models of the rover, CASPER then estimated the duration and energy requirements for the traverse, and integrated the traverse segment as a token in the activity plan.
During plan execution, the CLEaR system repaired plans in response to unanticipated data. The Morphin local navigation system  detected new obstacles that invalidated the original plans by requiring longer traverses between measurements. Measurement activities occasionally took longer to complete than anticipated. In such cases, the CLEaR system coordinated plan repair and removed lower-priority goals that could no longer be accomplished within the allotted time.
Summary of CLEaR Observations:
• Goal selection was performed by human operators and paths between goals were not pre-planned. However, activity planning considered the expected time and energy costs for traverse activities, which was derived from path planning that avoided all known obstacles.
• Traverse and science activities were closely interleaved, preventing an approach that planned them independently. The time and resource allocations of each activity strongly affected the feasibility of the others. Despite this, path planning to estimate the distance between goals was ignorant of mission goals, time, resource limitations and geometric constraints.
• Rocky 7, Rocky 8 and FIDO achieved the goal positions autonomously like the MER rovers. Rover navigation considered only the local terrain and immediate drive arcs. The eventual paths followed by the rovers had little or no connection to the paths generated to estimate the distance between goals in the planning phase.
The CLEaR example represents a major advance towards rover autonomy for localized operations. The test scenarios enabled automated planning and execution of a number of goals that would have occupied several sols of operations in Pathfinder or MER. For focussed site surveys, a system like CLEaR might enable a far greater collection of science data, and could significantly reduce the number of operational staff needed to oversee daily activities. However, for science operations distributed over greater distances, path planning would have to take a far more prominent role in planning and execution.
In the context of missions conducted at greater scales, with more complex terrain, dynamic lighting and resources that vary spatially and temporally, a plan that purely avoids terrain obstacles might, at best, be inefficient or operationally infeasible and, at worst, might endanger the rover and the mission.
1.2 Future Rover Scenarios Future rover missions will demand far more coordination between activity planning and navigation planning. A greater ambition for distance, and pressure to reduce operations staff, will require navigational autonomy over greater distances - a schedule involving daily long-distance traverses cannot afford the labor of the detailed scrutiny seen in MER. Long distance traverses will intersect a variety of terrains, whose slope and orientation affect locomotion and solar power. Motion with respect to large-scale terrain features may entail driving through sunlight or communications shadows. Missions will take greater advantage of available time, operating from dawn to dusk, and even at night. Diurnal variations will affect power, thermal and sensing systems. Resources will continue to be in short supply. The navigation route, timing and resource profile will inevitably affect the preconditions for downstream activities, and vice versa. Under these projected circumstances, this thesis asserts the need for a new kind of path planning that considers these factors - mission-directed path planning.
The next subsections introduce two mission scenarios that directly motivate mission-directed path planning.
1.2.1 Mars Exploration Mission-directed path planning is initially motivated by the needs of future missions to Mars, like Mobile Science Laboratory , Mars Sample Return, and others. These missions may send highly-capable rovers to Mars for multiyear scientific surveys covering tens of kilometers of terrain. Missions such as these would benefit from reliable, effective rover autonomy, which would ease the planning workload of human operators in support of the missions for years at a time, and which could make intelligent decisions about the use of time and resources in unexpected situations.
Figure 1-3: Future Mars missions will require rovers to access increasingly difficult terrain.
Judging from Mars Pathfinder and the Mars Exploration Rover missions, energy management will continue to be a prime concern for future missions. Solar power remains a technologically simple means of generating power on Mars. A solar powered rover must consider the energy cost of its path of motion and determine how the time of travel affects the orientation of its solar array relative to the sun in the sky. Terrain may cast shadows on the route, particularly at dawn and dusk. At the end of each sol, a rover must recharge its batteries in preparation for survival or limited night operations. A careful evaluation of hibernation sites may allow the rover to find slopes that receive sunlight earlier the following morning, and tip the solar arrays to improve solar power throughout a sol.
Nuclear thermoelectric power generation is gaining favor for rover power. The clear advantage of nuclear power is that it removes the dependence of rover power and heating on sunlight1. Future rover missions may be able to operate at all times of day, virtually doubling the time efficiency of rover missions. Nuclear generators might also enable