# Improving Search in Scheduling by Aggregation of Resource and State Constraints

# Russell Knight, Gregg Rabideau, and Steve Chien

Jet Propulsion Lab, M/S 126-347

California Institute of Technology

4800 Oak Grove Drive, Pasadena, CA 91109-8099

firstname.lastname@jpl.nasa.gov

### **Abstract**

> *This paper describes the use of aggregation techniques to improve the
> efficiency of search finding legal temporal placements for sets of
> interdependent activities. Our approach computes the aggregate state
> and resource requirements of a cluster of interdependent activities
> and searches for a minimally conflicting temporal placement for this
> cluster of requirements. We first define the state, resource and
> temporal constraints we consider, and describe the difficulty in
> determining a placement for a set of interdependent activities.
> Second, we describe an algorithm for aggregating resource and state
> requirements and for searching for placements of aggregate resource
> state profiles. Third, we show that our aggregation search method
> outperforms the alternative approach of searching for legal placements
> of the constituent activities individually on both synthetic problems
> and problems from planetary rover and spacecraft operations domains.*

**1. Introduction**

Automated planning and scheduling has shown considerable promise in
enabling faster decisions, better decisions, and decisions incorporating
more information in a wide range of application areas ranging from
production management, supply chain optimization, to spacecraft
operations. However, as these systems scale up to real-world problems,
they must be able to represent complex resource, state, and temporal
constraints while solving large problems. It is in the ability to
increase the richness of problems represented while efficiently finding
solutions that the success of these approaches will be measured.

One difficulty of scaling up is the ability to solve problems involving
large number of activities, states and resources. As the number of
activities increases, the search space relating to activity placement
tends to grow exponentially. Additionally, as the number of states and
resources grows, the number of decisions and checks to determine whether
or not an activity placement is valid increases, further increasing
computational difficulties. Large problems are difficult because of
problem interactions through complex, interlinked activities. Often a
set of activities is tightly coupled through resource and/or state usage
or enablement. For example, one activity may control a state which a
subsequent activity requires (such as activity *A* turning on a piece of
equipment that satisfies a requirement for activity *B*). Or an activity
may deplete a resource that is subsequently renewed by another activity
(such as activity *A* producing data stored in a buffer which is then
transmitted by activity *B*, freeing the buffer resource). These highly
interdependent activities cause difficulties in search because a change
to one of the activities typically significantly affects the interlinked
activities, thus it is difficult to propose changes in the placement of
one of the activities without a detailed analysis of the options of
re-placement of the linked activities.

Interdependent activities are challenging because they stymie local
search approaches. Local, heuristic problem-solving methods \[6, 12\]
have been used with considerable effectiveness in solving some
large-scale problems. Unfortunately, interdependent activities cause
difficulties to local search methods. This is because in order to
resolve a problem with one of the coupled activities, the plan is likely
to require modification of all of the clustered activities. To the local
search, when changing a single one of the activities, it appears that
resolution of a single conflict has caused emergence of a large number
of new conflicts that may take considerable effort to resolve. Thus, the
local search method observes a local maxima.

This paper describes an approach to solving the problem of placement of
interdependent sets of activities. In this approach, we compute an
aggregate profile that encapsulates the requirements and effects of the
activities on states and resources. This aggregate profile is then used
to determine legal (or best possible) placements for the complete set of
activities allowable in the current plan.

This problem of placement of activities is an important aspect of
solving combined planning and scheduling problems. In many approaches to
combined planning and scheduling, one alternates between finding
activities to satisfy state and temporal constraints (planning) and
finding temporal assignments and resources for those activities
(scheduling). Complex activity placement is also an important component
of many scheduling problems, as finding temporal assignments for complex
activities can be computationally challenging.

**2. Problem Definition**

We address the problem of finding legal placements for complex
activities. A legal placement for an activity is the assignment of its
start- and end-times such that no constraints in the problem are
violated. In this section we define the constraints that we use to
represent the problem.

The activity is the basic component of a plan. Activity schemas
correspond to types of activities. Activity instances that occur in a
plan must respect the general constraints defined by the schemas. An
activity schema has *temporal constraints* that require all instances of
the activity to satisfy interval temporal relations with respect to
other activities in a plan. For example, every instance of a machine
action may require that there be an instance of a calibrate action from
10 to 120 time units beforehand. In general, a temporal constraint for
an activity *A* specifies that there must exist and activity *B* of type
*T* with *R*(*A*,*B*) holds for a specified temporal relation *R* that
relates the start- or end-point of *A* to the start- or end-point of *B*
(e.g., *A* ends after the start of *B*).

An activity schema may also specify state and resource constraints (also
called *reservations*). For example, the machine action may require 20
units of power (a resource constraint) and that the specified machine is
ON (a state constraint).

Our model of states (and resources) is based on timelines, where a
timeline is a representation of a discrete variable over time. A
timeline is a series of ground values and each element in this series is
called a timeline unit. The start and end of each unit is grounded (that
is to say it is an absolute point in time). No two units overlap in time
and no gaps in value assignments appear from the start of the timeline
to the end.

State and resource timelines have problem instance constraints. For
example, a problem instance constraint on a resource may specify the
minimum and maximum legal value for a resource variable. A problem
instance constraint on a state timeline may specify the legal state
transitions that are allowed for that state variable.

Activities also have state and resource requirements and influences
(called reservations). There are two types of state reservations: 1)
changers and 2) users. A state-changer reservation assigns a value to a
state-variable starting at the state-changer's start-time and continuing
until another state-changer or the end of the planning horizon. The
start-time of a state-changer is the same as the start-time of the
activity containing it. A state-user reservation constrains the value of
a state variable over its temporal extent. The temporal extent of a
state-user is the same as the temporal extent of the activity containing
it. Resource reservations require the availability of a resource. There
are two types of resources: depletable and non-depletable. If the
resource is depletable, an activity's usage of the resource reduces the
resource availability in perpetuity (such as fuel). If the resource is a
non-depletable, the resource is returned at the end of the reservation
(such as use of a piece of equipment).

We now return to the problem addressed by this paper: given a plan *P*
with an existing set of activities *A*~1~, find placements for a new set
of interdependent activities *A*~2~ that is consistent with all
constraints of all activities in *A*~1~ and *A*~2~*.*

The constraints of activities in *A*~1~ may be resource or state
constraints. Activities in *A*~2~ contain temporal constraints as well
as resource and state constraints. Temporal constraints are one example
of how multiple activities may be linked together as groups. The
constraints of activities in *A*~1~ and *A*~2~ are consistent when
considered independently. Constraints are violated only when *A*~1~ and
*A*~2~ are combined.

However, moving an activity may violate its temporal constraints. We can
still move the activity, but then we will need to re-satisfy the
temporal constraints of the activity. In order to end up moving a set of
interlinked activities the algorithm would need to move all of the
related activities individually and then re-validate their temporal
constraints. Unfortunately, this is a large number of search steps to
escape a local minimum (from the perspective of the number of violated
constraints).

![](media/image1.wmf)

**Figure 1** *Moving Interlinked Activities*

One solution is to consider *all* temporally "connected" activities in
unison, thereby preserving the temporal constraints while satisfying
reservations. We call the application of such macro operations
*aggregate search*[^1]. This method is depicted graphically above in
section A of Figure 1. The alternative, considering each of the
constituent activities individually, is hown graphically in section B of
the above Figure. However, the reservations among the group of
activities being moved may *interact*. This complicates efficiently
calculating legal intervals (if any exist) to move the group with
respect to all reservations.

For example, consider a collection of activities: a science observation
*C* that includes activities *a*~1~ and *a*~2~ where *a*~1~ precedes
*a*~2~. Activity *a*~1~ includes a state-changer reservation that
constrains the "camera aperture" state to be "open" and *a*~2~ includes
a state-user reservation that constrains the "camera aperture" state to
be "open", then *a*~2~'s reservation is satisfied by *a*~1~'s
reservation (assuming no intervening activities' reservations affect the
state of the "camera-aperture"). If we naïvely examine valid temporal
locations for *C* with respect to the "camera-aperture" state by
examining each reservation independently, then *a*~2~ can only be placed
during an interval where the "camera-aperture" is already "open." This
is incorrect because *a*~1~ is in *C* and will be moved along with
*a*~2~. Thus, in this case, the naïve approach would incorrectly report
some legal placements as illegal.

**Figure 2** *Camera Aperture*

Now consider a complex activity *C* where *a*~1~ uses 5 MB of memory
storage and *a*~2~ uses 10 MB of memory storage. Also suppose that
before a 10 a.m. downlink, we have a total of 10 MB storage available
and after 10 a.m. we have 30 MB of storage available. If we naïvely
examine valid temporal locations for *C* as before, *a*~1~ can be placed
anywhere that there is 5 MB storage and *a*~2~ anywhere that there is 10
MB storage available so that *C* could occur either before or after 10
a.m. This is incorrect because *a*~1~ and *a*~2~ negatively interact.
The naïve approach would in this case incorrectly report some illegal
placements as legal.

**Figure 3** *Memory Storage*

In general, the problem is that the activities in a group may influence
states and resources used by other activities in the group. Thus, the
straightforward approach of considering each activity independently and
intersecting the legal times will produce incorrect results.[^2]

One possible approach would be to note that one could incrementally
place individual activities in the grouping. Such an approach would
place activities in forward temporal order (because only a previous
activity could alter a state or resource for a subsequent activity).
Such an approach would place *a*~1~ at a legal time then determine legal
placements for *a*~2~ and so on. This approach has two problems. First,
to be complete one would need to attempt all legal placements for each
of the preceding activities (i.e. one would have to iterate through all
placements of *a*~1~ and for each such placement compute legal times for
*a*~2~). Second, we allow an action model where two activities may begin
at the same start time where each causes a state or resource change that
affects a reservation of the other activity. Such activities must be
considered simultaneously to determine valid placements.

The remainder of the paper we describe an approach to correctly
computing the legal locations for a complex activity, empirically
document the effectiveness of this technique, and discuss conclusions,
related and future work.

**3. Aggregate Search**

Our aggregate search technique is based on the observation that
interacting reservations impose different constraints on the state or
resource than those imposed by individual reservations. This new
reservation may be more or less constraining, depending on the nature of
the interaction. Therefore, we first transform *interacting*
reservations into *non*-*interacting* reservations that preserve the
semantic content of the original set of reservations. We then calculate
valid intervals for the collection of activities by collecting valid
intervals for the new non-interacting reservations and intersecting
them. This results in the solution to our problem: "where can we move
this collection of activities considering constraints on states and
resources while maintaining the existing temporal relationships?"

We describe the processing of three types of constraints: 1)
non-depleting resource; 2) depleting resource; and 3) symbolic state
heretofore referred to as *state*. A resource timeline represents a
continuous resource with a minimum and maximum value. Minimum and
maximum values are part of the global reservations set. The value of a
reservation on a particular resource is applicable only during the
temporal extent of that reservation. In this sense, resource timelines
represent the depletion and renewal (or renewal and depletion) of a
shared resource at the start and end of each reservation constraining
the shared resource represented by the timeline. Clearly, purely
depleting or renewing reservations are possible by setting the end-time
of the reservation to the end of the planning horizon, *End*. However,
it is possible to implement depletable resources more efficiently -- we
describe such an implementation in this article. A state timeline
represents a symbolic state. Global reservations on a particular state
are the allowed transitions from one state to the next. Both state and
resource timelines are constrained by global reservations defining a
single default value. We will proceed by formalizing state and resource
timelines, reservations, and violations of constraints heretofore
referred to as *conflicts*.

####### Definitions

We assume the earliest and latest start- and end-times, *Start* and
*End*, i.e. the planning horizon. We assume that we are given the
previously mentioned plan-state *P* and set of constraints. We assume
that we wish to compute times to move a collection of activities *C*
that violate no timeline constraints, heretofore referred to as *legal*
times*.* We assume global set of activities *A* which contains *C*. We
select a reference activity *a* from *C* and compute possible
start-times of *a* such that if all connected activities would move in
unison (thus maintaining consistency among temporal constraints)
reservations of activities in *C* would be consistent. Because the
relative positioning of all of the activities in *C* is being preserved,
we ignore temporal constraints among the members of *C*. We cannot
ignore constraints from time-points of activities in *C* to either
*Start* or *End*, but valid times are easily calculated by examining
each constraint individually and translating the result by the
difference between the start-time of *a* and the constrained time-point.
We do not concern ourselves with temporal constraints between activities
in *C* and other activities in *A*‑*C*. Thus, we must now concern
ourselves only with timeline constraints.

A reservation is a 3-tuple \<*s*, *e*, *v*\> such that *s* is the
start-time, *e* is the end-time, and *v* is the value. For this
discussion, *v* is an integer for resources and a symbol for states.

We use timelines to represent the values of variables over time. So,
each timeline consists of a series of values or timeline units. Each
timeline unit is a 3-tuple with same definition as a reservation for
each type of timeline. The set of timeline units *U* is a series of
units that completely cover without overlapping the temporal extent of
the entire timeline.

A resource timeline is a 4-tuple \<*min*, *max*, *U*, *R*\> where *min*
is the minimum value of the variable at any point in time, *max* is the
maximum value of the variable at any point in time, *U* is the set of
timeline units used to describe the value of the variable over time, and
*R* is the set of reservations whose constraints are already represented
by *U*. We calculate *U* based on *R*. Each timeline unit *u* ∈*U* is
the sum of the values of all *r* ∈ *R* such that *u* is contained
temporally by *r*.

We describe two types of resource timelines: non-depletable and
depletable. The difference between the two is the temporal extent of
reservations. The temporal extent of a non-depletable reservation *r* =
\<*s*, *e*, *v*\> is \[*s*, *e*). The temporal extent of a depletable
reservation *r* = \<*s*, *e*, *v*\> is \[*s*, *End*). We differentiate
between them because we can gain some efficiencies both in aggregating
and calculating valid intervals for reservations based on knowledge
about the temporal extent of a reservation.

A resource timeline is in *conflict* (at least one of the constraints on
the shared resource represented by the timeline is violated) iff ∃
\<*s*, *e*, *v*\> ∈ *U* \| *v* \< *min* ∨ *v* \> *max*.

A state timeline is a 5-tuple \<*transitions*, *U*, *R~changers~*,
*R~users~*, *d*\> where *transitions* is a set of 2-tuples of symbols
representing allowable transitions from one state to the next, *U* is
the set of timeline units used to describe the value of the variable
over time, *R~changers~* is the set of reservations whose constraints
are already represented by *U*, *R~users~* is the set of constraints on
the validity of values represented by *U*, and *d* is the default symbol
for the timeline if no changer reservation defines the value of a
timeline unit. We also reserve the symbol ω for the conflicting
assignment of a timeline unit (e.g. two changers at the same time change
a unit to two different values). We calculate *U* based on
*R~changers~*. If no changer in *R~changers~* begins at the start of the
timeline, then the earliest timeline unit in *U* is assigned a value of
*d*, otherwise it is handled as a subsequent timeline unit. Each
subsequent timeline unit *u* = \<*s~u~*, *e~u~*, *v~u~*\> ∈ *U* contains
at least one changer *c* = \<*s~c~*, *e~c~*, *v~c~*\> ∈ *R~changers~*
such that *s~u~* = *s~c~*. If there exists another *c\'* = \<*s~c~\'*,
*e~c~\'*, *v~c~\'*\> ∈ *R~changers~* such that *s~u~* = *s~c~\'* but
*v~c~* ≠ *v~c~\'*, then *v~u~* is assigned ω. Otherwise, all *v~c~*,
*v~c\'~*, etc. are the same, so *v~u~* is assigned *v~c~*. There exists
no changer *c* = \<*s~c~*, *e~c~*, *v~c~*\> ∈ *R~changers~* such that
*s~u~* \< *s~c~* \< *e~u~*.

Two types of conflicts are possible for state timelines: *state-usage*
and *state-transition* conflicts. A state timeline is in *conflict* if
there exists either a state-usage or a state-transition conflict. There
exists a state-usage conflict iff ∃ \<*s*, *e*, *v*\> ∈ *U* \| (∃
\<*s~u~*, *e~u~*, *v~u~*\> ∈ *R~users~* \| (*s~u~* ≤ *s* \< *e~u~* ∨
*s~u~* \< *e* ≤ *e~u~* ) ∧ *v* ≠ *v~u~* ). There exists a
state-transition conflict iff ∃ \<*s*, *e*, *v*\> ∈ *U* \| (∃ \<*s\'*,
*e\'*, *v\'*\> ∈ *U* \| *e* = *s\'* ∧ \<*v*, *v\'*\> ∉ *transitions*).

We define an activity *a* be a 3-tuple \<*s*, *e*, *R*\> such that *s*
is the start-time of the activity, *e* is the end-time of the activity,
and *R* is a set of 2-tuples \| ∀ \<*T*, *r* = \<*s~r~*, *e~r~*,
*v~r~*\> \> ∈ *R*, (*T* ∈ *Timelines*) ∧ *s~r~* = *s* ∧ *e~r~* = *e*.

At last, we can describe the transformation of interacting state and
resource reservations into non-interacting reservations. We start by
gathering all reservations from all activities in *C* into a set *R~m~*
(reservations to be moved). Since all temporal relationships are
grounded and we wish to maintain these, we require a single time-point τ
that is related to all time-points in *C*. We are given *a* in *C*, so
we will use the start-time of *a* for τ. Thus, our transformed problem
is to find valid assignments for τ such that no new conflicts arise,
assuming all reservations in *R~m~* are moved maintaining their
relationship to τ.

We then partition reservations according to the type of timeline being
constrained because interactions among reservations are limited to
reservations on the same timeline. Let *R~p~* be the partition of *R~m~*
according to the timeline being constrained by any *r* in *R~m~* . An
element (*T*, *R*) of the partition *R~p~* is a timeline *T* and a set
of reservations on that timeline *R*. Note that valid assignments *V*
for τ considering *R~p~* can be calculated by finding valid assignments
*V~i~* for each (*T*, *R*)*~i~* ∈ *R~p~* and intersecting them.
Therefore, our task is to find *V~i~* for each (*T*, *R*)*~i~* ∈ *R~p~*.

In the simplest case, either *R* in (*T*, *R*)*~i~* is empty or has only
one reservation. We need only calculate *V~i~* as we had using the naïve
calculation because no interactions are possible.

####### Interacting Non-Depletable Resource Reservations

For non-depletable timelines, only reservations that overlap temporally
interact because the temporal extent of the effect of the reservation is
exactly the temporal extent of the reservation. Formally, *r*~1~ and
*r*~2~ ∈*R* **interact** iff *r*~1~ ≠ *r*~2~, \<*s*~1~, *e*~1~, *v*~1~\>
= *r*~1~, \<*s*~2~, *e*~2~, *v*~2~\> = *r*~2~, *s*~1~ ≤ *s*~2~ \< *e*~1~
∨ *s*~1~ \< *e*~2~ ≤ *e*~1~. Valid assignments for τ with respect to
non-interacting *r* ∈*R* can be calculated directly using the naïve
approach. For interacting *r* ∈*R*, we calculate a new set of
reservations *R\'* that contains reservations that are temporally
disjoint (and therefore non-interacting) but express the same
constraints. This requires at most 2*n* reservations where *n* =
\|*R*\|.

First, we assume *R\'* = {\<*Start*, *End*, 0\>}. To transform an
interacting \<*s*, *e*, *v*\> ∈ *R*, we first split any reservation in
*R\'* that contains either *s* or *e* into two reservations i.e.

**if** ∃ \<*s\'*, *e\'*, *v\'*\> ∈ *R\'* \| *s\'* \< *s* \< *e\'*

> *R\'* ← (*R\'* - \<*s\'*, *e\'*, *v\'*\>) ∪ {\<*s\'*, *s*, *v\'*\>,
> \<*s*, *e\'*, *v\'*\>}

**endif**

**if** ∃ \<*s\'*, *e\'*, *v\'*\> ∈ *R\'* \| *s\'* \< *e* \< *e\'*

> *R\'* ← (*R\'* - \<*s\'*, *e\'*, *v\'*\>) ∪ {\<*s\'*, *e*, *v\'*\>,
> \<*e*, *e\'*, *v\'*\>}

**endif**

Then, we update the values of all *r\'*∈ *R\'* contained by \[*s*, *e*)
by *v*. This results in *R\'* being a set of non-interacting
reservations. We simply calculate the valid assignments for τ for each
*r\'* ∈ *R* and intersect these with *V*.

**Figure 4** *Transformed Non-depletable Resource Reservations*

We describe a function that returns a set of valid assignments *S* given
a timeline *T* and an individual non-depletable reservation *r*. We
assume *S* = ∅.

[Valid-Non-Depletable-Intervals]{.smallcaps}(*r* = \<*s~r~*, *e~r~*,
*v~r~*\>, *T* = \<*min*, *max*, *U*, *R* \>) returns a set *S*

1.  *lookingForStart* ← TRUE

2.  **foreach** \<*s~u~*, *e~u~*, *v~u~*\> ∈ *U* **in ascending order
    by** *s~u~*

3.  **if** *min* ≤ (*v~r\ ~*+ *v~u~*) ≤ *max*

4.  **if** *lookingForStart*

5.  *st* ← *s~u~*

6.  *lookingForStart* ← FALSE

7.  **else if** ¬*lookingForStart*

8.  *et* ← *s~u\ ~*- (*e~r~* - *s~r~*)

9.  **if** *st* ≤ *et*

10. *S* ← *S* ∪ {\<*st*, *et*\>}

11. *lookingForStart* ← TRUE

12. **return** *S*

####### 

####### 

####### Interacting Depletable Resource Reservations

For depletable resource timelines, all reservations interact because the
effect of a reservation compounds the effects of all previous and
simultaneous reservations. To calculate valid assignments for τ with
respect to *r* ∈*R*, we calculate a new set of reservations *R\'* that
contains reservations that are non-interacting but express the same
constraints. This requires at most *n* reservations where *n* = \|*R*\|.
Obviously, *R* can only contain one depletable reservation and still
remain temporally (and semantically) disjoint. The basic idea is that we
transform a collection of depletable reservations into a collection of
non-interacting non-depletable reservations followed by a single
depletable reservation.

The temporal extent of a depletable reservation *r* = \<*s*, *e*, *v*\>
is \[*s*, *End*), thus implying that this reservation will affect all
subsequent an simultaneous reservations. For example, consider *r*~1~ =
\<*s*~1~, *e*~1~, *v*~1~\> = \<10, 40, 10\> and *r*~2~ = \<*s*~2~,
*e*~2~, *v*~2~\> = \<20, 30, -9\>. If *r*~2~ is to be moved in
conjunction with *r*~1~, the actual requirements on the timeline are
that we require 10 from \[*s*~1~, *s*~2~) and we require 1 from *s*~2~
onward. Formally, {*r*~1~, *r*~2~} transforms to {*r\'*,
*r\'\'*}={\<s~1~, s~2~, v~1~\>, \<s~2~, s~2~, v~1~ + v~2~\>}, where
*r\'* is a non-depletable reservation and *r\'\'* is a depletable
reservation.

Generally, we transform all *r* ∈*R* as follows. First, we assume *R\'*
= {\<*Start*, *Start*, 0\>}. For each \<*s*, *e*, *v*\> ∈ *R*, we
proceed thusly:

**if** ∃ \<*s\'*, *e\'*, *v\'*\> ∈ *R\'* \| *s\'* \> *s*

*R\'* ← *R\'* ∪ {\<*s*, *s*, *v* + *v\'*\>}

*e\'* ← *s*

**else if** ∃ \<*s\'*, *e\'*, *v\'*\> ∈ *R\'* \| *s\'* = *s*

*v\'* ← *v\'* + *v*

**else //** we know that there must ∃ \<*s\'*, *e\'*, *v\'*\> ∈ *R\'* \|
*s\'* \< *s* \< *e\'*

*R\'* ← (*R\'* - \<*s\'*, *e\'*, *v\'*\>) ∪ {\<*s\'*, *s*, *v\'*\>,
\<*s*, *e\'*, *v* + *v\'*\>}

**endif**

Then, we update the values of all *r\'*∈ *R\'* contained by (*s*, *End*)
by *v*, and continue for all *r* ∈*R.* This results in *R\'* being a set
of non-interacting reservations. We simply calculate the valid
assignments for τ for each *r\'* ∈ *R* and intersect these with *V*.

**Figure 5** *Transformed Depletable Resource Reservations*

We describe a function that returns a set of valid assignments *S* given
a timeline *T* and an individual depletable reservation *r*. We assume
*S* = ∅.

[Valid-Depletable-Intervals]{.smallcaps}(*r* = \<*s~r~*, *e~r~*,
*v~r~*\>, *T* = \<*min*, *max*, *U*, *R* \>) returns a set *S*

1.  *et* ← *End* - (*e~r~* - *s~r~*)

2.  *st* ← *End*

3.  **foreach** \<*s~u~*, *e~u~*, *v~u~*\> ∈ *U* **in descending order
    by** *s~u~*

4.  **if** *min* ≤ (*v~r\ ~*+ *v~u~*) ≤ *max*

5.  *st* ← *s~u~*

6.  **else** **break**

7.  **if** *st* ≤ *et*

8.  *S* ← *S* ∪ {\<*st*, *et*\>}

9.  **return** *S*

####### Interacting State Reservations

For state timelines, many interactions are possible because
state-changer reservations can affect the value of the timeline outside
of their temporal extent. First, we partition *R* into *L~changers~* and
*L~users~*. If *L~changers~* = ∅ we can naïvely calculate and intersect
valid intervals on all *r~u~* in *L~users~* because state-user
reservations only constrain the value of the timeline within their
temporal extent. Likewise, if no *r~c~* in *L~changers~* begin before
the end of an *r~u~* in *L~users~* we can calculate and intersect valid
intervals naïvely. Thus, we assume that *V* represents the results of
all non-interacting reservations, *L~changers~* ≠∅, and all *r~u~* ∈
*L~users~* begin after or at the same time as the beginning of at least
one *r~c~* ∈ *L~changers~*. We proceed by generating a set *R´* of
non-interacting state reservations. These will be neither changers nor
users. We assume that *T* = \< *transitions*, *U*, *R~changers~*,
*R~users~*, *d* \>.

We first consider interactions among *r~c~* ∈ *L~changers~*. We assume
no two changers share the same start-time. This is valid because the
effect of two (or more) different changer reservations starting at the
same time but having the same value is exactly the same as a single
changer reservation. If two (or more) changers start at the same time
but have different values, at least one timeline unit *u* ∈ *T* will
have a value of ω, meaning that the resultant set of intervals will be
∅. We are guaranteed that *L~changers~* contains at least one
reservation.

Let *s* and *v* be the start-time and value of the first changer in
*L~changers~* , respectively.

> *R\'* ← *R\'* ∪ {*leading-changer* \<*s*, *End*, *v*\>}

(End-times are not pertinent for changer reservations.) A
*leading-changer* *r~lc~* may be placed within the temporal extent of
any timeline unit *u* ∈ *T* that contains *r~lc~* and for which there
exists a \<*v~u~*, *v~c~*\> ∈ *transitions* where *v~u~* is the value of
the unit and *v~c~* is the value of the changer *r~lc~*.

Let *s* and *v* be the start-time and value of the last changer in
*L~changers~* , respectively.

> *R\'* ← *R\'* ∪ {*ending-changer* \<*s*, *End*, *v*\>}

![](media/image10.wmf)An *ending-changer* *r* = \<*s*, *e*, *v*\>
constrains *T* with respect to the nearest changer \<*s~c~*, *e~c~*,
*v~c~*\> in *R~changers~* \| *s* ≤ *s~c~*, if such a changer exists. If
*s* = *s~c~*, then *v~c~* must equal *v*. Otherwise, \<*v*, *v~c~*\>
must be in *transitions*. *r* also constrains *T* with respect to all
users \<*s~u~*, *e~u~*, *v~u~*\> in *R~users~* whose temporal extent
overlaps \[*s*, *s~c~*). Note: if no changer exists after or during *s*,
then *s~c~* = *End*. *v~u~* must equal *v*.

**Figure 6** *Leading- and Ending-Changer Reservations*

If *L~changers~* contains two or more reservations, we must create
reservations that represent the interactions between them. We need only
consider consecutive reservations because the effect of one
state-changer reservation never extends past another (in time).

**foreach** \<*s*~1~, *e*~1~, *v*~1~\> and \<*s*~2~, *e*~2~, *v*~2~\> ∈
*L~changers~* \| no other reservation in *L~changers~* is contained in
\[*s*~1~, *s*~2~\]

> **if** \< *v*~1~, *v*~2~\> ∈ *transitions*
>
> *R\'* ←*R\'* ∪{*no-changers-or-allow-first* \<*s*~1~+1, *s*~2~,
> *v*~1~\>}
>
> *R\'* ←*R\'* ∪{*no-changers-or-allow-last* \<*s*~1~+1, *s*~2~,
> *v*~2~\>}
>
> **else**
>
> *R\'*←*R\'* ∪{*need-a-changer-to-allow-first*\<*s*~1~+1, *s*~2~,
> *v*~1~\>}
>
> *R\'*←*R\'* ∪{*need-a-changer-to-allow-last*\< *s*~1~+1, *s*~2~,
> *v*~2~\>}
>
> **endif**
>
> *R\'* ← *R\'* ∪ {*users-match-or-hidden* \<*s*~1~+1, *s*~2~, *v*~1~\>}

**endfor**

A *no-changers-or-allow-first* \<*s*, *e*, *v*\> constrains *T* to
either have no changers in *R~changers~* over \[*s*, *e*) or for the
first changer \<*s´*, *e´*, *v´*\> *transitions* contains \<*v*, *v´*\>.
A *no-changers-or-allow-last* reservation \<*s*, *e*, *v*\> constrains
*T* to either have no changers in *R~changers~* over \[*s*, *e*) or for
the last changer \<*s´*, *e´*, *v´*\> *transitions* contains \<*v´*,
*v*\>. A *need-a-changer-to-allow-first* \<*s*, *e*, *v*\> constrains
*T* such that there exists at least one changer in *R~changers~* within
\[*s*, *e*) and for the first contained changer \<*s´*, *e´*, *v´*\>,
*transitions* contains \<*v*, *v´*\>. A *need-a-changer-to-allow-last*
reservation \<*s*, *e*, *v*\> constrains *T* such that there exists at
least one changer in *R~changers~* within \[*s*, *e*) and for the last
contained changer \<*s´*, *e´*, *v´*\>, *transitions* contains \<*v´*,
*v*\>. A *users-match-or-hidden* reservation *r* = \<*s*, *e*, *v*\>
constrains *T* such that for the earliest reservation *r\'* = \<*s\'*,
*e\'*, *v\'*\> ∈*R~changers~* ∪ *R~users~* \| *s* ≤ *s\'* \< *e*, *r\'*
∈ *R~changers~* ∨ *v* = *v\'*.

![](media/image11.wmf)

**Figure 7** *Allowed Changer to Changer Reservations*

![](media/image12.wmf)

**Figure 8** *Disallowed Changer to Changer Reservations*

[Valid-No-Changers-or-Allow-First-Intervals]{.smallcaps}

(*r* = \<*s~r~*, *e~r~*, *v~r~*\>, *T* = \<*transitions*, *U*,
*R~changers~*, *R~users~*, *d*\>) returns a set *S*

1.  **foreach** \<*s~u~*, *e~u~*, *v~u~*\> ∈ *U* **in ascending order
    by** *s~u~*

2.  **if** (*e~r~* - *s~r~*) + 2 \< (*e~u~* - *s~u~*) // no changers
    calculation

3.  *S* ← *S* ∪ {\<*s~u~*+1, *e~u~*-(*e~r~* - *s~r~*)-1\>}

4.  **if** ∃ \<*s\'*, *e\'*, *v\'*\> ∈ *U* \| *s\'* \> *s~u~* ∧ ∀
    \<*s\'\'*, *e\'\'*, *v\'\'*\> ∈ *U*, *s\'\'* \< *s\'* ⊃ *s\'\'* \<
    *s~u~* // next unit in *U*

5.  **if** \<*v~r~*, *v\'* \> ∈ *transitions* // allow first calculation

6.  *S* ← *S* ∪ {\<**max**(*s~u~*+1, *e~u~*-(*e~r~* - *s~r~*)-1),
    *e~u~*\>}

7.  **return** *S*

[Valid-No-Changers-or-Allow-Last-Intervals]{.smallcaps}

(*r* = \<*s~r~*, *e~r~*, *v~r~*\>, *T* = \<*transitions*, *U*,
*R~changers~*, *R~users~*, *d*\>) returns a set *S*

1.  **foreach** \<*s~u~*, *e~u~*, *v~u~*\> ∈ *U* **in ascending order
    by** *s~u~*

2.  **if** (*e~r~* - *s~r~*) + 2 \< (*e~u~* - *s~u~*) // no changers
    calculation

3.  *S* ← *S* ∪ {\<*s~u~*+1, *e~u~*-(*e~r~* - *s~r~*)-1\>}

4.  **if** \<*v~u~*, *v~r~* \> ∈ *transitions* // allow last calculation

5.  *S* ← *S* ∪ {\<su + 1 - (*e~r~* - *s~r~*), **min**(*s~u~*, *e~u\ ~*-
    (*e~r~* - *s~r~*)-1)\>}

6.  **return** *S*

[Valid-Need-a-Changer-to-Allow-First-Intervals]{.smallcaps}

(*r* = \<*s~r~*, *e~r~*, *v~r~*\>, *T* = \<*transitions*, *U*,
*R~changers~*, *R~users~*, *d*\>) returns a set *S*

1.  **foreach** \<*s~u~*, *e~u~*, *v~u~*\> ∈ *U* **in ascending order
    by** *s~u~*

2.  **if** ∃ \<*s\'*, *e\'*, *v\'*\> ∈ *U* \| *s\'* \> *s~u~* ∧ ∀
    \<*s\'\'*, *e\'\'*, *v\'\'*\> ∈ *U*, *s\'\'* \< *s\'* ⊃ *s\'\'* \<
    *s~u~* // next unit in *U*

3.  **if** \<*v~r~*, *v\'* \> ∈ *transitions* // allow first calculation

4.  **if** (*e~r~* - *s~r~*) \< (*e~u~* - *s~u~*)

5.  *S* ← *S* ∪ {\<*e~u~*-(*e~r~* - *s~r~*), *e~u~* - 1\>}

6.  **else**

7.  *S* ← *S* ∪ {\<*s~u~* + 1, *e~u~* - 1\>}

8.  **return** *S*

[Valid-Need-a-Changer-to-Allow-Last-Intervals]{.smallcaps}

(*r* = \<*s~r~*, *e~r~*, *v~r~*\>, *T* = \<*transitions*, *U*,
*R~changers~*, *R~users~*, *d*\>) returns a set *S*

1.  **foreach** \<*s~u~*, *e~u~*, *v~u~*\> ∈ *U* **in ascending order
    by** *s~u~*

2.  **if** ∃ \<*s\'*, *e\'*, *v\'*\> ∈ *U* \| *s\'* \> *s~u~* ∧ ∀
    \<*s\'\'*, *e\'\'*, *v\'\'*\> ∈ *U*, *s\'\'* \< *s\'* ⊃ *s\'\'* \<
    *s~u~* // next unit in *U*

3.  **if** \<*v\'*, *v~r~* \> ∈ *transitions* // allow last calculation

4.  **if** (*e~r~* - *s~r~*) \< (*e~u~* - *s~u~*)

5.  *S* ← *S* ∪ {\<*e~u~*-(*e~r~* - *s~r~*), *e~u~* - 1\>}

6.  **else**

7.  *S* ← *S* ∪ {\<*s~u~* + 1, *e~u~* - 1\>}

8.  **return** *S*

[Valid-Users-Match-or-Hidden-Intervals]{.smallcaps}

(*r* = \<*s~r~*, *e~r~*, *v~r~*\>, *T* = \<*transitions*, *U*,
*R~changers~*, *R~users~*, *d*\>) returns a set *S*

1.  *S* ← {\<*Start*, *End*\>}

2.  **foreach** \<*s~u~*, *e~u~*, *v~u~*\> ∈ *U*

3.  **foreach** \<*s~user~*, *e~user~*, *v~user~*\> ∈ *R~users~* \|
    *s~u~* ≤ *s~user~* \< *s~e~* ∨ *s~user~* \< *s~u~* \< *e~user~* //
    users of this unit

4.  **if** *v~user~* ≠ *v~r~*

5.  *S* ← *S* - \<**max**( *s~user~* - (*e~r~* - *s~r~*), *s~u~*),
    **min**(*e~u~* - 1, *e~user~* - 1)\>

6.  **return** *S*

Next, we consider interactions among *r~u~* in *L~users~*. We assume
that no two state-user reservations in *L~users~* overlap and have
different values because this is impossible to solve and would result in
no possible non-conflicting assignments for τ.

**foreach** \<*s~u~*, *e~u~*, *v~u~*\> ∈ *L~users~*

> *R\'* ← *R\'* ∪ {*no-changers-or-match* \<*s~u~*, *e~u~*, *v~u~*\>}

**endfor**

A *no-changers-or-match* reservation constrains *T* such that either no
changers in *R~changers~* are contained by \[*s~u~*, *e~u~*) or for each
contained changer \<*s~c~*, *e~c~*, *v~c~*\>, *v~c~* = *v~u~*.

![](media/image13.wmf)

**Figure 9** *User Reservations*

[Valid-No-Changers-Or-Match-Intervals]{.smallcaps}

(*r* = \<*s~r~*, *e~r~*, *v~r~*\>, *T* = \<*transitions*, *U*,
*R~changers~*, *R~users~*, *d*\>) returns a set *S*

1.  *S* ← {\<*Start*, *End*\>}

2.  **foreach** \<*s~u~*, *e~u~*, *v~u~*\> ∈ *U* **in ascending order
    by** *s~u~*

3.  **if** *v~u~* ≠ *v~r~*

4.  *S* ← *S* - \<*s~u~* - (*e~r~* - *s~r~*) + 1, *s~u~*\>

5.  **return** *S*

Finally, we consider interactions among changers and users. We assume ∀
\<*s*, *e*, *v*\> ∈ *L~users~*, ∀ \<*s\'*, *e\'*, *v\'*\> ∈
*L~changers~*, *s* ≤ *s\'* \< *e* ⊃ *v* = *v\'*. Otherwise, there are no
possible non-conflicting assignments for τ.

**foreach** *r~u~* = \<*s~u~*, *e~u~*, *v~u~*\> in *L~users~*

> find the latest *r~c~* = \<*s~c~*, *e~c~*, *v~c~*\> ∈ *L~changers~* \|
> *s~c~* ≤ *s~u~*
>
> **if** (*s~c~* = *s~u~* or *s~c~* = *s~u~* +1) ∧ *v~c~* = *v~u~*
>
> the reservation *r~u~* is satisfied by *r~c~* and we know (due to the
> semantics of previously described reservations) that any changers in
> *R~changers~* contained by \[*s~c~*, *s~u~*\] also satisfies *r~u~*,
> therefore this interaction is satisfied.

**elseif** *v~c~* = *v~u~*

> *R\'*←*R\'* ∪{*no-changers-or-last-changer-match*\<*s~c~*+1,*s~u~*
> -1,*v~u~*\>}
>
> **else**
>
> *R\'*←*R\'* ∪{*need-a-changer-to-match-last* \< *s~c~*+1, *s~u~*,
> *v~u~*\>}
>
> **endif**

**endfor**

A *no-changers-or-last-changer-match* reservation *r* constrains *T*
such that either no reservations in *R~changers~* are contained by the
temporal extent of *r* or the last contained changer *r\'* has a value
equal to that of *r*. A *need-a-changer-to-match-last* reservation *r*
constrains *T* such that there exists at least one changer in
*R~changers~* contained within the temporal extent of *r* and the last
contained changer *r\'* has a value equal to that of *r*. So, for each
user in *L~users~* we add at most two reservations to *R´*.

**Figure 10** *Transformed State Reservations*

[Valid-No-Changers-Or-Last-Changer-Match-Intervals]{.smallcaps}

(*r* = \<*s~r~*, *e~r~*, *v~r~*\>, *T* = \<*transitions*, *U*,
*R~changers~*, *R~users~*, *d*\>) returns a set *S*

1.  *S* ← {\<*Start*, *End*\>}

2.  **foreach** \<*s~u~*, *e~u~*, *v~u~*\> ∈ *U* **in ascending order
    by** *s~u~*

3.  **if** *v~u~* ≠ *v~r~*

4.  *S* ← *S* - \<*s~u~* - (*e~r~* - *s~r~*), **min**(*s~u~*, *e~u~* -
    (*e~r~* - *s~r~*) -1)\>

5.  **return** *S*

[Valid-Need-a-Changer-to-Match-Last-Intervals]{.smallcaps}

(*r* = \<*s~r~*, *e~r~*, *v~r~*\>, *T* = \<*transitions*, *U*,
*R~changers~*, *R~users~*, *d*\>) returns a set *S*

1.  **foreach** \<*s~u~*, *e~u~*, *v~u~*\> ∈ *U* **in ascending order
    by** *s~u~*

2.  **if** *v~u~* = *v~r~*

3.  *S* ← *S* + {\<*s~u~* - (*e~r~* - *s~r~*), **min**(*s~u~*, *e~u~* -
    (*e~r~* - *s~r~*) )\>}

4.  **return** *S*

It can be shown that valid intervals for each type of reservation
described herein can be computed in time that is proportional to the
number of reservations on the timeline (space constraints preclude
description here). Also, faster schemes in terms of average complexity
using already calculated intervals to reduce the computation of
intervals are possible, but scoring all intervals for fewest conflicts
would require a complete intersection of all valid intervals for all
reservations.

This completes our transformation from interacting reservations to
non-interacting reservations. We now give a brief analysis of the
complexity of the technique. Let *n~fixed~* be the number of
reservations constraining all timelines. Let *n~move~* be the number of
reservations in the collection to be "moved." If we assume that valid
intervals can be computed for a single reservation in time that is
proportional to the number of reservations on any timeline, then this
algorithm is at worst *O*(*n~fixed~ n~move~*). If we consider the total
number of reservations in the problem to be *n* =*n~fixed\ ~*~+~
*n~move~*, then the complexity of this algorithm is at worst
*O*(*n*^2^). This is true because the transformation from interacting to
non-interacting reservations adds at most a constant factor more
reservations. This transformation might in fact reduce the number of
reservations, depending on the nature of the interaction. It should be
noted that in practice *n~fixed~* is much larger than *n~move~*.

**4. Empirical Evaluation**

We now describe an empirical comparison of the aggregate search
technique to the naïve approach for determining valid placements for
activity groups. In this comparison we examine the number of iterations
and time to place the activity group in a conflict free fashion and the
total number of problems solved for each domain. If superior, the
aggregate search algorithm should result in better solutions (placements
with fewer conflicts), in faster reduction of conflicts, and more
problems being completely solved.

In our empirical analysis we use five models (and corresponding problem
set generators): 1) the VTLI (valid timeline intervals) domain--- a
synthetic model designed to have inter-activity interactions, 2) the EO1
spacecraft operations domain, 3) the Rocky-7 Mars rover operations
domain, 4) the DATA-CHASER shuttle payload operations domain, and 5) the
New Millennium Deep Space Four landed operations domain.

Within each model and corresponding problem set, we generate random
problems that include a background set of fixed activities and a number
of movable activity groups. The activity groups are placed randomly. The
goal is to minimize the number of conflicts in the schedule by
performing planning and scheduling operations.

To solve each problem, we use the ASPEN (Automated Scheduling and
Planning Environment) system using an "iterative repair" algorithm,
which classifies conflicts and attacks them each individually \[4\].
Conflicts occur when a plan constraint has been violated; this
constraint could be temporal or involve a resource or state timeline.
Conflicts are resolved by performing one or more schedule modifications
such as moving, adding, or deleting activities. The iterative repair
algorithm continues until no conflicts remain in the schedule, or a
timeout has expired.

The scheduler entertains minimally conflicting placements when moving
activity groups. In the *control* trials the scheduler does so using the
naïve algorithm for computing valid placements. In the *experiment*
trials the scheduler is using the aggregate search method to compute
valid placements. In all cases for each domain, both trials are using
the same set of heuristics at all other choice-points (e.g., selection
of a conflict or activity group to attempt to repair, where to place
within computed valid intervals, etc.). Note that simple (non-aggregate)
operations are available in both real domains, although they are of
limited comparative utility. Using only non-aggregate operations, the
problems are intractable within reasonable time bounds because the
distance in terms of sub-optimal moves from one local optima to the next
is *O*(*n*) and the space to be searched is *O*(*m^n^*) where *n* is the
number of activities in a movable collection and *m* is the number of
possible locations given by a naïve calculation of legal intervals for
an individual activity, e.g. in the EO1 domain, *n* ranges from 23 to
56; in the Rover domain, *n* ranges from 8 to 17.

We now briefly describe each domain including information on the types
of activities and resources modeled, what the activity groups are, and
how they are interdependent.

*VTLI Domain*

The VTLI domain consists of a color state variable and a charge
resource. Color may be *red*, *purple*, or *blue*, and allows any
transition except *red*-to-*blue* and *blue*-to-*red*. Charge is allowed
to be an integer between 0 and 25, defaulting to 0. There are two types
of activity groups for aggregation: color and charge. Each group
consists of four activities: a color-activity may be either a user-of or
changer-to any of the allowed colors; a charge-activity may use from ‑22
to 22 of charge. Because members of the same activity group all use the
same timeline, there will be many intra-group interactions. For example,
one member may change the color to red while a later member needs
purple. This requires placing the pair with a transition to purple
between them. Charge members may overlap, hence reserving the sum of
their values during the overlapping period.

A VTLI problem instance includes random, fixed profiles for the
timelines. Each timeline has 60 fixed reservations with values chosen
from *red*, *purple*, or *blue* for color and from integers between 0
and 24 for charge. The values are chosen randomly, but without
introducing inconsistencies with the model (e.g., illegal transitions).
Each problem also includes ten movable groups of four activities with
equal chance of each group being a color or charge group. We preclude
intra-group reservations which are contradictory (e.g., overlapping
members requiring different color states) but inter-group interactions
may make problems unsolvable for a given fixed profile. The groups are
initially placed at random times within the planning horizon.

######## EO1 Domain

The EO1 domain models the operations of the New Millennium Earth
Observer 1 operations for a two-day horizon \[9\]. It consists of 14
resources, 10 state variables and total of 38 different activity types.
Several activity groups correspond to activities necessary to perform
different types of instrument observations and calibrations. The
activity groups range in size from 23 to 56 activities, many of which
have interactions. For example, taking an image of the earth requires
fixing the solar array drive to avoid blurred images. The high-level
observation activity group includes both commands to fix the SAD and
take the image.

Each EO1 problem instance includes a randomly generated, fixed profile
that represents typical weather and instrument pattern. Each problem
also includes 8 randomly placed instrument requests for observations and
calibrations.

*Rocky-7 Domain*

The Rocky-7 Mars rover domain models operations of a prototype rover for
a typical Martian day \[8\]. It consists of 14 shared resources, 7 state
variables and 25 activity types. Resources and states include cameras
(front, rear, mast), mast, shovel, spectrometer, solar array, battery,
and RAM. There are four activity groups that correspond to different
types of science experiments: imaging a target, digging at a location,
collecting a spectrometer reading from target, and taking a panoramic
image from a location. Activity group size ranges from 8 to 17
activities. Members in activity groups have positive resource
interactions, e.g. opening the aperture for the camera enables
subsequently taking a picture. Activity groups also have negative
interactions, e.g. several member activities using the onboard buffer.
Rover problems are constructed by generating four experiments and
randomly generating parameters for the experiments (such as target
locations).

*New Millennium Deep Space Four Landed Operations Domain*

The DS4 domain models the landed operations of a spacecraft designed to
land on a comet and return a sample to earth. This model has 6 shared
resources, 6 state variables, and 22 activity types. Resources and
states include battery level, bus power, communications,
orbiter-in-view, drill location, drill state, oven states for a primary
and backup oven state, camera state, and RAM. There are two activity
groups that correspond to different types of experiments: 1) mining and
analyzing a sample, 2) taking a picture. Activity group sizes range from
5 to 10. As in the rover domain, activities interact positively and
negatively.

Each DS4 problem instance includes a randomly generated, fixed profile
that represents communications visibility to the orbiting spacecraft.
Each problem also includes five mining and two picture experiments (each
randomly placed.)

*DATA-CHASER Domain*

The DCAPS domain models operations of a shuttle science payload that
flew onboard Space Shuttle Flight STS-85 in August, 1997. It consists of
19 shared resources, 25 state variables, and 70 activity types.
Resources and states include shuttle orientation, contamination state, 3
scientific instruments (doors, relays, heaters, etc.), several RAM
buffers, tape storage, power (for all instruments/devices), and downlink
availability. There is one type of activity group corresponding to one
experiment for each of the 3 scientific instruments. This activity group
consists of 23 activities. As with the other domains, activities in this
activity group interact positively and negatively.

Each DCAPS problem instance includes a randomly generated, fixed profile
that represents shuttle orientation and contamination state. The number
of randomly placed experiments ranges from 2 to 20 based on the fixed
profile for the given problem instance.

*Discussion of the Empirical Results*

We generate twenty random problems for each domain and run ASPEN with
twenty different random seeds for each combination of problem and
technique. Note that we do not guarantee that the problems are solvable.

We evaluate the performance of our technique versus the performance of
the naïve technique in terms of the number of iterations to solve
conflicts, amount of time to solve conflicts, and the total number of
problems solved for each domain.

For the VTLI domain, our aggregate technique is slightly slower than the
naïve technique per iteration, but performs better than the naïve
technique in terms of the number of conflicts solved. This slowdown is
expected in that aggregation of interacting state reservations leads to
a constant factor more non-interacting reservations.

For the EO1 operations domain, the naïve technique and aggregate
technique perform similarly at first. This is because a number of the
conflicts do not involve interacting reservations and hence the naïve
technique can solve them. However, many of the conflicts involve
interacting reservations. Because the aggregate techniques correctly
handle these interactions, it is able to solve these conflicts. Thus in
the longer term the aggregate is able to solve more conflicts in the
schedule.

For the Rocky-7 Mars rover operations domain, the aggregate technique
appears to strictly dominate the naïve technique. Interestingly,
conflict count rises before it falls for both algorithms. This is due to
the added planning necessary to solve conflicts. Adding activities leads
to more conflicts initially, but eventually leads to solutions.

For the New Millennium DS4 Landed Operations domain, the aggregate
technique strictly outperforms the naïve technique. Conflict count rises
before it falls as in the rover domain and for the same reason, except
the algorithm employing the naïve technique never recovers. Many of the
activities in a group interact, therefore the naïve technique often
makes mistakes in recommending placements for activity groups. Because
of this faulty advice, repair using the naïve approach actually
increases the number of conflicts in the schedule.

For the DCAPS domain, the aggregate technique strictly outperforms the
naïve technique. In this domain, almost all of the activities in a group
interact, leading to similar consequences as the DS4 domain.

In terms of number of problems solved, we observe that the aggregate
search technique is able to completely solve (i.e., remove all
conflicts) more problems than the naïve approach in all five domains.

  --------------- ---------- ----------- ----------- ----------- ----------- -------------
                  **VTLI**   **EO1**     **Rover**   **DCAPS**   **DS4**     **total**

  **aggregate**   84/~400~   149/~400~   390/~400~   387/~400~   243/~400~   1253/~2000~

  **naïve**       4/~400~    60/~400~    243/~400~   1/~400~     0/~400~     308/~2000~
  --------------- ---------- ----------- ----------- ----------- ----------- -------------

**Table 1** *Problems Solved*

![](media/image16.png)![](media/image17.png){width="3.1458333333333335in"
height="2.43125in"}![](media/image18.png){width="3.1458333333333335in"
height="2.43125in"}![](media/image19.png){width="3.1458333333333335in"
height="2.43125in"}

![](media/image20.png){width="3.1458333333333335in" height="2.43125in"}

**Figure 11** *Performance*

These empirical results imply that aggregate reasoning is effective in
synthetic and real domains, both in terms of number of constraint
violations repaired and in terms of overall time to reach a desired
solution quality. We have computed the statistical confidence that the
average final number of conflicts using the aggregate search method is
less than the final number of conflicts using the naïve method. For the
VTLI, EO1, DS4, and DCAPS domains, this confidence is greater than
99.9%. For the Rover domain, this confidence is greater than 98%.

**4. Discussion and Conclusions**

There are a number of related systems that perform both planning and
scheduling. IxTeT uses least-commitment approach to sharable resources
\[5\] that does not fix timepoints for its resource and state usages.
HSTS \[7\] enforces a total order on (state and resource) timelines but
the start and endpoints of tokens are only constrained temporally by an
interval. In both cases these are less committed representations than
our grounded time representation but this flexibility incurs a greater
computational expense to detect and/or resolve conflicts. O-PLAN \[1\]
also deals with state and resource constraints. O-PLAN's resource
reasoning \[10\] uses optimistic and pessimistic resource bounds to
efficiently guide its resource analysis when times are not yet grounded.
Like ASPEN, O-PLAN also allows multiple constraint managers which would
enable it to perform general reasoning when times are unconstrained and
more efficient reasoning in the case where all timepoints are grounded
(also enabling aggregate search as described in this paper). SIPE-2
\[11\] handles depletable/non-depletable resource and state constraints
as planning variables using constraint posting and reasons at the same
level of commitment as IxTeT. Cesta, Oddi and Smith \[2\] apply
constraint-posting techniques to satisfy multi-capacitated resource
problems at the same level of commitment. Depletable/non-depletable
resource constraints are easily transformed to multi-capacitated
resource constraints. None of these systems generally consider aggregate
operations in their search space.

This paper has described the use of aggregation techniques to improve
the efficiency of scheduling sets of interdependent activities. We
describe our algorithm for processing interacting state and resource
requirements of a cluster of interdependent activities into a set of
independent requirements and using these to search for placements for
the activity set. We show empirically that our aggregation search method
outperforms the alternative approach of searching for legal placements
on both synthetic problems and problems from planetary rover and
spacecraft operations domains.

###### References

1.  B. Drabble and A. Tate, "Use of Optimistic and Pessimistic Resource
    Profiles to Inform Search in an Activity Based Planner," Proc.
    AIPS94.

2.  Cesta, A. Oddi, S. Smith, "Profile-Based Algorithms to Solve
    Multiple Capacitated Metric Scheduling Problems." *Proceedings of
    the Fourth International Conference on Artificial Intelligence
    Planning Systems*, Pittsburgh, Pennsylvania, 1998, pp. 214-223.

3.  T. Estlin, S. Chien, and X. Wang, "An Argument for an Integrated
    Hierarchical Task Network and Operator-based Approach to Planning,"
    in *Recent Advances in AI Planning*, S. Steel and R. Alami (eds.),
    Lecture Notes in Artificial Intelligence, Springer---Verlag, 1997,
    pp. 182-194.

4.  Fukunaga, G. Rabideau, S. Chien, D. Yan, "Towards an Application
    Framework for Automated Planning and Scheduling," *Proceedings of
    the 1997 International Symposium on Artificial Intelligence,
    Robotics and Automation for Space*, Tokyo, Japan, July 1997.

5.  P. Laborie & M. Ghallab "Planning with Sharable Resource
    Constraints," Proc. IJCAI-95, 1643-1649

6.  S. Lin and B. Kernighan, "An Effective Heuristic for the Traveling
    Salesman Problem," *Operations Research* Vol. 21, 1973.

7.  N. Muscettola, "HSTS: Integrating Planning and Scheduling."
    *Intelligent Scheduling*. Morgan Kaufmann, March 1993.

8.  Rabideau, G., Chien, S., Backes, P., Chalfant, G., and Tso, K., "A
    Step Towards an Autonomous Planetary Rover," *Space Technology and
    Applications International Forum*, Albuquerque, NM, February 1999.

9.  R. Sherwood, A. Govindjee, D. Yan, G. Rabideau, S. Chien, A.
    Fukunaga, "Using ASPEN to Automate EO-1 Activity Planning,"
    Proceedings of the 1998 IEEE Aerospace Conference, Aspen, CO, March
    1998.

10. A. Tate, B. Drabble, and J. Dalton, "O-Plan: a Knowledge-based
    planner and its application to Logistics," *Advanced Planning
    Technology, Technological Achievements of the ARPA/RL Planning
    Initiative*, AAAI Press, 1996, pp. 259-266.

11. Wilkins, D. "Using the SIPE-2 Planning System: A Manual for Version
    4.22." SRI International Artificial Intelligence Center, Menlo Park,
    CA, November 1998.

12. M. Zweben, B. Daun, E. Davis, and M. Deale, "Scheduling and
    Rescheduling with Iterative Repair," in *Intelligent Scheduling*,
    Morgan Kaufman, San Francisco, 1994.

[^1]: Note that this technique will be useful for consideration of
    moving/placing any abstract organization of activities, e.g.
    hierarchies of tasks or decompositions, etc. There is significant
    evidence that these organizations of activities commonly occur in
    application domains \[3\].

[^2]: Note that this incorrectness applies also to computing the number
    of conflicts for moving a set of activities. In the same two cases
    listed the number of conflicts resulting from moving C would be
    either under or over-estimated.