Task Interdependencies in Design-to-time Real-time Scheduling

Alan Garvey, Marty Humphrey, Victor R. LesserAAAI 1993

Abstract

Real-time AI systems often face the challenge of scheduling tasks with unpredictable durations and complex interdependencies. This paper introduces a "design-to-time" scheduler capable of handling relationships such as "enables" and "hinders" between tasks. By utilizing a recursive pruning engine, the scheduler maintains computational efficiency, demonstrating polynomial-time performance in practice despite the underlying NP-hard nature of the problem.

Introduction

In real-time AI, predictability is difficult to achieve because search-based techniques often have variable execution times. To manage this, researchers frequently employ approximation methods—choosing between different versions of an algorithm that offer various speed and quality tradeoffs. However, traditional schedulers often assume task independence, ignoring the reality that AI subproblems are deeply intertwined.

Two primary interdependencies addressed are:

  1. Enables: A prerequisite relationship where one task must complete before another can begin.
  2. Hinders: A negative interaction where a low-quality or "quick" version of one task increases the duration or decreases the quality of a subsequent task.

The goal is to find a combination of task methods that maximizes total quality within a strict deadline.

Methodology

The proposed Design-to-time Scheduler operates on the principle that all available time should be used to produce the highest quality result possible.

Task Modeling and Relationships

Tasks are organized into hierarchical trees. Quality is aggregated using functions like MIN (requiring all subtasks) or MAX (selecting the best subtask). The algorithm explicitly models how constraints like "hinders" affect the duration and quality of downstream tasks.

A sample task structure showing hierarchical decomposition and interdependencies.

Pruning and Complexity Management

The core of the scheduler is a recursive pruning engine. It explores possible task solutions but immediately discards (prunes) any method that is strictly inferior—meaning it is both slower and produces lower quality—than another available option. This local decision-making prevents an exponential explosion of the search space. Furthermore, "clustering" or discretizing quality values into small integers helps group similar alternatives, making pruning more effective.

Evaluation and Results

The scheduler was evaluated using simulated task structures modeled after the Distributed Vehicle Monitoring Testbed (DVMT). Variables such as branching factors and the frequency of "enables" vs. "hinders" relationships were controlled to test scalability.

Scalability and Performance

The empirical results indicate that the scheduler's average runtime increases polynomially with the number of executable methods. This suggests that the pruning techniques are highly effective at managing complexity in typical AI task structures.

Scheduler runtime as a function of the number of executable methods.

Additionally, the runtime increases only logarithmically with the number of distinct quality values. This confirms that "bucketizing" quality is a viable strategy for trading off scheduling precision for significant gains in speed.

Discussion and Future Work

While the scheduler is efficient, it relies on the assumption that task durations and qualities are relatively predictable. If performance is highly stochastic, the generated schedules may fail. Currently, the model is limited to acyclic relationships and does not yet handle "facilitates" relationships (where one task makes another easier but is not strictly required).

Future research aims to extend this framework to distributed multi-agent systems and to develop "meta-scheduling" capabilities, where the scheduler can manage its own computational overhead as a design-to-time task itself.

Summary updated

BibTeX
@inproceedings{garvey1993task,
  author = {Alan Garvey and Marty Humphrey and Victor R. Lesser},
  title = {{Task Interdependencies in Design-to-time Real-time Scheduling}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure