Online Planning Algorithm
- Created on Sunday, 01 August 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.