3.5.1 Representation

We start with a new example for simplicity that motivates our choice of representation. Consider the task of coordinating a collection of rovers as they explore the environment around a lander on Mars. This exploration takes the form of visiting different locations and making observations. Each traversal between locations follows established paths to minimize effort and risk. These paths combine to form a network like the one mapped out in Figure 10, where vertices denote distinguished locations, and edges denote allowed paths. Thinner edges are harder to traverse, and labeled points have associated observation goals. While some paths are over hard ground, others are over loose sand where traversal is harder since a rover can slip.

Figure 10: Example map of established paths between points in a rover domain

Figure 11 gives an example of an abstract task. Imagine a rover that wants to make an early morning trip from point $A$ to point $B$ on the example map. During this trip the sun slowly rises above the horizon giving the rover the ability to progressively use soak rays tasks to provide more solar power (a non-consumable resource³) to motors in the wheels. In addition to collecting photons, the morning traverse moves the rover, and the resultant go tasks require path dependent amounts of power. While a rover traveling from point $A$ to point $B$ can take any number of paths, the shortest three involve following one, two, or three steps.

Figure 11: $and$/$or$ tree defining a rover's tasks and their resource usages

A summarized resource usage consists of ranges of potential resource usage amounts during and after performing an abstract task, and we represent this summary information for a plan $p$ on a resource $res$ using the structure $$usage_{sum}(p, res) = \langle local\_min(p,res),local\_max(p,res),persist(p,res)\rangle,$$ where the resource's local usage occurs within $p$'s execution, and the persistent usage represents the usage that lasts after the execution terminates for consumable resources.

Definition 12   $$\setlength{\arraycolsep}{0in} \begin{array}[t]{lll} usage_{... ...p\in E(h)}(-r(res,h,t_f(e_p)))]& \rangle \end{array}\end{array}$$

The context for Definition 12 is the set of all histories $H$ where the value of $res$ is 0 in the initial state, and $E(h)$ only contains the execution of $p$ and its subexecutions. Thus, the $-r(res,h,t)$ term is the combined usage of $res$ at time $t$ of all executions in the hierarchy as defined in Section 2.4. So, the maximum of the $local\_min$ is the highest among all histories of the lowest point of usage during $p$'s execution. The usage ranges capture the multiple possible usage profiles of a task with multiple decomposition choices and timing choices among loosely constrained subtasks. For example, the high path task has a $\langle$[4,4],[6,6],[0,0]$\rangle$ summary power use over a 40 minute interval. In this case the ranges are single points due to no uncertainty - the task simply uses 4 watts for 15 minutes followed by 6 watts for 25 minutes. The $move$(A,B) task provides a slightly more complex example due to its decompositional uncertainty. This task has a $\langle$[0,4],[4,6],[0,0]$\rangle$ summary power use over a 50 minute interval. In both cases the $persist$ is [0,0] because solar power is a non-consumable resource.

As an example of reasoning with resource usage summaries, suppose that only 3 watts of power were available during a $move$(A,B) task. Given the [4,6] $local\_max$, we know that there is not enough power no matter how the task is decomposed. Raising the available power to 4 watts makes the task executable depending on how it gets decomposed and scheduled, and raising to 6 or more watts makes the task executable for all possible decompositions.

This representation of abstract (or uncertain) metric resource usage can be seen as an extension of tracking optimistic and pessimistic resource levels [Drabble TateDrabble Tate1994]. Computing only the upper and lower bounds on resource usage for an abstract plan gives some information about whether lower or upper bound constraints on a resource may, must, or must not be violated, but it is not complete. By representing upper and lower bounds as ranges of these bounds over all potential histories, we can certainly know whether bounds may, must, or must not be violated over all histories. For the example above, if we only tracked one range for the local usage, [0,6], we would not know that there is definitely a conflict when only 3 watts are available. Knowing this extra information can avoid exploration of an infeasible search space.