TUFs in Space: The Science of Dynamic and Adaptive Scheduling

---

May 2004

A conceptual artist's sketch of the Mars Science Laboratory, scheduled to be launched by NASA as early as 2009.

The Mars Science Laboratory hunkers down in a shallow basin at the foot of Olympus Mons, the largest volcano in the solar system. The lab's telescopic arm snakes back with a sample from a long-dead lava flow. Its alpha particle x-ray spectrometer finishes its elemental analysis of the soil underfoot. A last microscopic study is taken of the grain angularity of a nearby rock outcropping. Its schedule of experiments successfully completed, the lab prepares to roll off to its next staging area.

But before the lab can be on its way, a tempest descends. A dust devil, five miles high, spirals out of the nearby Amazonis Planitia. It lurches past Olympus Mons, showering the laboratory with particles and debris. In its wake, the devil leaves the basin floor covered with a thick layer of fine red dust. As the lab attempts to roll up the slope of the basin, its wheels spin in the dust. The lab is forced to tack its way up the slope to gain the necessary traction. By the time its reaches the top of the slope, the lab has consumed twice as much of its reserve energy as it had budgeted for the ascent. Yet the lab is still scheduled before the end of the day to reach its next site, analyze the lava sample, compile the day’s data, and download it back to Earth.

The lab doesn't have the resources to complete all those tasks at the desired times, if at all. It must abandon some and reprioritize the others. It will need to inform Mission Control of its dilemma and then sit idle, squandering precious time, as mission technicians reconfigure its programming and broadcast the changes back to the laboratory across the 100 million-mile stretch of space.

Or Will It?

The new Mars Science Laboratory, which NASA plans to launch as early as 2009, may have greater "thinking powers." While today the missions are programmed in advance with a detailed sequence of tasks and deadlines, a mission as complex as that of the 2009 Mars Science Laboratory will require that the rover be able to evaluate the priorities of the requested goals and develop its own schedule to meet them as best possible under the circumstances. MITRE and the NASA Jet Propulsion Laboratory are currently investigating the employment of Time-Utility Functions (TUFs) to enable the laboratory to autonomously determine the most efficient sequence of actions to meet its mission goals.

E. Douglas Jensen, a Consulting Scientist in MITRE's Center for Air Force C2 Systems, is recognized as one of the original pioneers and leading visionaries of real-time computing and the inventor of TUFs scheduling. "In the real world," explains Jensen, "the assumptions that tasks can only be scheduled by deadlines and that you must meet every deadline are simply false in virtually every non-trivial case."

Taken to Task

Jensen uses as an example the "task" of attending a customer meeting. If you arrive at the meeting five minutes late or five minutes early, it will affect the quality of the meeting very little. But if you arrive a half-hour early, the conference room door may be locked, and if you arrive a half-hour late, your customer may have already left the conference room in a huff.

So the utility of the task "Attend Customer Meeting" is not affected by the deadline assigned to that task: missing the deadline by five minutes does not lower the utility of the meeting to zero. However, the utility of the meeting can be affected by the "earliness" or "lateness" of the task: the greater the "earliness" or "lateness," the less the utility.

By replacing the deadlines in a system's programming, TUFs allow tasks to be scheduled based on the utility the task is expected to contribute to the system. A processing system performing tasks based on deadlines is faced with such instructions as "Finish Task A and then finish Task B and then finish Task C." However, such scheduling handcuffs a system: if there are not enough resources to finish Task A, the system never gets to Tasks B and C. Because systems such as the Mars Science Laboratory need to be dynamic, their scheduling cannot usually be pre-planned.

A processing system performing tasks based on TUFs is faced with such instructions as "Complete Tasks A, B, and C in such a way that Task A provides 100 percent of its expected utility, Task B provides at least 85 percent of its expected utility, Task C provides at least 50 percent of its expected utility, and the sum utility of the three tasks is maximized." The system now has the autonomy to appraise the resources on hand to schedule its tasks. It can react to an unanticipated deficit in resources or overload of tasks by abandoning, scaling back, or deferring goals. Likewise, an unanticipated surplus of resources or task underload might enable the system to perform, enhance, or accelerate high-utility tasks initially deemed too costly.

The advantages of such autonomous scheduling are obvious. The trouble, Jensen explains, is that scheduling based on deadlines is much better understood than scheduling based on utility. Jensen is attempting through several MITRE projects to display the advantages of replacing limited and inflexible deadline algorithms with powerful and adaptable TUF-based algorithms.

TUF Enough for the Field

In one MITRE field study, TUF-based scheduling was integrated into the tracker of an airborne warning and control system (AWACS) aircraft surveillance mission. AWACS aircraft are charged with detecting airborne objects and then tracking them. However, trackers may become overloaded when the number of targets exceeds the available computing power. An overloaded tracking system may "drop" a target if the system does not have enough resources to update its track database often enough. The utilization of TUFs allows the tracking system to assign the right tracking resources to the right targets at the right time.

Another field study probed the use of TUFs in a cruise missile defense system. The system is charged as part of its mission with destroying enemy cruise missiles using guided interceptor missiles. However, the system faces many challenges. The number of enemy missiles and decoys may outnumber the available interceptors, or insufficient computational resources may prevent interceptor missiles from closing in closely enough on targets to destroy them. A defense system might dedicate its limited resources to targets that do not pose the greatest threat or may fail to provide guidance updates to an interceptor before it has achieved a final lock on its target. The use of TUFs allows the defense system to continuously update the priority of targets and allocate its resources accordingly.

Years from now on a red planet millions of miles away, the Mars Science Laboratory will assess its resources and weigh its goals and then will decide for itself the most effective way to carry out its mission. And back at home, E. Douglas Jensen and MITRE will continue to advance the state-of-the-art in dynamic, adaptive scheduling systems.

—by Christopher S. Lockheardt

---

Related Information

Websites

• E. Douglas Jensen's "Real-time for the Real World"
• National Aeronautics and Space Administration (NASA)

Page last updated: August 10, 2004 | Top of page