Mission-Directed Path Planning for Planetary Rover Exploration

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 soph

MISSION-DIRECTED PATH PLANNING FOR

PLANETARY ROVER EXPLORATION

Paul Tompkins

CMU-RI-TR-05-20

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

Thesis Committee:

William “Red” Whittaker, Chair

Jeff Schneider

Anthony Stentz

Richard Volpe, NASA Jet Propulsion Laboratory

© Paul Tompkins, 2005

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 soph

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 soph

Abstract

Robotic rovers uniquely benefit planetary exploration - they enable regional exploration with the precision of in-situmeasurements, a combination impossible from an orbiting spacecraft or fixed lander. Current rover mission planningactivities utilize sophisticated software for activity planning and scheduling, but simplified path planning and execu-tion approaches tailored for localized operations to individual targets. Routes are coarsely hand-selected by humanoperators and executed by the rover’s local obstacle detection and avoidance software. Neither route selection nornavigation 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 regionalaccess; the effect of route timing on resource availability; the limitations of finite resource capacity and other opera-tional constraints on vehicle range and timing; and the mutual influence between traverses and upstream and down-stream stationary activities. Encapsulating this reasoning in an efficient autonomous planner would allow a rover tocontinue operating rationally despite significant deviations from an initial plan.

This research presents mission-directed path planning that enables an autonomous, strategic reasoning capability forrobotic explorers. Planning operates in a space of position, time and energy. Unlike previous hierarchicalapproaches, it treats these dimensions simultaneously to enable globally-optimal solutions. The approach calls on anew incremental search algorithm designed for planning and re-planning under global constraints, in spaces of higherthan two dimensions. Solutions under this method specify routes that avoid terrain obstacles, optimize the collectionand use of rechargable energy, satisfy local and global mission constraints, and account for the time and energy ofinterleaved mission activities. Furthermore, the approach efficiently re-plans in response to updates in vehicle stateand 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 plane-tary-relevant field experiments demonstrate the power of mission-directed path planning in directing actual explora-tion robots. Offline mission-directed planning sustained a solar-powered rover in a 24-hour sun-synchronoustraverse. Online planning and re-planning enabled full navigational autonomy of over 1 kilometer, and supported theexecution of science activities distributed over hundreds of meters.

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 soph

Acknowledgements

In the pursuit of this research, I have been fortunate to associate with so many intelligent, motivating and helpful indi-viduals. I begin by thanking my advisor, Red Whittaker. He inspired me early to pursue the grandest of dreams, andpushed me to work harder than I ever had. I reflect proudly on our time interacting with scientists, engineers andentrepreneurs to elevate and enable concepts for robotic lunar polar exploration. I maintain hope that one day we willsucceed 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. Ourpartnership on the Advanced Global Path Planning project allowed me to mix with the space robotics community likeI never had before. For his support of TEMPEST as leader of three successful robot developments and field cam-paigns, my warmest thanks also goes to David Wettergreen. Dave’s competent yet easygoing leadership style andincredible diversity of knowledge in robotics and field work inspires me for my own career. Tony’s and Dave’sincredible energy fuels my belief that it is possible to succeed with career, family and friends simultaneously.

I could not have tested my work under relevant conditions without my fellow teammates on the Sun-SynchronousNavigation project and the Life in the Atacama project, including Vijay Baskaran, Bernardine Dias, Stu Heys, DomJonak, Ben Shamah, Trey Smith, Jim Teza, Chris Urmson, Vandi Verma, Dan Villa, Mike Wagner and Chris Will-iams. Their enormous effort and skill led to the creation of Hyperion and Zoe, two robots uniquely qualified to testlong-distance, solar powered exploration strategies. Their friendships moulded field experiments into some of themost fun experiences of my life.

I thank my colleagues on the Advanced Mars Global Path Planning project, including Bernardine Dias for helping tointegrate TEMPEST into the NASA CLARAty software repository, Ayorkor Mills-Tettey for her dedicated assistancein 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, TomBrooks, Bill Brose, Bob Coblentz, Jason DiChicchis, Shawn Klimek, Dave Micklo, Bill Molczan, and MariannMondik. Together we shared unforgettable experiences in some very cold, high places, and built friendships that willlast forever. Their pull to get me away from research and into the wild places on this planet kept me sane through allmy years at Carnegie Mellon.

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 soph

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 otherthrough the hard times over the months of thesis writing, and spent all our free moments plotting a way to live andwork 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 andlove for me I could not have achieved this dream. I love you both.

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 soph

v

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 soph

Table of Contents

ABSTRACT...................................................................................................................................... IIACKNOWLEDGEMENTS.................................................................................................................. IIITABLE OF CONTENTS.................................................................................................................... VILIST OF FIGURES............................................................................................................................ XLIST OF TABLES........................................................................................................................... XIVCHAPTER 1: INTRODUCTION............................................................................................................ 1

1.1Planetary Rover Navigational Autonomy ....................................................................................................1

1.1.1Mars Pathfinder: Sojourner Rover ....................................................................................................1

1.1.2Mars Exploration Rovers: Spirit and Opportunity ............................................................................3

1.1.3Experimental State of the Art: CLEaR .............................................................................................5

Future Rover Scenarios ................................................................................................................................6

1.2.1Mars Exploration ...............................................................................................................................7

1.2.2Lunar Polar Circumnavigation ..........................................................................................................8

Mission-Directed Path Planning ..................................................................................................................9

1.3.1Over-the-Horizon Foresight ..............................................................................................................9

1.3.2Temporal Cognizance .....................................................................................................................10

1.3.3Resource Cognizance ......................................................................................................................10

1.3.4Uncertainty Robustness ...................................................................................................................10

1.3.5Mission Directedness ......................................................................................................................11

Thesis Statement ........................................................................................................................................12

Assumptions ...............................................................................................................................................12Dissertation Roadmap ................................................................................................................................121.21.31.41.51.6

CHAPTER 2: RELATED WORK........................................................................................................ 15

2.1Deterministic Path Planning ......................................................................................................................15

2.1.1Cell Decomposition .........................................................................................................................15

2.1.2Roadmap Approaches .....................................................................................................................16

2.1.3Potential Fields ................................................................................................................................17

Randomized Path Planning ........................................................................................................................17

2.2.1Rapidly Exploring Random Trees ...................................................................................................17

Temporal Path Planning .............................................................................................................................17

Resource Path Planning .............................................................................................................................19

Path Planning in Unknown Environments .................................................................................................19

Path Planning Under Global Constraints ...................................................................................................20

Applied Path Planning: Natural Terrain ....................................................................................................21

2.7.1Local Path Planning ........................................................................................................................21

2.7.2Global Path Planning ......................................................................................................................24

Planning and Scheduling ...........................................................................................................................27

2.8.1Contingency Planning .....................................................................................................................282.22.32.42.52.62.72.8

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 soph

TABLE OF CONTENTS2.9Summary ...................................................................................................................................................29CHAPTER 3: INCREMENTAL SEARCH............................................................................................. 31

3.1States, Transitions and Cost ......................................................................................................................32

3.1.1Independent and Dependent State Parameters ...............................................................................32

3.1.2State Transitions .............................................................................................................................32

3.1.3Local Constraints ............................................................................................................................33

3.1.4Global Constraints ..........................................................................................................................33

3.1.5Resource Parameters ......................................................................................................................34

3.1.6Path Cost .........................................................................................................................................37

3.1.7Non-Monotonic Path Cost ..............................................................................................................38

3.2Efficiency Mechanisms .............................................................................................................................40

3.2.1Dynamic State Generation ..............................................................................................................40

3.2.2Resolution Equivalence ..................................................................................................................40

3.2.3State Dominance .............................................................................................................................41

3.3Search ........................................................................................................................................................42

3.3.1Modes and Search Termination ......................................................................................................43

3.3.2Path Extraction ...............................................................................................................................43

3.4Experimental Results .................................................................................................................................44

3.4.1Test Domain ...................................................................................................................................44

3.4.2Comparison of Two Solution Approaches .....................................................................................44

3.4.3 Scaling With Map Size or Start-Goal Separation ..........................................................................47

3.4.4Scaling With Resolution .................................................................................................................48

3.4.5Scaling with Branching Factor .......................................................................................................49

3.4.6Re-Planning Performance ...............................................................................................................50

3.4.7Scaling With Solution Approach ....................................................................................................51

3.4.8Qualitative Comparison of Approaches .........................................................................................52CHAPTER 4: MISSION-DIRECTED PATH PLANNING....................................................................... 59

4.1Problem Definition ....................................................................................................................................59

4.1.1Terrain Interaction and Obstacle Avoidance ..................................................................................59

4.1.2Temporal Planning .........................................................................................................................61

4.1.3Resource Planning ..........................................................................................................................62

4.1.4Coupling of Variables .....................................................................................................................63

TEMPEST .................................................................................................................................................64

4.2.1World Model ..................................................................................................................................65

4.2.2Rover Model ...................................................................................................................................68

4.2.3Constraint Set .................................................................................................................................69

4.2.4Action Set .......................................................................................................................................71

4.2.5Mission Specification Set ...............................................................................................................73

4.2.6Incremental Search Engine .............................................................................................................74

Algorithm ..................................................................................................................................................75

4.3.1Definitions ......................................................................................................................................76

4.3.2Single-Goal Planning ......................................................................................................................77

4.3.3Single-Goal Re-Planning ................................................................................................................80

4.3.4Sequential Goal Planning ...............................................................................................................82

4.3.5Sequential Goal Re-Planning .........................................................................................................84

4.3.6Time-Bounded Sequential Goal Planning ......................................................................................87

Plans ..........................................................................................................................................................90

Plan Evaluation .........................................................................................................................................91

4.5.1Distance ..........................................................................................................................................91

4.5.2Time ................................................................................................................................................944.24.34.44.5

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 soph

MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION4.6Simulation Results .....................................................................................................................................94

4.6.1Re-Planning .....................................................................................................................................94

4.7Discussion ..................................................................................................................................................98CHAPTER 5: SUN-SYNCHRONOUS NAVIGATION.......................................................................... 101

5.1

5.2

5.3The Polar Navigation Problem ................................................................................................................102Navigation Strategy .................................................................................................................................103Field Experiment ......................................................................................................................................104

5.3.1Devon Island .................................................................................................................................105

5.3.2Hyperion Rover .............................................................................................................................105

5.3.3Software Architecture ...................................................................................................................106

5.3.4Planning Problem ..........................................................................................................................107Planning Approach ..................................................................................................................................108Experiment 1 Results ...............................................................................................................................110

5.5.1Planning ........................................................................................................................................110

5.5.2Execution ......................................................................................................................................117Experiment 2 Results ...............................................................................................................................118

5.6.1Planning ........................................................................................................................................119

5.6.2Execution ......................................................................................................................................122Discussion ................................................................................................................................................1245.45.55.65.7

CHAPTER 6: ROBOTIC ASTROBIOLOGY....................................................................................... 127

6.1

6.2

6.3

6.4Life in the Atacama ..................................................................................................................................127Navigational Autonomy for Science ........................................................................................................128Atacama Desert ........................................................................................................................................128Field Experiment 2003 .............................................................................................................................129

6.4.1Objectives ......................................................................................................................................129

6.4.2Hyperion Rover .............................................................................................................................130

6.4.3Software Architecture ...................................................................................................................130

6.4.4Sequence of Operations ................................................................................................................131

6.4.5Planning Approach ........................................................................................................................132Results 2003 .............................................................................................................................................133

6.5.1Path Length ...................................................................................................................................133

6.5.2Large-Scale Terrain Avoidance ....................................................................................................134

6.5.3Energy Efficiency .........................................................................................................................135

6.5.4Plan Monitoring and Re-Planning .................................................................................................136

6.5.5Plan Stability .................................................................................................................................137Field Experiment 2004 .............................................................................................................................140

6.6.1Objectives ......................................................................................................................................140

6.6.2Zoe Rover ......................................................................................................................................140

6.6.3Software Architecture ...................................................................................................................142

6.6.4Planning Approach ........................................................................................................................143Results 2004 .............................................................................................................................................145

6.7.1Planning ........................................................................................................................................146

6.7.2Execution ......................................................................................................................................149Discussion ................................................................................................................................................1496.56.66.76.8

CHAPTER 7: CONCLUSION........................................................................................................... 151

7.1

7.2

7.3Contributions ...........................................................................................................................................152Perspectives .............................................................................................................................................153Future Work .............................................................................................................................................155

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 soph

TABLE OF CONTENTSREFERENCES................................................................................................................................ 157APPENDIX 1: ISE ALGORITHM ....................................................................................................161APPENDIX 2: PROGRESS DISTANCE .............................................................................................171GLOSSARY OF TERMS.................................................................................................................. 175

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 soph

List of Figures

Figure 1-1:

Figure 1-2:The Entire Pathfinder/Sojourner Mission Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2Spirit Traverse Route, Sol 1 to Sol 160. MER demonstrates the scientific interest in regional explo-

ration. These distances might be traversed in a fraction of the time spent by Spirit, using greater lev-

els of navigational autonomy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Future Mars missions will require rovers to access increasingly difficult terrain. . . . . . . . . . . . . . 7

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 antici-

pate terrain hazards, power availability, thermal transitions and areas of sunlight and shadow for sci-

ence.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

An example of terrain classification and arc evaluation from the CMU Mars Autonomy software by

Singh et al. [59] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

A screen shot from the ASPEN scheduler. Rover activities are shown as ticks in the middle rows.

The colored bars represent mission-relevant parameters, for example solar array current, sun eleva-

tion, and surface temperature, over the course of one Mars sol. . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Plots of Duration, a Monotonic Resource Parameter, Over an ISE Search. The solid curve depicts a

path that satisfies the global duration constraint, the dashed curve shows a duration profile that ex-

ceeds the maximum duration before reaching the start. Steeper slopes indicate slower progress to

the goal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Computer Memory, a Non-Monotonic Resource Parameter, Over an ISE Search. The three curves

depict different outcomes of the search: a path that requires more than the maximum available mem-

ory (Rejected path 1), a path that exceeds the memory available at the start (Rejected path 2), and a

path that meets both the maximum and initial memory requirements (Legal path).. . . . . . . . . . . 36

Approach 2 (3-D BESTPCOST) Performance for Initial Planning Time vs. Map Size and Time

DPARMS Resolution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Time for Four and Eight Connected State Spaces for Approach 2 (BESTPCOST).. . . . . . . . . . . 50

Ratio of Re-Plan Time to Initial Plan Time for Approach 2 (3-D BESTPCOST). Re-planning shows

one to two orders of magnitude improvement on speed over initial planning. . . . . . . . . . . . . . . . 51

Comparison of Approach 1 and Approach 2 Time Performance. . . . . . . . . . . . . . . . . . . . . . . . . . 52

Qualitative Comparison of Planned Routes and Energy Profiles between BESTPCOST Mode (a and

b) with BESTDPARMS Mode (c and d) with Tmax=TBESTPCOST . . . . . . . . . . . . . . . . . . . . . 54

Qualitative Comparison of Planned Route, Energy Profile and Progress Distance between BESTD-

PARMS Mode with Tmax=2TBESTPCOST (a through c) and Tmax=3TBESTPCOST (d through f)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56

Coupling Between Terrain, Time, Resources and Mission Return . . . . . . . . . . . . . . . . . . . . . . . . 63

Principal TEMPEST Components. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

Example LOS map for sunlight on natural terrain, in this case a system of canyons exposed to the

sun from the direction of the top of the image. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

ISE Domain Definition through TEMPEST Models. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74Figure 1-3:Figure 1-4:Figure 2-1:Figure 2-2:Figure 3-1:Figure 3-2:Figure 3-3:Figure 3-4:Figure 3-5:Figure 3-6:Figure 3-7:Figure 3-8:Figure 4-1:Figure 4-2:Figure 4-3:Figure 4-4:

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 soph

LIST OF FIGURESFigure 4-5:

Figure 4-6:Single-Goal Planning Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77Single-Goal Planning. a) Goal time interval definition; b) Reachable and allowable space; c) Goal

states and start query; d) Progression of search from goal states; e) Completion of search; f) Optimal

plan. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

The Sequential Goal Planning Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

Sequential Goal Planning. a) Final goal time interval definition; b) Previous segment goal time in-

terval definitions; c) Segment goal states and start queries; d) Planning in last segment and genera-

tion of goal states for previous segment; e) Completion of planning; f) Optimal plan . . . . . . . . . 85

Initialization for Time-Bounded Sequential Goal Planning: a) Originally-specified reachable and al-

lowable time limits; b) Earlier goal-imposed allowable time limit; c) Goal time interval definitions;

d) Final segment goal states and query start states. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

Representation Factor for Regular Four and Eight-Connected Grids . . . . . . . . . . . . . . . . . . . . . . 92

Obstacle Avoidance with fA=1 (solid) and fA>1 (dashed) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

Initial Plan Route: TEMPEST plans a path from “Start” at the southeast of the map, to Goal 1 in the

valley in the center of the map, and then through the saddle point to Goal 2 in the northwest. . . 95

First Significant Re-Plan Route: The robot discovers a much steeper approach to the saddle point at

the end of the valley after visiting Goal 1, prompting a detour through an opening to the valley to the

northeast. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Progress Distance vs. Time: The initial plan (shown in red) follows a very direct path (compare to

the straight-line maximum speed curve). The re-plan detour (shown in blue) requires the rover to

endure a night in hibernation, as shown by the flat region indicating no forward progress. In the

morning of the following day, the rover resumes its course to Goal 2.. . . . . . . . . . . . . . . . . . . . . 97

Battery Energy Requirement vs. Time: The initial plan enables the rover to start from total battery

discharge to reach to the goal charge level. The detour from the re-plan requires the rover to perform

stationary charging to nearly full capacity in anticipation of the nighttime hibernation. Note the sim-

ilarity between the re-plan profile in the morning after hibernation and the original plan profile. 98

Hyperion Rover: Sun-synchronous navigation enabled solar powered travel over kilometers without

the added complication and mass of a gimbal mechanism. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

Lunar Sun Elevation Angle Variations for Polar and Sub-Polar Positions. At mid-summer at a pole

(a), the sun remains above the horizon at a roughly constant angle. Below the arctic circle, the sun

elevation oscillates between a maximum elevation (b) above the horizon and a minimum elevation

(c) below the horizon.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

Idealized Sun-Synchronous Navigation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

Hyperion Autonomy Software Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

Experiment 1 Route and Elevation Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

Experiment 1 Results: a) Progress Distance; b) Required Minimum Battery Energy. . . . . . . . . 114

The Experiment 1 plan shows how TEMPEST achieved an optimal energy path under terrain and

solar array constraints. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

Experiment 1 Planned and Executed Solar Array Sun Angles. . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Experiment 1 Executed Progress Distance: Execution followed the plan very closely. . . . . . . . 117

Experiment 1 Battery Voltage: Data indicates that the batteries did not show signs of extreme dis-

charge. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118Figure 4-7:Figure 4-8:Figure 4-9:Figure 4-10:Figure 4-11:Figure 4-12:Figure 4-13:Figure 4-14:Figure 4-15:Figure 5-1:Figure 5-2:Figure 5-3:Figure 5-4:Figure 5-5:Figure 5-6:Figure 5-7:Figure 5-8:Figure 5-9:Figure 5-10:

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 soph

MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATIONFigure 5-11:Experiment 2 Route and Elevation Map: The route starts and ends at the point marked ‘Return To

Start’, and traversed a nominal distance of 8.4 km, including a circumnavigation around the terrain

feature known informally as Marine Peak at the West end of the route.. . . . . . . . . . . . . . . . . . . 120

Experiment 2 Results vs. Time: a) Progress Distance; b) Minimum Required Battery Energy . 121

Experiment 2 Executed Progress Distance: the most substantial delay put Hyperion behind the plan

by several hours, causing significant battery discharge. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

Experiment 2 Battery Voltages: evidence strongly suggests that falling behind the TEMPEST sched-

ule, which resulted in poor sun angles, caused the substantial battery discharge during the mission.

123

Hyperion in its LITA Configuration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

LITA 2003 Autonomy Software Architecture. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

Plans and executed paths. TEMPEST plans assigned the location of periodic goal regions. Goal re-

gions gave the Local Navigator flexibility in selecting the specific path between waypoints.. . 131

Avoidance Factor and Representation Factor for LITA 2003: The points suggest that avoidance was

often dominant in determining path length.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

Plan and re-plan routes from April 25 on an elevation contour map, and a close-up with contours of

constant slope. The initial plans seem to have located a break in steeper slopes.. . . . . . . . . . . . 135

TEMPEST placed Hyperion very close to a hazardous slope on April 18. Map registration errors or

position uncertainty may have been to blame.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

Rover Average Speed vs. Re-Plan Frequency. Operational delays often caused the HM to trigger re-

planning. The solid lines in a) show average rover speed over a Drive action. The dashed lines are

the average rover speed over the particular plan or re-plan execution. Speeds below the TEMPEST

rover model speed (plans 2, 5, 7) caused re-plan events, shown in b). Blank regions in plot b) are

human-designated suspensions of operation to enact manual fault recovery.. . . . . . . . . . . . . . . 136

Route Stability: Most routes became more stable, as measured by progress to the upper left of the

plot, with decreasing distance to the goal.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

Arrival Time Stability: Changes in arrival time in re-plans correlate well with deviations from the

previous plan during execution.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

Zoe Rover. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

LITA 2004 Autonomy Software Architecture. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

LITA October 18 2004 Route and Terrain Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

LITA October 18 2004: a) Progress Distance; b) Minimum Required Battery Energy . . . . . . . 148

Plots of Progress Distance for a Hypothetical Plan. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .172Figure 5-12:Figure 5-13:Figure 5-14:Figure 6-1:Figure 6-2:Figure 6-3:Figure 6-4:Figure 6-5:Figure 6-6:Figure 6-7:Figure 6-8:Figure 6-9:Figure 6-10:Figure 6-11:Figure 6-12:Figure 6-13:Figure A2-1:

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 soph

LIST OF FIGURES

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 soph

List of Tables

Table 3-1:

Table 4-1:

Table 4-2:

Table 4-3:

Table 4-4:

Table 4-5:

Table 4-6:

Table 4-7:

Table 4-8:

Table 4-9:

Table 5-1:

Table 5-2:

Table 5-3:

Table 6-1:

Table 6-2:

Table 6-3:

Table A1-1:

Table A1-2:

Table A1-3:

Table A1-4:

Table A1-5:

Table A1-6:Summary of Experiment Approaches Using ISE Modes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Data Required to Define a TEMPEST Action. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71Drive Action Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72Solar Charge Action Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73Informal Definitions of Symbols and Functions Used in the TEMPEST Algorithm Description 76INIT_SEGMENT(S,G) Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78PLAN_SINGLE_GOAL(S,G) Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79INIT_SEGMENTS(S,G,k) Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83PLAN_SEQ_GOALS(S,G) Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86INIT_TB_SEGMENTS(S,G,k) Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88Sun-Synchronous Navigation Planning Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108Summary of Experiment 1 Plan and Execution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111Summary of Experiment 2 Plan and Execution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119LITA 2003 Planning Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132LITA 2004 Planning Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145Summary of October 18 Plan and Execution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146Application-Specific ISE Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162Application-Generic ISE Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163BESTPCOST Mode Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164BESTDPARMS Mode Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165EXPAND_NEXT_STATE Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166DOM_INSERT_STATE Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

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 soph

LIST OF TABLES

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 soph

1.Introduction

Robotic rovers have been demonstrated as effective tools for planetary surface exploration on the moon [23] and onMars [43]. As a result of early success with the Pathfinder and Mars Exploration Rover missions, NASA has pro-jected follow-on Mars rover missions with increasing technological and scientific ambition. In the course of theirdevelopment, these programs will lay the foundation for robotic technology that will enable access to a far greaterrange of locations on Mars and other bodies in the Solar System. One of the most exciting research thrusts is thedevelopment of robot navigational autonomy. Path planning and execution components allow a robot to select andnavigate paths across planetary landscapes without human assistance. This thesis contends that to serve future mis-sions, 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 iscognizant of mission parameters and enables far more difficult surface operations than were previously possible.

1.1Planetary Rover Navigational Autonomy

What will be demanded of rover navigational autonomy in future missions? Before creating a vision for future navi-gational autonomy, it is useful to assess the approaches taken in the most recent rover missions - the Mars Pathfindermission and the combined Mars Exploration Rover missions - as well as a state-of-the-art research system. Overthese three examples, note the clear disparity between the growing sophistication of automated stationary activityplanning, and navigation planning, which continues to be restricted to obstacle avoidance.

1.1.1Mars Pathfinder: Sojourner Rover

Sojourner made the first steps toward rover navigational autonomy on another planet [43]. Sojourner relied heavilyon 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 Sojournerto estimate safe routes of travel - routes that minimized the traversal of rock obstacles and avoided regions that pre-

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 soph

INTRODUCTIONvented direct line-of-sight between Sojourner and the Pathfinder lander (and hence prevent communications and poseestimation via stereo vision). Operators selected waypoints along these safe paths, at intervals of 1-2 meters, as inter-mediate goals for autonomous navigation.

Using cameras and laser stripers, Sojourner executed “Go To Waypoint” commands by periodically assessing the dif-ficulty of terrain ahead of the rover, and performing scripted avoidance maneuvers to circumnavigate obstacles. Therover avoided pursuing unreachable goals by abiding by a timeout clock that prevented travel after a set number ofhours. Sojourner managed its resources during execution - it measured solar array current as a means of determiningwhether sufficient power was available for various activities. It also periodically checked its communications linkwith 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 activi-ties. Using this general approach, Sojourner covered more than 100 meters, all within 12 meters of the Pathfinderlander (see Figure 1-1), over 83 sols.

Figure 1-1: The Entire Pathfinder/Sojourner Mission Path

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 soph

MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATIONSummary 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 way-

points.

Traverse activities were largely isolated from other focussed rover activities (e.g. science measurements), allow-ing waypoint selection and activity sequencing to occur mostly independently.

Terrain, time, resources and communications remained a consideration in deciding the next course of action dur-ing traverse execution.

Simple terrain sensing and scripted obstacle avoidance behaviors, combined with human operators’ strong a pri-ori 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 fromtravelling well beyond the landing site.

1.1.2Mars 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 landingsites. The MER rovers produce their own stereo imagery, both from hazard cameras (mounted at fixed angles on therover) and the Pancam instrument (mounted on a mast pan/tilt mechanism). As with Sojourner, MER operators use agraphical user interface to assess the terrain around the rover, and hand-select waypoints that avoid hazardous terrainon the way to long-distance goals. Distant goals are selected using imagery collected from orbit. During the Martianwinter months, when the sun was lowest on the horizon, rover operators were also forced to find paths and loiterpoints that maximized the solar array’s exposure to sunlight. Travel favored sun-facing slopes, and slopes facingaway 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 astraight path between waypoints without visual sensing, or in “autonomous navigation” mode that enables autono-mous closed-loop driving. In a conservative strategy, blind mode driving is favored for the portion of a traverse near-est the rover where a priori stereo data is most reliable, and autonomous navigation mode is used to safeguard therover from hazards where a priori data is least reliable.

Earth-based MER planning incorporates substantial autonomy. The MAPGEN system [2] combines a plan editingsystem called APGEN and automated reasoning derived from the EUROPA constraint-based planner [28]. Thoughplans remain largely hand-edited, EUROPA enables active constraint enforcement during the edit process, completespartial plans and repairs plans that violate constraints or resources, and provides operators with explanations for whycertain edits are illegal.

本文来源：https://www.bwwdw.com/article/tvbi.html