«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
6.7 Results 2004 An experiment toward the end of the 2004 field season illustrated mission-directed path planning in support of integrated science measurement and navigation. The Mission Specification required Zoe to perform Panorama actions (collect a full panorama image sequence) and Workspace Acquire actions (collect workspace camera images) at each of four goal locations, entailing a traverse of 2.74 km in map distance that terminated in a narrow valley. Figure 6-12
ROBOTIC ASTROBIOLOGYshows the terrain map and the initially-planned route for the traverse, which starts at the right of the map and progresses uphill into a canyon between two peaks. Table 6-3 summarizes the planning results.
6.7.1 Planning In examining the distance and time factors in Table 6-3, one observes that increases in plan distance above the minimum were isolated to the eight-connected grid representation. The route diagram in Figure 6-12 confirms this graphically - the route follows horizontal, diagonals and vertical moves on the map grid rather than taking a direct path between goal positions. However, this is not to say that representation was at fault for increasing the distance. It seems apparent that TEMPEST used the degrees of freedom in the eight-connected path to avoid hazardous terrain (as illustrated in Figure 4-11). The final segment follows a path that avoids high slope areas by strategically alternating between diagonal and horizontal Drive actions. In many cases, the straight-line path between goals would have been inappropriate.
Figure 6-13 depicts the plan progress distance and minimum energy profile for the initial plan. The stair-stepping behavior of time-bounded sequential goal planning is plain in the distance plot. The plan allocates time for each goal to accommodate the Panorama and Workspace Acquire actions. The left dashed line in the distance plot is again the line of fastest possible approach under a speed of 1 m/s. The right dashed line is the line of slowest allowable approach to the goal, which for these runs was a factor 20 slower than the maximum speed. The intention is to provide ample time to allow for selecting circuitous routes or to insert Solar Charge actions. This scenario required neither, as reflected in the avoidance factor and loiter factor. The distance plot shows steady progress between each goal at a slightly lower slope than the line of fastest approach, reflecting the extra distance due to eight-connected travel.
Unfortunately, this plan does not demonstrate the End Of Day goal mechanism - the End Of Day time bounds were
set to open at the time of the start time of the plan, and close just before sundown.
Looking at the energy plot, the plan satisfies the initial condition of 200 W-hr and reaches the final goal energy requirement of 50 W-hr. TEMPEST models predicted no trouble in achieving the plan from a power perspective.
The plan predicts that the rover could start with an empty battery and could remain fully discharged along the first two segments and still reach the goal target energy. It does predict a small, non-zero requirement at the start of the fourth segment. The plan terminates by rising to the target final goal energy.
6.7.2 Execution Global map registration was an unanticipated difficulty with the October 18 experiment. Prior to the experiment, the field team collected many GPS-derived ground control points that would allow cartographers at the US Geological Survey to associate absolutely-referenced positions with specific locations in unregistered elevation data collected from space1. Using those control points, the USGS provided the team with the map of the terrain that was intended to be referenced absolutely to Earth coordinates. A globally-referenced map would have allowed the team to initialize the rover state estimator with a correct map position using GPS. However, in initial tests, the team discovered that GPS measurements converted to map coordinates indicated substantial map registration errors (hundreds of meters in translation, and unknown errors in rotation). Matching GPS measurements of landmarks to salient elevation features in the map, the team attempted to better register the map to the Earth with translation. Closer examination of the translated map seems to indicate the attempted corrections were also in error.
Through the first three segments of the mission, Zoe exhibited reasonable navigational behavior. However, during the final segment, in attempting to enter the canyon area, Zoe attempted to follow a path that was farther south of the canyon opening than was suggested in the plan. Its course took it to the base of the large hill depicted in Figure 6-12, where it struggled to find traversable terrain on steep slopes through a network of water drainages. The preliminary judgment is that map registration errors prevented Zoe from entering the canyon at the correct point.Unfortunately, with mis-registered maps, the GPS “ground truth” from Zoe is of ambiguous value. It provides Zoe’s absolute position on Earth, but does not yield Zoe’s true path through the terrain model.
6.8 Discussion These experiments highlight a number of important distinctions from experiments conducted in the Arctic. First, the mid-latitude environment presents a different set of challenges to mission-directed path planning. In polar summer, the sun never sets, but its low elevation angle does not favor a rover with a horizontal solar array. At mid-latitude, the sun rises and sets, but enables a rover to travel confidently during the day, under solar power, with a solar panel that is horizontally mounted and unarticulated. Daytime energy management in a polar environment demands a mechanical or navigational strategy, whereas daytime energy management at mid-latitude is not as much a significant challenge.
From the perspective of demonstrating persistent operations on a planet, the two experiments were quite different.
Arctic experiments demonstrated operations over 24 hours; Atacama experiments started well after dawn, occasionally extended until dusk, but never continued at night. Consequently, the LITA experimental planning and execution results presented here do not present the energy management challenges that might have arisen in enabling 24-hour operations.
1. Elevation data derived from imagery from the ASTER instrument aboard the Terra spacecraft.
ROBOTIC ASTROBIOLOGYTEMPEST’s performance in LITA experiments demonstrated several new strengths above what was shown in the
Terrain Avoidance: TEMPEST planned paths that avoided high terrain slopes. In a planetary setting, with a priori data, a robot using TEMPEST could anticipate large-scale terrain from “over the horizon” and take measures to avoid slope hazards from a distance. Current path planners for planetary exploration cannot consider terrain beyond their sensor horizon.
Integrated Science, Energy Management and Navigation: In the LITA 2004 experiment, TEMPEST coordinated mission and navigation activities effectively. It integrated naturally with other software modules - the Goal Manager, and the Rover Executive - to create plans that achieved the navigation goals of the mission and accommodated the requirements of science activities.
Effective Online Re-Planning: TEMPEST re-planning enabled far greater navigational autonomy than is possible by planning once in advance. A rover that can adapt its plans to unanticipated changes will be able to continue operating effectively without human intervention. In response to requests from plan monitoring modules, TEMPEST replanned in fractions of the time required for initial planning. Re-planning periods rarely caused the rovers to halt for more than a fraction of a second.
The LITA experiments also uncovered challenges for future mission-directed path planning research:
Mission Re-Scoping: TEMPEST could not alter the scope of a mission in response to evolving state and environmental conditions. If operational delays are too significant, TEMPEST may not be able to find a feasible plan that meets time constraints. Conversely, if operations go more quickly than anticipated, TEMPEST cannot add more goals to the mission plan to take advantage of the situation. Deviations from expected behavior in position state and energy state can cause similar problems.
No Planning for Uncertainty: The Atacama again stressed the need to consider uncertainty in planning. Experiments in 2003 suggest map registration was responsible for a near disaster with Hyperion (see Section 6.5.2). Map registration in 2004 caused Zoe to struggle with navigation into a canyon. Also, time uncertainty was a problem.
TEMPEST models only consider the nominal rover behavior. TEMPEST cannot anticipate the effects of operational delays, as often happen in the course of experiments, and more importantly, in planetary operations.
7. Conclusion This thesis concludes that mission-directed path planning achieves a significant, practical advance in planetary rover autonomy, and enables a new, challenging class of planetary surface rover missions.
The research is significant because it extends path planning beyond local obstacle avoidance to time, resources and mission objectives and constraints - issues recognized by the space mission planning community to be of critical importance. Judging from MER, future missions will also seek to investigate regionally distributed targets, and may baseline years of operation. The greater ambition for autonomous regional exploration will require a commensurate sophistication in navigation and activity planning. Mission-directed path planning could automate path selection for regional exploration. With less manual planning to be done, missions would require far fewer operations staff and be correspondingly far cheaper. Greater robot autonomy would also reduce the frequency of decisions that require human intervention, resulting in less wasted time and greater return for each operational day. This research supports the ambition for cheaper, more efficient surface exploration.
This research demonstrates a practical solution to mission-directed path planning. TEMPEST derives plans that exhibit sensible navigation behaviors under complex interactions between terrain, time, resources and constraints.
The approach combines models of the world, rover, relevant actions and constraints imposed on them, and mission objectives. Incremental search enables efficient search for optimal paths over three or more dimensions, and under global constraints. It offers efficient re-planning mechanisms to repair plans in response to unexpected state excursions and measurements of the local environment. Operating on the Hyperion and Zoe robots, TEMPEST operated efficiently and effectively in conjunction with automated local navigators, science planners and executives. In planning traverses of several hundred meters several hours in duration, TEMPEST spent on the order of ten minutes. Frequent re-plans thereafter caused only minor, and often imperceptible delays in progress.
Mission-level path planning enables a new class of planetary surface missions. Experiments demonstrate its utility in a number of specific scenarios: missions with overnight hibernation contingencies; polar exploration under sun-synchronous navigation; and missions that conduct widely distributed sampling to characterize regional variations.
More generally, this new approach best addresses missions that operate in highly-variable, complex lighting and power, and missions that regularly interleave focussed stationary activities and extensive traverses. Chapter 1 introduces two planetary mission scenarios for which mission-directed path planning would certainly be an enabling technology.
Time, resources and mission objectives must factor into route selection to support the global needs of the mission.
Without reasoning about these factors, planners must make conservative assumptions about legal operating ranges to guarantee a vehicle’s safety. Imposing broad limits on operations can severely restrict the productivity of a robot.
Occasionally, the conservatism required to guarantee rover safety disallows all operations. Deeper reasoning, through mission-directed path planning, allows a rover to take advantage of time and resource opportunities if they exist, and enables a measured level of protection against hazardous conditions when they arise.
7.1 Contributions This research develops the most comprehensive global planner for planetary rovers to date.
Prior planetary mission planning has sought to optimize paths to avoid obstacles over traverses on the order of 100 meters. This new work achieves multi-kilometer planning, temporal and resource planning and interleaving of traverse and mission activities.
This research creates the first planner to optimize path selection for a non-monotonic resource.
The planning developed here incorporates resource collection as well as consumption to solve problems that are infeasible without recharge or refueling. Other path planners rely on monotonic resource models that cannot represent recharging. Non-monotonic resources, like battery energy, fuel or onboard memory, are commonplace in space, military, transportation and many other applications.
The research solves path planning in spatial, temporal and resource bounds using a non-hierarchical, resolution-optimal method.
The non-hierarchical approach developed in this research enables coupling between the spatial, temporal and resource state variables and solves for globally-optimal plans. Other path planners are sub-optimal or incomplete
because they commit to a spatial path in one operation and then select a velocity or power profile to avoid time-varying obstacles and meet other constraints.
The thesis extends planetary rover path planning into the realm of more general mission planning.