Proposal Submitted to the National Aeronautics and Space Administration

Operational Autonomy for Planetary Robots
	Technical and Administrative Contact:
	Anthony Stentz (412) 268-8155

Robotics Institute, Carnegie Mellon University
Pittsburgh, PA 15213

For the period 10/1/97 through 09/30/00
Amount requested: $750,000
1.0	Project Summary
NASA Telerobotics has succeeded in developing a wide variety of robotic systems, from free-flying manipulators to planetary rovers and associated supporting technologies. While teleoperation is appropriate when communications and robot simplicity allows, some missions require a degree of autonomy. Bold, high-return space missions may drive ambitions for autonomy beyond terrestrial standards. The robotics community has made substantial advances in navigation, motion safeguarding, manipulation, sensing and cognition. We propose to enable true operational autonomy for space robotics systems by building bottom-up from these existing robotic technologies to enable long-duration high-complexity autonomous missions.
We propose to begin with existing mobility capabilities and marry these behavioral building-blocks to state-of-the-art cognition systems explicitly designed for field operation of robotic systems. By providing a system which can reason about its operational primitives (i.e. drive-to-goal, collect-sample) and associated contingency plans, a mission-capable autonomous mobile robot system can be realized. This program will design, build and test such a system in the context of a planetary ice exploration mission.
2.0	Objectives
The objective of this three year program is to deliver a means for self-reliant autonomously generated and controlled activity that creates and executes productive tasks like exploration, assembly, and sitework. Many tasks envisioned for robotic execution exhibit similar characteristics. They require the ability to self-localize, track objects, move from one location to another, perform tasks at given locations, and decide on future courses of action, all in the context of the mission requirements. For example, a geological survey robot may need to drive to an exploration site, collect a sample, evaluate the usefulness of the sample, and determine the next site to explore; or, an assembly robot may need to retrieve a piece of material, transport it to an installation site, and perform the installation. 
Many robotic primitives are robust or are progressing toward maturity, including navigation, safeguarding, simple manipulation, and structured assembly operations, but these are best described as components of tasks, rather than tasks themselves. The environment in which any autonomous system must operate is one of uncertainty and change. Thus, it is necessary to chain together these operational primitives and permit the dynamic generation of intelligent task-consistent activity. 
General-purpose intelligent reasoning systems that are robust and tractable remain an elusive research goal. However, for most planetary operations, general intelligence is not needed; instead, most tasks can be accomplished by the artful combination of primitive operations, embedded in a straightforward reasoning system which pays attention to goals, exceptions and contingencies. Thus, our objective is to fulfill a clear need: To imbue genuine mission-oriented onboard intelligence, thereby creating robots that exhibit competent task capability with purpose and intent.
3.0	Justification
3.1	Overview
The need for operational autonomy is clear for planetary, asteroid, and deep-space probes. Being able to issue only a single command every 45 minutes, (or more on distant locations) greatly limits the maximum potential effectiveness of teleoperation. The problem is further compounded by communications black-outs on planetary far-sides, the extremely limited bandwidth of deep-space probes, and the inherent difficulty of providing sufficient “situation assessment” for a remote operator to control the system effectively. While teleoperation (and the human control implicit therein) is advantageous when possible, autonomy can enable higher performance of robots in many scenarios.
Telerobotics has invested well to develop hardware and physical controls, producing substantial mechatronic and robotic building-blocks. Many of these components have successfully progressed beyond laboratory settings to actual deployment. The next wave of NASA missions beg for capabilities beyond simple driving or grasping, for example:
•	Precursor site preparation, with assembly and checkout of delivered modules
•	Search for life on planetary surfaces without teleoperated micromanagement
•	in situ resource utilization, such as oxygen production and delivery service
•	Construction and management of a solar power grid and associated facilities
•	Exploration and discovery, beyond step-and-stop photography
Therefore, for operations on remote planetary surfaces, as well as on asteroids or deep space probes, it is impractical to expect teleoperation to permit complex tasks and missions; it will be highly advantageous for autonomous systems to behave intelligently. Operations in these environments cannot be preprogrammed, as there may simply not be enough a priori information to permit the detailed specification of the mission. The needed intelligence can be expressed as the ability for the robot to convey its understanding of the task by making reasonable trade-offs between mission alternatives as it operates in this environment.
3.2	Limitations of Existing Technologies
Many existing areas of research in robotics, autonomous systems, and artificial intelligence provide insight into the problems of Operational Autonomy (OA). Existing systems for autonomous robots fail to permit OA because they overlook two primary difficulties of these endeavors: mission planning and dynamic planning. Mission planning is the process of determining what a robot should do to achieve the goals of the mission. Dynamic planning is the process of updating the mission plans (i.e. changing a robot’s plan) when further knowledge of the world is gained or when an exception occurs, causing the current plan to no longer be applicable.
3.2.1	Mission Planning
In the robotics community, the term “planning” has three distinct meanings. First, from the Artificial Intelligence (AI) perspective, planning refers to the autonomous generation of plans which consist of a sequence of actions that change the state of the world to a specified goal state. Second, from a mobility perspective, planning refers to robot motion planning, that is, a finding a path for the robot to follow which ensures that it reaches the goal state without colliding with obstacles in its environment. Third, from a scheduling perspective, it can refer to determining how to order the allocation of scarce resources, typified by machine-shop scheduling operations. 
AI planning systems began with STRIPS and have since been improved and applied to a variety of domains from simple robot control to naval logistics. These planners typically attempt to be domain independent, and frequently focus on increasingly complex methods for searching for the appropriate sequence of operators (ways the robot may affect the world.) Planning is viewed as a heuristic search, with more advanced planners having greater ability to modify, adjust, and learn from partial plans while building up to a global plan. Few of these systems have demonstrated the capability to integrate well with the existing capabilities of autonomous agents, nor have they effectively demonstrated functionality in a dynamic world. 
Motion planning systems have ranged from simple local control schemes to avoid nearby obstacles to omniscient systems which reason about the entirety of the robot workspace. The basic motion planning problem considers moving a single robot from a start location to a goal location amidst a bounded workspace of polygonal obstacles. This problem can be complicated by considering an unknown world, a changing world, non-point robots, nonholonomic robots, non-polygonal obstacles, uncertainty in motion, and so forth. For most space-relevant robotics tasks, the robot is nonholonomic, motion control introduces uncertainty, perception information is unreliable, and the state of the world is not fully known. In addition, these planners are almost exclusively concerned with achieving a single goal state, with little concern for sequencing multiple goals together.
Scheduling systems exist for a wide variety of applications. Examples include systems for ordering observation tasks for the Hubble space telescope and optimizing the completion of jobs in a manufacturing setting. Applications suited for scheduling-style systems are those which exhibit a great deal of structure and regularity. Tasks can usually be very well modelled by their resource use, duration, and relationship to other tasks. Unfortunately, the needs of OA cannot be met in such a rigid fashion because the situation may be changing regularly, and many tasks are complex enough to be of unknown duration. Finally, while these missions can be highly constrained, they are not easily modelled by the Linear Programming approach taken by many scheduling algorithms as reasoning about tasks and motion is very different from scheduling a task sequence.
Thus, AI-planners are good at ordering actions, while motion-planners are good at keeping the robot safe while moving to a single goal. Schedulers offer efficient mechanisms for choosing between options in highly constrained spaces. It is necessary to connect these worlds so that more complex tasks can be completed. 
3.2.2	Dynamic Planning
Most systems in both the AI- and Motion- planning domains perform poorly when the coupling of the planner to the robot is weak, that is, these planners typically assume both that a plan will be followed precisely and that it is acceptable to replan fully when a change in the plan is needed. For real applications, planning must be secondary to the moment-to-moment tasks which maintain the safety of the robot as it moves through its workspace. The planner must therefore operate in a advisory manner with respect to whatever control system is actually moving the robot. The planner cannot assume that its command will be followed, nor can it assume a static world model. As new information becomes available, or as the state/location of the robot changes, the planner must notice these changes and act accordingly, without requiring unreasonable computational bandwidth. For typical environments, efficient dynamic replanning can be 300 times faster than full replanning. 
Dynamic planning is a necessity for motion planning in a real environment because of a wide variety of events which may necessitate changes to the initial plan. Every perception system can introduce unavoidable noise into the system, “surprise” the planner with unexpected terrain, limit the motion of the robot due to a narrow field of view, and “change its mind” about terrain when viewed from a different, frequently closer, position. The local navigator may determine that it is unsafe to drive in the planned direction and veer from the course. The positioning system may determine that the robot is not in the location previously estimated. All of these issues would necessitate complete replanning under a traditional static planning paradigm. Dynamic planning allows these changes to be incorporated in real-time, allowing the constant optimization of the mission plan in an unknown environment.
For space scenarios, the need for dynamic mission planning extends beyond the mobile aspects of the mission. The intent of the mission is to perform some task such as assembly or scientific data collection, in which motion is but a portion of the entire task. Other difficulties can arise. For example, for solar-power reasons a robot may have a limited period of time during which it may remain in a shadowed area. Alternatively, the analysis of a given geologic sample may imply the need to alter the sites of future sampling. In either of these cases, the success of the mission requires that the robot alter its strategic plan in response to changes in the operational situation. While this type of reasoning or contingency planning seems covered by the capabilities of existing planning systems, the need to replan in an efficient dynamic fashion implies the need for new approaches.
3.3	User Community, Responsiveness to Requirements, and Advances on State-of-the-Art
This program will deliver a level of operational autonomy beyond the task autonomy that typifies space robotics practice. By reducing the degree of human supervision and interaction required during a robotic mission, the cost of mission operations can be substantially reduced. Many NASA initiatives including the search for extraterrestrial life, Human Lunar Return, astronaut EVA augmentation, and orbital reconfiguration and servicing could be enabled or significantly enhanced by the technologies produced by this program, as they all would benefit from increased capabilities in operational autonomy. 
These capabilities provide clear quantitative improvement over the state-of-the-art in space robotics systems. The ability to operating autonomously during periods of communications dead-time due to operation on remote sites or planetary craters, lims, and far-sides will greatly increase the potential scientific return on future NASA planetary missions. Compared to the intermittent operation possible using teleoperation, operational autonomy offers the potential to deliver a higher duty-cycle during a given operational time-frame. 
4.0	Technical Approach
4.1	Overview
Our approach to providing true operational autonomy to space telerobotic systems is to design for autonomy from the bottom up - by first integrating existing robotic components to solve a base level mission, then incrementally adding technical capability to solve increasingly more challenging missions. Each plateau in the system’s evolution will be fully autonomous, thus completely solving a given problem of increasing complexity. The advantage of this approach is that the resultant system will be complete (i.e., addresses all issues for a given problem) without being overly general to the point that it is fraught with unused and unnecessary features that are difficult to validate and fully debug. The final system will fully automate a complex and NASA-relevant mission. This goal will be realized in part by interacting with existing robotics groups within NASA (in particular, the IMG group at NASA Ames), to ensure the applicability of this system to actual NASA scenarios.
The following sections will introduce the fundamental concepts behind an operational autonomy system, discuss the nature of our existing technology and experience, and identify target improvements to permit effective operational autonomy.
4.2	OA System - Basic Design
The initial Operation Autonomy System (OASys) will consist of the integration of existing navigation and operator reasoning components developed at CMU into a complete system capable of solving a base level mission. NASA will leverage off of all these components in the development of OASys. These robotic components are:
•	RANGER: safeguards a rover using imaging sensors to detect and avoid obstacles;
•	D*: plans routes between goal locations given no or partial terrain map data; sensor data is used to update the map enroute and replan the routes in real-time;
•	GRAMMPS: orders the goal sequence for the robot to visit to optimize a high-level mission; replans the mission enroute as new information is discovered and the map is updated;
•	DGP: plans sequences of operations, including motion, to achieve a given mission; replans the mission during execution as needed to account for new information or uncertainty.
The integration of RANGER and D* permits safeguarded, route-based navigation for a rover. Integrating GRAMMPS enables the system to reason about a sequence of motion goals, rather than just a single goal. Finally, the integration of DGP enables the system to reason about operations other than motion. The entire system can replan as needed to account for uncertainty about the rover’s environment and actions.
This system (OASys) will be able to perform a base-level mission such as core sampling over an area of planetary terrain. As the mission is increased in complexity, the following planning extensions will be investigated as needed to solve these problems while preserving autonomous operation.
4.3	Planning extensions
While there are existing capabilities for both the dynamic planning engines and the operational primitives which can be adapted and refined for OASys, extending these capabilities to provide robust and reliable autonomy for space missions is critical. We focus on three critical areas in which extensions will need to be made:
•	Contingency Planning
•	External Constraint Planning
•	Risk/Reward Analysis
The driving goal in all these modifications and adaptations is to ensure that they are made only when necessary to making real missions feasible and achievable. A known problem with general planning and automated reasoning systems is that they are complex, hard to maintain, and hard to understand. For a mission to be performed reliably, it is essential to have the minimum complexity planning system capable of performing the reasoning which is necessary for success; wasted capability only increases the difficulty of the testing and verification of an operational architecture. Generality will not be added to this system at the cost of producing a system which is ungainly, intractable, or hard to understand.
4.3.1	Contingency Planning
During actual operations of an autonomous system, there are a wide variety of failure modes which can occur. Given the nature of operating in uncertain environments, the likelihood of a given operation not being carried out as planned can be substantial. For this reason, it is necessary for all operational primitives to have an understanding of their implicit failure modes, the methods of rectification, and/or consequences of such a failure. For example, during a long traverse, it is possible that the robot will lose its way or follow a wrong path. In a planetary scenario, a behavior which turns the robot around, and then allows it to follow its tracks back to a previously known location might engage in response to this difficulty. Alternatively, the robot might stop and run a position estimation behavior which is perhaps computationally and time expensive. The planning system would be responsible for comparing the two alternatives, and selecting between them. By embedding this kind of reasoning in a larger planning domain, the consequences of choosing one action over another can be propagated to upcoming mission-relevant tasks. 
4.3.2	External Constraint Planning
While the primary goal of a mobile mission may be to collect scientific data, or checkout and assemble delivered equipment, the robot is a real physical system and, as such, has some operational constraints. For example, a planetary ice robot must not spend too long in shadow as it might run out of power, and an exploration robot may need to periodically ensure it reaches a location where it can transmit data back to Earth. All of these constraints, while not implicitly part of the mission statement, must be satisfied to keep the robot alive and functioning.
4.3.3	Risk/Reward Analysis
To exhibit intelligent behavior, an autonomous system must be able to trade-off the potential risks and rewards of different courses of action. Traditionally, dynamic planning systems evaluate possible plans of action by determining which solution satisfies the mission goals with lowest cost. It is more realistic, however, to recognize that all valid solutions are not of equal value, nor of equal likelihood of success. For example, it may be more valuable for a given number of ice core samples to be taken in several craters rather than taking the same number in a single crater, though it is riskier to travel to multiple craters. Being able to select between differing acceptable alternatives based on their potential risks and rewards will further advance the intelligent capabilities of such a robotic system.
4.4	Example Domain
The example domain on which OASys will be validated is the Planetary Ice Discovery Mission. The goal of such a mission is to sample a large area of planetary terrain to discover, analyze, and map ice deposits. The problem is challenging because ice is likely to remain in areas such as valleys and craters that are shielded from the sun, areas in which a solar-powered rover with battery backup can operate for only a limited amount of time. They are also areas where communication with Earth is difficult, thus motivating the need for autonomy. Besides the recently publicized evidence of ice on the lunar south pole, it is likely that ice exists on comets, Mercury, Mars, and Ceres. Other sampling and exploration missions are similar to this domain, ensuring an amount of general applicability to OASys.
High-level reasoning is needed to chain together navigation and sampling operations in order to properly characterize a given area. Based on analysis of samples extracted during mission execution, the mission may need to be replanned in situ to pursue more promising leads. Rover navigation between sampling sites is critical. The sites must be ordered properly to conserve energy and minimize risk. Routes must be planned that minimize time spent in shadowed areas to avoid energy depletion. Finally, the rover itself must be safeguarded as it moves from goal to goal.
5.0	Schedule and Milestones
The mission will be achieved by fully automating a “bare bones” capability in the first year, extending it to handle more difficult conditions in the second year, and finally addressing all aspects in the third and final year. For the first year mission, OASys will be provided with a map of the planetary terrain with areas classified as either always illuminated (class 1) or sometimes/never illuminated (class 2.) A static set of sampling sites will be selected by a human and provided to OASys. OASys will investigate how to order the sampling sites to conserve fuel and minimize risk. It will proceed to execute this plan by driving the rover through class 1 areas as much as possible, venturing into the class 2 areas only briefly to obtain a sample and return. The entire mission will be replanned as needed to account for route obstructions discovered along the way. OASys will be demonstrated using a planetary terrain simulator. This first year mission will demonstrate the ability to integrate existing robotic components with some attention to planetary map representation and operation cost metrics.
For the second year mission, the map of the planetary terrain will consist of class 1 and class 2 designations as a function of time. That is, more information will be encoded into the map about which areas are illuminated at which time. The same static set of sampling sites will be provided to OASys. OASys will be extended to reason about temporal constraints to produce a mission that travels through the class 1 areas at the appropriate times, venturing into class 2 areas as needed to shorten paths and acquire samples. The mission OASys produces will be adjusted in real-time to accommodate both unanticipated terrain and inaccurate terrain classifications. These missions will consume less fuel and be less risky since OASys is better able to reason about illumination and misclassifications, thereby enabling it to select a better strategy than a strictly conservative one. Again, OASys will be demonstrated using the planetary simulator.
For the third year mission, OASys will be provided with a map of known ice deposits along with a request to map a specific planetary area, rather than a static set of sampling sites to visit. OASys will be extended to reason about the scientific worth of sample data, so that it can select the sites itself from the input data. As samples are collected, the mission will be replanned to pursue more interesting leads. The end result is that the designated area will be better sampled, since the mission will be replanned to concentrate on interesting areas, rather than pursuing a static coverage pattern. OASys will be demonstrated using the simulator.
The work items are listed by year below:
5.1	Year 1 - FY ‘98
•	Develop a planetary simulator capable of modeling mobility obstructions and illumination.
•	Develop map representations and cost metrics appropriate to the mission.
•	Integrate basic D* and GRAMMPS with the above data structures to create OASys.
•	Milestone: Demonstrate basic OASys using the simulator.
5.2	Year 2 - FY ‘99
•	Extend simulator to handle time-based illumination.
•	Extend map representation to store time-based illumination data.
•	Extend OASys to reason about temporal constraints on traversability.
•	Milestone: Demonstrate extended OASys using the simulator.
5.3	Year 3 - FY ‘00
•	Extend simulator to model ice deposit data.
•	Extend map representation to store ice deposit data.
•	Extend OASys to reason about multiple types of operators, adding data sampling to the repertoire.
•	Milestone: Demonstrate mission-capable OASys using the simulator.
5.4	Yearly Deliverables
Each year’s deliverables will consist of a videotaped demonstration, commented source code, and a complete annual report. 
6.0	Resource Requirements
Table 1: Yearly Budgets			
FY ‘98	FY ‘99	FY ‘00	
$250,000	$250,000	$250,000	
Table 2: FY ‘98 Budget Breakdown		
Category	Amount	
Personnel	$126,000	
Travel	$15,000	
Operating Expenses	$14,000	
Equipment	$7,000	
Overhead	$88,000	
Total	$250,000	
Personnel expenses include 5% of Red Whittaker (Principal Investigator), 20% of Tony Stentz (Senior Research Scientist), 100% of Barry Brumitt (Post Doctorate Fellow), 50% of a staff programmer, and 100% of an undergraduate research assistant.
7.0	Dual-use Potential 
Autonomy is the destiny of NASA since the charter for remote operations defies approaches that succeed on earth. Particularly for deep space, the planets, and intricate orbital operations, a genuine viable agenda to set a new course and a new standard for autonomy is needed so that space automation, in the true sense, becomes the byline of the new millennium.
8.0	Qualifications
The Field Robotics Center at Carnegie Mellon is well qualified to develop and deliver Operational Autonomy. Over the last decade, we have developed many robots, employed a variety of sensing systems, generated safeguarded mobility methodologies, and explored diverse options for integrating these hardware and software capabilities into real, fieldable robots. The metric of our success has consistently been the production of robots and associated technologies which both advance the state-of-the-art and are field-deployable. The attainment of a mission-capable Operational Autonomy systems demands this kind of experience with tangible robotic systems.
Carnegie Mellon has a history of NASA Telerobotics projects, including Ambler, Tesselator, Daedalus, Dante, Ratler, Demeter and Nomad research robots. In addition, other projects include robots for use in nuclear clean-up, underground mining, construction, outdoor navigation (wheeled and legged), road following, and a variety of hazardous waste remediation scenarios. Beyond constructing these robots, we have employed an array of sensors (including ladar, stereo vision, sonar, radar, INS, and GPS) to perform the perception necessary for a robot to function in the world. 
Autonomy has been a prime focus of many of these projects. Together, RANGER, SMARTY, ALVINN, RALPH, the Ambler Autonomous Planning System, MORPHIN, and others have autonomously traversed over 10000km on-road and over 300km on natural terrain. These behaviors allowed straightforward intentions, such as heading-following, path-following, and wandering. Beyond using a single behavior, we have combined these behaviors to permit more complex tasks via arbiters, communications schemes, sequencers, and architectures such as DAMN, SAUSAGES, TCX, IPT and TCA. 
With a repertoire of mechanisms, sensors, and multiple operational behaviors, the Field Robotics Center has moved towards providing situated intelligence for robots which permits greater autonomy in operation. The D* algorithm (Dynamic A*) was developed to provide efficient real-time replanning. D* is a planning algorithm that produces an initial plan based on known and assumed information, and then incrementally repairs the plan as new information is discovered about the world. The repaired plan is guaranteed to be optimal and is functionally equivalent to replanning from scratch. GRAMMPS (a Generalized Robotic Autonomous Mobile Mission Planning System) was developed to extend D* to groups of robots and more complex mobile missions. For example, it is possible to specify conjunctions, disjunctions, and orderings of goal locations for multiple robots, and it ensures that the optimal plan is being followed in a changing environment. Dynamic Graph Plan (DGP) allows general AI-type planning (involving pre-conditions, post-conditions, and operators) to be performed in a dynamic fashion. D*, GRAMMPS and DGP are driven by the demands of real mechanisms and sensors, and are the state-of-the-art in situated intelligence for mobile robots. They provide the basis for a dynamic planning system which can reason about mobile missions on planetary surfaces as required for Operational Autonomy.
Through this program, NASA leverages years of experience in all aspects autonomous mobile robotics. With each past project, we have developed new technology that solved a specific problem that we encountered in the real world and thus provided greater operational capability. Progressing from mechanisms, to perception, to behaviors, and now to cognition, the Field Robotics Center has the essential experience in truly autonomous mobile robotics systems to develop a system for Operational Autonomy as required for future high-return NASA planetary missions.
9.0	Partnerships and Participants
9.1	NASA Ames
This program will collaborate with groups at NASA Ames. The IMG group will provide experience and knowledge concerning the nature of remote robotic science data collection and assist in the development of planning and execution operators for OASys appropriate to the example domain.
9.2	Carnegie Mellon TRIWG Programs
CMU TRIWG programs are building complementary technologies that stand on their own merit, and also synergize to produce a whole that is greater than the sum of its parts. The Meteorite Search Technology program provides the basis for perception and automatic search and exploration strategies. The Meteorite Search Demonstration program allows for these technologies to be fielded and hardened for flight scenarios. The Unified Lander-Rover is a spacecraft paradigm that could deliver a higher fraction of scientific payload to planetary surfaces while still permitting the mobility required for exploration. Finally, Operational Autonomy promises the ability for such rovers to autonomously perform ambitious high-return missions when teleoperation is infeasible due to task complexity and communications limitations. But CMU goes beyond creation and promulgation of knowledge, using the REC to carry development to a commercial standard by productizing and hardening NASA technologies for industry.