Online Planning Algorithm

Sunday, August 01 2010

AVA v2 software selects goals for execution from a set of goals that oversubscribe shared resources. The term “goal” refers to a science or engineering request to execute a possibly complex command sequence, such as image targets or ground-station downlinks.

Developed as an extension to the Virtual Machine Language (VML) execution system, the software enables onboard and remote goal triggering through the use of an embedded, dynamic goal set that can oversubscribe resources. From the set of conflicting goals, a subset must be chosen that maximizes a given quality metric, which in this case is strict priority selection. A goal can never be preempted by a lower priority goal, and high-level goals can be added, removed, or updated at any time, and the “best” goals will be selected for execution.

The software addresses the issue of re-planning that must be performed in a short time frame by the embedded system where computational resources are constrained. In particular, the algorithm addresses problems with well-defined goal requests without temporal flexibility that oversubscribes available resources. By using a fast, incremental algorithm, goal selection can be postponed in a “just-in-time” fashion allowing requests to be changed or added at the last minute. Thereby enabling shorter response times and greater autonomy for the system under control.

This work was done by Gregg R. Rabideau and Steve A. Chien of Caltech for NASA’s Jet Propulsion Laboratory.

This software is available for commercial licensing. Please contact Daniel Broderick of the California Institute of Technology at This e-mail address is being protected from spambots. You need JavaScript enabled to view it . Refer to NPO-46503.