Robust Real-Time Computations
Mobile agents, such as unmanned aerospace vehicles, are real-time systems that are designed for environments in which the utility of actions is strongly time-dependent. In such applications, the utility of the decisions degrade with the time spent on computation. Uncertain environments will often require quick decisions to be made or introduce complexity in computation that require more time to compute. The degradation in utility due to cost of time will render traditional models of computation useless for mobile agents in uncertain environments. Such scenarios will require the decision procedure to tradeoff decision quality for high utility. Such computation models are called anytime algorithms. In real-time systems, anytime algorithms provide robustness with respect to uncertainty in computational time and complexity.
Anytime algorithms represent a class of algorithms that incrementally improve quality of solution with available computational time. A standard algorithm is an implementation of a mapping from a set of inputs into a set of outputs. For each input that specifies a problem instance there is a particular element in the output set that is considered the correct solution to be generated by the algorithm. An anytime algorithm is an implementation of the mapping from a set of inputs and time allocation into a set of outputs. For each input, there is a corresponding set of possible outputs, each of which is associated with a particular time allocation and some measure of its quality. The advantage of this generalization is that computation can be interrupted at any time and still produce results of a certain quality, hence the name anytime algorithm.
Figure 21 illustrates the characteristics of decision quality with time for ideal, traditional and anytime procedures. In the ideal situation, the best solution is computed instantaneously and does not degrade with time. Traditional algorithms output valid result only after a certain time that does not degrade with time. For anytime procedures, solution quality improves over time with large improvements occurring in the early phases of computation.
Work presented in earlierintroduces the notion of anytime algorithms in the context of control and dynamical systems and studies the tradeoff between robust performance and computational time. We will use and adapt these computational models when implementing various computational tasks. Research along this direction includes formulation of motion planning problems as anytime algorithms; developing computational techniques that guarantee anytime performance; and analyzing the tradeoff between robust performance and computational time for motion planning algorithms.
PIs:: Raktim Bhattacharya
• Control in Computationally Constrained Environments - R. Bhattacharya, G. J. Balas, submitted IEEE Control Systems Technology, 2006.