An Analysis of Time-Dependent Planning

Thomas L. Dean, Mark S. BoddyAAAI 1988

Abstract

This seminal 1988 paper introduces the concept of anytime algorithms—computational processes that can be interrupted at any moment to provide a solution whose quality improves with the time invested. It provides a formal framework for "deliberation scheduling," allowing robots and autonomous systems to maximize their utility when the time available to "think" before acting is unpredictable.

Introduction

In traditional computer science, performance is typically measured by two metrics: correctness and execution time. However, in real-world robotics—such as a robot sorting items on a fast-moving conveyor belt—a "correct" answer that arrives even a second too late is worthless. The authors identify a significant gap in planning theory regarding time-dependent planning. This occurs when the time available to respond to an event varies (e.g., objects appearing at irregular intervals) and the decision-making process is complex.

Standard algorithms are often "all-or-nothing," but a robot in a time-crunch needs to be able to trade off computation time for result quality. This paper seeks to move beyond simple approximation algorithms toward a system that can manage its own "thinking time" as a scarce resource, treating deliberation as an action that must be scheduled just like physical movements.

The Anytime Framework

The authors propose a framework built on three pillars:

  1. Anytime Algorithms: These are algorithms characterized by three traits: they are preemptible with negligible overhead, they can be terminated at any time to return an answer, and the quality of that answer is a well-behaved function of time.
  2. Performance Profiles: These map the utility of an algorithm's output to the time spent on computation. The authors categorize how utility grows over time into several classes.
  3. Deliberation Scheduling: This is the "meta-reasoning" component. Given a set of pending events and a single processor, the system must decide how to allocate "thinking time" across different tasks to maximize the total expected utility.

Performance Profiles

A critical component of the framework is the performance profile, which allows the system to predict the benefit of allocating additional processor time to a specific task. The authors define five classes of profiles, ranging from "one-shot" (all-or-nothing) to "diminishing returns."

Taxonomy of performance profiles showing different utility growth patterns over time, including step functions (ii), linear improvement (iii), and plateauing functions (iv).

These profiles are essential for the deliberation scheduler to make informed decisions about where "extra thought" provides the most value.

Deliberation Scheduling and Key Insights

The paper includes a polynomial-time algorithm for scheduling deliberation when the tasks exhibit diminishing returns. In these cases, an optimal strategy involves "time-slicing" the processor to ensure the marginal utility of computation is equalized across all pending tasks.

The diminishing returns performance profile (v), where the most significant improvements occur early in the computation.

The authors argue that for time-dependent planning to be effective, algorithms with the "diminishing returns" profile are ideal. This allows the system to have a "safe" default reaction almost immediately, which then improves as more time is invested. The goal shifts from finding the perfect plan to finding the best possible plan given the current temporal constraints.

Implementation and Results

The paper successfully formalizes the components of time-dependent planning: prediction time, deliberation time, and reaction time. The authors demonstrate a high-level implementation of a time-dependent planner using a specification language based on Prolog, proving the framework can be integrated into existing logical reasoning systems. While the paper uses a conceptual "conveyor belt robot" example rather than modern benchmark datasets, it establishes the mathematical requirements for managing deliberation as a resource.

Limitations and Future Work

Despite its foundational contributions, the model has several limitations:

  • Preemption Costs: It assumes that stopping and starting a "thought" costs nothing, whereas real systems face context-switching overhead.
  • Interdependent Events: The current scheduling logic assumes reactions to different events are independent. Relaxing this assumption significantly increases complexity.
  • Uncertainty: The paper assumes the robot knows exactly when events will happen, which is rarely the case in dynamic environments.

Future work involves building a library of generic anytime algorithms for tasks like pathfinding and object recognition, and extending the framework to handle greater environmental uncertainty.

Summary updated

BibTeX
@inproceedings{dean1988analysis,
  author = {Thomas L. Dean and Mark S. Boddy},
  title = {{An Analysis of Time-Dependent Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure