---
title: "Deadline Compliance, Predictability, and On-line Optimization in Real-Time Problem Solving"
authors:
  - "Babak Hamidzadeh"
  - "Shashi Shekhar"
doi: ""
url: "https://ijcai.org/proceedings/1995/29"
pdf: "https://ijcai.org/proceedings/1995/0029.pdf"
venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence"
year: 1995
pages: "220-225"
track: "Automated Reasoning"
keywords:
---

# Deadline Compliance, Predictability, and On-line Optimization in Real-Time Problem Solving

Babak Hamidzadeh, Shashi Shekhar

*Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 220-225.

## Abstract

Real-time algorithms need to address the time constraints (e.g. deadlines) imposed by applications like process control and robot navigation. Furthermore, dependable realtime algorithms need to be predictable about their ability to meet the time constraints of given tasks. A real-time algorithm is predictable, if it can decide the feasibility of meeting time constraints of a given task or an arbitrary task from a task set well ahead of the deadline. Lastly, a real-time algorithm should exhibit progressively optimizing behavior (i.e. the quality of the solution produced should improve as time constraints are relaxed). We propose a new algorithm, SARTS, that is based on a novel on-line technique to choose the proper values of parameters which control the time allocated to planning based on the time constraints. SARTS also provides criteria to predict its ability to meet the time constraints of a given task. The paper provides theoretical and experimental characterization of SARTS as a dependable real-time algorithm.