Interruptible Algorithms for Multi-Problem Solving

Spyros Angelopoulos, Alejandro López-OrtizIJCAI 2009 · OpenReview

Abstract: In this paper we address the problem of designing an interruptible system in a setting in which $n$ problem instances, all equally important, must be solved. The system involves scheduling executions of contract algorithms (which offer a trade-off between allowable computation time and quality of the solution) in $m$ identical parallel processors. When an interruption occurs, the system must report a solution to each of the $n$ problem instances. The quality of this output is then compared to the best-possible algorithm that has foreknowledge of the interruption time and must, likewise, produce solutions to all $n$ problem instances. This extends the well-studied setting in which only one problem instance is queried at interruption time. We propose a schedule which we prove is optimal for the case of a single processor. For multiple processors, we show that the quality of the schedule is within a small factor from optimal.

Introduction

In real-time AI applications, such as medical diagnosis or automated trading, the exact time available for computation is often unknown until an interruption occurs. This necessitates the use of interruptible algorithms, which can provide a valid solution at any moment, improving in quality over time. These are often constructed from contract algorithms, which require a pre-specified running time and yield no result if interrupted early.

A standard technique for this conversion involves running a sequence of increasingly longer contracts. Traditionally, performance is measured by the "acceleration ratio," comparing the interruptible algorithm's performance to an ideal offline algorithm that knows the deadline in advance. However, previous research has largely focused on solving a single problem instance. This paper expands the scope to the multi-problem setting, where $n$ problems must be solved simultaneously using $m$ parallel processors.

The Deficiency Metric

The authors argue that the traditional acceleration ratio is unsuitable for multi-problem environments because it allows the ideal offline algorithm to "cheat" by dedicating all resources to a single problem. To address this, they introduce a new metric called deficiency. Deficiency compares the quality of the least-developed problem in the interruptible schedule against the least-developed problem in an ideal offline schedule that also must provide solutions for all $n$ instances by time $t$.

3D visualization of deficiency (def) across varying numbers of processors (m) and problem parameters (p).

By requiring the offline comparison to be "fair"—i.e., making progress on all tasks—deficiency provides a more meaningful performance bound for multi-tasking systems. As shown in Figure 2, the deficiency metric varies predictably across different system configurations.

Methodology: Cyclic Exponential Scheduling

To minimize deficiency, the paper proposes a Cyclic Exponential Schedule. This strategy relies on two main components:

  1. Round-Robin Assignment: Problems are assigned to the $m$ processors in a fixed, repeating sequence.
  2. Geometric Growth: Each time a specific problem is revisited, the length of the contract increases exponentially (e.g., $b^k, b^{k+1}, \dots$).

The authors provide a mathematical framework to determine the optimal base $b$ for this exponential growth, ensuring the system remains robust regardless of when the interruption occurs.

Results and Analysis

The proposed schedule demonstrates strong performance across various configurations:

  • Single Processor ($m=1$): The cyclic exponential schedule is proven to be strictly optimal, with a closed-form deficiency of $\frac{(n+1)^{n+1}}{n^n}$.
  • Multi-Processor ($m > 1$): For cases where $n > m$, the deficiency is bounded by approximately 3.74. If $n \le m$, the deficiency is at most 4.
Performance (deficiency) as a function of the ratio of problems to processors (n/m).

A key insight is that the system's relative performance improves as the problem density increases. As illustrated in Figure 1, as the ratio of problems to processors ($n/m$) grows, the deficiency decreases and approaches a constant value (approximately 2.75 in the plotted range), indicating that the schedule becomes more efficient in high-load scenarios.

Conclusion

This work provides a robust theoretical foundation for anytime multi-problem solving. By introducing the deficiency metric and proving the near-optimality of cyclic exponential schedules, the authors offer a practical approach to parallel real-time computation. Future work may explore settings where only a subset of problems is queried at interruption or apply these findings to multi-agent robotics and search problems.

Summary updated

Abstract

In this paper we address the problem of designing an interruptible system in a setting in which n problem instances, all equally important, must be solved. The system involves scheduling executions of contract algorithms (which offer a trade-off between allowable computation time and quality of the solution) in m identical parallel processors. When an interruption occurs, the system must report a solution to each of the n problem instances. The quality of this output is then compared to the best-possible algorithm that has foreknowledge of the interruption time and must, likewise, produce solutions to all n problem instances. This extends the well-studied setting in which only one problem instance is queried at interruption time. We propose a schedule which we prove is optimal for the case of a single processor. For multiple processors, we show that the quality of the schedule is within a small factor from optimal.
BibTeX
@inproceedings{angelopoulos2009interruptible,
  author = {Spyros Angelopoulos and Alejandro López-Ortiz},
  title = {{Interruptible Algorithms for Multi-Problem Solving}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=ryb_4rGObS},
}
Figure