Planning with Sharable Resource Constraints

1 Introduction

Classical approaches decompose plan generation and re­ source management into two different steps for solving a given planning problem. Plan generation consists in se­ lecting and organising a set of operators that will achieve the problem goals; its result is a plan, that is a partially ordered set of operators. Resource management is then performed on this plan to ensure its correctness with re­ spect to temporal and resource constraints. The result, then, is a schedule that, if executed, will ensure the goal resolution while satisfying the physical constraints of the environment.

The strict separation between plan generation and re­ source management raises difficulties such as how to backtrack to the plan generation process, when neces­ sary, or how to generate the plan in an opportunistic way according to resource constraints.

This paper develops a representation and an algorith­ mic approach integrated into a system called IxTeT, for handling abreast and in an opportunistic way plan gen­ eration and time/resource management .

The following section is a short digest of scheduling and planning literature that influenced our work. Sec­ tion 3 describes a temporal representation of operators and problems. The general control of the planner is dis­ cussed in section 4 whereas section 5 focuses on the re­ source analysis module. We finally presents some experi­ mental results and applicability domains for our system.

2 Related Work

2.1 Scheduling

Scheduling systems are essentiallr concerned with time and resource management. ISIS lFox and Smith, 1984) was one of the first attempt to deal with a large vari­ ety of realistic constraints for job-shop scheduling. Some operator pre-conditions were handled to detect inconsis­ tency but nothing was done to enforce their satisfac­ tion. Other systems .like OPIS [Smith et al., 1986) or MICRO-BOSS [Sadeh, 1991) introduced the notion of opportunistic search that is the ability to dynamically revise the search procedure. In their approach, this con­ sists in choosing first to schedule the most constrained operations i.e. those with the highest contribution to resource bottlenecks. Systems like OPAL [Bensana et al., 1988) or MASCOT [Erschler et al., 1990) work out a constraint based analysis to detect some necessary fea­ tures of the solutions represented by the current partial schedule. In these approaches, opportunity of a conflict resolution depends on the number and characteristics of the different ways to solve it . The resource manager of IxTeT has been highly influenced by the latter ap­ proaches as an opportunistic search is made necessary by the plan generation aspects the system deals with.

2.2 Planning

The algorithmic basis of classical planning have been well clarified, e.g. in [Chapman, 1987) and [McAllester and Rosenblitt, 1991).

Extending the classical representation to handle tem­ poral constraints like operator durations or earliest, lat­ est time, has been an important preoccupation in plan­ ning. Like FORBIN [Dean et al., 1988) or 0-PLAN [Currie and Tate, 1991], IxTeT uses time-points as primitives and propagates metric constraints between time-points. This has been shown to be less complex [Vilain and Kautz, 1986] than interval based approaches [Allen et a/., 1991].

Concerning resource management, SIPE was the first planner to handle consumable and producible resources [Wilkins, 1988]. Although no constraint was added to the plan to prevent potential resource conflicts, the search space was pruned to avoid some unuseful explo­ ration of over-consumer plans. SIPE also implemented the notion of unsharable re-usable resources.

Because their management is inherently untractable, sharable resources has rarely been inte~rated into a plan­ ning system. The HSTS framework [Muscetolla, 1993] addresses this problem however, it over-constrains the current partial plan as sharable resources are handled through a total-ordered time-line. 0-PLAN handles sharable resources by using a criterion based on op­ timistic and pessimistic resource profiles [Drabble and Tate, 1994] to prune the search space but these profiles seem not to be sufficient to ensure the soundness of the search with respect to resource conflicts.

This paper presents a sound, complete and efficient /east-commitment based approach to manage sharable resources during the planning process. The approach re­ lies on various techniques and ideas from classical plan­ ning, scheduling, constraint satisfaction problems and graph theory. It develops an original procedure for man­ aging efficiently and jointly temporal and resource con­ straints. It has been integrated with a sophisticated con­ trol into the IxTeT temporal planner.

3 Representation

3.1 Time and Variables

For algorithmic complexity reasons, the IxTeT time-map manager [Ghallab and Alaoui, 1989; Ghallab and Vidal, 1995] relies on time-points as the elementary primitives. Time-points are seen as symbolic variables on which tem­ poral constraints can be posted. We handle both sym­ bolic constraints (precedence, simultaneity) and numeric constraints expressed as bounded intervals [I-, J+] on the temporal distance between time-points. Disjunc­ tions of these constraints are not directly handled by the time-map manager but through the control module.The time-map manager propagates constraints to ensure the global consistency of the network and answers queries about the relative position of time-points.

A variable constraint manager handles atemporal vari­ ables ranging over finite sets and propagates domain re­ striction, equality, and unequality constraints 1 .

3.2 Description of World and Change

The world state is described through a set of multi-valued state attributes. A state attribute is a k-ary state variable which can take only one value at a time.

1 Actually, as propagating variable unequalities is an un­ tractable problem in itself, we just work out a local consis­ tency for this type of constraints.

IxTeT is based on a reified logic formalism where state attributes are temporally qualified by the predicates hold and event:

• an assertion hold(att(x1, ... ): v,(t1,t2)) asserts the persistence of the value of attribute att( x 1 , .. . ) to v for each t: t1 < t < t2. Assertions allow the expression of operator conditions as well as of causal links.
• event(att(x1, ... ): (v1,v2),t) states that an instan­ taneous change of value of att(x1, ... ) from v1 to v2 occured at time t. Events allow the description of state change in operators as well as of expected changes of the world in the initial problem descrip­ tion.

3.3 Description of Resource Uses

We define a resource as any substance or set of objects whose cost or availability induces constraints on the ac­ tions that use them.

A resource can be a single item with a unit capacity (an unsharable resource), or an aggregate resource that can be shared simultaneously between different actions seeing that its maximal capacity is not exceeded. Re­ sources are gathered together into resource types: two resources belong to the same type if they can be indif­ ferently used.

The resource availability profiles and their uses by dif­ ferent operators are described by means of three predi­ cates:

• use(typ(r) : q, (t1 , t2)) means that an integer quan­ tity q of resource r of type typ will be used between time-points t1 and t2. Notice it is just a borrowing of a part of the resource;
• consume(typ(r) : q, t) states that a quantity q of resource r will be consumed at time t, i.e. that the availability of r will decrease at t.
• produce(typ(r) : q, t) represents a production of re­ source at time t.

This paper focuses on the management of sharable re­ sources (i.e. whose capacity exceed 1). As these re­ sources are often equivalent resources for which we don't need to explicitly manage a final allocation, we first make the hypothesis that all the resources of a given type are completely aggregated so that the only informa­ tion binded to a resource type is its maximal capacity. Furthermore, we will only consider the borrowing of re­ sources (predicate use). We will extend these hypotheses at the end of the paper.

3.4 Planning Operators

Planning operators are described through a hierarchy of tasks. A task is a temporal structure composed of:

• a set of sub-tasks;
• a set of events describing the changes of the world induced by the task;
• a set of assertions on state attributes to express the required conditions or some causal links between task events;
• a set of resource uses; and

• a set of temporal and instantiation constraints bind­ ing the different time-points and variables of the task.

Tasks are deterministic operators without ramification effects. We assume that all conditions and changes linked to the task are explicitly defined into its hierarchic de­ composition. Notice that this hierarchy is but a user programming facility to build complex tasks on the ba­ sis of simpler ones; a compilation procedure is worked out before planning to translate tasks into IxTeT struc­ tures by expanding the events, assertions, resource uses and constraints of sub-tasks up to the top level task. Ix­ TeT also uses a control hierarchy but it is not directly linked to this representation hierarchy [Garcia and La­ borie, 1994].

Below is described the task "INCUBATE" for plan­ ning in the context of a spatial station where biological experiments are carried out 2 .

resource POWER() { capacity= 100; } attribute POSITION(?Elt) { ?Elt in {Culture!, Culture2, Tubel, ... }; ?value in {Stock, Wb, Incub ... }; } task INCUBATE(?Elt, ?T)(start,end) { hold(TEMPERATURE():?T, (start,end)); hold(POSITION(?Elt):Incub, (start,end)); event(INCUBATED(?Elt,?T):(no,yes), end); use(INCUBATOR():l, (start,end)); use(POWER():8, (start,end)); (end- start) in [00:09:00,00:10:00];}

3.5 Initial Plan

The initial plan 'Pinit is a special task that describes the problem scenario, that is:

• the initial values for the set of instantiated at­ tributes;
• the expected changes on some state attributes that will not be controlled by the plan·ner;
• the expected availability profile of resources; and
• the goals that must be achieved.

The first two points are represented thanks to a set of explained events, the availability profiles with a set of uses and the goals as a set of assertions to explain. IxTeT allows a total flexibility on the expression of temporal constraints between these elements.

As many classical planners, IxTeT explores a search tree of partial plans whose root is the initial problem and branches are operators or constraints inserted on the current partial plan.

4 Control

4.1 Flaws and Resolvers

Our planner relies on the use of causal links. In the fol­ lowing, we extend the vocabulary defined in [McAllester and Rosenblitt, 1991] to the IxTeT temporal formalism.

2 A complete modeling for this domain has been defined within the framework of the PADRE project for the COLUM­ BUS European Space Lab, financed by the French Minister for Education and Scientific Research, in collaboration with the companies lXI and Matra Marconi Space France.

Unexplained propositions: a temporal proposition hold(att(x1, ... ,xn) : v , (t , t·)) or event(att(x1, ... ,xn) (v,v·),t) will be said explained iff:

1. there is an establisher event( att( x~ , ... , x~) (v., v'), t') such that necessarily (t' ~ t), (v' = v), (x~ = xl), ... and (x~ = Xn)i and
2. if (t' < t), there is a causal-link between the es­ tablisher and the proposition hold(att(x1 , ... , xn) : v,(t',t))

In IxTeT, establishers are naturally represented by events and causal links by assertions. The sub-goal anal­ ysis module analyses the unexplained propositions and create two kind of resolvers: causal links (establishment by an event already in P) and tasks insertion .

Threats are possibly conflicting propositions, ie either:

1. a pair < e, cl > where e = ev~nt(att(x~, ... , x~) : (v., v·), t') and cl = hold(att(x1, ... , Xn): v, (t1 , t2)) such that the current plan P does not contain one of the constraints {(t' < t1); (t' = t 1 and v = v·); (t2 < t'); (t' = t2 and v = v.); (x1 f. xl.) ; ... ; (xn f. x~)} or
2. a pair < h, cl > where h = hold(att(x~ , ... , x~) : v',(t.,t·)) and cl = hold(att(x1 , ... ,xn) : v,(t1,t2)) such that P does not contain one of the constraints {(t· < tl); (t2 < t.); (x1 f. xl); ... ; (xn f. x~); (x1 = x~ and ... and Xn = x~ and v = v')}

For each possible threat, the threat analysis module computes a disjunction of resolvers composed of the above temporal or variable constraints.

Resource conflicts for a type typ of resource with max­ imal capacity Q(typ) are sets < u1 , ... , Uk >such that , if u; = use(typ() : q;, (ti, tt)) :

1. P does not contain one of the constraints {(tt < tj)(i;CJ)} i and 2. L:7=1 q; > Q(typ)

Resolvers of a resource conflict consist in a disjunction of temporal constraints and eventually, variable unequal­ ities if different resources of the same type are allowed . This is discussed in section 5.

Solution plan criterion

We define a flaw as being either an unexplained propo­ sition, a threat or a resource conflict .

A partial plan P will be a solution plan iff it verifies the following conditions:

1. there is no flaw;
2. the temporal constraint network is consistent; and
3. the variable binding network is consistent .

An essential condition for a real integration of resource management and plan generation is the existence of a ho­ mogeneous representation on which the system can rely to continually justify the choices it has to make between these two activities. The later paragraph points out that , although their origin differ, resource conflicts resolvers are of the same nature as plan generation ones (pend­ ing subgoals and threats) : either temporal constraints , variable constraints or task insertion. It is finally the representation of the current plan as a set of flaws and resolvers that will constitute a homogeneous represen­ tation where the control module chooses a flaw inde­ pendently of its being a resource conflict, a threat or a pending subgoal. This idea meets the one developed in WATPLAN [Yang, 1992] where the flaw /resolver rep­ resentation is seen as a constraint satisfaction problem (CSP) [Tsang, 1993] whose variables are represented by flaws , and their possible values by resolvers.

4.2 Choosing a Resolver to Solve a Flaw

In IxTeT, the explicit representation of temporal met­ ric constraints and finite domain variables permits an estimation of the commitment induced by a constraint posting.

Indeed, as a partial plan P represents a set of possible instantiations INST(P), we estimate the commitment of posting a constraint p on P as:

that is the ratio of instantiations eliminated by the post­ ing of p.

commit(P, p) = 0 iff p is redundant with constraints already posted in P; commit(P, p) = 1 iff pis inconsis­ tent with P.

Thus, if t and t' are two time points such that numeric constraints propagation on the temporal network of P states that (t'- t) E [dmin , dmaxl. we will estimate the commitment of posting (t' < t) on P by supposing, in IN ST(P) , a uniform repartition of the value of variable (t'- t) into [dmin, dmax]; so that

Variable constraint as well as causal link commitment are estimated through functions of the same kind.

Determining which task is the most relevant for a pending goal and how a task insertion will further con­ strain the partial plan is a complex problem. Such a procedure called feasibility is described in [Ghallab and Laruelle, 1994] and corresponds to a look-ahead that ig­ nores threats and resource conflicts. Its result is a com­ mitment value attached to a given task insertion.

Given a flaw and according to these definitions of com­ mitment, IxTeT always chooses to first insert the least­ commitment resolvers.

4.3 Choosing next Flaw to Solve

Flaws are chosen in an opportunistic way to reduce the chances of backtracking. A function I< ( <P) measures the easiness to make a choice between the different resolvers of flaw¢ : {p1 , . .. , pk} according to our least-commitment st rategy. It estimates how far the best resolver Pmin is "ahead" of the other resolvers:

The control module always choose to solve first the flaw <P that maximises I< ( ¢). Notice that 0 < J{ ( ¢) ~ 1. I<(¢)= 1 iff¢ has a unique resolver, we say in this case that ¢ is a deterministic flaw as it does not complicate the search tree. Function K permits to solve in priority those flaws with the smallest number of resolvers, this being modulated by the value of resolvers commitment.

4.4 Search Tree Exploration

The search is controlled by a near-admissible Af algo­ rithm [Ghallab and Allard, 1983] which provides a trade­ off between the efficiency of the search and the quality of the solution in terms of flexibility. The estimate f of a partial plan P at a given node is a combination of g, the commitment along the path leading from Pinit to P, and h, a combination of the minimal commitment for each remaining flaw ¢ in P. Assuming that each remaining flaw in P can be independently solved by its least-commitment resolver, f is inversely proportional to the maximal flexibility 3 of solution plans contained in P.

5 Resource Management

Resource conflicts are detected and solved through min­ imal critical sets [Erschler et a/. , 1990]. Minimal criti­ cal sets (MCS) are detected as particular cliques on a specific representation of the temporal constraints: the possible intersection graph (PIG) .

5.1 Possible Intersection Graphs

The possible intersection graph (PIG) associated to a resource type typ on a partial plan P is a non-oriented graph 9typ(U, E) whose vertices U are the resource propositions { u1 , .. . , un} for resource typ and edges E the pairs { u; , Uj} such that u; and Uj may possibly intersect in some temporal instantiation of P (i.e. P does not contain one of the constraint { (tt < tj), (tj < t;)} ).

PIGs, being the complementary of comparability graphs, are a special kind of weakly triangulated graphs which are themselves a sub-class of perfect graphs. More­ over, when all the time-points are instantiated, the PIG becomes a triangulated graph 4 .

5.2 Minimal Critical Sets

A set¢=< u1, ... , Uk >is a MCS of partial plan P iff:

1. ¢ is a resource conflict ; and

2. V¢' C ¢, ¢' is not a resource conflict.

According to these definitions, MCS are exactly the minimal over-consumer cliques of 9typ· e.g. on fig­ ure 1, < u3, u4, U7 > is a MCS. Because of the least­ commitment strategy, the smallest MCSs are the most interesting ones.

Our MCS detection algorithm consists in finding some maximal cliques of 9typ and splitting them into MCS.

Although the maximum clique problem for weakly tri­ angulated graphs can be solved in polynomial time [Hay­ ward et a/., 1989], these algorithms are very inefficient in average and furthermore, they would only give some MCS and not necessarily the most interesting ones.

3 Flexibility of a solution plan P, being defined as a mea­ sure proportional to card (IN ST(P, )).

4 A triangulated or chordal graph is a graph which does not have chordless cycle with length more than 4. A weakly triangulated graph is a graph which does not have chordless cycle with length more than 5 or its complement . A chord is an edge joining to non-consecutive vertices in a cycle.

On the other hand, it can be shown that if n is the size of9typ, the maximal number of MCS may reach n 1 1 2 .2n making a complete search untractable.

Our approach makes a compromise between the qual­ ity of the found MCS and the complexity of such a search.

We develop a search tree whose nodes N are a triplet < !:i(N), P(N), ~(N) >. Node N represents a current clique

that we try to enlarge in the following nodes. More pre­ cisely,

• !:i(N) C U is the contribution of node N to the enlargement of the current clique;
• P( N) C U is the pool of candidate propositions to enlarge the current clique in the following nodes; and
• ~(N) C 2P(N) is exactly those MCS which have at least one proposition in each !:i(M) for M E fathers(N) UN.

Developping node N consists in:

1. partitioning P(N) into sets !:i(N;) where N; are node N's sons;
2. computing nodes N;'s pools P(N;) ; and
3. computing ~(N;), the MCSs attached to nodes N;.

Points 1 and 2 are processed simultaneously through a vertex ordering of P(N) similar to the one defined in [Gavril, 1972] for triangulated graphs. A son N; can be processed in less than l!:i(N;)I.IP(N)I steps. Point 3 is achieved through an enumeration method in 0(2k) where k is bounQ.ed by the size of 9typ maximum clique.

See fig. 1 for an example of MCS search tree. The search tree is explored by a breadth first search that al­ lows to detect first the smallest MCSs that are the most interesting ones according to a least-commitment strat­ egy. For each node of the global search tree, we can select all or a given subset of the smallest MCS of the current partial plan. The algorithm is further detailed in [La­ borie, 1994] where we show this MCS's search procedure to be sound, complete and systematic.

5.3 Minimising MCS's resolvers

To solve a MCS ¢> =< u1, ... , Un >, it is sufficient to post one of the constraints { (tt < tj )(i,j)E[l,n]x[l,n],i;tj} . Thus a MCS of size n has at most n .( n - 1) resolvers.

To find the smallest disjunction of resolvers that would be necessary and sufficient to solve ¢>, we introduce the notion of equivalence between two disjunctions of prece­ dence constraints on a partial plan P : 8 = {p1 , ... ,pn} and 8' = {p~, ... , p~,} will be said equivalent on P iff each precedence constraint p; of 8 implies one of the prece­ dence constraint pj of 8 1 on P and vice versa. It can be shown that, given a disjunction 8 and a partial plan P, there exists a unique disjunction 8min such that 8 and 8min are equivalent on P and card(8min) is minimal.

Applying this result to the disjunction of resolvers of a MCS ¢> leads to a minimisation procedure that runs in O(n 3 ) (if n is the size of the disjunction) and that consists in removing those resolvers p that would imply another resolver p' of ¢> . The obvious interest of this minimisation is to prune the global search tree of some over-constraining branches.

e.g., for the MCS ¢> =< ua , u4, u7 > in figure 1, we have the following disjunction of resolvers: 8 = {(t 11 < is), (tg < t10), (t11 < t2), (ta < t10), (ta < ts)}, but, as (tg < t10) implies (ta < ho) on P, resolver (tg < t1o) will not be considered.

5.4 Integration Planning/Scheduling

Figure 2 shows how the resource analysis module is in­ tegrated into the planning system. At each node of the global search tree, the resource analysis module se­ lects a certain number of smallest MCSs (§5.2) and com­ putes their minimal resolvers (§5 .3) , whereas the other analysis modules focus on threats and pending subgoals (§4.1) . The control module, then, can choose a flaw (§4.3) and one of its resolver (§4.2) according to the least­ commitment strategy.

6 Experimental Results

6.1 MCS Search Procedure

Curves in figure 3 show the performances in the worst case of the MCS search procedure described in §5.2. Times along the Y-axis are given in ms on a Sun Spare station 10. Along the X-axis is the number of resource proposition for a given type of resource. Parameter size is the size of the smallest MCS of the analysed partial plan, nb is the number of smallest M CS we look for. Each point is an average over 50 of the more unfavourable randomly generated problems in terms of temporal con­ straint density.

We can notice the quasi-linear behaviour in average. The running time is not fundamentally increased when we look for more than one smallest MCS. In practice

··

··

··

Figure 3: MCS search procedure performances

we have about 20 to 50 resource propositions of a given type, size is in the order of 3.

6.2 Scheduling problems

To compare it to other schedulers, our approach has been tested on some pure scheduling problems, such as the scheduling of equipment compartments integration for the Ariane 4 rocket launcher. This problem uses 6 sharable resource types (mainly, skilled manpower and test systems) for a total of about 150 resource propo­ sitions. Because of operations earliest start times and latest completion time, the problem is globally very con­ strained. IxTeT finds a solution in about 5s without backtracking; this time should, for example, be com­ pared to the 1 or 2 mn required by MICRO-BOSS lSadeh, 1991] to solve problems of the same size.

6.3 Integrating Planning and Scheduling

Figure 4 gives a part of the solution plan for planning biological experiments in the COLUMBUS space lab do­ main which is described by means of 9 state attributes, 11 type of resources and 11 task operators.

The upper part of the IxTeT plan table shows the selected tasks ; the lower part , the cumulative use of resources. The horizontal axis refers to the time points in the plan, linearised only for the purpose of an easy dis­ play of barcharts. The actual precedence constraints of the solution plan are given in the IxTeT plan lattice. It should be noticed how our least-commitment approach leads to a highly parallel and flexible solution plan as we try to never over-constrain it.

The IxTeT Planner has been tested on many plan­ ning problems involving resources (house building, room finishing problem, task-level control for a team of 3 mo­ bile robots, etc .. . ) whose generated solution plan con­ tains between 20 to 30 tasks and requires less than 1mn of running time. For example, planning for a plane­ tary exploration of Mars with 2 rovers requires about 1mn of running time for a three day long plan involving more than 20 tasks, 200 temporal propositions and 100 time-points. The plan was generated while taking into account visibility windows between the rovers and an orbiter, sun-light , communication channels and energy constraints. The problem was initially stated as a set of data concerning the planet that were to be received by the orbiter within 3 days.

6.4 Applicability Domains

Many fields may be interested in such an integrated ap­ proach of plan generation and resource management. They can be classified according to their needs in terms of plan generation. Our approach allows for a great flex­ ibility to express implicit conditions and effects of op­ erations instead of explicit and hard-coded precedence constraints between them as it is traditionally done to describe problems in factory production or project man­ agement. Furthermore, domains as spatial station oper­ ations planning or management of test systems need, in addition of resource management , facilities to generate reconfiguration operations of some sub-systems that de­ pend on their last state. These operations, because of their duration or because of their use of resources for themselves, may affect the resource management pro­ cess. Finally, activities like autonomous robots planning, where plan generation play a major part must take re­ sources into account to produce robust plans.

Our approach has been highly motivated by a pre­ analysis of these various domains.

7 Conclusion and Future Work

IxTeT, is a temporal planner that integrates sharable resource management into the plan generation pro­ cess. This paper shows how this integration is achieved through the crossing of various techniques and ideas from classical planning, scheduling, graph theory and constraint satisfaction problems.

The performances of the resource analysis module allows IxTeT to tackle realistic problems involving sharable resources while the underlying algorithmic en­ sures the completeness of the search.

Future work will mainly consist in improving the ex­ pressiveness of the planner. We have already integrated producible and consumable resources. In the same way that consumption of resources can easily be seen as a borrowing over a temporal half-line [t, +oo[, we consider the production of resource as an atemporal increase of the resource capacity combined with a borrowing of the resource over]- oo, t]. This allows to manage producible resources with the possibility of automatically inserting resource production tasks without modifying our MCS detection procedure.