Planning & Scheduling Group
Overview
The NASA Ames Planning and Scheduling Group (PSG) has developed and demonstrated techniques for automated planning, scheduling, and control. The group has technical expertise in a variety of areas including AI planning, combinatorial optimization, constraint satisfaction, and multi-agent coordination. Additionally, the group has extensive experience delivering planning and scheduling software to NASA missions involving ground, flight, and surface operations across the spectrum of NASA endeavors on Earth, in space, and for planetary exploration.
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.
Planning and Scheduling Flyer
Current Projects
The NASA Ames Planning and Scheduling Group is currently engaged in a number of exciting projects in a wide variety of settings, including space exploration, unmanned flight, and quantum computing.
Activity Planning with Resources for the Exploration of Space (APRES)
Project Lead: John Bresina
Objective: Design and implement the Intelligent Systems Division’s next generation mission planning system for ground operations of spacecraft, rovers, and landers. The APRES system is intended to have the following improvements over deployed mission planning systems:
- Richer domain model representation (ANML)
- Limited forms of uncertainty reasoning
- Richer forms of effects – e.g., (more) continuous effects
- Inclusion of “processes” in addition to activities
- Improved resolution of resource violations
Overview: APRES is intended to be an upgraded replacement of OpenSPIFe with Dynamic Europa, taking advantage of the current state-of-the-art in AI planning & scheduling technology and browser-based interfaces. The initial version of the mission planning system is intended to be a mixed-initiative mission plan editing system with automation support for resource modeling, constraint specification, violation detection, and violation explanation. In later versions of the system, we will add capabilities for mixed-initiative resolution of violations; focusing first on temporal constraints and mutual exclusions (flight rules from the AD), then later, resource constraints. The system will also be enhanced to manage a limited representation of uncertainty in activity duration and resource usage.
Ames Stereo Pipeline (ASP)/AAM
Project Lead: John Kaneshige
Autonomous Systems and Operations (ASO)
Project Lead: Jeremy Frank
Overview: NASA’s Autonomous Systems and Operations (ASO) develops advanced technologies for autonomous operation of spacecraft. Recently, the project conducted an empirical investigation of the impact of time delay on today’s mission operations, and of the effect of targeted organizational changes, processes and mission support tools designed to mitigate time-delay related impacts. The products of this study will be employed to create technologies that will be flight validated as part of experiments onboard the International Space Station, and as part of the upcomng Exploration Flight Test of the Orion capsule.
ASO Software Plan Input Interface
Distributed Spacecraft Autonomy (DSA)
Project Manager: Nicholas Cramer (TI/ACES)
Deputy Project Manager: Jeremy Frank
Overview: Autonomy is a critical need for future spacecraft missions, especially those that will be composed of independent spacecraft that must work in concert in order to accomplish mission goals. Distributed Spacecraft Autonomy (DSA) is a NASA project that enables multi-spacecraft missions by advancing command and control methodologies for commanding a swarm as a collective, maturing autonomous coordination among the swarm members, and developing and demonstrating approaches to distributed decision making and reconfiguration in response to external stimuli.
DSA is composed of a flight demonstration that acts as the primary development and testing environment, and a scalability demonstration that shows that the technologies developed in the flight demonstration are applicable to a diverse range of mission contexts and can scale to swarms with a larger number of assets. The flight demonstration will operate as a software payload on the Starling-1 small-spacecraft mission and use the on-board GPS receiver to perform in-situ, swarm-level reconfiguration in response to observed features in the Topside Ionosphere. Additionally, the scalability demonstration applies the tools developed for the flight mission to a hardware-in-the-loop simulation of a position, navigation, and timing (PNT) constellation in Lunar orbit and composed of up to 100 agents.
Distributed Spacecraft with Heuristic Intelligence to Enable Logistical Decisions (D-SHIELD)
Principal Investigator: Sreeja Nag (R)
Co-Investigator: Richard Levinson
Overview: D-SHIELD is a suite of scalable software tools that helps schedule payload operations of a large constellation, with multiple payloads per and across spacecraft, such that the collection of observational data and their downlink, constrained by the constellation constraints (orbital mechanics), resources (e.g., power) and subsystems (e.g., attitude control), results in maximum science value for a selected use case. Constellation topology, spacecraft and ground network characteristics can be imported from design tools or existing constellations and can serve as elements of an operations design tool. D-SHIELD will include a science simulator to inform the scheduler of the predictive value of observations or operational decisions. D-SHIELD uses scalable autonomy to make satellite constellations more responsive to evolving observables.
HelioSwarm
Formulation Lead: Butler Hine (P)
Missions Operations Lead: John Bresina
Overview: HelioSwarm is a project intended to help improve our understanding of the dynamics of the Sun, and the dynamic space environment with which it interacts with Earth. This project, in particular, would observe the solar wind over a wide range of scales in order to determine the fundamental space physics processes that lead energy from large-scale motion to cascade down to finer scales of particle movement within the plasma that fills space, a process that leads to the heating of such plasma. PSG is currently involved in preliminary Missions Operations work for the HelioSwarm project.
Integrated System for Autonomous and Adaptive Caretaking (ISAAC)
Project Manager: Trey Smith (TI/IRG)
Co-Investigator: Bob Morris
Overview: The Integrated System for Autonomous and Adaptive Caretaking (ISAAC) project will develop key technologies required for autonomous and adaptive caretaking. The project is intended to address the need for autonomous systems to help monitor and maintain exploration spacecraft and habitats during long-duration, deep-space missions. As part of this effort, PSG will be involved in a number of tasks, including the development of autonomous task planning and execution capabilities for Astrobee, as well as exploring options for a distributed architecture (both vehicle-robot and robot-robot) for robot deliberation (planning, scheduling, monitoring) for Gateway.
Intelligent Long Endurance Observing System (ILEOS)
Principal Investigator: Meghan Saephan
Co-Investigators: Jeremy Frank and Rich Levinson
Overview: Existing satellites provide coarse-grained (~ 10 km^2/pixel) data on surface features and column gas concentrations of climate-relevant trace gases. While these data can be supplemented by fine-pointing satellites and aircraft, the spatial and temporal resolution available is not sufficient to observe stochastic, ephemeral events that take place between observations. Emerging High Altitude Long Endurance (HALE) Unmanned Aircraft Systems (UAS) can operate for months at a time and loiter over targets to provide continuous daylight geostationary-like observations, but must be integrated with existing satellites. ILEOS will enable scientists to build plans to improve spatio-temporal resolution of climate-relevant gases by fusing coarse-grained sensor data from satellites and other sources (e.g., terrain, wind forecasts), and plan HALE UAS flights to obtain finer-grain (high spatio-temporal) data. ILEOS will also enable observations for longer periods and of environments not accessible through in-situ observations and field campaigns.
Interface Region Imaging Spectrograph (IRIS) Mission Operations
Mission Operations Lead: Marcie Smith (P)
Mission Operations Staff: Michael Iatauro
Overview: The Interface Region Imaging Spectrograph (IRIS) is a NASA Small Explorer Mission to observe how solar material moves, gathers energy, and heats up as it travels through a little-understood region in the sun’s lower atmosphere. The spacecraft flies at a near Earth orbit and comes into contact with 4 network locations (referred to as a pass). The IRIS mission operations are to prep the satellite for daily command production which executes during the pass by. The ground data systems is responsible for collecting and analyzing the data before packaging the data off to be used for scientific research. Engineers ensure that the communication between the satellite and ground operations are running throughout the week.
Jigsaw
Project Lead: Matthew D’ortenzio
Overview: Jigsaw is a project whose goal is to deconflict individual communication requests from closely related missions. The result is an optimized integrated request that is presented to the Deep Space Network. The testbed for this project involves three CubeSat missions: BioSentinel, Lunar Flashlight, and Near-Earth Asteroid Scout. These will be among several “piggyback” missions carried on the Exploration Mission 1 (EM-1) unmanned test flight of the Space Launch System (SLS) and the Orion capsule, currently scheduled for late 2018.
While the Orion capsule will circle the Moon and return to the Earth, the secondary payload missions will be deployed soon after launch, each with their own objectives and destinations. For the first few days of the mission all of the secondary payloads and the Orion will remain clustered in the same portion of the sky relative to ground-based communications assets. Hence the deployments and any subsequent early-mission critical events will be close together in both space and time, which will present potential conflicts as well as potential synergistic opportunities. The resulting challenging scheduling problem will be addressed by Jigsaw.
National Campaign
Project Lead: Spencer Monheim (A)
Project Member: J. Benton
Overview: The Air Traffic Management – eXploration (ATM-X) project works toward transferring air traffic management systems to safely accommodate growing demand of new air vehicles to enter the airspace to perform a variety of missions. The Urban Air Mobility (UAM) – National Campaign (NC) subproject of ATM-X involves NASA working with industry partners to coordinate airspace simulations with the goal of promoting public confidence and accelerating the realization of emerging aviation markets for transport of passengers and cargo.
Ocean Worlds Autonomy Testbed for Exploration Research & Simulation (OceanWATERS)
Project Lead: Mike Dalal
Overview: OceanWATERS (Ocean Worlds Autonomy Testbed for Exploration Research and Simulation) is a physical and visual simulation of a lander on Europa. It is intended as a testbed to aid in producing autonomy software that could fly on lander missions to ocean worlds, such as Europa and Enceladus.
Quantum Computing and Planning
Project Lead: Eleanor Rieffel
Project Member: Kyle E. C. Booth
Overview: In this joint project with the NASA Quantum Artificial Intelligence Laboratory (QuAIL), we investigate different approaches to utilize quantum computing to solve planning and scheduling problems effectively. First, we conduct both theoretical and empirical evaluations of planning and scheduling problems that can be solved more effectively by a quantum computer than a traditional computer. In particular, NASA-relevant planning problems which have certain properties or local search topology that make them suitable for quantum computing algorithms (quantum annealing in particular). Second, we look for novel hybrid algorithms that combine the advantages of both quantum computing and classical computer algorithms and how to utilize those algorithms to effectively solve existing planning and scheduling problems. Moreover, in the reverse direction, we are also start investigating how existing planning algorithms can be used to solve challenging quantum computing problems such as scheduling for quantum circuit implementations.
Software
The planning and scheduling group develops technologies that are publicly available and used within many of the group’s other projects:
Desktop Exploration of Remote Terrain (DERT)
Project Lead: Leslie Keely-Meindorfer
Source: www.github.com/nasa/dert
DERT is a software tool for exploring large Digital Terrain Models (DTMs) in 3D. It aids in understanding topography and spatial relationships of terrain features, as well as performing simple analysis tasks relevant to the planetary science community. DERT simulates the DTM as a virtual world, attempting to stay true to dimension, light, and color. Using a mouse, the user may freely navigate throughout this world, viewing the terrain from any viewpoint.
Extensible Universal Remote Operations Planning Architecture (EUROPA)
Project Lead: Michael Iatauro
Source: https://github.com/nasa/europa
EUROPA is a framework to model and tackle problems in Planning, Scheduling and Constraint Programming. It has been used in a wide variety of projects within NASA and elsewhere.
Plan Execution Interchange Language (PLEXIL)
Project Lead: Chuck Fry
Source: http://plexil.sourceforge.net/
PLEXIL is a language for representing plans for automation, accompanied by an execution engine (executive) that implements efficiently the PLEXIL language and can provide interfaces to controlled systems as well as decision support systems.
Ocean Worlds Autonomy Testbed for Exploration Research and Simulation (OceanWATERS)
Project Lead: Mike Dalal
Source: https://github.com/nasa/ow_simulator
OceanWATERS is a physical and visual simulation of a lander on Europa. It is intended as a testbed to aid in producing autonomy software that could fly on lander missions to ocean worlds, such as Europa and Enceladus. The ow_simulator is the top level repository for OceanWATERS. It primarily contains ROS/Gazebo packages related to visual and physical simulation for OceanWATERS.
Open Scheduling and Planning Interface for Exploration (OpenSPIFe)
Project Lead: John Bresina
Source: OpenSPIFe Home
OpenSPIFe is now an open source framework available on NASA GitHub. SPIFe is an integrated planning and scheduling toolkit based on hundreds of hours of expert observation, use, and refinement of state-of-the-art planning and scheduling technology for several NASA missions; which includes the Mars Exploration Rover, the Phoenix Mars Lander, and the Mars Science Laboratory. It has also been adapted as preflight planning and a real-time analysis console tool that supports all phases of planning on the International Space Station (ISS), as well as several other flight projects and analogs.
Team
Group Lead
Jeremy Frank
Group Members
Abiola Akanni
J. Benton
Kyle Booth
John Bresina
Michael Dalal
Minh Do
Matthew Dortenzio
Chuck Fry
Michael Iatauro
John Kaneshige
Elif Kurklu
Rich Levinson
Paul Morris
Robert Morris
Samantha Niemoeller
Christian Plaunt
Meghan Saephan
Alumni
Andrew Bachmann
Javier Barreiro
Tania Bedrax-Weiss
Alfredo Bencomo
Matt Boyce
John Chachere
Keith Golden
Kevin Greene
Bobby Grewal
Ari Jonsson
Dhananjay Joshi
Bob Kanefsky
Leslie Keely-Meindorfer
Melissa Ludowise
Conor McGann
Nicola Meuleau
Nicola Muscettola
Bob Nado
Kanna Rajan
Sailesh Ramakrishnan
Sudhakar Reddy
David Rijsman
Michael Scott
David Smith
Tristan Smith
Brian Yu
Thomas Stucky