NASA Spinoff

Scheduling Software for Complex Scenarios

Preparing a vehicle and its payload for a single launch is a complex process that involves thousands of operations. Because the equipment and facilities required to carry out these operations are extremely expensive and limited in number, optimal assignment and efficient use are critically important. Overlapping missions that compete for the same resources, ground rules, safety requirements, and the unique needs of processing vehicles and payloads destined for space impose numerous constraints that, when combined, require advanced scheduling.

Traditional scheduling systems use simple algorithms and criteria when selecting activities and assigning resources and times to each activity. Schedules generated by these simple decision rules are, however, frequently far from optimal. To resolve mission-critical scheduling issues and predict possible problem areas, NASA historically relied upon expert human schedulers who used their judgment and experience to determine where things should happen, whether they will happen on time, and whether the requested resources are truly necessary.

Partnership

NASA selected Stottler Henke Associates, Inc., a software design firm with a long history of solving NASA’s unique dilemmas, to capture and encode the knowledge embodied by these human experts. Located in San Mateo, California, the company is a leader in innovative artificial intelligence software applications. For this project, the company was contracted through a Small Business Innovation Research (SBIR) award facilitated by Kennedy Space Center.

As a result of the partnership, Stottler Henke developed Aurora, an intelligent planning and scheduling system that enables NASA to solve complex scheduling problems quickly, by encoding and applying sophisticated, domain-specific decision-making rules.

The proof-of-concept prototype was completed in the summer of 2001, and the Aurora scheduling system entered operational use at Kennedy in late 2003. It is being used to schedule the use of floor space and other resources at the Space Station Processing Facility, where International Space Station components are prepared for space flight. Aurora is also at the core of a system that generates short- and long-term schedules of the ground-based activities that prepare space shuttles before each mission and refurbish them after each mission. This system replaced the Automated Manifest Planner, also developed by Stottler Henke and used by NASA since 1994.

The software Stottler Henke designed for NASA applies a combination of artificial intelligence techniques to produce a system capable of rapidly completing a near-optimal schedule. It combines sophisticated scheduling mechanisms with domain knowledge and a bevy of expert conflict-resolution techniques to solve scheduling problems. It also takes into account a number of problems unique to Kennedy, such as the need to schedule floor space and maintain certain spatial relationships among the tasks and components. Aurora then graphically displays resource use, floor space use, and the spatial relationships among different activities. Scheduling experts can interactively modify and update the schedule, and can request detailed information about specific scheduling decisions. This allows them to supply additional information or verify the system’s decisions and override them, if necessary, to resolve any conflicts.

The company has modified the software and released it as a commercial scheduling tool that is usable in non-NASA situations, allowing the general public to solve a plethora of industry scheduling problems.