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

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.