«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
 K. Iagnemma, H. Shibly, A. Rzepniewski, S. Dubowsky, “Planning and Control Algorithms for Enhanced Rough-Terrain Rover Mobility,” Proceedings of the 6th International Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS 2001), St-Hubert, Quebec, Canada, June 2001.
 Jet Propulsion Laboratory website, “Update: Spirit and Opportunity”, http://marsrovers.jpl.nasa.gov/mission/status.html.
 Jet Propulsion Laboratory website, “Planetary Data System Standards Reference,” http://pds.jpl.nasa.gov/documents/sr/index.html.
 A. Jonsson, J. Frank, “A Framework for Dynamic Constraint Reasoning Using Procedural Constraints,” Proceedings of the European Artificial Intelligence Conference, 2000.
 A. Jonsson, P. Morris, N. Muscettola, K. Rajan, B. Smith, “Planning in Interplanetary Space: Theory and Practice,” Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2000), Breckenridge, CO, April 2000.
 L. Kavraki, P. Svestka, J-C Latombe, M. Overmars, “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces,” IEEE Transactions on Robotics and Automation, Vol. 12, No. 4, August 1996.
 A. Kelly, B. Nagy, “Reactive Nonholonomic Trajectory Generation via Parametric Optimal Control,” International Journal of Robotics Research, Vol. 22, No. 7, July 2003.
 A. Kelly, O. Amidi, M. Happold, H. Herman, T. Pilarsky, P. Rander, A. Stentz, N. Vallidis, R. Warner, “Toward Reliable Autonomous Vehicles Operating in Challenging Environments,” Proceedings of the International Symposium on Experimental Robotics (ISER ‘04), Singapore, Malaysia, June 2004.
 O. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots,” International Journal of Robotics Research, Vol 5. No. 1, p 60, 1986.
 S. Koenig, M. Likhachev, “Improved Fast Replanning for Robot Navigation in Unknown Terrain,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2002), Washington, D.C., May 2002.
 J. Kuffner Jr., S. LaValle, “RRT-Connect: An Efficient Approach to Single-Query Path Planning,” Proceedings of the 2000 IEEE International Conference on Robotics and Automation (ICRA 00), San Francisco, CA, April 2000.
 S. LaValle, “Rapidly-Exploring Random Trees: A New Tool for Path Planning,” Technical Report TR 98-11, Computer Science Department, Iowa State University, October, 1998.
 S. LaValle, S. Hutchinson, “An Objective-Based Framework for Motion Planning Under Sensing and Control Uncertainties,” The International Journal of Robotics Research, Vol. 17, No. 1, January 1998.
 J.C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, 1991.
 S. Laubach and J. Burdick, “RoverBug: An Autonomous Path-Planner for Planetary Microrovers,” Sixth International Symposium on Experimental Robotics (ISER 99), Sydney, Australia, March 1999.
 B. Logan, N. Alechina, “A* with Bounded Costs,” Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98), Madison, WI, July, 1998.
 R. Loui, “Optimal Paths in Graphs with Stochastic or Multidimensional Weights,” Communications of the Association of Computing Machinery, Vol. 26, No. 9, September 1983.
 A. Mason, J. Burdick, “Trajectory Planning Using Reachable State-Density Functions,” Proceedings of the 2000 IEEE International Conference on Robotics and Automation (ICRA 02), Washington, D.C., May 2002.
 A. Mishkin, J. Morrison, T. Nguyen, H. Stone, B. Cooper, B. Wilcox, “Experiences with Operations and Autonomy of the Mars Pathfinder Microrover,” Proceedings of the IEEE Aerospace Conference, Big Sky, MT, 1998.
 B. Murray, M. Malin, R. Greeley, Earthlike Planets, W. H. Freeman and Company, Copyright 1981.
 N. Muscettola, G. Dorais, C. Fry, R. Levinson, C. Plaunt, “IDEA: Planning at the Core of Autonomous Reactive Agents,” Proceedings of the American Association for Artificial Intelligence (AAAI-01), 2001.
 N. Nilsson, “A Mobile Automaton: An Application of Artificial Intelligence Techniques,” Proceedings of the 1st International Joint Conference on Artificial Intelligence (IJCAI-99), Washington, D.C., 1969.
MISSION-DIRECTED PATH PLANNING FOR PLANETARY ROVER EXPLORATION
 I. Nourbakhsh, M. Genesereth, “Assumptive Planning and Execution: a Simple, Working Robot Architecture,” Autonomous Robots, Vol. 3, No. 1, 1996.
 C. O’Dunlaing, M. Sharir, C. Yap, “Retraction: A New Approach to Motion Planning,” ACM Symposium on Theory of Computing, 15:207D. Pai, L. Reissell, “Multiresolution Rough Terrain Motion Planning,” IEEE Transactions on Robotics and Automation, Vol. 14, No. 1, February 1998.
 L. Pedersen, D. Smith, M. Deans, R. Sargent, C. Kunz, D. Lees, S. Rajagopalan, “Mission Planning and Target Tracking for Autonomous Instrument Placement,” Proceedings of the IEEE Aerospace Conference, Big Sky, MT, March 2005.
 T. L. Perez, M. Mason, R. Taylor, “Automatic Synthesis of Fine-Motion Strategies for Robots,” The International Journal of Robotics Research, Vol. 3, No. 1, 1984.
 R. Richbourg, N. Rowe, M. Zyda, R. McGhee, “Solving Global, Two-Dimensional Routing Problems Using Snell’s Law and A* Search,” Proceedings of the 1987 IEEE International Conference on Robotics and Automation (ICRA ‘87), Raleigh, North Carolina, March 1987.
 N. Rowe, D. Lewis, “Vehicle Path Planning in Three Dimensions Using Optics Analogs for Optimizing Visibility and Energy Cost,” Proceedings of the NASA Conference on Space Telerobotics, Pasadena, CA, January 1989.
 N. Rowe, R. Ross, “Optimal Grid-Free Path Planning Across Arbitrarily-Contoured Terrain with Anisotropic Friction and Gravity Effects,” IEEE Transactions on Robotics and Automation Vol. 6, No. 5, October 1990.
 N. Roy, W. Burgard, D. Fox, S. Thrun, “Coastal Navigation - Mobile Robot Navigation with Uncertainty in Dynamic Environments,” Proceedings of the 1999 IEEE Conference on Robotics and Automation (ICRA ‘99), Detroit, MI, May 1999.
 S. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, Prentice-Hall Publishers, Upper Saddle River, NJ, Copyright 1995.
 K. Shillcut, “Solar Based Navigation for Robotic Explorers,” Ph.D. thesis, technical report CMU-RI-TR-00-25, October 2000.
 Z. Shiller, Y. Gwo, “Dynamic Motion Planning of Autonomous Vehicles,” IEEE Transactions on Robotics and Automation, Vol. 7, No. 2, April 1991.
 S. Singh, R. Simmons, T. Smith, A. Stentz, V. Verma, A. Yahja, K. Schwehr, “Recent Progress in Local and Global Traversability for Planetary Rovers”, Proceedings of the 1999 IEEE International Conference on Robotics and Automation (ICRA 99), Detroit, MI, May 1999.
 M. Slade, B. Butler, D. Muhleman, “Mercury Radar Imaging: Evidence for Polar Ice,” Science, Vol. 258, pp. 635-640, 1992.
 R. Simmons, E. Krotkov, L. Chrisman, F. Cozman, R. Goodwin, M. Hebert, L. Katragadda, S. Koenig, G. Krishnaswamy, Y. Shinoda, W.
Whittaker, P. Klarer, “Experience with Rover Navigation for Lunar-Like Terrains,” Proceedings of the IEEE/RSJ Conference on Intelligent Robots and Systems (IROS ‘95), Pittsburgh, PA, August 1995.
 R. Simmons, D. Apfelbaum, “A Task Description Language for Robotic Control,” Proceedings of the IEEE Intelligent Robots and Systems Conference (IROS 98), Vancouver, Canada, October 1998.
 A. Stentz, “The Focussed D* Algorithm for Real-Time Replanning”, Proceedings of The 14th International Joint Conference on Artificial Intelligence (IJCAI-95), Montreal, Canada, August 1995.
 A. Stentz, M. Hebert, “A Complete Navigation System for Goal Acquisition in Unknown Environments”, Autonomous Robots, Vol. 2, No. 2, August 1995.
 A. Stentz, “Optimal and Efficient Path Planning for Unknown and Dynamic Environments”, International Journal of Robotics and Automation, Vol. 10, No. 3, 1995.
 A. Stentz, “CD*: A Real-time Resolution Optimal Re-Planner for Globally Constrained Problems,” Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-02), Edmonton, AB, Canada, July 2002.
 Z. Sun, J. Reif, “On Energy-Minimizing Paths on Terrains for a Mobile Robot,” Proceedings of the 2003 IEEE International Conference on Robotics and Automation (ICRA ‘03), Taipei, Taiwan, September 2003.
 R. Szczerba, D. Chen, “Using Framed Subspaces to Solve the 2-D and 3-D Weighted Region Problem,” Department of Computer Science and Engineering Technical Report CSE 96-18, Notre Dame University, 1996.
 H. Takeda, C. Facchinetti, J-C. Latombe, “Planning the Motions of a Mobile Robot in a Sensory Uncertainty Field,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 6, No. 10, October 1994.
 P. Tompkins, A. Stentz, W. Whittaker, “Mission Planning for the Sun-Synchronous Navigation Field Experiment,” Proceedings of the 2002 IEEE International Conference on Robotics and Automation (ICRA 02), Washington D.C., May 2002.
 C. Urmson, M. Dias, R. Simmons, “Stereo Vision Based Navigation for Sun-Synchronous Navigation,” Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS ‘02), Lausanne, Switzerland, October 2002.
 C. Urmson, “Locally Randomized Kinodynamic Motion Planning for Robots in Extreme Terrain,” Ph.D. thesis proposal, The Robotics Institute, Carnegie Mellon University, 2002.
 C. Urmson, J. Anhalt, M. Clark, T. Galatali, J. Gonzalez, J. Gowdy, J. Gutierrez, S. Harbaugh, M. Johnson-Roberson, Y. Kato, P. Koon, K.
Peterson, B. Smith, S. Spiker, E. Tryzelaar, W. Whittaker, “High Speed Navigation of Unrehearsed Terrain: Red Team Technology for Grand Challenge 2004,” Carnegie Mellon University Robotics Institute Technical Report CMU-RI-TR-04-37, June 2004.
 R. Volpe, I. Nesnas, T. Estlin, D. Mutz, R. Petras, H. Das, “The CLARAty Architecture for Robotic Autonomy,” Proceedings of the 2001 IEEE Aerospace Conference, Big Sky, MT, March 2001.
 Wellington, A. Stentz, “Online Adaptive Rough-Terrain Navigation in Vegetation,” Proceedings of the 2004 IEEE International Conference on Robotics and Automation (ICRA ‘04), New Orleans, LA, April 2004.
 M. Wellman, M. Ford, K. Larson, “Path Planning Under Time-Dependent Uncertainty,” Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (UAI-95), Montreal, Canada, August 1995.
 D. Wettergreen, B. Shamah, P. Tompkins, R. Whittaker, “Robotic Planetary Exploration by Sun-Synchronous Navigation”, Proceedings of the 6th International Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS 01), Montreal, Canada, 2001.
 D. Wettergreen, B. Dias, B. Shamah, J. Teza, P. Tompkins, C. Urmson, M. Wagner, W. Whittaker, “Experiments in Sun-Synchronous Navigation,” Proceedings of the 2002 IEEE International Conference on Robotics and Automation (ICRA 02), Washington D.C., May 2002.
 D. Wettergreen, N. Cabrol, M. Deans, D. Jonak, A. Luders, F. Shaw, T. Smith, J. Teza, P. Tompkins, C. Urmson, V. Verma, A. Waggoner, M.
Wagner, “Life in the Atacama: Field Season 2003 Experiment Plans and Technical Results,” Carnegie Mellon University Robotics Institute Technical Report CMU-RI-TR-03-50, October 2003.
 W. Whittaker, G. Kantor, B. Shamah, D. Wettergreen, “Sun-Synchronous Planetary Exploration,” AIAA Space 2000 Conference and Exposition, 2000.
Appendix 1: ISE Algorithm
This appendix describes the Incremental Search Engine (ISE) algorithm in greater detail than presented in Chapter 3.
ISE search centers around a priority queue called the OPEN list. The first section describes how the OPEN list operates. The following section presents the ISE algorithm at the highest level, in terms of the ISE search modes: BESTPCOST and BESTDPARMS. Each of these modes calls upon state expansion, whose details appear in the third section. An important feature of ISE is its ability to enforce and manage the dominance of some states over others.
The final section in the appendix describes the piece of the algorithm associated with that management task.
A1.1 OPEN List As with D*, ISE maintains a data structure, called the OPEN list, containing states prioritized for expansion. The OPEN list computes the path cost from states to the goals, and propagates information about changes to arc costs incurred during plan execution. The OPEN list propagates information by repeatedly expanding the highest priority state on the list. When a state is expanded, it is removed from the OPEN list, and all its child states are added to the OPEN list. States that are modified through cost increases or decreases are also placed on the OPEN list. All states have an associated tag function t ( X ) that defines their OPEN list status. Tags hold one of three values: t ( X ) = NEW if the X has never been on the open list, t ( X ) = OPEN if X is currently on the OPEN list, and t ( X ) = CLOSED if X was removed from the OPEN list.
For each state on the OPEN list, a key function k ( X ) is defined to be equal to the minimum of h ( X ) before a cost modification and over all values h ( X ) assumed after X was placed on the OPEN list. The key function classifies states on the OPEN list into two types: RAISE states ( k ( X ) h ( X ) )and LOWER states ( k ( X ) = h ( X ) ). RAISE states propagate information about path cost increases, and LOWER states propagate information about path cost reductions.