«The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 May 13, 2005 Submitted in partial fulfillment of the requirements for the ...»
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.
CONCLUSIONFuture 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.
 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.
 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.
 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.
 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.
 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.
 L. Bugayevskiy, J. Snyder, Map Projections: A Reference Manual, Taylor and Francis Group, 1995.
 R. Chatila, “Path Planning and Environment Learning in a Mobile Robot System,” Proceedings of the European Conference on Artificial Intelligence, Orsay, France, 1982.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 P. Fiorini, Z. Shiller, “Motion Planning in Dynamic Environments using Velocity Obstacles,” International Journal of Robotics Research, Vol. 17, No. 7, July 1998.
 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.
 R. Gaskell, J. Collier, L. Husman, R. Chen, “Synthetic Environments for Simulated Missions,” Proceedings of the IEEE Aerospace Conference, Big Sky, MT, March 2001.
 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.
 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.
 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.
 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.
 G. H. Heiken, D. T. Vaniman, B. M. French, eds., Lunar Sourcebook: A User's Guide to the Moon, Cambridge University Press, 1991.
 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.