On the application of least-commitment and heuristic search in temporal planning

1 Introduction

Many of the current challenges in AI planning focus on in­ creasing the functionalities of planners to deal with more real features, such as temporal capabilities, explicit management of resources, more expressive domain definition languages, heuristic techniques and optimisation criteria, etc. [Fox and Long, 2001; Gerevini and Serina, 2002; Smith and Weld, 1999]. This paper deals with three of the previous func­ tionalities: i) planning with temporal features (actions with duration), ii) more expressive domain definition languages (PDDL2.1 [Fox and Long, 2001 ]), and iii) plan optimisa­ tion (makespan). Traditional temporal planners have adopted a conservative model of actions, where two actions cannot overlap in any way if they have conflicting preconditions or effects. This model is adequate in some planning domains, but there exist others that require a richer model of actions. Level 3 of PDDL2.1 used in IPC-2002 provides a model of durative actions which allows a more accurate exploitation of action concurrency to obtain shorter makespan plans.

This paper describes our experiences with a Temporal Planning SYStem (from now on TPSYS), based on Graph­ plan [Blum and Furst, 1997] and TGP [Smith and Weld, 1999], to manage the model of durative actions proposed in level 3 of PDDL2.1. TPSYS performs a Graph plan back­ ward search, which guarantees the properties of completeness and optimality. However, backward search has some ineffi­ ciencies that impose important limitations in large temporal problems. In these problems, the search space is vastly in­ creased and the performance of the algorithm degrades. We suggest a new two-stage search process to overcome these inefficiencies. First, a backward search generates an initial relaxed plan. Next, this relaxed plan is used as an outline for generating a solution plan by means of a non-complete heuristic process, where actions are only definitively allo­ cated in the plan when they are applicable and no mutex (least-commitment). This allows to increase the scalability of search, producing non-optimal, but good quality, plans.

2 A Review of TPSYS

TPSYS is based on a three-stage process [Garrido et a!., 2002], which combines the ideas of Graphplan and TGP. This means that TPSYS incrementally extends a temporal planning graph, performs a backward search through that graph and extracts a plan.

Unlike conservative actions, durative actions present more conditions to be guaranteed for the success of the action. These conditions are SConda, EConda and Inva with the conditions of a to be guaranteed at the start, end and over all the execution of a, respectively. Durative actions have two types of effects: SEJ fa and EEf fa with the effects to be asserted at the start and end of a, respectively.

The first stage of TPSYS calculates the action-action and proposition-action static mutex relationships. These mutex relationships are static because they only depend on the def­ inition of the actions and they always hold. The second stage extends a temporal planning graph which alternates temporal levels of propositions (P[tJ) and actions (A[tJ) . Un­ like Graphplan, levels in TPSYS represent instants of time t E JR+ in which propositions are present and actions can start/end. Action-action, proposition-action and proposition­ proposition mutex relationships are calculated during the ex­ tension of the temporal planning graph. The third stage per­ forms the search in a Graphplan backward way, extracting an optimal plan through the planning graph. Since the third stage starts as soon as all the propositions in the final situa­ tion are present, non pairwise mutex, and the plan extraction is complete, TPSYS obtains the plan of optimal make span.

Backward search in TPSYS preserves the same proper­ ties of completeness and optimality of Graph plan, but it entails the mosttime consuming stage. Furthermore, this search presents some inefficiencies (inherited from Graphplan) which impose important limitations in temporal problems. Let us consider a simple problem from the ferry domain. The domain consists of transporting a number of cars from one location to another using a ferry which can carry only one car at a time. To keep the problem simple enough we assume three cars cl, c2 and c3 to be transported from location l1 to l2 by ferry f 1. The actions are board(? car, ?ferry,? local) , sail (?f erry, ?local 1, ? locat2) and debark(? car, ?ferry,? local) , with durations 1, 5 and 2, respectively. The optimal plan contains 11 actions (3xboard, 5xsail and 3xdebark) and the makespan is 34. The mutex relations are binary, so the sec­ ond stage ends at time 16 and the search starts from there (see Figure 1 ). Since every pair of actions is mutex, only one action is planned in each level. If we assume that applica­ ble actions are selected in each level from top to bottom in the planning graph of Figure 1, action A2 is firstly planned at time 14. Next, actions A 7 and Al are planned at times 9 and 8, and so on. Because no feasible plan is found, the search backs to time 14 where all permutations of actions A2, A4 , A6 are planned under the same schema with no success. This is the first indication of inefficiency: a lot of effort is wasted trying, unsuccessfully, to plan nearly identical actions in problems with symmetry. As no plan is found from time 16, the planning graph is extended to time 17 and the search is re-started from scratch. This entails the second indication of inefficiency: no actions planned in previous stages of search are reused as a part of the current plan, committing similar failures in the new one-deeper-/eve/ search space. Although memoization helps reduce the amount of failures committed during search, the way in which it prunes one branch of search does not allow to solve the real conflict until exhausting the whole level. This is the third indication of inefficiency: if one proposition becomes unsupported, no new actions supporting it are studied but that branch is discarded and the algorithm performs a backtracking stage.

These inefficiencies have a negative influence in Graph­ plan-based temporal approaches. While a classical Graph­ plan's planning graph for this problem has 11 levels, in tem­ poral planning no plan is found until level 34 is extended and explored. Particularly, in TPSYS the number oflevels gener­ ated depends on the dispersion of the durations of the actions.

The worst performance happens when the gcd of the dura­ tions is 1, forcing the algorithm to generate the maximum number oflevels. In consequence, the previous inefficiencies and wasted search are repeated more frequently.

3 Combining Least-Commitment and Heuristics to Improve the Search Process

In this section we substitute the backward search by a two­ stage search to avoid the previous inefficiencies in a temporal planning approach. First, a backward chaining stage gener­ ates an initial relaxed plan from the information of the tem­ poral planning graph. Second, a forward chaining stage allo­ cates the execution time of the actions in the relaxed plan.

3.1 Generation of an Initial Relaxed Plan

This stage generates an initial relaxed plan from the informa­ tion of the temporal planning graph (from now on TG) to be used as a skeleton of the final plan. We define a relaxed plan II as a partially ordered set of actions in which both the problem goals and action conditions hold. It is called relaxed because neither mutex relationships between actions nor commitment on their start time are considered.

A relaxed plan always contains two fictitious actions with no duration called IS and FS. IS achieves the propositions of the initial situation, whereas FS requires the problem goals. II is generated similarly to the relaxed solution plan in the FF planner [Hoffmann, 2000] with the exception that we handle durative actions (see Algorithm 1).

Step 6 studies the actions which support gi and selects the action which minimises the number of mutex in II. In prob­ lems with multiple resources, this selection tends to use as many resources as available. For instance, in a ferry prob­ lem with two or more ferries fl , /2, ... , step 6 distributes the use of the ferries in a homogeneous way. If action de­ bark(cl,fl,/2) is used for debarking the car cl, action de­ bark(c2,j2,12) is first selected when debarking the car c2 be­ cause debark(c2,fl,/2) is mutex with debark(cl,fl ,/2) and im­ poses more mutex in II. This selection provides the relaxed plan more information about the structure of the problem, thus increasing the quality (number of actions in parallel) of the final plan. Note that in step 6 we do not need to perform real search (or backtracking) because none of the mutexes are considered and, therefore, this strategy always leads to a so­ lution. Moreover, we introduce the term of obligatory action a as the only action which supports a goal which must hold in any plan for the problem. This is helpful because it means that a must be always present in II (steps 7-8). Obviously, both IS and FS are obligatory.

One important property of II is that if there is no mutex between overlapping actions, all actions in II form a feasible, optimal plan. The proof of this is straightforward and relies on the complete extension of the temporal graph. The level in which the temporal graph extension ends indicates the mini­ mal time in which the goals can be achieved by non-pairwise mutex actions. Thus, this level provides a minimal bound of the makespan for a feasible plan and, if no mutex between actions holds, the plan is not only feasible but also optimal. Unfortunately, this is not a very common situation and mutex relations break the plan relaxation. This entails to postpone the allocation of actions, and/or to plan new actions to solve the unsupported (sub )goals.

3.2 Planning and Allocating of Actions

This stage performs the allocation in time of actions in the re­ laxed plan. We use a structure called seLoLplans, with the search space formed by all the generated plans {IIi}. Ac­ tions in each IIi are divided into two disjunctive sets: Alloc; and Relax; . Alloc; contains the actions which have been al­ located in time and will never be removed from IIi. Relax; contains the actions which have not been allocated yet, and so they can be removed from IIi . Initially, Alloc; is empty and Relax; contains all the actions in IIi (the initial IIi is the relaxed plan computed in the previous section). This stage finishes once Relax; gets empty, obtaining in Alloc; the ac­ tions of the plan which support all the problem goals.

I: seLoLplans +- II, generated in Algorithm I 2: while seLoLplans # 0 do 3: extract the lowest cost IIi from seLoLplans 4: if AlloCi supports all the problem goals then 5: exit with success 6: else 7: a +- arg max( allocation priority) Vaj E Relaxi which can start at time.oLexe cutioni 8: if a is mutex in Alloc; (hen 9: if a is not obligatory then 10: remove a from Relax; II: else 12: postpone start time of a in Relax; 13: else 14: if a is applicable then 15: allocate a in Alloc; at tirne_oLexecution; 16: else 17: insert new plans into seLoLplans to make a ap­ plicable 18: update tirne_oLexecution;

The idea is to move forward in time, simulating the real ex­ ecution of IIi, progressively taking care of the actions which can start their execution (see Algorithm 2). The current time of execution in IIi, time_oLexecution;, is initialised to 0. The algorithm always selects the plan IIi of lowest cost from seLoLplans (step 3). If all the problem goals are supported the algorithm exits with success (step 5). Oth­ erwise, actions from Relax; which can start at the current time_oLexecutiolli are tried to be allocated (step 7). If one action a is mutex with actions in Alloc; and non­ obligatory, a is removed from IIi (step 10), delaying the ful­ fillment of its goals to a future time of execution. The reason to remove a non-obligatory action is that it could be a bad choice for the plan. If a is obligatory it is not removed but its start time is postponed (step 12). If a is not mutex and ap­ plicable, a is allocated in time (step 15). This step entails the first indication of loss of completeness. Although there exist alternative actions to a, if a can be allocated those actions are not considered in IIi. Step 17 is a branching point in which new actions are inserted (generating new plans) to achieve unsupported conditions of a. For each action ai supporting each condition a new plan IIj is generated and inserted into seLoLplans with ai marked as obligatory in IIj. It is im­ portant to note that ai is not allocated in time, but it is inserted with its earliest start time of execution extracted from the TG. This is part of the least-commitment technique performed in the allocation of actions when they are inserted into plans. Step 18 moves to the next relevant time_oLexecution; in which actions can start, extending the TG if necessary.

The algorithm has two important points of selection: steps 3 and 7. Step 3 selects the plan IIi with the lowest cost from seLoLplans, where the cost is estimated as follows :

The cost of a plan IIi consists of the sum of the cost due to Alloc; and Relax; . unsup(a, Alloci) is an estimation of the number of actions necessary to solve the unsupported conditions of a from the current time_oLexecution;. It is estimated through the TG, ignoring the delete effects of actions (as in the heuristic used in FF). add( a, FS) is the number of conditions of FS which a supports, whereas del(a, FS) is the number of conditions ofFS which a deletes. PA_mutex(a, FS) is the number of mutex between condi­ tions of FS and action a. This mutex information is extracted from the TG and indicates the impossibility to have simulta­ neously the conditions of FS and a. duration represents the duration of the plan/action to take into accountthe makespan of IIi. Note that a, /3, 'Y, B, >., f..L ;::=: 0 because they have a pos­ itive impact in the cost of the plan. In opposition, 8 S 0 because it has a negative impact in the cost.

In step 7, the action a with the maximal allocation priority is selected to be studied at time_oLexecution;. This priority is estimated as follows:

The allocation priority of action a depends on several local factors. succ(a, Relax;) is the number of direct successor

(dependent) actions of a in Relaxi. meetsucc(a, Relaxi) is the number of direct successor actions of a which can start as soon as a ends, i.e. which meet a. These two values in­ dicate the importance of an action for the successor actions in Relaxi . Intuitively, the more successor actions are directly supported by a, the more important a is in the plan. Similarly, the meeting successor actions indicate the number of succes­ sor actions which can be immediately executed without mu­ tex. unsup and duration are defined as above. Coefficients cr, T ~ 0 because they imply to select an appropriate action to be allocated. However, p, 'ljJ ~ 0 because they indicate that action a is not promising enough to be allocated yet.

The previous evaluation functions can have many more heuristic factors, but according to our experimental analysis they are general enough for most temporal planning prob­ lems. We can also implement different heuristic methods by setting the values of the coefficients, which in our case are the same for all the domains. Although the values of the co­ efficients can influence the search, their precise value is not as relevant as in other heuristic approaches based on local search as LPG [Gerevini and Serina, 2002]. For instance, the static cost of inserting an action in LPG is based on the number of unsupported conditions, what cannot represent the real complexity of solving each condition. On the contrary, the coefficient unsup deals with that complexity because it estimates the real cost to support it in the TG.

It is important to note that plans are incrementally gener­ ated without discarding allocated actions and with no redun­ dancy due to symmetry. Although Algorithm 2 explores the complete space of actions to make actions applicable, the al­ location priority imposes an order of execution and discards the rest of feasible orderings (second indication of loss of completeness) . For instance, in the ferry problem of sec­ tion 2, when studying the actions to debark { A2 1 A4 1 A6} the algorithm allocates one action and postpones the others. This avoids the complete exploration of all the permutations of A2, A4 and A6, preventing the planner from the generation of symmetric plans.

4 Experimental Results

We have implemented the previous search on top ofTPSYS, conducting several experiments 1 . The two first experiments compare the new search vs. the Graphplan backward search. In the first experiment, we studied the impact of the new search in problems with a high degree of symmetry, such as the ferry and gripper, focussing on the planner scala­ bility. Figures 2-a,b show the results for some problems of these domains. Although it is not surprising that the least­ commitment search (tpsys-LC) is faster than Graph plan backward search (tpsys-GP), it is worthy to mention that tpsys-LC scales up much better than tpsys-GP, espe­ cially in the gripper domain. Moreover, tpsys- LC found optimal plans without backtracking for all the problems.

The second experiment deals with some problems of the simple-time track of the last IPC-2002 2 . Although both approaches have difficulties to solve all the problems (see Fig­ ures 2-c,d,e,f) , the least-commitment search can solve more problems. On one hand, backward search difficulties rise as a result of the redundancy in the complete, blind search pro­ cess. On the other hand, least-commitment search difficulties rise as a result of: i) the heuristic, greedy approach, which can lead to the wrong path in the search, and ii) the non-complete preserving search. The zenotravel and satellite do­ mains show the highest speedups. It is important to note that the best improvement is produced in the satellite do­ main, which is the only domain in the competition that ex­ ploits the end conditions of durative actions.

1 The experiments were run on a Pentium IV 2 GHz with 512 Mb.

2 More information on the domains, problems and re­ sults of the international planning competition (IPC-2002) in:

The third and fourth experiments are aimed at evaluating the quality of the plans generated by the new approach. We are mainly interested in the makespan of the plans, but we also consider the number of actions as an additional indica­ tion of the plan quality. The third experiment uses the plans generated in the experiment 1 (Figures 2-a,b) and compares them with the plans generated by LPG 3 [Gerevini and Serina, 2002] and Mips 4 [Edelkamp, 2002]. We have chosen these two planners as they handle temporal features and showed distinguished performance in the last IPC. To date our inter­ est has not focussed on code optimisation, so in this experi­ ment we will not compare the execution time of the planners 5 but only their plan quality. Table 1 shows the comparison be­ tween the three planners taking into account the makespan and the number of actions of each plan. We have not in­ cluded the results for the ferry domain because the three planners generate the same fully sequential plans. However, plans for the gripper domain can have actions in paral­ lel (the gripper is a resource with capacity for two balls) so that the planner can exploit a better concurrency. In order to simplify the resulting plans the actions have been assigned duration 1. Hence, the optimal makespan is 2n - 1 and the number of actions in an optimal plan is 3n- 1, where n is the number of balls in the problem. Surprisingly, both LPG or Mips generate sequential plans as can be easily noticed from the fact that the makespan comes directly from the number of actions in the plan. tpsys-LC is the only of the three planners which generates optimal plans for all the problems, highly exploiting the action parallelism.

In the fourth experiment, we have used the plans gen­ erated in the last IPC to perform a comparison between tpsys-LC and some of the state-of-the-art planners which participated in the simple-time track. We have analysed the plans generated by the domain-independent (di) planners LPG, Mips and VHPOP, and the domain-dependent (dd) planners SHOP2, TALPianner and TLPian. For LPG and Mips we have run the problems again and for the rest of the planners we have used the results of the competition. Al­ though Sapa, TP4 and lxTeT also participated in the com­ petition we have not found enough results for the simple-time track to be considered in our comparison. Figure 3 shows the results of this comparison (for lack of space we only include the domains with more problems solved). In the driver­ log domain, the plans of tpsys- LC are generally longer than the rest of planners with the exception of LPG and SHOP2. In the satellite domain, tpsys-LC behaves in average better than the rest of the planners, with the only exception of TLPian. In the rovers domain, tpsys-LC generates again plans of very good quality, which are only improved by SHOP2 and TLPian. Further, we have no­ ticed that tpsys- LC generates plans with nearly the same (or even fewer) actions than the rest of the planners. These experimental results show that the new approach significantly improves the scalability of the Graphplan backward search.

http://www.dur.ac . uk/d.p . long/IPC

3 LPG is based on a non-deterministic local search and, con­ sequently, it would not be fair to work with the plan from only one execution. In our experiments with LPG, we have run each problem ten times and extracted the average val­ ues. We have used the LPG1 .0 version as provided in: http ://prometeo.ing.unibs . it/lpg

4 We have used the Mips version as provided in: http ://www.informatik.uni-freiburg.de/-mmips

5 LPG and Mips are clearly faster than tpsys- LC. For instance, they get to solve some simple problems before tpsys- LC finishes its I st and 2nd stages. Currently, these stages represent an impor­ tant bottleneck in our implementation and we think they could be drastically reduced.

5 Conclusions through Related Work

Least-commitment techniques have been widely used in plan­ ning, relying on the consistency of temporal constraints (lxTeT and HSTS), postponing the assignment of values to variables or the order of execution of actions, etc. [Weld, 1994]. We use a least-commitment approach to overcome the limitations of the Graphplan backward search detected in previous works [Fox and Long, 1999; Zimmerman and Kambhampati, 1999]. Our approach basically postpones the allocation in time of actions until they become not mutex and applicable. Thus, the algorithm generates a relaxed plan sim­ ilarly to FF, to be used as a skeleton of the plan. Next, it allocates actions in time according to their mutex relations and to several local heuristic criteria in the line of LPG. Our critical difference with LPG relies on several points. First, the planning graph is temporal and moves chronologically in time instead of planning steps. Second, the TG is not only used to extract heuristic information but also to generate a relaxed plan. Third, this plan is repaired in a forward chain­ ing direction, and unlike LPG the allocated actions are never removed. Fourth, the heuristics exploit better the structure of the plan and the real importance of each action in the plan. Fi­ nally, tpsys-LC uses a more precise model of action mutex which implies fewer constraints on the execution of actions and a larger search space.

This paper contributes in the way in which leastcommitment can be applied in a Graphplan-based temporal (or classical) approach, substituting the backward search by the new two-stage search. The new search combines the in­ formation calculated in the planning graph with a heuristic, greedy search process, and increases the planner scalability. The advantage is that the planner can exploit a high level of action concurrency, what leads to plans highly competitive with other state-of-the-art planners under a deterministic ap­ proach. Although in temporal planning the most important criterion of quality is the makespan, the experimental results show that the new search generates plans in which the number of actions is quite good (even in problems of IPC-1998 and IPC-2000). The main disadvantage of this approach is that it is not complete preserving. However, although completeness and optimality are desired properties, guaranteeing them en­ tails a huge complexity, preventing planners from producing plans with more than a few actions. The algorithm has still some limitations and our future work is to refine the heuristic functions to improve the quality of the plans, the performance and to avoid some of the inconveniences of the greedy search.

Acknowledgments

This work has been partially supported by the Spanish MCyT under projects DPI2001-2094-C03-03 and TIC2001-4936-E, and by the Universidad Politecnica de Valencia under projects 20010017 and 20010980.