«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
MISSION-DIRECTED PATH PLANNING FOR
PLANETARY ROVER EXPLORATION
The Robotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213
May 13, 2005
Submitted in partial fulfillment of
the requirements for the degree of
Doctor of Philosophy
William “Red” Whittaker, Chair
Richard Volpe, NASA Jet Propulsion Laboratory © Paul Tompkins, 2005 Abstract Robotic rovers uniquely benefit planetary exploration - they enable regional exploration with the precision of in-situ measurements, a combination impossible from an orbiting spacecraft or fixed lander. Current rover mission planning activities utilize sophisticated software for activity planning and scheduling, but simplified path planning and execution approaches tailored for localized operations to individual targets. Routes are coarsely hand-selected by human operators and executed by the rover’s local obstacle detection and avoidance software. Neither route selection nor navigation deeply considers high level mission goals, large scale terrain, time, resources or operational constraints.
This strategy is insufficient for the investigation of multiple, regionally distributed targets in a single command cycle.
Path planning tailored for this task must consider the impact of large scale terrain on power, speed and regional access; the effect of route timing on resource availability; the limitations of finite resource capacity and other operational constraints on vehicle range and timing; and the mutual influence between traverses and upstream and downstream stationary activities. Encapsulating this reasoning in an efficient autonomous planner would allow a rover to continue operating rationally despite significant deviations from an initial plan.
This research presents mission-directed path planning that enables an autonomous, strategic reasoning capability for robotic explorers. Planning operates in a space of position, time and energy. Unlike previous hierarchical approaches, it treats these dimensions simultaneously to enable globally-optimal solutions. The approach calls on a new incremental search algorithm designed for planning and re-planning under global constraints, in spaces of higher than two dimensions. Solutions under this method specify routes that avoid terrain obstacles, optimize the collection and use of rechargable energy, satisfy local and global mission constraints, and account for the time and energy of interleaved mission activities. Furthermore, the approach efficiently re-plans in response to updates in vehicle state and world models, and is well suited to online operation aboard a robot.
Simulations exhibit that the new methodology succeeds where conventional path planners would fail. Three planetary-relevant field experiments demonstrate the power of mission-directed path planning in directing actual exploration robots. Offline mission-directed planning sustained a solar-powered rover in a 24-hour sun-synchronous traverse. Online planning and re-planning enabled full navigational autonomy of over 1 kilometer, and supported the execution of science activities distributed over hundreds of meters.
In the pursuit of this research, I have been fortunate to associate with so many intelligent, motivating and helpful individuals. I begin by thanking my advisor, Red Whittaker. He inspired me early to pursue the grandest of dreams, and pushed me to work harder than I ever had. I reflect proudly on our time interacting with scientists, engineers and entrepreneurs to elevate and enable concepts for robotic lunar polar exploration. I maintain hope that one day we will succeed together in operating a robot on the Moon.
I would also like to thank Tony Stentz. His technical mentorship inspired the work I present in this document. Our partnership on the Advanced Global Path Planning project allowed me to mix with the space robotics community like I never had before. His incredible energy fuels my belief that it is possible to succeed with career, family and friends simultaneously.
For his support of TEMPEST as leader of three successful robot developments and field campaigns, my warmest thanks also goes to David Wettergreen. Dave’s competent yet easygoing leadership style and incredible diversity of knowledge in robotics and field work inspires me for my own career.
I could not have tested my work under relevant conditions without my fellow teammates on the Sun-Synchronous Navigation project and the Life in the Atacama project, including Vijay Baskaran, Bernardine Dias, Stu Heys, Dom Jonak, Ben Shamah, Trey Smith, Jim Teza, Chris Urmson, Vandi Verma, Dan Villa, Mike Wagner and Chris Williams. Their enormous effort and skill led to the creation of Hyperion and Zoe, two robots uniquely qualified to test long-distance, solar powered exploration strategies. Their friendships moulded field experiments into some of the most fun experiences of my life.
I thank my colleagues on the Advanced Mars Global Path Planning project, including Bernardine Dias for helping to integrate TEMPEST into the NASA CLARAty software repository, Ayorkor Mills-Tettey for her dedicated assistance in testing ISE, and Marc Zinck for creating an outstanding planning visualization tool.
I also want to thank my mountaineering friends in the Explorers Club of Pittsburgh, including Aaron Bennett, Tom Brooks, Bill Brose, Bob Coblentz, Jason DiChicchis, Shawn Klimek, Dave Micklo, Bill Molczan, and Mariann Mondik. Together we shared unforgettable experiences in some very cold, high places, and built friendships that will last forever. Their pull to get me away from research and into the wild places on this planet kept me sane through all my years at Carnegie Mellon.
MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATIONThis thesis would not have been possible without the love of my companion, Vandi Verma. We helped each other through the hard times over the months of thesis writing, and spent all our free moments plotting a way to live and work in the same city together. Now our theses are done, and every bit of planning for the future has paid off.
This thesis is dedicated to my parents, Mimi and David Tompkins, without whose unending confidence, support and love for me I could not have achieved this dream. I love you both.
TABLE OF CONTENTS
LIST OF FIGURES
LIST OF TABLES
CHAPTER 1: INTRODUCTION
1.1 Planetary Rover Navigational Autonomy
1.1.1 Mars Pathfinder: Sojourner Rover
1.1.2 Mars Exploration Rovers: Spirit and Opportunity
1.1.3 Experimental State of the Art: CLEaR
1.2 Future Rover Scenarios
1.2.1 Mars Exploration
1.2.2 Lunar Polar Circumnavigation
1.3 Mission-Directed Path Planning
1.3.1 Over-the-Horizon Foresight
1.3.2 Temporal Cognizance
1.3.3 Resource Cognizance
1.3.4 Uncertainty Robustness
1.3.5 Mission Directedness
1.4 Thesis Statement
1.6 Dissertation Roadmap
CHAPTER 2: RELATED WORK
2.1 Deterministic Path Planning
2.1.1 Cell Decomposition
2.1.2 Roadmap Approaches
2.1.3 Potential Fields
2.2 Randomized Path Planning
2.2.1 Rapidly Exploring Random Trees
2.3 Temporal Path Planning
2.4 Resource Path Planning
2.5 Path Planning in Unknown Environments
2.6 Path Planning Under Global Constraints
2.7 Applied Path Planning: Natural Terrain
2.7.1 Local Path Planning
2.7.2 Global Path Planning
2.8 Planning and Scheduling
2.8.1 Contingency Planning
CHAPTER 3: INCREMENTAL SEARCH
3.1 States, Transitions and Cost
3.1.1 Independent and Dependent State Parameters
3.1.2 State Transitions
3.1.3 Local Constraints
3.1.4 Global Constraints
3.1.5 Resource Parameters
3.1.6 Path Cost
3.1.7 Non-Monotonic Path Cost
3.2 Efficiency Mechanisms
3.2.1 Dynamic State Generation
3.2.2 Resolution Equivalence
3.2.3 State Dominance
3.3.1 Modes and Search Termination
3.3.2 Path Extraction
3.4 Experimental Results
3.4.1 Test Domain
3.4.2 Comparison of Two Solution Approaches
3.4.3 Scaling With Map Size or Start-Goal Separation
3.4.4 Scaling With Resolution
3.4.5 Scaling with Branching Factor
3.4.6 Re-Planning Performance
3.4.7 Scaling With Solution Approach
3.4.8 Qualitative Comparison of Approaches
CHAPTER 4: MISSION-DIRECTED PATH PLANNING
4.1 Problem Definition
4.1.1 Terrain Interaction and Obstacle Avoidance
4.1.2 Temporal Planning
4.1.3 Resource Planning
4.1.4 Coupling of Variables
4.2.1 World Model
4.2.2 Rover Model
4.2.3 Constraint Set
4.2.4 Action Set
4.2.5 Mission Specification Set
4.2.6 Incremental Search Engine
4.3.2 Single-Goal Planning
4.3.3 Single-Goal Re-Planning
4.3.4 Sequential Goal Planning
4.3.5 Sequential Goal Re-Planning
4.3.6 Time-Bounded Sequential Goal Planning
4.5 Plan Evaluation
MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION
4.6 Simulation Results
CHAPTER 5: SUN-SYNCHRONOUS NAVIGATION
5.1 The Polar Navigation Problem
5.2 Navigation Strategy
5.3 Field Experiment
5.3.1 Devon Island
5.3.2 Hyperion Rover
5.3.3 Software Architecture
5.3.4 Planning Problem
5.4 Planning Approach
5.5 Experiment 1 Results
5.6 Experiment 2 Results
CHAPTER 6: ROBOTIC ASTROBIOLOGY
6.1 Life in the Atacama
6.2 Navigational Autonomy for Science
6.3 Atacama Desert
6.4 Field Experiment 2003
6.4.2 Hyperion Rover
6.4.3 Software Architecture
6.4.4 Sequence of Operations
6.4.5 Planning Approach
6.5 Results 2003
6.5.1 Path Length
6.5.2 Large-Scale Terrain Avoidance
6.5.3 Energy Efficiency
6.5.4 Plan Monitoring and Re-Planning
6.5.5 Plan Stability
6.6 Field Experiment 2004
6.6.2 Zoe Rover
6.6.3 Software Architecture
6.6.4 Planning Approach
6.7 Results 2004
CHAPTER 7: CONCLUSION
7.3 Future Work
APPENDIX 1: ISE ALGORITHM
APPENDIX 2: PROGRESS DISTANCE
GLOSSARY OF TERMS
ix List of Figures
1. Introduction Robotic rovers have been demonstrated as effective tools for planetary surface exploration on the moon  and on Mars . As a result of early success with the Pathfinder and Mars Exploration Rover missions, NASA has projected follow-on Mars rover missions with increasing technological and scientific ambition. In the course of their development, these programs will lay the foundation for robotic technology that will enable access to a far greater range of locations on Mars and other bodies in the Solar System. One of the most exciting research thrusts is the development of robot navigational autonomy. Path planning and execution components allow a robot to select and navigate paths across planetary landscapes without human assistance. This thesis contends that to serve future missions, the scope of automated reasoning for navigation must include mission relevant parameters like time, resources, constraints and mission objectives. This research achieves significant advances in autonomous navigation that is cognizant of mission parameters and enables far more difficult surface operations than were previously possible.
1.1 Planetary Rover Navigational Autonomy What will be demanded of rover navigational autonomy in future missions? Before creating a vision for future navigational autonomy, it is useful to assess the approaches taken in the most recent rover missions - the Mars Pathfinder mission and the combined Mars Exploration Rover missions - as well as a state-of-the-art research system. Over these three examples, note the clear disparity between the growing sophistication of automated stationary activity planning, and navigation planning, which continues to be restricted to obstacle avoidance.
1.1.1 Mars Pathfinder: Sojourner Rover Sojourner made the first steps toward rover navigational autonomy on another planet . Sojourner relied heavily on both the Pathfinder lander and a team of Earth-based engineers and scientists to enable travel to places of interest.
The Pathfinder lander produced stereo imagery used to generate three-dimensional models of the landing site terrain.
Human operators used a graphical user interface that combined the terrain model and a kinematic model of Sojourner to estimate safe routes of travel - routes that minimized the traversal of rock obstacles and avoided regions that pre
vented direct line-of-sight between Sojourner and the Pathfinder lander (and hence prevent communications and pose estimation via stereo vision). Operators selected waypoints along these safe paths, at intervals of 1-2 meters, as intermediate goals for autonomous navigation.