«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
Thermal control will be another issue influenced by exposure to the sun. A nuclear powered rover, exposed to the waste heat from inefficient thermoelectric cycles, might be prone to overheating. In that case, a rover might adopt a motion strategy that occasionally seeks shadow to avert thermal buildup. If staying warm is the dominant thermal challenge, staying in sunlight could save power that would otherwise go toward heating rover electronics.
1.2.2 Lunar Polar Circumnavigation The moon's South Pole Aitken Basin is a probable target for future rovers. Orbital missions over the past several years indicate a high probability of water ice trapped in permanently shadowed regions of the lunar poles, and hence present a strong scientific motivation for surface exploration (e.g. ). During summer months at the pole, the sun rises no higher than 1.5°, and from the point of view of an observer there would appear to skim over the complete horizon in the course of the moon's 29.5-day lunar month . A combination of axial tilt and orbital eccentricity cause the Earth to inscribe a tilted elliptical path in the sky that rises to 6.7° above the horizon at its high point and falls to 6.7° below the horizon roughly two weeks later. The low sun and Earth elevation angles, combined with the South Pole’s rough terrain, are cause for widespread and highly varied sun and communications shadowing. Shadow patterns change continually with the moon's rotation and progress of the Earth/moon system about the sun.
A rover in this challenging environment could not survive without a path planner whose solutions maximize sun exposure and communications while satisfying operational constraints. Planning could discover paths that follow the course of sunlit regions to enable solar power and avoid extended exposure to the cold of lunar night. Such paths could also follow regions with direct line-of-sight to the Earth and relay spacecraft to allow high-rate imagery, teleoperated control and continual science data return. Mission objectives might force the planner to deviate from these zones of relative safety. Entering a region of permanent dark to look for signs of water ice would force the rover to abandon sunlight and to enter low-lying areas where communications might be occluded by surrounding terrain. A
1. Nuclear generators suffer from several disadvantages - launch approval for nuclear devices is extremely difficult, and generators are only made in a few different sizes which may be poorly matched to rover capabilities and demands.
mission planner would aid in timing this foray to maximize science data collection and rover contact while maintaining an adequate battery state-of-charge and maximizing the chance of survival.
Figure 1-4: The Lunar North Pole. Future exploration missions may investigate permanently shadowed craters in search of water ice deposits. Such operations would require detailed traverse planning to anticipate terrain hazards, power availability, thermal transitions and areas of sunlight and shadow for science.
1.3 Mission-Directed Path Planning
As part of a broad effort towards planetary rover autonomy, this research introduces a new ideal for path-based reasoning based on the following five desirable attributes:
1.3.1 Over-the-Horizon Foresight A critical task in achieving rover autonomy is automatic route planning between a landing site and operations sites.
To date, path planning research for planetary rovers has focused on the problem of navigating locally through fields of rock obstacles en route to a global position goal, over tens of meters. In upcoming missions, long-distance and long-duration path planning will enable robots to travel between landing sites and operations sites. To target specific locations for scientific study, a robot must be able to traverse at least the size of the landing error ellipse, which could be tens of kilometers. To complement local path planning strategies, tailored for travel amongst rocks at or below the scale of the rover, path planning must utilize regional map data generated from orbit or during descent. Regional data will enable a rover to anticipate opportunities and hazards and to incorporate these predictions into path selection.
Large scale and duration introduce factors absent in local path planning, including navigation around and through large-scale terrain, significant changes in line-of-sight geometry, and time-varying lighting stemming from planetary motion. Long treks anticipated for future missions will demand that rover planning consider these issues.
1.3.2 Temporal Cognizance Time is as important to path planning as it is to mission activity planning. Planetary motion defines the gross schedule for daylight, solar flux and opportunities for communications downlinks to Earth. A planner that considers the paths of the sun, Earth and orbiting relay spacecraft, and determines whether they are shadowed or visible at specific times will be better able to select routes that provide sufficient energy or enable communications at different times of day. A path planner must also ensure that paths obey time-dependent operational constraints. As examples, a science activity may only be successful under particular time-dependent lighting or thermal conditions; communications passes often require both geometric visibility and ground antenna availability. A path planner that operates in a mission context must use time efficiently and effectively, and tailor its paths to respect the operational constraints on other activities.
1.3.3 Resource Cognizance Resource management is essential to rover self-sufficiency. Resources take many forms, from metric resources like battery energy and onboard memory, to unit resources like cameras, whose usage state is Boolean. The favored approach for rover resource management is through AI planning and scheduling (see  ). This approach proves effective in situations where path or orbit selection and resource management are independent. In surface vehicle operations, a tighter coupling of path and resource considerations offers distinct advantages over the traditional approach. Many resource expenses and gains for rovers are path-dependent and cannot be adequately considered outside a path planner. In the case of energy management, these include locomotion energy as a function of terrain and solar energy as a function of position, orientation and time. A rover must consider the effects of path choices on energy balance to determine which paths are feasible or optimal.
1.3.4 Uncertainty Robustness It is essential that a rover planner be robust to uncertainty. Knowledge of the area of operations will be limited. Environment and rover models will be purposely coarse to ease the computational burden of considering long-distance and long duration paths. Rover behavior will be impossible to predict accurately. A robot that cannot adapt to unexpected events will, at best, be unable to operate for long durations because plans quickly become invalid, and at worst, may execute inappropriate or dangerous actions that could result in mission failure. At minimum, a robot should be able to perform quick re-planning when its state strays outside acceptable bounds of an earlier plan, or in response to new information about itself, the environment or goals. However, by anticipating the effects of uncer
tainty sources on the cost of future actions, a robot can select plans that avoid hazardous situations with sufficient, but not overly conservative margins.
1.3.5 Mission Directedness Robot software should be designed to maximize the chances of achieving mission objectives. A path planner must balance a number of competing mission pressures, for example to maximize science data return, to maintain adequate battery levels, or to remain safe, all of which impact the mission outcome. A path planner with mission focus must represent all relevant activities - navigation, science, power generation to name a few - in a consistent framework.
Navigation affects the timing of science activities, and could enable or prevent opportunities for battery charging.
The location, timing and resource requirements for science activities impact navigation and may determine whether batteries require dedicated charge time. By reasoning about all significant activities, at the appropriate level of granularity, a path planner can correctly integrate route selection, timing, and energy management into a cohesive mission profile.
In considering operations over long distance and duration, it might be inappropriate to select a typical path metric such as distance or energy to evaluate plans, or alternatively, to select an arbitrary weighting to define the balance between several desired metrics. If the value of mission objectives is encoded in terms of reward, then the appropriate balance between these factors is achieved by maximizing the expected reward over the path. Suddenly, a single framework promotes the correct strategy in every situation. If a higher reward specifies the shortest path, the planner will seek it. If low batteries threaten rover survival, the planner will develop a course of action to charge to adequate levels as it proceeds to the goals. Finally, a rover planner would benefit from an ability to balance reward against risk. The expected return from a mission does not take into account the variance of reward. Avoiding undue risk may entail taking a route for which expected reward is lower, but for which the chances of failure are lower. A robot that can evaluate risk, and balance it against potential rewards could adjust its behavior according to mission preferences.
In combination, the above five attributes define an ideal for rover navigational autonomy - mission-directed path planning. Mission-directed path planning will enable a rover to autonomously achieve mission objectives, enforce operational constraints, and combat the effects of uncertainty under a single framework, and optimize plans in terms of probability of mission success. This thesis has developed an initial capability for mission-directed path planning
embodying elements of each characteristic:
Over-the-Horizon Foresight: This research develops models and planning approaches that consider large-scale terrain, and execution approaches that integrate naturally with local navigation planners.
INTRODUCTIONTemporal Cognizance: This research enables planning in an absolute time frame, and develops models and planning approaches that consider time-varying sunlight and solar power and absolute operational constraints.
Resource Cognizance: This research presents two approaches to optimizing path selection in terms of renewable stored energy.
Uncertainty Robustness: The research presents a strategy for fast re-planning in response to updates in vehicle state and localized changes in models of the environment.
Mission Directedness: This research integrates planning for navigation, temporal path planning, path-based resource management and satisfaction of constraints on mission activities.
1.4 Thesis Statement This thesis asserts 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.
1.5 Assumptions Planning will occur at a spatial resolution at which the size of the vehicle and vehicle steering radii are insignificant.
Planning will consider scales and vehicle speeds at which dynamics are insignificant.
Planning will not solve the general planning and scheduling problem.
This research will not consider adversarial domains.
The research will use only deterministic models for planning.
Multi-goal planning will not solve or approximate solutions to the Traveling Salesman Problem.
The research will only consider optimal or resolution-optimal planning approaches.
1.6 Dissertation Roadmap Having introduced the concepts of mission-directed path planning and established the assertions of this research, the
remaining chapters answer the following questions:
• What techniques currently exist, and how do they fall short in solving this class of problems?
• What approach does this research take?
• How does the approach perform in laboratory examples?
• Is the technique useful in real-world problems?
Chapter 2 is an overview of current planning techniques relevant to path planning considering time, resources and constraints.
The work in this thesis relies heavily on incremental search strategies. Chapter 3 describes a previously-developed approach to incremental search, upon which this thesis builds.
Chapter 4 is the heart of the thesis. It further motivates and develops the ideas of mission-directed path planning, and introduces the approach that is the foundation of this work. The TEMPEST planner, one of the research contributions, is a representative mission-directed path planner. The second half of Chapter 4 presents experiments done in simulation that demonstrate the utility of TEMPEST and mission-directed path planning in general on space-relevant problems.
The highlights of this research are the demonstrations of TEMPEST in support of solar-powered robots in highly space-relevant terrestrial field trials. Chapter 5 illustrates how TEMPEST solved for plans that enabled two 24-hour, multi-kilometer traverses exhibiting a new large scale motion strategy for polar exploration called Sun-Synchronous Navigation. In a second field experiment, described in Chapter 6, TEMPEST generated plans to interleave long-distance routes with science activities for two solar-powered robots in support of robotic astrobiology.
Chapter 7 discusses the findings of this research, presents its principal contributions, and suggests several avenues of future research.
2. Related Work The goal of this chapter is to prove the need for this work and its novelty relative to past approaches. The following sections examine past accomplishments in the fields of path planning and classical planning and scheduling and point out their shortcomings in the context of mission-level path planning.