Adaptive Control of Acyclic Progressive Processing Task Structures

1 Introduction

Planetary rovers are unmanned vehicles equipped with cameras and a variety of scientific sensors. They have proved to be a cost-effective mechanism in space exploration and will continue to play a major role in future NASA missions [Washington et al., 1999]. Despite dramatic improvements in capabilities and computational power, space systems continue to operate with scarce resources such as power, computer storage, and communication bandwidth. They also have a limited life span. As a result, it is necessary to maximize operation time during periods of no communication with the control center. It is also necessary to manage resources carefully when deciding what activity should be performed and how to best accomplish the rover's tasks. The main objective of this work is to develop planning and monitoring algorithms that can optimize scientific return when operating with limited resources.

For this purpose, the progressive processing model provides a suitable framework [Mouaddib and Zilberstein, 1997; 1998]. Progressive processing allows a system to trade off computational resources against the quality of the result similar to other resource-bounded reasoning techniques such as "flexible computation" [Horvitz, 1987],"anytime algorithms" [Dean and Boddy, 1988; Zilberstein, 1996], "imprecise computation" [Hull et al., 1996; Liu et al., 1991] and "design-to-time" [Garvey and Lesser, 1993]. The specific characteristic of progressive processing is the mapping of the computational process (or a plan) into a hierarchical graph of alternative methods. Each method has an associated probabilistic description of the resource/quality tradeoff it offers.

In previous work, Mouaddib and Zilbertstein [Mouaddib and Zilberstein, 1997; 1998] presented a solution to the control problem of progressive processing. This problem is to decide at run-time which subset of methods should be executed so as to maximize the overall utility of a system. The reactive controller is adaptive and takes into account the remaining resources and possible changes in the environment. This is achieved by reformulating the control problem as a Markov decision process (MDP). An efficient implementation that can handle run-time modifications of the overall plan has been implemented [Mouaddib and Zilberstein, 1998]. In the past, only semi-linear task structures have been used. That is, each step of a task could be implemented by one of several alternatives, after which the next step is considered.

The rover application, however, requires several extensions of the previously developed controller. Figure 1 shows a sample plan that illustrates the problem. In the plan, the rover locates an object and aims the camera, possibly after moving closer to the object. It can take a picture at one of three different resolutions, and can compress it using either high or low compression methods. In between, depending on the analysis of the image, the rover may decide to investigate the chemical components of the object. This plan presents several new requirements that have not been previously addressed:

Task inter-dependency: Task execution may depend on the outcome of previous actions. For example, the ability to investigate the chemical components depends on the results of image analysis.

Non linearity: The overall task structure becomes a directed acyclic graph. Execution follows a linear path through the graph.

Multiple resources: The controller must optimize its operation with respect to multiple resources.

The contribution of this paper is three fold. First, we generalize progressive processing to non-linear task structures with one resource and construct an optimal controller for such plans. Second, we analyze the complexity of the solution both analytically and empirically and show that it is an effective approach. Third, we examine the implications of increasing the number of resources and size of the plan on the complexity. We address this problem by introducing the notion of opportunity cost that can be estimated quickly for large, nonlinear plans.

2 Progressive processing control problem

The work presented in this paper builds on the concepts of progressive processing units and plans. In this section, we define these notions and define our problem.

2.1 Preliminary definitions

Progressive processing is a reasoning technique that creates an incremental solution of a problem by using a hierarchy of steps, where each step contributes to the solution. This hierarchy can be viewed as the reasoning scheme which leads us to the solution. We denote by PRU (progressive processing unit) this hierarchy. Notice that we may associate a utility to the execution of a PRU's step. This utility is an abstract measure of the step's quality in the solution.

With this intuitive definition, a rover's plan may be seen as an ordered set of PRUs. More generally, the plan may be non-linear, i.e., a directed acyclic graph of PRUs. One unit has many successors. In this graph, a step will be considered for execution when the succession of steps executed so far has sufficient quality to enable this step.

For the example of planetary rovers, we have three PRUs. The first corresponds to going to a site, taking a picture and analyzing this image in order to find rocks. The second depends on the analysis results. If the site contains rocks, the rover may activate its APXS (alpha proton X-ray spectrometer) in order to determine the chemical components of the rocks. The last PRU corresponds to compressing the scientific data (images and chemical components).

We may transform this plan to a linear plan but, in that case, we lose generality and the inter-unit dependency information. In fact, the non-linearity of a plan and the notion of dependence allow for more realistic applications.

The planetary rover's problem (or progressive processing problem control) is to choose the set of executing tasks that maximize the global utility while respecting resource constraints.

2.2 Formal definitions

We formalize these definitions, focusing on one resource: operation time.

Definition 1 A plan  is a directed acyclic graph of progressive processing units,  BD BN  BE BN BMBMBMBN   .

Example: One plan is figure 1, where  BD is unit 1,  BE is unit 2 and  BF is unit 3.

Definition 2 A progressive processing unit (PRU),  CX , consists of a set of steps, D2 CX BP CU CXBNBD BN CXBNBE BN BMBMBMBN CXBNAZD2 CX CV, a deadline CS CX and a set of successors, D7 CX BP CUD7D9CRCRB4CY BD B5BN BMBMBMBN D7D9CRCRB4CY AZD7 CX B5CV, where D7D9CRCRB4CY D0 B5 BP B4
CY D0 BN  CY D0 B5 and
CY D0 is the utility interval CJCXD2 CY D0 BNCPDC CY D0 CL corresponding to minimal and maximal utilities required to move to the next unit  CY D0 .

Example: PRU  BD has three steps:  BDBNBD is step 1,  BDBNBE is step 2 and  BDBNBF is step 3. It has two successors:  BE and  BF .

Definition 3 A step CY of a unit CX,  CXBNCY , consists of a set of tasks, D8 CXBNCY BP CUCC CXBNCYBNBD BN CC CXBNCYBNBE BN BMBMBMBN CC CXBNCYBNAZD8 CXBNCY CV and a userspecified attribute, skippable, which indicates if this step may be skipped or not. We denote by D7 CXBNCY the skippable attribute, and D7 CXBNCY BP BD when  CXBNCY is skippable and 0 otherwise. We define  CXBNBC to be the special step (with no tasks) that is used to show the beginning of executing a unit.

Example: Step 2 of unit 1 has three tasks. The first CC BDBNBEBNBD is "Picture low resolution", the second CC BDBNBEBNBE is "Picture medium resolution" and the third CC BDBNBEBNBF is "Picture high resolution". This step can be skipped if we don't want to take a picture at a particular site.

Definition 4 A task CZ of a step CY of a unit CX, CC CXBNCYBNCZ , consists of an executable module, a utility (or quality) and a discrete probability distribution D6CR CXBNCYBNCZ of resources consumed when the module is executed. The number of elements of D6CR CXBNCYBNCZ is AZD6CR CXBNCYBNCZ .

The probabilities can be determined from ground experimental rovers and simulations.

Example: Task 2 of step 2 of unit 1, CC BDBNBEBNBE consists of taking a medium resolution picture of the site. The distribution of resource consumption for this task, as used in our experiments, is D6CR BDBNBEBNBE BP CUB4BEBKBN BCBMBEB5BN B4BEBLBN BCBMBIB5BN B4BFBCBN BCBMBEB5CV.

Definition 5 The progressive processing control problem is to select at run-time the set of tasks that maximizes the global utility.

2.3 Selecting tasks

When the rover has completed step  CXBNCY (meaning that a task CC CXBNCYBNCZ of that step has been executed or that the step has been skipped), it has three possible decisions:

• AF it can execute one task CC CXBNCYB7BDBNCZ BC of the next step  CXBNCYB7BD if this step exists,
• AF it can skip the next step  CXBNCYB7BD , if it exists and it is skippable,
• AF it can move to a accessible successor unit  D7D9CRCRB4CXB5 .

The optimal decision is the one that maximizes the global utility. The sequence of decisions will determine the set of tasks executed. The global utility is the cumulative reward of the executed tasks (reward is measured by the qualities associated to the tasks).

In this context, the progressive processing control problem is a state space where a transition from one state to an another is the decision made by the rover. The state represents the last executed step and the remaining resources. In fact, the choice of the next action (when the rover is in a particular state) depends only on the current state. This is the Markov property. So, the progressive processing problem control may be seen as a problem of controlling a Markov decision process.

2.4 Markov Decision Process Controller

We now define the corresponding Markov decision process.

States

A Markov decision process is a graph of states such that:

Definition 6 A state, CJ CXBNCY BNCACACL, consists of the last executed step  CXBNCY and the remaining resources.

Definition 7 The accumulated quality is the sum of qualities of all executed task.

Definition 8 Quality dependency of units: A state CJ CX BC BNBC BNCACA BC CL is the successor of CJ CXBNCY BNCACACL when the accumulated quality of CJ CXBNCY BNCACA BC CL belongs to the utility interval
CX BC and B4
CX BC BN  CX BC B5 BE D7D9CRCR CX . We say in this case that CJ CX BC BNBC BNCACA BC CL is an accessible state from CJ CXBNCY BNCACA BC CL.

With the quality dependency, we express the dependence between the problems, including the precedence constraint (quality not null or belonging to a certain interval).

Example: To go to site 2, the rover should have executed CC BDBNBFBNBD (analysis of taken picture). So, we give a high reward to CC BDBNBFBNBD andCXD2 BE BP D5 BDBNBFBNBD , where B4
BE BN  BE B5 BE D7D9CRCR BD .

Definition 9 A state is terminal when all the resources have been fully elapsed, or when there is no accessible successor.

Transitions

We have three possible transition types: BX, CB, and BW.

Definition 10 A transition BX CXBNCYBNCZ (type BX) is probabilistic. It consists of executing a task CC CXBNCYBNCZ of the next step  CXBNCY . We

denote it CJ CXBNCYA0BD BNCACACL BX CXBNCYBNCZ A0AX CJ CXBNCY BNCACA A0 A1CACL, where A1CA represents the resources consumed for the execution of CC CXBNCYBNCZ .

Definition 11 A transition CB CXBNCY (type CB) is deterministic. It consists of skipping the next step  CXBNCY . We denote it CJ CXBNCYA0BD BNCACACL CB CXBNCY A0AX CJ CXBNCY BN CACACL.

Definition 12 A transition BW CX (type BW) is deterministic. It consists of passing to an another unit. We denote it CJ CX BC BNCY BNCACACL BW CX A0AX CJ CXBNBC BNCACACL, where  CX is an accessible successor of  CX BC .

Transition rules

Now, let us define transition rules.

Pr(state CU CY state CT, transition D8) is the probability of moving from CT to CU when taking transition D8.

Let CT BP CJ CXBNCYA0BD BNCACACL be the current state.

1. Transitions BX CXBNCYBNCZ

Let A1CA be the resources consumed by task CC CXBNCYBNCZ .

• (a) A1CA AK CACA, D6B4CJ CXBNCY BNCACA A0 A1CACLCYCTBNBX CXBNCYBNCZ B5 BP  D6B4D6CR CXBNCYBNCZ BP A1CAB5,
• (b) A1CA BQ CACA, D6B4CJ CX BC BNBC BN CS CX BC A0 CS CX CLCYCTBNBX CXBNCYBNCZ B5 BP D6B4D6CR CXBNCYBNCZ BQ CACAB5, where CJ CX BC BNBC BN CS CX BC A0 CS CX CL is accessible from CT.
• Transitions CB CXBNCY (if D7 CXBNCY BP BD, i.e., the step is skippable)  D6B4CJ CXBNCY BN CACACLCYCTBN CB CXBNCY B5 BP BD.
• Transitions BW CX  D6B4CJ CX BC BNBC BN CS CX BC A0CS CX B7CACACLCYCTBN BW CX B5 BP BD, where CJ CX BC BNBC BN CS CX BC A0 CS CX B7CACACL is accessible from CT.

2.5 State's value

The value associated to each state CE B4CJ CXBNCY BN CACACLB5 is a measure of utility of this state in the MDP. This value is calculated recursively by using the value of successor states.

For this, we denote CT BP CJ CXBNCYA0BD BNCACACL, BX BT BP CUstates accessible from CTCV and CTCP CX BC BE BX BT an accessible state for which the associated task is in unit  CX BC .

• AF Transitions BX CXBNCYBNCZ

• AF Transitions CB CXBNCY

• AF Transitions BW CX

So, the value of one state is:

3 Performance of the MDP controller

We have implemented the execution model described above, the policy-construction algorithm, and a simulator that allows plans to be executed and visualized in the rover domain. The performance of the resulting system is evaluated using the simulator. This section illustrates the results obtained using the system.

3.1 Analysis

Because of the one-to-one correspondence between the states of MDP and the states of the control, the optimal solution of the MDP is the optimal control.

Claim 1 (MDP size) The number of states in the MDP is bounded by:

Proof: Note that two states with same remaining resources and associated step generate the same successors. So, to avoid an exponential complexity, we must notice already created states.

Since consumable resources are bounded, as well as the number of steps, we obtain a bounded number of states. Moreover, two states are different if and only if the associated steps are different or the remaining resources are different. So, we have the bound:  A1 D1CPDC BK CX CS CX A1 D1CPDC BK CX AZD2 CX . BE

Claim 2 (solution time) The time elapsed to calculate the optimal policy for the MDP is bounded by:

Proof: The time consumed to solve the MDP is bounded by the number of transitions multiplied by the cost of searching already created states (if we don't want an exponential complexity).

The number of transitions from a state CJ CXBNCYA0BD BNCACACL is bounded by the number of transitions of each type: AZD6CR CXBNCYBNCZ of type BX, and one each of type CB and BW. So, for that one state, the number of transitions generated is bounded by:

Therefore, the bound on the number of transitions in the entire MDP is (using equation 2):

Finally, the search of already created states involves CS CX states in the worst case: since we store states by unit and by step, only those states associated with the specified unit and step need to be checked.

So, we obtain the following bound:

In conclusion, our controller has a complexity of B4 A1 D1CPDC BK CX CS CX B5 in space and B4 A1 B4D1CPDC BK CX CS CX B5 BE B5 in policyconstruction time. We also notice that if the deadline is not a function of N, we obtain a linear complexity.

3.2 Experimental results

We take a non-linear plan composed of  units and of depth D0D3CV. Each unit is composed of four steps. The first step consists of going to a site, the second of arming the camera, the third of taking the photo (low, medium or high resolution) and the last of compressing the obtained scientific data.

For our experiments, we set the average time to execute this unit to be 32 seconds. So, the deadline of each unit in plan is 32 seconds multiplied by the depth of this unit in the plan. If we assume that the number of nodes at each level of the plan increases by at least a constant factor CQ BQ BD, then the depth of the plan is B4D0D3CVB5, and we obtain the complexity B4 A1 D0D3CVB5 in space and B4 A1 B4D0D3CVB5 BE B5 in time.

However, we notice that we use exactly the resources needed to execute a task. What happens if we consume resources in fixed-size packets instead of exactly the needed resources?

Table 1 shows state values computed for packet sizes of 1 and 2; little error is incurred by increasing the packet size. Figure 2 shows policy-creation time for plans of realistic size. Using a packet size of 2, the time used to solve the MDP is divided by 4 and the number of states created is divided by 2.

In fact, we can generalize this result:

Claim 3 If BXBV is the number of states created and CCBV is the time consumed to create these states (for packet size equal to 1), then BXBV D9 is the maximal number of created states and CCBV D9 BE the maximal time elapsed (for packet size equal to D9).

BXBV D9 and CCBV D9 BE are bounds since equations 2 and 3 are bounds for BXBV and CCBV.

Proof: We suppose that BXBV and CCBV are number of created states and time consumed for packet size equal to 1. We now take packets of D9 resources.

Solution time (in seconds)

Notice that size of packet has no influence on the size of the problem . Moreover, it leaves the number of steps in unit and number of tasks in step invariant.

So, the packet size proportionally reduces the deadline of each unit (CS CX AX CS CX D9 ). Therefore, equation 2 implies that BXBV D9 is the maximal number of created states and equation 3 implies that CCBV D9 BE is the maximal time consumed to create these states.

The last term of equation 3 can be changed by packets, but it is just a constant. BE

4 Dynamic operation and scalability

In the previous section, we presented an optimal solution to the control problem of acyclic progressive processing task structures. In this section, we extend the applicability of the solution to situations in which the global policy cannot be computed at run-time either by the control center or the rover itself. There are two primary motivations to avoid run-time construction of the policy.

1. Dynamic operation: We want to be able to modify the plan at run-time (e.g., insert or delete a PRU) without necessarily recomputing the control policy.
2. Scalability: We want to be able to track more resources, and the complexity of global policy construction grows exponentially with the number of resources.

While we focus in this paper on the dynamic operation, scalability is also enhanced by the proposed solution. Our approach is to exploit the fact that the units of the plan are largely independent. We try to capture the dependency of the execution of each unit on the remaining plan using a notion similar to opportunity cost [Zilberstein and Mouaddib, 1999].

4.1 Dynamic control with one resource

Definition 13 Let DA  B4CJ CXBNCY BNCACACL represent the optimal local value of the state after step  CXBNCY with remaining resources CACA.

Note that DA  is the same as CE for a modified plan in which unit CX has no successors. DA  is simply the value of the best policy for PRU CX ignoring the remaining plan, hence it is called local value.

Claim 4 The global value function can be reformulated as follows.

Proof: This is an immediate result of the definition of DA  , CE and DA BW , and the additivity of the utility. BE

For each PRU, we can easily compute the local value function DA  and construct a local policy off-line. The global value function (and policy) can be constructed at run-time, if we can obtain a fast estimate of DA BW .

4.2 Estimating DA BW

One way to think about DA BW is as the value of terminating the work on a certain PRU with some level of resources, then using the resources for the remaining plan. This is exactly what we need to know. Estimating DA BW is equivalent to estimating the global value of the remaining plan. We have examined several approximation schemes for DA BW . Due to space limitations, we only sketch one simple approach.

• AF Construct an optimal local value function and local policy for each PRU (done once, off-line).
• AF For each level of RR, compute the expected value and expected resource consumption by the optimal local policy (done once, off-line).
• AF Go over the plan graph "backwards" from the leaves and compute an expected value for each node, for each level of CACA at that node. The backup is relatively simple: maximizing for each level of CACA at that node the combined parent/child value. In this process, it is necessary to take into account the difference between the deadlines of each parent/child pair. The quality dependency constraints are enforced with respect to the expected quality of the parent.

This algorithm is linear in the size of the graph. The computational savings and sub-optimality of the outcome are the result of using precalculated expected resource consumption and value for each PRU.

5 Conclusion

We have presented a solution to the problem of adaptive control of acyclic progressive processing tasks. This approach, which relies on solving a corresponding MDP, generalizes earlier work on MDPC [Mouaddib and Zilberstein, 1998]; it permits for the first time the treatment of non-linear progressive processing task structures. Moreover, our approach addresses effectively the high degree of uncertainty regarding resource consumption. In that sense, it improves on existing models for resource-bounded reasoning such as "imprecise computation" [Hull et al., 1996; Liu et al., 1991] and "design-to-time" [Garvey and Lesser, 1993]. Finally, the model captures inter-task quality dependency similar to the enable and disable relationships in the "design-to-time" framework [Garvey et al., 1993].

We also address in the paper a potential deficiency of the approach which may require a large amount of memory and time to create and solve the MDP and to store the resulting policy. Using packets of consumable resources, we managed to reduce the size of the MDP with a small loss of quality (4.5% for packet size equal to 2). Finally, we address the issue of dynamic operation and scalability by approximating the solution of the MDP.

The solution presented in this paper includes time as the only resource. Future work will allow us to represent a vector of resources [Mouaddib, 2000] such as storage capacity and power. An additional challenge is to develop more precise estimates of the value function DA BW and adapt the approach to the case of multiple resources. A related project is using reinforcement learning to estimate DA BW [Bernstein and Zilberstein, 2001].

More accurate models of resource usage can be obtained by using results from actual rover testing or high-fidelity simulations. We plan to make use of ongoing development of a high-fidelity rover simulation at NASA Ames Research Center to refine our models to make them more accurate and applicable to realistic rover problems, with the goal of testing our approach on actual rover hardware.

The PRU used in our experiments (Cf. 3.2) can be extended to solve a satellite scheduling problem. With this approach, more units can be scheduled than by traditional methods. Indeed, at this moment, a satellite in orbit around the world schedules the equivalent of only about 20 units. With our approach, it would be able to schedule 100, thus increasing its productivity 5-fold.

Acknowledgements

Support for this work was provided in part by the National Science Foundation under grants IRI-9634938, IRI-9624992, and INT-9612092, and by a Project of Plan Etat/Nord-PasDe-Calais, and by IUT de Lens.