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:
- Enables: A prerequisite relationship where one task must complete before another can begin.
- 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.
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.
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