Planning and scheduling problems are pervasive in NASA ground and flight operations. Examples include:
A key component in every phase of mission operations is planning and scheduling activities, including crew training, ground operations, control of life support systems, and exploration and construction tasks. Future exploration missions to the moon and Mars will involve complex vehicles, habitats, and robotic systems. Automated planning and scheduling will increase the safety of these missions and reduce their cost. Similarly, automated planning is crucial in order to maximize science return from deep space probes and even terrestrial observing systems. Finally, automated planning complements and enhances the capabilities of human operators.
Diverse as they are, all of these planning and scheduling applications share some common characteristics:
The Planning and Scheduling Group at NASA Ames Research Center has a long history of research and development of cutting edge techniques that address these technical challenges, in addition to infusing this technology into a wide range of NASA missions.
Many scheduling problems consist only of simple temporal constraints. Examples of such constraints are absolute time limits (e.g., finish the EVA by 0:300) or relative constraints (e.g., the drilling activity must last less than 10 minutes). Complex problems often have many such constraints, and can benefit from special-purpose methods designed to efficiently solve such problems. Our work in this area includes fast algorithms for temporal scheduling, and tightly integrating such algorithms with general-purpose planning and scheduling systems.
Temporal reasoning becomes more difficult when resource constraints are mixed with time constraints. For example, a rover doing a construction task may need to recharge the batteries in order to finish the task. Our work in this area includes developing techniques to incorporate knowledge and efficient reasoning about resources into automated planners.
Planning and scheduling systems can be used to find the shortest plan to achieve a goal, or the most fuel-efficient plan to achieve a goal. Other planning and scheduling problems include achieving the largest number of goals, or the best subset of goals. Our work in this area includes incorporating existing optimization techniques into planners as well as developing new techniques for over-subscription planning.
Planning is not an activity that is performed only once. This is especially true for missions that take place far from Earth, where novel situations arise frequently. Forcing spacecraft to wait for new plans is wasteful in the best case, and dangerous in the worst case. This problem is handled in one of several ways. First, fast planners and schedulers can be deployed onboard spacecraft to re-plan when necessary in certain cases. Second, planners can generate contingency plans that account for uncertainty ahead of time. Our work in this area includes developing methods for selectively adding contingency branches to plans to improve their robustness, as well as developing planning and scheduling techniques able to handle uncertain activity duration, uncertain resource consumption, and uncertain action outcomes (e.g., uncertain position after movement actions).
Plans and schedules ultimately are executed. Work in this area includes development of a language for specifying discrete control of robots, spacecraft and significant spacecraft subsystems. Additional work includes transforming procedures into this target language for safe, adjustable automatic execution.
Planning and scheduling systems must be integrated into a wider context. For example, spacecraft must be able to call planners when new plans are needed. Onboard planners must be fast and use as little memory as possible. Finally, humans must be able to control planning and scheduling at a fine degree of detail, and understand why particular plans were generated. Work in this area includes providing planning and scheduling systems that can be integrated with onboard systems or human operators, as well as developing knowledge acquisition and maintenance tools.