Handling Duration Uncertainty in Meta-Level Control of Progressive Processing

1 Introduction

Progressive processing [Mouaddib, 1993] is a problem­ solving technique that allows a system to trade-off so­ lution quality against computational resources. This technique is suitable in situations where it is not fea­ sible (computationally) or desirable (economically) to compute the best result. Progressive processing shares the motivation of such resource-bounded reasoning. tech­ niques as flexible computation [Horvitz, 1987], anytime algorithms [Boddy and Dean, 1994; Zilberstein, 1995; 1996], and design-to-time [Garvey and Lesser, 1993]. The distinctive characteristic of progressive processing is the use of a multi-level deliberation hierarchy in order to gradually transform an approximate solution into a Shlomo ZilbersteintComputer Science Department University of Massachusetts Amherst, MA 01003 U.S.A.

·support for this author is provided in part by the Ganymede II project of the contract Plan Etat/Nord-Pas­ De-Calais and by M.ENESR.

tsupport for this author is provided by the National Science Foundation under grants IRI-9624992, IRI-9634938, INT-9612092, and by the U.S. Air Force under grant F3060295-1-0012.

shlomo@cs. umass.edu

precise one. The mapping from the set of inputs (prob­ lem instances) to the set of outputs (solutions) is based on progressive utilization of data and knowledge. This incremental process is facilitated by using a hierarchical structure of input elements defined by the system's de­ signer [Mouaddib and Zilberstein, 1995]. This mapping is especially suitable for domains where the reasoner uses abstraction to structure the search space (as in hierar­ chical planning), and for problems that require the result to be expressed at varying levels of detail (as in model­ based diagnosis).

In 'systems based on this technique, each time­ constrained component is designed in such a way that it can produce a usable approximate solution within the available run-time. However the use of progressive pro­ cessing as a component of a real-time system introduces a problem of execution monitoring: determining how long to run. This kind of scheduling problems are common in real-time AI applications, such as medical monitoring [Hayes-Roth, 1990], real-time data transmission [Millan­ Lopez et al., 1994], speech processing [Feng and Liu, 1993], mobile robot navigation [Zilberstein, 1996] and flexible manufacturing. The real-time data transmission application that we address in this paper is another ex­ ample. These application require a meta-level control mechanism that can deal with (1) dynamic environment, (2) limited amount of t ime to produce a response, and (3) uncertainty regarding the duration of problem-solving.

The focus of this work is handling duration uncer­ tainty. Most of the existing approaches to the prob­ lem do not deal with duration uncertainty and their schedulers work in isolation; the schedule runs for the predetermined length of time regardless of the situation [Boddy and Dean, 1994; Liu et al., 1991; Millan-Lopez et al., 1994]. Hansen and Zilberstein [Hansen and Zilber­ stein, 1996] show that monitoring the progress of prob­ lem solving allows a system to take advantage of the information gathered during execution time and to im­ prove the overall performance. Garvey and Lesser [Gar­ vey and Lesser, 1993] introduce a design-to-time tech­ nique that represents duration uncertainty and revises the schedule during execution. We address two limi­ tations of that approach: (1) its time interval representation of duration uncertainty is not sufficiently in­ formative when the duration variation is large; and (2) its scheduler is assumed to always complete its process­ ing. This design-to-time approach is suitable in domains characterized by low level of uncertainty so that the scheduler is significantly faster than the evolution of the controlled process. We suggest that it is beneficial to design the scheduler itself as an incremental process so that it can handle rapid change in the environment and unexpected interruption before completing its execution.

This paper focuses on the problem of meta-level con­ trol of computational resources in domains characterized by rapid change and duration uncertainty. We show that the task structure of progressive processing facilitates ef­ ficient run-time monitoring and meta-level control. The approach we present is based on an interruptible algo­ rithm which incrementally builds a schedule and returns an approximate complete schedule when it is interrupted unexpectedly. This approach can handle rapid change and a large deviation from the predicted schedule. The incremental scheduler that we present allows: (1) to ini­ tially construct schedule that contains the first reasoning level for each task and to then refine it progressively by introducing additional reasoning levels for each task, (2) to revise the schedule when a significant deviation is de­ tected at run-time, and (3) to reduce the frequency of revision using information on duration uncertainty.

Section 2 presents a data transmission application for which our approach was implemented. Section 3 presents a formal definition of the problem and the initial task structure. A description of our approach based on an incremental scheduling and a revision technique is given in Section 4. Section 5 presents an empirical comparison of our approach with an adaptation of the design-to-time approach to handle progressive processing. We conclude with a summary of the contributions and future work.

2 Real-Time Data Transmission Application

We examine a data transmission application that pro­ vides real-time communication services. These services include time constraints on the duration of transmission and a deadline for data delivery. The duration of trans­ mission is the time interval between the point at which the data is generated and the point at which it is deliv­ ered. This duration is uncertain because of the variation on the behavior of the communication network. Data misses its deadline whenever the duration of transmis­ sion exceeds the maximum permitted time.

Our approach is designed to manage real-time World­ Wide Web (WWW) services providing information on staff members of our laboratory. This information may include textual data, video frames and voice. The sys­ tem must satisfy asynchronous requests of information by taking their deadlines into account. The implemen­ tation consists of eleven (11) WWW pages, each of which contains information on one member of the laboratory. Each page consists of textual data, video frames and voice. Different requests for information may refer to the same page. The information system must handle (1) asynchronous requests (dynamic and rapid change as­ pect of the application); and (2) uncertainty regarding the behavior of the network (uncertainty on execution time). To apply the progressive processing technique, we assume that each WWW page could be transmitted as three separate packages of information (text, video frames and voice). The incremental process of satisfy­ ing a request is based on dividing it into a sequence of information packages. Consequently, the requests could be satisfied at varying levels of detail. Our experimental evaluation is based on a simulation of arrival of informa­ tion requests and transmission of information packages.

3 Formal Framework

3.1 Description of the Problem

Our framework relaxes two assumptions that are com­ mon in classical scheduling systems. First, they opti­ mize performance by satisfying the most important re­ quests and if time permits they satisfy additional re­ quests. These approaches neglect the fact that each re­ quest could be satisfied at varying levels of detail. It has been demonstrated that requests can be logically decom­ posed into two parts: a mandatory part and an optional part [Liu et al., 1991]. This structure facilitates the de­ velopment of more flexible systems that allow to satisfy the mandatory parts of all the requests and then im­ proving performance by satisfying some of the optional parts. This approach is applies to problems that could be solved at varying levels of detail, such as hierarchi­ cal planning [Knoblock, 1994] and incremental diagnosis [Hayes-Roth, 1990]. Second, classical scheduling systems ignore the deviation of execution time from the predeter­ mined expected length. In fact, data transmission appli­ cations are characterized by a high level of uncertainty regarding transmission time that cannot be ignored.

More precisely, the problem we solve consists of a set P = {P1 , ... , Pn} of individual problems such that:

• P is constructed dynamically; a new problem is added to the set when a new request arrives,
• each problem Pi has a deadline Di to respect,
• each problem Pi could be solved at varying levels of detail using a hierarchy of processing levels, and
• each processing level has probabilistic information characterizing its duration and duration uncertainty.

3.2 Progressive Processing

A progressive processing unit is a composite unit a of processing levels L~ ordered by a linear precedence­ constraint graph. The level L~ can begin execution only after the level L~- 1 completes. The level L~ is the im­ mediate successor of L~- 1 , and the output of L~- 1 is one of the inputs of L~ . The output of the last level L~a is the (best) output of the unit a. In general, the output of a unit can be used by any successive unit as soon as the first level has finished its processing. We as­ sume that the information necessary for successive units is produced by the first level. The hierarchical structure of each unit allows to characterize precisely the tradeoff between computation time and the quality of the result. The solution quality is discretizd into a finite number of levels, QL' , qp , ... , Qca, where QL' is the lowest quality and Q£ na a is thae highes"t quality ret~rned respectively by the firsat level L~ and the last level L~a . The purpose of monitoring is to optimize the time/quality tradeoff offered by each unit .

3.3 Formal Framework

Scheduling progressive processing units consists of de­ ciding how long to run each unit taking its progressive structure into account and satisfying the timing con­ straints imposed on the problem. Before elucidating this problem and its solution, we briefly present some general notation and concept definitions used by the meta-level control algorithm.

Stating the problem We consider a set A comprising n progressive processing units (PRUs) a, (3, .. . , "(sorted according to the deadlines (earliest-deadline-first) of the corresponding problems Pi in P that they solve. The problem is to find for each PRU the optimal subset of its set of processing levels such that all deadlines are respected. This decision is made under uncertainty re­ garding the execution time of each processing level and regarding future changes of the set A.

Progressive processing unit Each PRU a is repre­ sented by a linear graph L~ -+ L; -+ ... -+ L~a, de­ noted LGa=(.C00 Succ_Level) where:

• La= {L~ 11 ~ i ~ na} U {t:}, t: means no successor
• Succ_Level : .Ca -+ .Ca,

Processing level formulation Each level L~ is char­ acterized by the triplet (c~, v~, V(qL~)) where:

• c~ , v~: its computation time average and variance.
• V(qL· ): its intrinsic value of solution quality.

The a;erage and the variance are dynamically deter­ mined and updated by statistical analysis on the be­ havior of this level. The average represents the most likely computation time. The variance is used for judg­ ing whether the deviation during execution from the pre­ dicted schedule is important.

Utility of a processing level The utility U~ of a reasoning level L~ is defined as follows:

Where Cost ( c~) is an application-dependent cost func­ tion provided by the user. This utility is used to attach a comprehensive value to each processing level at any given time. Based on this value, a utility-based approach is used in order to select processing levels to be included in the schedule. Similarly, at execution time, the utility of each processing level is used to determine which level is to be added/removed from the current schedule when execution is faster/slower than originally predicted.

Framework used We represent the ordered set A by a graph (9 , Succ_Unit, Succ_Node) (Figure 1) where:

• 9 = {L~ E LGal'v' a E A} .
• Succ_Unit: A-+ A,

Succ_Unit(a) = (3, (3 is the immediate successor in A ,

• Succ_Node: 9-+ 9,

This structure allows to perform utility-based schedul-

ing by incrementally inserting nodes (processing levels) into the current schedule. We now define several con­ cepts necessary to describe the scheduling process.

• The envelop, £, is a subgraph of 9 containing all the levels scheduled for execution (nodes drawn with bold lines in Figure 1). This is similar to the notion of a closed list in search algorithms. The envelop is a dy­ namic structure that can be revised during execution.
• The fringe, :F, is the set of direct successors to the nodes in £ (nodes drawn with dotted lines in Figure 1). This is similar to the notion of an open list in search that contains nodes on the frontier of the search tree that are candidates for expansion.
• The frozen space, Z, is a set of branches pruned during the scheduling cycle. It contains the levels that violate some deadlines during the scheduling phase. We save these levels because during the revision of the schedule, these levels may be added to the search space and even­ tually they may be added to the schedule.

4 Incremental Scheduling

The main design goal of the incremental scheduler is the ability to return an approximate schedule for all the PRUs of A at any time and to revise this schedule when a deviation from the predetermined schedule is detected at run-time. These two properties allow the system to deal with domains characterized with rapid change and a high level of uncertainty.

4.1 Conceptual Description

With the PRU structure and formal framework described above, scheduling could be seen as the problem of find­ ing an optimal path that visits the maximum number of levels in the graph 9 without violating any deadline. There are different possible paths with different quali­ ties. Our strategy consists of finding a minimal schedule that includes all the PRUs and refining it progressively. The minimal schedule has the lowest quality since it vis­ its only the first node of each LG (in the example shown in Figure 1, the minimal envelop is {LL L§, L§ } ). The path with the highest quality is the path that visits all the nodes (in the example, the maximal envelop is { L~, Lr, Lr, L§, L~, L§, L~, L~, L~ } ) . The scheduler starts its processing by building the schedule with the lowest quality (the minimal envelop) and refining it by insert­ ing additional nodes into the graph as long as all the deadlines are respected. The incremental processing of the scheduler is guided by the progressive structure of the PRUs and by the the (easy to construct) fringe.

4.2 Utility-Based Scheduling Algorithm

The construction of the schedule is based on a series of cycles of expansion of the current envelop. This ex­ pansion consists of inserting levels of the fringe into the envelop. This process is repeated until a maximal en­ velop is reached (i.e., any further expansion leads to a violation of a deadline) or until an external even causes the interruption of scheduling. At each cycle, a schedule is available and its quality is improved from one cycle to another. The algorithm consists of the following steps:

· Initialization step:

· Expansion step:

This step consists of extending E to all the levels in :F:

The operator l:J allows to insert levels while respecting the structure of the graph 9 and thus at each cycle, E is a subgraph of 9 (as shown in Figure 1).

· Test of feasibility step:

The schedule fails when one deadline is violated:

If the schedule fails, go to the approximation step, oth­ erwise go to the new cycle step.

· Approximation step:

The level with the lowest utility, noted Lmin, when is discarded when the schedule fails. The level Lmin is se­ lected among the levels L~ inserted by the last expansion cycle.

The branch containing the successors nodes in LG1/! is pruned from 9 and is placed in Z. Formally:

The operator 8 performs the following operation: Succ_Node(Lmin)=t:. Afterwards, go to the test of fea­ sibility step.

· New fringe step:

For each processing level L~ inserted in E by the last expansion cycle, we insert into the fringe its successor (if it exists). Formally:

If the fringe is not empty go to the expansion step, oth­ erwise stop the algorithm and return the envelop E.

4.3 Utility-Based · Revision Algorithm

This algorithm adjusts the schedule by taking into ac­ count the actual progress made at run-time. After the execution of each PRU, the algorithm examines the ac­ tual execution time and determines whether an impor­ tant deviation has occurred. A deviation is impor­ tant when it exceeds the variance v~ of one process­ ing level which is not yet scheduled or executed. This algorithm allows to optimally revise the schedule and to update statistical information concerning the exe­ cuted level. The processing time gained/lost, Dev, is used to insert/remove levels and correspondingly in­ crease/decrease the global performance efficiently. The algorithm inserts the level L~ of :For Z with the maxi­ mum utility U~ and removes the level L~ of E with the minimum U~. If there is more than one PRU having a maximum/minimum utility we choose the most urgent PRU when we want to insert a level and the latest PRU when we want to remove a level. The revision algorithm is based on the following rules:

• If Dev is positive, this means that the amount of time was lost during execution (i.e., execution is slower than predicted): ( 1) select the level such as Lmin = arg(MINLEt:(UL)), (2) use the rules of the approximation step of the scheduling algorithm.
• If Dev is negative, this means that the amount of time was gained during execution (i.e., execution is faster than predicted): ( 1) select the level such as Lmax = arg(M AX L E (F U Z) (UL)), (2) add this level to E, (3) if the selected level is in :F, then its correspond­ ing branch { Succ_Level(Lmax), .. . , L~"} is reintegrated into 9:

4.4 Properties

To summarize, here are the main properties of our ap­ proach:

• Its scheduler could be interrupted at any time and it re­ turns an approximate global schedule (global means that all the PRUs are included). As a result, this approach can deal with applications characterized by rapid change and a high level of uncertainty.
• The probabilistic representation of duration uncer­ tainty reduces the deviation from the predetermined schedule during execution. It also helps reducing the frequency of revising the schedule and thus limits the effect of revision time on the performance of the system.

5 Experimental Evaluation

To evaluate our scheduling and monitoring technique, we compare its performance to the design-to-time tech­ nique. The comparison examines two fundamental ques­ tions: (1) the ability of each approach to handle duration uncertainty that is typical in such applications as real­ time data transmission; and (2) the advantage of using a resource-bounded scheduler in domains characterized by rapid change and high level of uncertainty. Before assessing both approaches, let us give a brief overview of design-to-time. This approach assumes the existence of multiple methods for each subtask with each method having different duration and quality. The problem is to design a solution to a problem that uses all the avail­ able time to maximize solution quality. design-to-time tolerates uncertainty in its prediction if monitoring can be performed quickly and each method performs as ex­ pected or within a small variation. The experimental results confirm these characteristics.

5.1 Experiment Design

We describe first how we have transformed the PRU structure to multiple methods used by design-to-time. The linear precedence-constraint graph of each PRU is mapped to a set of methods designed as follows: the first method M 1 consists of the first level (the first node in LG) while the it,h method Mi consists of the sub­ graph of the LG containing the first ith levels [Mouaddib, 1996]. With this adaptation, we can evaluate both ap­ proaches for different problem instances generated based on a given set of size and time parameters.

Since the WWW data transmission application is un­ der development right now, we tested the scheduler with synthetic data simulating this application. The initial problem is specified in a PRU-language allowing us to create PRUs for the specific application. We have col­ lected data on the scheduling and the execution phase for both the incremental scheduler and the design-to-time technique. The data for each problem instance includes intrinsic-utility, total cpu consumed and the frequency of revision. Finally, we compare the results based on the notion of global utility, QU, and the notion of revision frequency, Freq. The global-utility is computed as fol­ lows:

Where U~ is the intrinsic utility of an executed process­ ing level. We compare Freq and QU for different problem sizes and time.

Handling duration uncertainty

The frequency of revision reflects the degree to which an approach is suitable for handling duration uncertainty. We measured the frequency and global utility as a func­ tion of the size of the application. Problem instances were generated with execution time variation of 20% (this figure is quite conservative for data transmission applications). The table (Figure 2) summarizes the fre­ quency of revision of our approach (IS) and design-to­ time (DTT): Figure 3 shows the evolution of the global

utility over size in both approaches.

Resource-bounded scheduling

This experiment measures the performance of both ap­ proaches when the scheduling algorithm operates under time constraints (Figure 4). The experiment tests the degree to which an approach is suitable for dynamic en­ vironments in which the scheduler may not have enough time to complete its processing. For this experiment, we use a size of 10 and a variable allocation of time to the scheduler of both approaches . We measured the intrin­ sic utility that allows to compute QU. Design-to-time requires to finish its processing before delivering a com­ plete schedule for all tasks. In this experiment, we mea­ sure the intrinsic utility of the current available schedule that is not complete for all tasks but only for the earlier ones.

5.2 Summary of results

• Handling duration uncertainty: our approach is more efficient than design-to-time in handling duration uncertainty. The main reason is the time interval repre­ sentation of duration uncertainty used by design-to-time which is not sufficiently informative and leads to more schedule revisions. The higher frequency of revision has a negative effect on the overall performance of the ap­ proach a8 shown in the Figure 3.
• Resource-bounded scheduling: design-to-time schedules tasks one by one by selecting for each task the appropriate method to optimally trade solution qual­ ity against computational resources. If the scheduling is interrupted before completing its processing, the latest tasks are not scheduled. This situation arises in appli­ cations that must respond to frequent and rapid state change. In contrast, our incremental scheduler, with its incremental processing, is able to be interrupted at any time and to return a solution. We show in Figure 4 that our approach is more suitable to these applications than design-to-time.

6 Conclusion and Future work

We describe in this paper an approach to scheduling progressive processing units in domains characterized by rapid change and duration uncertainty such as in data transmission applications. Our approach is based on a utility-directed greedy scheduling algorithm that pro­ duces a minimal schedule of all the tasks and refines it when time permits. This is a local optimization ap­ proach to a scheduling problem that is hard to optimize globally. The incremental structure of the scheduler, its interruptibility, and its ability to dynamically revise the schedule during execution time make it an attractive resource-bounded scheduling technique. Experimental evaluation shows that for the type of progressive pro­ cessing tasks that we are interested in, the incremental scheduler has advantages over the design-to-time tech­ nique. Future work is concerned with alternative repre­ sentations and propagation of duration uncertainty by mapping the graph 9 to a Bayesian network [Mouad­ dib, 1996]. Another future direction is concerned with applying this model to non-linear structure of PRUs.