FREE ELECTRONIC LIBRARY - Books, abstracts, thesis

Pages:     | 1 |   ...   | 22 | 23 || 25 | 26 |

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

-- [ Page 24 ] --

The plans generated in the approach developed here consider the time and energy expense of mission goals and obey mission constraints. As demonstrated in field experiments in this research, a mission-directed path planner can act as a simple mission planner for a robot. If acting in support of a general mission planner, the planning developed in this research enables much tighter coupling between activities and traverses in a plan. Planetary rover mission planning has historically been the purview of classical artificial intelligence planning and scheduling approaches. They typically insert traverse plans into the mission plan that derive from a path planner that is incapable of reasoning about mission objectives.

The research successfully demonstrates mission-directed planning for solar powered robots in three planetaryrelevant field experiments.

TEMPEST planning guided and sustained the solar powered Hyperion rover on a 6 km, 24-hour long polar sun-synchronous traverse. TEMPEST planning and re-planning enabled Hyperion to achieve several long-distance autonomous traverses in the Atacama Desert, including one over 1 km. TEMPEST created and maintained plans that allowed the Zoe rover to interleave a traverse of several hundred meters with several targeted panoramic and underbelly camera image sequences.

7.2 Perspectives This thesis illustrates the power and limitations of incremental search as applied to time and resource-oriented path planning. In the positive, incremental search approaches offer the advantage of enabling guarantees of completeness and optimality. Conventionally, incremental search algorithms have been used to plan paths in two-dimensional spaces. Through the mission-directed path planning problem, this work illustrates the utility of incremental search for problems of greater than two dimensions. In enabling efficient representation of additional dimensions, the distinction between independent and dependent variables is a profitable segmentation of the state space. In effect, it collapses the representation of a very large space into the dimensionality of the independent variables, until the search dictates that other dimensions are important. Further, dependent variables can be treated at two resolutions, enabling efficiency mechanisms like resolution-based state pruning and state dominance. The resource optimization problem also demonstrates how resources can be correctly tracked and constrained outside the state space, and even optimized without adding the significant burden of an extra search dimension. Specifically, if state transitions and transition costs can be assumed to be independent of the resource variable, then that resource dimension can be represented


within a composite objective function or as an auxiliary variable, at the cost of removing the guarantee of completeness. Reduction of search dimensions is the fastest means of reducing search time and space complexity, and in practice, the reduced-dimensionality planner readily produces solutions. Under these efficiency mechanisms, incremental search enables efficient planning and re-planning for complex domains, and yields provably resolution-optimal solutions.

Efficient re-planning is a major advantage of the incremental search approach. Re-planning enables a vehicle to compensate for unanticipated excursions away from an initial plan trajectory, and allows it to repair plans in light of new information. In most real-world mobile robot applications, particularly for planetary surface exploration, models of the world and the robot will be incomplete. A planning method that rapidly adjusts to on-the-fly measurements is essential for efficient robot operation.

This thesis also illustrates the limitations of an incremental search approach. Despite the array of available efficiency mechanisms, time and space complexity grows exponentially as dimensions are added to the state space. Specific to the mission-directed planning problem, time and energy are two of many interesting and important dimensions to the problem. One could easily envision problems where vehicle heading, multiple resources, and belief of state are equally important. In view of these larger, more general problems, it is not clear that incremental search is the correct approach.

Hierarchical navigation was proven highly effective in all three field experiment involving TEMPEST. The combination of a local navigator that senses the immediate environment and steers clear of rover-scale hazards with a missionlevel path planner that reasons about the large-scale, time and resources is natural and powerful.

On the negative side, despite the array of available efficiency mechanisms available to incremental search, time and space complexity grow exponentially as dimensions are added to the state space. Specific to the mission-directed planning problem, time and energy are only two of many interesting and important dimensions that might be considered. One could envision problems where vehicle heading, multiple resources, and belief state are as important as time and energy. In view of so many additional variables, it is clear that incremental search cannot adequately address such problems.

TEMPEST proved vulnerable to a number of sources of uncertainty during the field experiments - principally time cost uncertainty, as demonstrated in the Arctic, and position state uncertainty as shown in both expeditions to the Atacama.


–  –  –

7.3 Future Work Future work might fully characterize the benefit of mission-directed path planning, in comparison to standard spatial path planners, under varying terrain, lighting conditions and rover power configurations.

Mission simulations, controlled by a mission-directed planner and parameterized on terrain, lighting and rover energetics, could yield planning performance metrics in mission-relevant terms, for example time efficiency, energy efficiency, likelihood of success. Determining trends with respect to parameters would aid in establishing planning utility bounds for future missions.

Future work might investigate the use of rapid re-planning as a means of evaluating contingency branches in a meta-planning mode.

Fast re-planning could be leveraged to plan for hypothetical situations as easily as for actual ones. Research should evaluate the planning benefit in re-planning for hypothetical contingencies, and characterize the performance of replanning under model updates not necessarily in the immediate vicinity of the rover.

Future work might characterize randomized and anytime algorithms that sacrifice optimality but enable efficient search over higher dimensional spaces, and evaluate them in the context of mission-directed path planning.

Research might determine whether randomized approaches can be designed to reliably generate reasonable, safe and mission effective solutions under probabilistic completeness and without the guarantee of optimality. Anytime algorithms could provide sub-optimal path solutions for high-dimensional spaces with known bounds on cost with respect to optimal. Adapting these search algorithms to mission-directed path planning might enable efficient planning over many additional variables, for example onboard memory, thermal state, or uncertainty parameters.

Research might develop an integrated approach for multi-scale navigation.

Unifying navigation at all scales might employ a common planning algorithm and encode a continuum of increasing representational granularity and decreasing re-planning frequency with distance from the robot. Unified navigation would extend the use of robot sensors to identify and characterize mid- and large-scale terrain features, foster a consideration of varying geometry, time, and resources at the local scale, and greatly streamline future rover software architectures.


Future work might enable efficient approaches to planning under uncertainty, with a consideration of risk sensitivity, in a mission-directed context.

Research must identify the sources of uncertainty most apt to disable mission-directed path planning, and evaluate current and develop new approaches to planning and sensing to diminish their effects. Furthermore, assessing plans in terms of risk, for instance by the variance in reward or cost, would enable a vehicle to select plans based on the evolving risk tolerance of the mission. Statistical methods are promising - they provide a natural, rigorous means of integrating sensing, planning and control, and have been successfully employed in an increasingly wide range of domains. Addressing uncertainty would enable more reliable planning for long-distance traverses that are particularly subject to errors in control, state and model accuracy.


[1] C. H. Acton Jr.,”Ancillary Data Services of NASA’s Navigation and Ancillary Information Facility”, Planetary and Space Science, 44 (1):65M. Ai-Chang, B. Kanefsky, P. Maldague, P. Morris, K. Rajan, J. Yglesias, “MAPGEN: Mixed Initiative Planning and Scheduling for the Mars 03 MER Mission,” Proceedings of the 7th International Symposium on Artificial Intelligence, Robotics & Automation in Space (iSAIRAS-03), Japan, 2003.

[3] D. Bernard, G. Dorais, E. Gamble, B. Kanefsky, J. Kurien, G. Man, W. Millar, N. Muscettola, P. Nayak, K. Rajan, N. Rouquette, B. Smith, W.

Taylor, Y. Tung, “Spacecraft Autonomy Flight Experience: The DS1 Remote Agent Experiment,” Proceedings of the AIAA Conference 1999, Albuquerque, NM.

[4] D. Bernard, G. Dorais, C. Fry, E. Gamble, B. Kanefsky, J. Kurien, W. Millar, N. Muscettola, P. Nayak, B. Pell, K. Rajan, N. Rouquette, B.

Smith, B. Williams, “Design of the Remote Agent Experiment for Spacecraft Autonomy,” Proceedings of the 1998 IEEE Aerospace Conference, Snowmass, CO, 1998.

[5] J. Bobrow, S. Dubowsky, J. Gibson, “Time-Optimal Control of Robotic Manipulators Along Specified Paths,” International Journal of Robotics Research, Vol. 4, No. 3, Fall 1985.

[6] J. Bresina, R. Washington, “Expected Utility Distributions for Flexible, Contingent Execution,” Proceedings of the American Association of Artificial Intelligence (AAAI-2000) Workshop: Representation Issues for Real-World Planning Systems, Austin, TX, 2000.

[7] L. Bugayevskiy, J. Snyder, Map Projections: A Reference Manual, Taylor and Francis Group, 1995.

[8] R. Chatila, “Path Planning and Environment Learning in a Mobile Robot System,” Proceedings of the European Conference on Artificial Intelligence, Orsay, France, 1982.

[9] S. Chien, R. Knight, A. Stechert, R. Sherwood, G. Rabideau, “Using Iterative Repair to Increase the Responsiveness of Planning and Scheduling for Autonomous Spacecraft,” Workshop on Scheduling and Planning meets Real-time Monitoring in a Dynamic and Uncertain World, (IJCAI-99), Stockholm, Sweden, August 1999.

[10] S. Chien, G. Rabideau, R. Knight, R. Sherwood, B. Engelhardt, D. Mutz, T. Estlin, B. Smith, F. Fisher, T. Barrett, G. Stebbins, D. Tran, “ASPEN - Automating Space Mission Operations using Automated Planning and Scheduling,” SpaceOps 2000, Toulouse, France, June 2000.

[11] J. Cutts, S. Hayati, D. Rapp, C. Chu, J. Parrish, D. Lavery, R. DePaula, “The Mars Technology Program,” Proceedings of the 6th International Symposium on Artificial Intelligence, Robotics & Automation in Space (i-SAIRAS 2001), St-Hubert, Quebec, Canada, June, 2001.

[12] T. Estlin, F. Fisher, D. Gaines, C. Chouinard, S. Schaffer, I. Nesnas, “Continuous Planning and Execution for and Autonomous Rover,” Proceedings of the Third International NASA Workshop on Planning and Scheduling for Space, Houston, TX, October 2002.

[13] W. C. Feldman, S. Maurice, D.J. Lawrence, R.C. Little, S.L. Lawson, O. Gasnault, R.C. Weins, B.L. Barraclough, R.C. Elphic, T.H. Prettyman, J.T. Steinberg, A.B. Binder, “Evidence for Water Ice Near the Lunar Poles,” abstract of the Lunar and Planetary Science Conference XXXII, Houston, TX, 2001.

[14] D. Ferguson, A. Stentz, “Planning with Imperfect Information,” Proceedings of the IEEE/RSJ Conference on Intelligent Robots and Systems (IROS 2004), Sendai, Japan, October 2004.

[15] A. Finzi, F. Ingrand, N. Muscettola, “Model-based Executive Control through Reactive Planning for Autonomous Rovers”, Proceedings of the IEEE/RSJ Conference on Intelligent Robots and Systems (IROS 2004), Sendai, Japan, October 2004.

[16] P. Fiorini, Z. Shiller, “Motion Planning in Dynamic Environments using Velocity Obstacles,” International Journal of Robotics Research, Vol. 17, No. 7, July 1998.

[17] T. Fraichard, “Dynamic Trajectory Planning with Dynamic Constraints: a ‘State-Time Space’ Approach,” Proceedings of the 1993 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 93), Yokohama, Japan, July 1993.

[18] R. Gaskell, J. Collier, L. Husman, R. Chen, “Synthetic Environments for Simulated Missions,” Proceedings of the IEEE Aerospace Conference, Big Sky, MT, March 2001.

[19] S. Goldberg, M. Maimone, L. Matthies, “Stereo Vision and Rover Navigation Software for Planetary Exploration,” Proceedings of the 2002 IEEE Aerospace Conference, Big Sky, MT, March 2002.

[20] M. Golombeck, D. Rapp, “Size-Frequency Distributions of Rocks on Mars and Earth Analog Sites: Implications for Future Landed Missions,” Journal of Geophysical Research, Volume 102, No. E2, February 25, 1997.


[21] J.-P. Gonzalez, A. Stentz, “Planning with Uncertainty in Position: An Optimal Planner,” Carnegie Mellon University Robotics Institute Tech Report CMU-RI-TR-04-63, November 2004.

[22] A. Hait, T. Simeon, “Motion Planning on Rough Terrain for an Articulated Vehicle in Presence of Uncertainties,” Proceedings of the 1996 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 96), Osaka, Japan, November 1996.

[23] G. H. Heiken, D. T. Vaniman, B. M. French, eds., Lunar Sourcebook: A User's Guide to the Moon, Cambridge University Press, 1991.

[24] A. Howard, H. Seraji, E. Tunstel, “A Rule-Based Fuzzy Traversability Index for Mobile Robot Navigation,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2001), Seoul, Korea, 2001.

Pages:     | 1 |   ...   | 22 | 23 || 25 | 26 |

Similar works:

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

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

«Systematische Ganzheitlichkeit Eine methodologische Vermittlung zwischen Perspektivität und Universalität mit einem Grundriß der Anwendbarkeit dieses Ansatzes auf die Geowissenschaften Inauguraldissertation zur Erlangung der Würde eines Doktors der Philosophie vorgelegt der Philosophisch-Naturwissenschaftlichen Fakultät der Universität Basel von Alec A. Schaerer Bürger von Sumiswald / BE und Genf Basel, Oktober 2011 Genehmigt von der Philosophisch-Naturwissenschaftlichen Fakultät auf...»

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

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

«The interaction between physical and sedimentary biogeochemical processes in south-west Spencer Gulf, South Australia. Emlyn Morris Jones B. Sc. (Hons) A thesis submitted in fulfillment for the degree of Doctor of Philosophy School of the Environment Faculty of Science and Engineering Flinders University of South Australia March, 2010 Contents Abstract v Declaration viii Acknowledgments ix 1 General introduction 1 1.1 Regional setting.......................... 5 1.1.1...»

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

«Proceedings von Nachdenken und Vordenken – Herausforderungen an die Philosophie Herausgeber: Oliver Petersen, Dagmar Borchers, Thomas Spitzley, Manfred Stöckler Proceedings von GAP.7 Nachdenken und Vordenken – Herausforderungen an die Philosophie Herausgeber: Oliver Petersen, Dagmar Borchers, Thomas Spitzley, Manfred Stöckler Online-Veröffentlichung der Universität Duisburg-Essen (DuEPublico) ISBN 978-3-00-036440-2 Vorwort Vom 14.-17.9.2009 fand in Bremen der siebte Internationale...»

«SHAKESPEARE‟S TELLING WORDS: GRAMMAR, LINGUISTIC ENCOUNTERS, AND THE RISKS OF SPEECH by Alysia Michelle Kolentsis A thesis submitted in conformity with the requirements for the degree of Doctor of Philosophy Graduate Department of English University of Toronto © Copyright by Alysia Michelle Kolentsis (2008) ii Shakespeare‟s Telling Words: Grammar, Linguistic Encounters, and the Risks of Speech Alysia Michelle Kolentsis Doctor of Philosophy Department of English University of Toronto...»

«J. TECHNICAL WRITING AND COMMUNICATION, Vol. 34(4) 265-290, 2004 HERBERT SPENCER’S PHILOSOPHY OF STYLE: CONSERVING MENTAL ENERGY RUSSEL HIRST University of Tennessee, Knoxville ABSTRACT My article traces the development, chronicles the impact, and explains the essence of Herbert Spencer’s “The Philosophy of Style” (1852). Spencer’s essay has had a significant influence on stylistics, especially in scientific and technical communication. Although in our generation Spencer’s...»

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

«MAN AND SUPERMAN A COMEDY AND A PHILOSOPHY George Bernard Shaw This public-domain (U.S.) text was produced by Eve Sobol, South Bend, Indiana, USA. The Project Gutenberg edition (designated “mands10”) was subsequently converted to LTEX using GutenMark software and reA edited by Ron Burkey. The text of the Appendix, “The Revolutionist’s Handbook,” which was omitted from the Project Gutenberg edition, has been restored from alternate online sources (www.bartleby.com). Report problems to...»

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