NASA Logo, National Aeronautics and Space Administration

Background

Planning and scheduling problems are pervasive in NASA ground and flight operations. Examples include:

  • Scheduling of crew training facilities
  • Scheduling activities aboard the International Space Station
  • Scheduling of Deep Space Network communications
  • Planning daily activities of rovers such as the Mars Exploration Rovers
  • Planning activities of spacecraft such as Deep Space 1
  • Science operations planning for UAVs
  • Emergency planning for damaged aircraft

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:

  • Complex temporal constraints – Many activities like communication can only be done during certain time windows, while 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.
  • Control – The resulting plan may be executed autonomously.

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.

Capability Overview

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). 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.

Limited Resources

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.

Over-subscription and optimization

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.

Uncertainty

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).

Control

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.

Integration

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.

Applications to NASA Missions

For the Exploration Technology Development Program (ETDP), Ames develops advanced prototypes of planning and scheduling applications for future human spaceflight mission operations tasks such as crew planning, power planning, and mixed initiative crew procedure operation.

For the Space Operations Mission Directorate, Ames has developed the Solar Array Constraint Engine (SACE) for managing ISS solar arrays, and is developing the Power Planning and Analysis Tool (PLATO) to perform ISS power plan analysis. Ames is also working on the Next Generation Planning System (NGPS), which will be used to schedule crew time for ISS.

For the Science Mission Directorate, Ames prototyped an automated flight planner for the SOFIA astronomical observatory. Projects are ongoing to create decision support tools for coordination of satellite and aircraft-based remote sensing assets.

For the Mars Technology Program, Ames technology was developed for the Phoenix and LCROSS missions, and is being developed for the Mars Science Lander. MAPGEN is in daily use for generating command sequences for the ongoing Mars Exploration Rovers mission.

For the Aeronautics Research Mission Directorate, Ames is developing a pilot aid to guide a damaged or degraded aircraft to a safe landing spot as part of work performed under the Intelligent Resilient Aircraft Project, and is developing a prototype integrated rotorcraft control architecture.

Team

Group Lead
Jeremy Frank

Group Members
Alfredo Bencomo
John Bresina
John Chachere
Michael Dalal
Minh Do
Chuck Fry
Michael Iatauro
Bob Kanefsky
Leslie Keely-Meindorfer
Elif Kurklu
Paul Morris
Robert Morris
Christian Plaunt
David Smith
Tristan Smith
Brian Yu

Alumni
Andrew Bachmann
Javier Barreiro
Tania Bedrax-Weiss
Matt Boyce
Keith Golden
Kevin Greene
Bobby Grewal
Ari Jonsson
Dhananjay Joshi
Melissa Ludowise
Conor McGann
Nicolas Meuleau
Nicola Muscettola
Bob Nado
Kanna Rajan
Sailesh Ramakrishnan
David Rijsman

News & Updates
Division Proposal Submission
ICAPS 2014
code.NASA

First Gov logo
NASA Logo - nasa.gov