|Automated Planning and Scheduling|
The Ames Planning and Scheduling Group has developed and demonstrated techniques for planning and scheduling with complex temporal and resource constraints in a wide range of NASA applications involving ground, flight and surface operations.|
Ames combines extensive technical expertise with experience delivering planning and scheduling software to flight missions.
Complex temporal constraints
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).
More complex problems often have many such constraints, and can benefit from special-purpose methods designed to efficiently solve such problems. Our research in this area includes fast algorithms for temporal scheduling, and tightly integrating such algorithms with general-purpose planning and scheduling systems.
Right: Artist rendition of Remote Agent Satellite. Image courtesy: NASA.
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. While reasoning about resources is common in scheduling algorithms, it is relatively new in planning. Our research in this area includes developing techniques to incorporate knowledge and efficient reasoning about resources into planners.
Over-subscription and optimization
Recently, planning and scheduling systems have begun to consider optimizing make span or energy consumed by a plan. However, little attention has been given to problems of over-subscription and multi-criteria optimization in planning. Our research in this area includes incorporation of existing optimization techniques as well as development of 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 research in this area includes the development of methods for selectively adding contingency branches to plans to improve their robustness, as well as the development of techniques to allow Markov Decision Processes to deal with time and continuous quantities.
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.
Image right: MER:MAPGEN.
Planning and scheduling technology developed at ARC has been infused into several missions. One notable success is the Remote Agent Planner, which demonstrated on-board planning in space as part of an experiment aboard the Deep Space 1 spacecraft. Currently, an automated planning and scheduling system (MAPGEN) is in daily use for generating command sequences for the ongoing Mars Exploration Rover mission. Other mission applications include scheduling astronomy observations for SOFIA, scheduling satellite activities, planning image processing activities for analyzing satellite data, and scheduling space shuttle ground operations.
Planning and scheduling problems are pervasive in NASA ground and flight operations. Examples include:
Scheduling of crew training facilities.
Scheduling ground processing and maintenance for the space shuttle.
Scheduling crew activities aboard the ISS.
Scheduling Deep Space Network communications.
Planning and scheduling the daily activities of rovers.
Planning complex image processing tasks.
Planning and scheduling spacecraft activities such as Deep Space 1.
Future exploration missions to the moon and Mars will involve complex vehicles, habitats and robotic systems. In order to keep operations costs low, automation will be paramount. Planning and scheduling is a key component in every phase of operation from crew training to ground operations, activity scheduling, control of life support systems, planning and scheduling of exploration and construction activities.
Image left: Remote Agent Process. Image courtesy: NASA.
Diverse as they are, all of these applications of planning and scheduling share some common characteristics:
complex temporal constraints - many activities like communication can only be done during certain time windows and other activities must be done in a particular order.
limited resources - rovers and spacecraft have very limited energy and memory available and these assets must be managed carefully.
over-subscription and optimization - typically there are many more objectives than can be satisfied, but these objectives have different value and importance.
uncertainty - the time required to travel to a given location, complete a maintenance operation, or to assemble a structure, is uncertain.