Composing Real-Time Systems

1 Introduction

Our objective in this research has been to develop and automate a methodology for the construction of utility­ driven, real-time agents. A real-time agent is an agent whose utility function depends on time. For example, a utility function defined as the number of widgets as­ sembled per hour depends on time; a robot designed to maximize this utility function is a real-time agent . Simi­ larly, problems such as chess-playing, reentry navigation for a space shuttle, financial planning and trading, and medical monitoring in an intensive care unit have util­ ity functions that depend on time, and therefore require the construction of real-time systems. This approach generalizes the traditional view of real-time systems as systems that can guarantee a response after a fixed time has elapsed [Laffey et al., 1988], in that deadlines can be expressed by a sharp drop in the utility function .

We show in this paper how to construct real-time sys­ tems using anytime algorithms 1 as basic blocks. Any­ time algorithms are algorithms whose quality of re­ sults degrades gracefully as computation time decreases, hence they introduce a tradeoff between computation time and quality of results. The algorithm's perfor­ mance profile (PP) gives a probabilistic description of the quality of results as a function oftime (we define and generalize this notion in section 2) . For example, con­ sider a hierarchical diagnosis algorithm that recursively performs a test to identify the defective component of an assembly. This algorithm can be interrupted at any time to produce a partial diagnosis whose quality can be measured by the level of specificity. By translating the quality of results into a utility measure that takes into account the time needed to produce these results, we can compute the optimal amount of time that should be allocated to diagnosis, after which a complete defective component should be replaced rather than being further analyzed. A similar technique was used by Boddy and Dean [1989) for solving a real-time path planning prob­ lem and by Horvitz (1987) for real-time decision making in the health care domain.

An important distinction that has to some extent been ignored in the literature should be made between inter­ ruptible algorithms and contract algorithms. Interrupt­ ible algorithms produce results of the 'advertised qual­ ity' even when interrupted unexpectedly; whereas con­ tract algorithms, although capable of producing results whos~ quality varies with time allocation, must be given a particular time allocation in advance. If a contract algorithm is interrupted at any time shorter than the contract time it may yield no useful results. An impor­ tant result of this paper, given in section 2, shows that there is in fact a simple reduction from interruptible al­ gorithms to contract algorithms.

In this work we extend the use of anytime algorithms to the construction of complex real-time systems. It is unlikely that a complex system will be developed by im · plementing one large anytime algorithm. Systems ar( normally built from components that are developed and tested separately. In standard algorithms, the quality of the output is fixed, so composition can be implemented by a simple call-return mechanism. However, when algo­ rithms have resource allocation as a degree of freedom, there arises the question of how to construct, for exam­ ple, the optimal composition of two anytime algorithms, one of which feeds its output to the other. Consider mak­ ing a repair system from a 'diagnosis' component and a 'therapy' component. The more time spent on diagno­ sis, the more likely the hypothesis is to be correct. The more time spent on therapy planning, the more likely the problem is to be fixed, assuming the diagnosis is correct. Given the performance profiles of the two sub­ systems (as shown in Figure lab), it is straightforward to construct the optimal apportionment of resources for a given total allocation, and hence to construct the op­ timal anytime algorithm for the whole problem (whose performance profile is shown in Figure lc).

1 Dean and Boddy [1988] coined the term "anytime algo­ rithm" in their paper on time-dependent planning.

To summarize, in our approach the user specifies the structural decomposition of a complex problem into ele­ mentary performance components, each of which can be a traditional or an anytime algorithm. For example, the repair system might be specified as:

Our system generates an anytime algorithm for the original problem by scheduling and monitoring the com­ ponents in an optimal way (with respect to a given utility function). The rest of this paper describes this method in detail. In Section 2 we define the probabilistic descrip­ tion of the performance of anytime algorithms and exam­ ine their essential properties. In Section 3 we present a framework for evaluating anytime algorithms within the context of a given domain and a utility function . In Sec­ tion 4 we explain and demonstrate the task of compiling anytime algorithms. Finally, Section 5 summarizes the benefits of our approach and discusses related work and further work to be undertaken.

2 Anytime algorithms

Anytime algorithms are characterized by their perfor­ mance profile (PP), a probabilistic description of the quality of results as a function of time. The exact mean­ ing and concrete representation of a PP is implemen­ tation dependent. In this section we define three types of PP and explain the basic properties of anytime algo­ rithms.

2.1 Performance profiles

A PP maps computation time to a probabilistic descrip­ tion of the quality of the results. The main reason for the uncertainty concerning the quality of results (especially with deterministic algorithms) is the fact that the input to the algorithm is unknown. Therefore, a PP should always be interpreted with respect to a particular prob­ ability distribution of input.

Given an anytime algorithm A, let 9A(z, t) be the quality of results produced by A with input :c and com­ putation timet; let 9A(t) be the expected quality of re­ sults with computation time t; and let PA,c(q) be the probability (density function in the continuous case) that A with computation timet produces results of quality q. A complete description of the performance of A is given by the following definition:

Definition 2.1 The performance distribution pro­ file (PDP), of an algorithm A is a function DA : n+ - Pr('R) that maps computation time to a probability distribution of the quality of the results.

In some cases the summation over all possible inputs may produce too wide a range of qualities and the infor­ mation provided by the PP may be too general. In that case we use conditional PPs by partitioning the input domain into classes and storing a separate PP for each class (this partitioning is done using any attribute of the input, such as size or a complexity measure) .

Definition 2.2 The expected performance profile (PEP), of an algorithm A is a function EA : n+ - 'R that maps computation time to the expected quality of the results.

Note that EA(t) = LqPA,c(q)q = E.,Pr(:c)qA(:c,t) . This is exactly what Dean and Boddy (1988] used as a performance profile.

Definition 2.3 The performance interval profile (PIP), of an algorithm A is a function lA : n+ - 'R. x 'R. that maps computation time to the upper and lower bounds of the quality of the results.

Note th~t if IA(t) = (L, U] then 'V:c: L $ 9A(:c,t) $ U. The quality of results described by a PP is measured in one of the following ways:

• I . Certainty - Probability of correctness determines quality (e.g. randomized algorithms for primality testing) .
• Accuracy - Error bound determines quality (e.g. Newton's method).
• Specificity - Amount of detail determines quality (e.g. hierarchical diagnosis).

While accuracy is typically used to measure quality in numerical domains, and specificity in symbolic do­ mains, the former can be seen as a special case of the latter; an inaccurate numerical solution is very specific but incorrect, and could be mapped to an equally useful, correct statement that the solution lies within a certain interval. Anytime algorithms can also have multidimen­ sional quality measures, for example PAC algorithms for inductive learning are characterized by an uncertainty measure 6 and a precision measure £.

2.2 Elementary anytime algorithms

Elementary anytime algorithms are already widely avail­ able, contrary to popular supposition. Many exist­ ing general programming and reasoning techniques pro­ duce useful anytime algorithms: search techniques such as iterative deepening; asymptotically correct infer­ ence algorithms such as approximate query answer­ ing [Elkan, 1990; Vrbsky et a/., 1990], bounded cutset conditioning (see [Horvitz, 1987]), and variable preci­ sion logic [Michalski and Winston, 1986]; various greedy algorithms (see [Boddy and Dean, 1989]); iterative meth­ ods such as Newton's methodi adaptive algorithms such as PAC learning algorithms LHaussler, 1990] or neural networks; Monte Carlo algorithms for simulating proba­ bilistic models; and the use of optimal meta-level control of computation [Russell and Wefald, 1989].

2.3 Interruptible vs contract algorithms

As mentioned in section 1, we distinguish between two types of anytime algorithms. Interruptible algorithms are those whose run-time need not be determined at the time of activation. They can be interrupted at any time to yield results whose quality is characterized by their PP. Many of the elementary anytime algorithms men­ tioned above, such as iterative deepening algorithms, are interruptible. Contract algorithms require a specific time allocation when activated. For example, Korf's RTA · [1988] performs a depth-first or best-first search within a predetermined search horizon that is computed from the time allocation provided, and can therefore modeled as a contract algorithm. Although this algo­ rithm can produce results for any given time allocation , if it is interrupted before the expiration of the allocation it may yield no results.

Every interruptible algorithm is trivially a contract algorithm, however the converse is not true. In general , the greater freedom of design makes it easier to construct contract algorithms than interruptible ones. The follow­ ing theorem is therefore essential for the compilation of interruptible algorithms.

Theorem 1 For any contract algorithm A, an in­ terruptible algorithm B can be constructed such tkat qa(4t) ~ q_.t(t) .

Proof: Construct B by running A repeatedly with exponentially increasing time limits. Let the sequence of run-time segments be T, 2T, ... , 2iT, ... , and assume that the code required to control this loop can be ignored. Note also that L::~~-l 2i = 2n - 1. The worst case occurs when B is interrupted after almost (2n -l)T time units, just before the last iteration terminates and the returned result is based on the previous iteration with a run-time of 2n- 2 T time units. Since ~::J < 4, we get the factor of 4. If we replace the multiplier of time intervals by a we get a time ratio of: 0 .~t_- 01 1 ._ 2 · The lower bound of this expression is 4, for a = 2, hence the above sequence of run-times is optimal 2 .

2 This factor can obviously be reduced by scheduling the contract algorithm on multiple processors. The parallel scheduling options are non-trivial, and are not discussed in this paper.

··

Figure 2: PP of the constructed interruptible algorithm

Note that T may be arbitrarily small and should be in general the shortest run-time for which there is a signif­ icant improvement in the results of A.

Figure 2 shows a typical performance profile for the contract algorithm A, and the corresponding perfor­ mance profile for the constructed interruptible algorithm B, reduced along time axis by a factor of 4.

As an example, consider the application of this con­ struction method to Korf's RTA ·, a contract algorithm. As the time allocation is increased exponentially, the al­ gorithm will increase its depth bound by a constant; the construction therefore generates an iterative deepening search automatically.

3 Evaluating anytime algorithms

Traditional algorithms are verified in the context of input and output predicates specified by the designer. Opti­ mizing performance means simply reducing the execu­ tion time of a correct algorithm. The use of anytime algorithms in agents requires taking into account the real-time environment in which they operate and the utility function of the agent (or its designer). It is as­ sumed that imprecise results have some value depending on their quality and the utility function of the system. The following framework, roughly analogous to that of [Horvitz, 1987], defines precisely what it means to be a better anytime algorithm; this depends not only on the PP of the algorithm but also on the domain and utility function (which are defined by the user).

A utility function is defined over the states of the do­ main: u :s-n.

Given an algorithm A, let [S, q] denote the state of the domain that is reached by providing results of quality q when the domain is in state S. We can always view A as a decision making algorithm and the new state is simply the state resulting from performing the action recommended by the A.

Now, given the current state So and a certain time period t, we want to compute the comprehensive utility of the results produced by A with computation timet. The problem is that there is uncertainty concerning:

1. The quality of results of A at timet.
2. The state of the domain at timet .

The probabilistic description of the former is given by the PP of A, and the probabilistic description of the latter is given by the model of the environment (we assume that the environment is not affected by which algorithm is running up until t; p,(S;) is the probability that the state of the domain will be S; at timet). Hence we get:

The value of an algorithm is then defined as the maximal utility achieved by optimal time allocation, that is:

Based on this definition we can define an order rela­ tion over anytime algorithms: we say that A1 >- A2 if V(Al) > V(A2) . This relation replaces the traditional notion of correctness.

4 Compilation of anytime algorithms

The compilation of anytime algorithms is the process of constructing an optimal anytime algorithm using any­ time algorithms as components. Creating interruptible algorithms directly is complicated, because the total time allocation is unknown in advance. We therefore start by considering only the construction of contract al­ gorithms and then we extend the results to interruptible algorithms using Theorem 1.

The compilation methods that we describe in this sec­ tion will be integrated into a programming language for anytime computation. Our goal is to develop a compiler for a language that might be in fact syntactically indis­ tinguishable from simple LISP, but all of whose functions might in principle be anytime algorithms. We suggest LISP as the basic language since it is already widely used for AI applications, it allows the association of objects (such as PPs) with functions, and its functional nature is more suitable for the kind of composition of algorithms that we propose.

In our proposed language, the user simply specifies how the total real-time system is built by composing and sequencing simpler elements, and the compiler generates and inserts code for resource. subdivision and scheduling given only the PPs of the most primitive routines. Fur­ thermore, the flexibility of each function makes possible richer forms of composition than is normally available in programming languages; for example, a task can be solved by interleaving several solution methods until one produces the answer. The overall performance profile of the resulting system is computed by the compiler, allow­ ing it to be used as a new building block for still more complex systems. The following in-flight aircraft moni­ toring system is an example of the kind of program that our compiler is eventually intended to handle:

(defun monitor () (calibrate-instruments) (if (setq pl (passengers-missing)) (mapc #'(lambda (p) (remove-from-plane (hunt-for-bags p))) pl)) (~ait-for-take-off-permission) (loop (if (setq co (collision-imminent)) (alert-pilot (plan-avoidance))) (if (setq ep (engine-problems)) (alert-pilot

In this program fragment, the only algorithms that are not anytime are remove-from-plane, alert-pilot, and off-course. All others could consume arbitrary amounts of resources, depending on the accuracy and certainty produced, and hence need to be scheduled ap­ propriately.

4.1 Choosing the right type of PP

Earlier we defined three types of performance profiles the most informative of which was the probability distribu­ tion profile (PDP). This representation is both expen­ sive to maintain and complicated to compile, especially in the continuous case. The simplest representation, the expected performance profile (PEP) is not suitable for our compilation scheme as explained below. We use per­ formance interval profiles (PIP) that keep the lower and upper bounds of the quality of results. Assuming that performance is monotonically increasing, we can com­ pute the quality bounds of a complex algorithm using the quality bounds of its components.

4.2 Compiling contract algorithms

We analyze first several cases of compilation of con­ tract algorithms - that is, the problem is to produce a contract algorithm from anytime components (which can be either interruptible or contract algorithms). The constructs we consider are certainly not an exhaustive collection, but serve to illustrate the issues involved in building the compiler .

4.2.1 Sequences

We first consider the optimal composition of two any­ time algorithms, A1 and A2, one of which feeds its out­ put to the other. The repair system that was described earlier illustrates this situation. Let q1 and q2 be the performance profiles of A1 and A2 , and let u·(ql, q2) be the quality combination function, that is, the func­ tion that defines how the quality of the module depends on the quality of the components. For each allocation of time, t , A1 gets x time units and A2 gets the re­ maining t- x time units, where x is chosen to maximize W ( q1 ( x), q2( t- x)). The performance profile of the com­ pound module is therefore

Similarly, in the case of n steps we get :

Figure 3 shows a problem with two alternative anytime algorithms that can solve the entire problem (for exam­ ple, two different bin-packing algorithms for the same van on a single trip) . In this case the quality combi­ nation function is the maximum of the two components

{since we can use the best solution among the alterna­ tives) and the given amount of time should be allocated to the component that has higher expected quality. This is essentially the case studied by Dean and Boddy [1988}. Rather than using a generalized sequence construct and a particular quality combination function, it might be appropriate to supply a special construct any for the case of multiple alternative methods.

4.2.2 Conditional statement

Consider a real-time currency trading program that uses one of two different trading strategies (A and B) de­ pending on whether interest rate will rise (P) . We would represent this by the conditional statement:

(if P then A else 8 )

Conditional statements have several variations depend­ ing on whether the condition P is calculated by an any­ time algorithm or whether there is a penalty, over and above the cost of time, for executing A when the con­ dition is false. Here we analyze the compilation for the case in which P is a fixed-time algorithm that returns (after time tp) the probability (p) that the condition is true. We also assume that the overall quality is the qual­ ity of A when the condition is true and the quality of B when the condition is false. The optimal time allocation is given by:

A partially evaluated version of this expression IS m­ serted into the 'object code', to be evaluated at run-time when the value of pis known . A PP can be computed at compile time based on the a priori value of p.

4.2.3 Loops

Any system that repeatedly performs a complex task can be implemented using a loop through a sequen­ tial anytime process. Examples include operating sys­ tems, part-picking robots, and network communication servers. In these cases, an infinite loop is an adequate model:

(loop < body >)

The time allocation should maximize the utility gain per unit time, that is, at each iteration we choose x such that:

where Qs(x) is the PP of the body of the loop. This amounts to stopping the sequence when it reaches the point of contact of the steepest tangent to the PP (fig­ ure 4). Loops with anytime termination tests offer more complex but very interesting optimization problems.

4.3 Compiling interruptible algorithms

With interruptible algorithms we cannot simply allocate a certain amount of time to each component since we do not know the total computation time in advance. For example, in the case of the repair system mentioned ear­ lier, if we allocate a certain amount of time to 'diagnose' and the execution is interrupted before 'therapy' starts, then there will be no results to report. We therefore have to interleave the execution of all the components so that results are generated continuously.

The compilation of interruptible algorithms is solved by reduction to contract algorithms using Theorem 1. The idea is to create the best contract algorithm, using the compilation methods described above, and then cre­ ate an interruptible version from the contract algorithm using the iterating construction described in the proof of the theorem.

5 Conclusion

We have presented a method for constructing real-time systems based on the use of elementary anytime alge? rithms together with a set of compilation methods to optimally compose these algorithms. Our method is a meta-level approach in which the meta-level problem is limited to scheduling of anytime algorithms. Laffey et al [1988} claim that "Currently, ad hoc techniques are used for making a system produce a response within a speci­ fied time interval" . Our approach has several advantages over currellt techniques: it achieves optimal performance not just acceptable performance; it can handle situa­ tions in which resource availability is unknown at design time; it allows for a wide range of possible run-times and hence is more flexible; it provides machine independent real-time modules. Finally, our approach avoids a time­ consuming hand-tuning process associated with the con­ struction of real-time systems because the compilation methods are mechanized.

5.1 Related work

As mentioned above, there has been considerable work on designing and using individual anytime algorithms, both before and after Dean's coining of the term 'any­ time'. There has, however, been very little work capi­ talizing on the additional degree of freedom offered by anytime algorithms- freedom in the very general sense that the algorithm offers to fulfill an entire spectrum of input-output specifications, over the full range of run­ times, rather than just a single specification. This freedom is required by a user with a time-dependent utility function rather than a fixed output specification 3 .

One exception is the Concord system, developed by Lin et al. [1987]. Concord is a programming language that supports approximate computations in which the run-time of the subroutine is controlled by the consumer of the results. The main design issues involve the run­ time environment structures needed to support flexible procedure calls. Its development was motivated, like our compilation scheme, by the problem of optimizing per­ formance given a limited supply of system resources. For each procedure, a supervisor is used to record values of the approximate results obtained to date, together with a set of error indicators. When a procedure is terminated, its supervisor returns the best result found. Intermedi­ ate results are handled by the caller using a mechanism similar to exception handling. The handlers for impre­ cise results determine whether a result is acceptable or not; this decision is local to the caller, rather than being made in the global utility context that we use. In this sense, Concord actually performs satisficing rather than optimization. Concord has several other disadvantages compared to our approach: it leaves to the programmer the decision of what quality of results is acceptable; it does not mechanize the scheduling process but only pro­ vides tools for the programmer to perform this task; and it does not provide for simple cumulative development of more complex anytime systems.

5.2 Further work

There is still much system work to be done in order to implement a complete set of compilation methods as an integral part of a programming language for any­ time computation. We also need to understand how best to represent multidimensional, probabilistic and condi­ tional performance profiles, and how to insert monitors to check the partial results obtained and update the PPs accordingly.

We are currently extending the framework to cover the generation and scheduling of anytime actions and observation actions, both of which are essential for the construction of autonomous agents. Anytime actions are actions whose outcome quality improves gradually over time. For example, moving toward a target in order to get a better view is an interruptible anytime action. Aiming a gun at a target is another example of an inter­ ruptible anytime action. In many cases anytime actions can be implemented by interleaving computation and ac­ tion. Our ultimate goal in this project is to construct a real-time agent that acts by performing anytime actions and makes decisions using anytime computation.

3 In fact, the notion of anytime applies much more broadly, for example to contracts among economic agents. A crude version is presented by the model ranges offered by car and computer manufacturers, where different allocations of money will obtain different quality of results. We are begin­ ning to investigate the economics literature to see if similar generalizations have been proposed.