WWW.BOOK.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Books, abstracts, thesis
 
<< HOME
CONTACTS

Pages:   || 2 | 3 | 4 | 5 |   ...   | 26 |

«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»

-- [ Page 1 ] --

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

iiAcknowledgements

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.

iii

MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION

This 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.

–  –  –

Abstract

ACKNOWLEDGEMENTS

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.5 Assumptions

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

–  –  –

2.9 Summary

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 Search

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 TEMPEST

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 Algorithm

4.3.1 Definitions

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.4 Plans

4.5 Plan Evaluation

4.5.1 Distance

4.5.2 Time

vii

MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION

4.6 Simulation Results

4.6.1 Re-Planning

4.7 Discussion

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.5.1 Planning

5.5.2 Execution

5.6 Experiment 2 Results

5.6.1 Planning

5.6.2 Execution

5.7 Discussion

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.1 Objectives

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.1 Objectives

6.6.2 Zoe Rover

6.6.3 Software Architecture

6.6.4 Planning Approach

6.7 Results 2004

6.7.1 Planning

6.7.2 Execution

6.8 Discussion

CHAPTER 7: CONCLUSION

7.1 Contributions

7.2 Perspectives

7.3 Future Work

–  –  –

REFERENCES

APPENDIX 1: ISE ALGORITHM

APPENDIX 2: PROGRESS DISTANCE

GLOSSARY OF TERMS

ix List of Figures

–  –  –

xv

1. Introduction Robotic rovers have been demonstrated as effective tools for planetary surface exploration on the moon [23] and on Mars [43]. 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 [43]. 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

<

INTRODUCTION

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.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 26 |


Similar works:

«DIPLOMARBEIT „Der Umgang mit Fremden im europäischen Detektivroman des XX. Jahrhunderts, analysiert an Beispielen Agatha Christies und Georges Simenons.“ Verfasser Vanja Eichberger angestrebter akademischer Grad Magister der Philosophie (Mag. phil.) Wien, 2013 Studienkennzahl lt. A 393 Studienblatt: Studienrichtung lt. Diplomstudium Vergleichende Literaturwissenschaft Studienblatt: Mag. Dr. Sandra Vlasta Betreuerin: INHALTSVERZEICHNIS 1. Einleitung 4 1.1. Themenwahl 4 1.1.1. Hercule Poirot...»

«Studia Lingüistica Germanica Herausgegeben von Stefan Sonderegger Walter de Gruyter • Berlin • New York Elisabeth Leiss Die Verbalkategorien des Deutschen Ein Beitrag zur Theorie der sprachlichen Kategorisierung Walter de Gruyter • Berlin • New York UniversitaxsBibüothek I ; ^ ^ J f N Q. / 1/ ( München 1 J •^ Als Habilitationsschrift auf Empfehlung der Philosophischen Fakultät II der Universität Erlangen-Nürnberg gedruckt mit Unterstützung der Deutschen Forschungsgemeinschaft...»

«PROCEEDINGS OF T H E F I F T H INTERNATIONAL CONGRESS OF MATHEMATICIANS CAMBRIDGE UNIVERSITY PRESS ftoifton : FETTER LANE, E.C. C. F. CLAY, MANAGER ŒbfatoltSÎ): ioo, PRINCES STREET Berlin: A. ASHER AND CO. &eqrçtg: F. A. BROCKHAUS $efo goffe : G. P. PUTNAM'S SONS Bombag mis Calcutta: MACMILLAN AND CO., L T D. All lights reserved PROCEEDINGS OF THE FIFTH INTERNATIONAL CONGRESS OF MATHEMATICIANS (Cambridge, 22—28 August 1912) EDITED BY THE GENERAL SECRETARIES OF THE CONGRESS E. W. HOBSON...»

«TEACHING ENGLISH AS A SECOND OR FOREIGN LANGUAGE TO ADULTS IN QATAR: EXPLORING GENDER DIFFERENCES IN LANGUAGE ACQUISTION by RIANA ROUSSEAU submitted in accordance with the requirements for the degree of DOCTOR OF PHILOSOPHY WITH SPECIALISATION IN ADULT EDUCATION at the UNIVERSITY OF SOUTH AFRICA SUPERVISOR: PROF E.R. MATHIPA APRIL 2014 Acknowledgements My sincere thanks and appreciation are due to Prof E.R. Mathipa for selecting me, and under whose supervision, this research was conducted. His...»

«The pragmatics of monologue: interaction in video blogs Dissertation zur Erlangung des akademischen Grades eines Doktors der Philosophie der Philosophischen Fakultäten der Universität des Saarlandes vorgelegt von Maximiliane Frobenius aus Freiburg im Breisgau Saarbrücken, 2014 Dekan: Professor Dr. Roland Marti Berichterstatter: Professor Dr. Neal R. Norrick Professor Dr. Elke Teich Professor Dr. Wolfram Bublitz Professor Dr. Christoph Schubert Tag der letzten Prüfungsleistung: 11.02.2014...»

«Clustering Categorical Data Using Data Summaries and Spectral Techniques By Eman Abdu A dissertation submitted to the Graduate Faculty in Computer Science in partial fulfillment of the requirements for the degree of Doctor of Philosophy, The City University of New York ©2009 Eman Abdu All Rights Reserved ii This manuscript has been read and accepted for the Graduate Faculty in Computer Science in satisfaction of the dissertation requirement for the degree of Doctor of Philosophy. _ _ Date...»

«Diplomarbeit Titel der Diplomarbeit „240 Tage Sodom – Sade, Pasolini und die Verwertung des Individuums in der Moderne“ Verfasser Lukas Johne Angestrebter akademischer Grad Magister der Philosophie (Mag. phil.) Wien, September 2011 A – 296 Studienkennzahl lt. Studienblatt: Diplomarbeitsgebiet lt. Studienblatt: Philosophie Univ.-Doz. DDr. Mădălina Diaconu Betreuerin: But inside doesn’t matter.whatever. There are no more barriers to cross. All I have in common with the uncontrollable...»

«DIPLOMARBEIT Titel der Diplomarbeit „na wos ge / ge wos na“ Die Konkrete Dichtung und Dialektdichtung der Wiener Gruppe aus sprachwissenschaftlicher Sicht Verfasserin Verena Maria Weigl angestrebter akademischer Grad Magistra der Philosophie (Mag.a phil.) Wien, 2010 Studienkennzahl lt. Studienblatt: A 332 Studienrichtung lt. Studienblatt: Diplomstudium Deutsche Philologie Betreuer: Ao. Univ.-Prof. Mag. Dr. Franz Patocka II Danksagung Zuallererst möchte ich meinen Eltern großen Dank für...»

«Wittgenstein and the Future of Philosophy Wittgenstein und die Zukunft der Philosophie A Reassessment after 50 Years Eine Neubewertung nach 50 Jahren Beiträge der Österreichischen Ludwig Wittgenstein Gesellschaft Contributions of the Austrian Ludwig Wittgenstein Society Editorial Board Elisabeth Leinfellner Rudolf Haller Werner Leinfellner Klaus Puhl Paul Weingartner Volume IX (1) Band IX (1) Wittgenstein und die Zukunft der Philosophie Eine Neubewertung nach 50 Jahren Beiträge des 24....»

«Ludwig-Maximilians-Universität München Fakultät für Geschichtsund Kunstwissenschaften Before Britannia ruled the Waves Die Konstruktion einer maritimen Nation Inaugural-Dissertation zur Erlangung des Doktorgrades der Philosophie an der Ludwig-Maximilians-Universität München vorgelegt von Torsten Reimer Erstgutachter: Prof. Dr. Winfried Schulze Zweitgutachter: Prof. Dr. Eckhart Hellmuth Tag der mündlichen Prüfung: 13. Juli 2006 Inhaltsverzeichnis Einleitung 1 Fragestellung und...»

«© Copyright 2005 Joseph Tate SHAKESPEARE, PROSE AND VERSE: UNREADABLE FORMS Joseph Tate A dissertation submitted in partial fulfilment of the requirements for the degree of Doctor of Philosophy University of Washington Program Authorized to Offer Degree: Department of English University of Washington Graduate School This is to certify that I have examined this copy of a doctoral dissertation by Joseph Tate and have found that it is complete and satisfactory in all respects, and that any and...»

«DR. WOLFGANG THORWART Dozent für Philosophie und Literatur Goethes Naturund Gottesbegriff Johann Wolfgang Goethes (1749-1832) Lebensspanne fiel größtenteils in die allgemeine Zeitenwende des späten 18. Jahrhunderts, die man heute eine “Sattelzeit” nennt. Es ist die Epoche der Hochaufklärung mit ihrer allgemeinen Aufwertung der menschlichen Fähigkeiten, nachdem man die Menschen im Namen der göttlichen Vernunft ein Jahrtausend zur Verleugnung der menschichen Fähigkeiten gezwungen...»





 
<<  HOME   |    CONTACTS
2016 www.book.xlibx.info - Free e-library - Books, abstracts, thesis

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.