A Parametric Hierarchical Planner for Experimenting Abstraction Techniques

1 Introduction

There is experimental evidence that humans repeatedly use abstractions while solving different kinds of prob­ lems [Stillings et a/., 1987], thus justifying the research in the field of automated hierarchical planning.

It is apparent that abstraction is usually not effective on simple problems, due to the overhead introduced by the need of going back and forth across abstract spa~es while performing the search. In other words, enforc~ng abstraction on simple problems may end up by wastmg computational resources. Yet, under certain as~umptions abstraction can significantly reduce the search time when applied to complex problems [Knoblock, 1991]. .

In order to investigate the impact of abstraction mechanisms on the search complexity, we devised and implemented a hierarchical wrapp.er able to embod~ any domain-independent planner provided that a compliance with the STRIPS subset of PDDL 1.2 standard [McDer­ mott et a/., 1998] is ensured. The embodied planner is exploited at any level of the hierarchy, each level being characterized by its own definitions. A suitable decoup­ ling between levels is guaranteed by using domain­ specific rules that establish the correspondence between entities belonging to a level and its superior. Translation rules are given in a PDDL-like format, explicitly defined to support abstractions. .

Experiments have been performed on some classi.cal planning domains, widely acknowledged by the plannmg community -although not specifically tailored for ab­ straction. To better assess the significance of the results, three different planners have been used while performing experiments.

The remainder of this paper is organized as follows : first, some relevant work on planning by abstraction is briefly recalled, to give the reader a better insi.ght of the issues deemed relevant. Then, the overall architecture of the system is illustrated, including the semi-automatic technique we developed for generating abstract spaces. Subsequently, experiments are described and results are discussed. Finally, conclusions are drawn and future

work is outlined.

2 Related Work

Building an ordered set of abstractions for controlling ~he search has proven to be an effective approach for dealmg with the complexity of planning tasks. This technique requires the original search space to be mapped int? cor­ responding abstract spaces, in which irrelevant detmls are disregarded at different levels of granularity. .

Two main abstraction mechanisms have been studied in the literature: action- and state-based. The former combines a group of actions to form macro-operators [Korf, 1987]. The latter exploits rep~es~ntations ?f the domain given at a lower level of detail; Its most sigmfi­ cant forms rely on (i) relaxed models, obtained by dro~­ ping operators' applicability condition~ [Sacerdotl, 1974], and on (ii) reduced models, obtamed by com­ pletely removing certain conditions from the problem space [Knoblock, 1994). Both models, while preserving the provability of plans that hold at the ground level, per­ form a "weakening" of the original problem space, thus suffering from the drawback of introducing "false" solu­ tions at the abstract levels [Giunchiglia and Walsh,

1990). .

As for Knoblock's abstraction hierarchies, each predi­ cate is associated with a unique level of abstraction according to the constraints imposed by the ordered monotonicity property [Knoblock, 1994]. Any such hier­ archy can be obtained by progressively removing certain predicates from the domain (or problem) space.

From a general perspective, let us assume that abstrac­ tions might occur on types, predicates, and operators. Relaxed models are a typical example of predicate-based abstraction, whereas macro-operators are an example of operator-based abstraction.

3 System Architecture

The system has been called HW[}, standing for (paramet­ ric) Hierarchical Wrapper. Note that square brackets are part of the name, indicating the ability to embed an ex­ ternal planner; being P any such planner, the notation HW[P] shall be used to denote an instance of HW[] able to exploit the planning capabilities of P.

Figure 1 illustrates the architecture of the system, fo­ cusing on its main components, i.e., an engine and the embedded planner. The former is devoted to controlling the communication between adjacent levels, whereas the latter is exploited to perform planning at any given level of abstraction.

Any domain-independent planner can be embodied within the system, provided that compliance with the STRIPS subset of the PDDL 1.2 standard is ensured.

Although the system supports a multiple-level hierar­ chy, for the sake of simplicity, in the following we as­ sume that only one abstract level exists, giving rise to a two-level (i.e., ground and abstract) hierarchical descrip­ tion.

3.1 The Planning Algorithm

Once instantiated with an external planner P, HW[P] takes as inputs a ground-level problem and a structured description of the corresponding domain, including a set of rules to be used while mapping ground into abstract states and vice-versa. In fact, to perform planning at dif­ ferent levels of abstraction, the engine of HW[} must op­ erate bi-directional translations (upwards and down­ wards) to permit communication between adjacent levels.

To find a solution of a given problem, first the engine of HW[P] translates the init and goal sections from the ground to the abstract level. P is then invoked to search for an abstract solution. Subsequently, each abstract op­ erator is refined by repeatedly invoking P. The refine­ ment of an abstract operator is performed by activating P, at the ground level, on the goal obtained by translating downward its effects. Note that the initial state of each refinement depends on the previous refinement; hence, refinements must be performed according to the order specified by the abstract plan. To avoid incidental dele­ tion of subgoals already attained during previous refine­ ments, they are added to the list of subgoals that results from translating downward the effects of the current ab­ stract operator to be refined.

When the attempt to refine the current abstract solution fails P is invoked to find the next abstract solution, 1 unless the number of abstract solutions found so far ex­ ceeds a given threshold (m) . If no abstract solution could be successfully refined, to ensure the completeness of the algorithm, an overall search is performed at the ground level. The whole process ends when a ground solution is found or the overall search fails.

3.2 Extending PDDL for Dealing with Abstraction

A problem and its corresponding domain are described in accordance with the standard PDDL 1.2 syntax, using the "define problem" and "define domain" statements, re­ spectively. To describe how bi-directional communica­ tion occurs between adjacent levels an extension to the standard PDDL has been devised and adopted.

More precisely, the syntactic construct "define hierar­ chy" has been introduced. It encapsulates an ordered set of domains, together with a corresponding set of map­ pings between adjacent levels of abstraction. Since the mappings are given in term of types, predicates and op­ erators, three subfields have been introduced (i.e., :types, :predicates, and :actions), to represent the abstraction over such dimensions. The general form of the construct is:

(define (hierarchy <name>) (:domains <domain-name>+ ) (:mapping (<src-domain> <dst-domain>) [:types <types-def>] [:predicates <predicates-def>] [:actions <actions-def>] ) '>

The following notation is adopted in the :types field to represent a clause for mapping types:

(abstract-type ground-type)

It specifies that ground-type becomes abstract-type while performing upward translations. To disregard a type, the following notation must be used:

1 Due to the limitations of most of the existing planners, the process of incrementally querying for another solution may be simulated by preliminarily querying for m abstract solutions, to be released incrementally on demand.

(nil g r ound - type )

Moreover, the following notation is adopted in the :predicates field to represent a clause for mapping predicates:

( (abstract - predicate ?pll ?p21 _ ) (ground-predicate ?pl2- t12 ?p22- t22 _,))

It specifies that ground -predi cate must be pre­ served while going upward and vice-versa. Note that, if no differences exist in mapping a predicate between adja­ cent levels, the corresponding clause can be omitted.

To disregard a predicate while performing upward translations, the following notation is used:

(nil (ground-predicate ?p l 2- t12 ?p22- t22 _ ) )

It specifies that ground- p redica te is not translated into any abstract-level predicate.

In addition, abstract-pred icate can be expressed as a logical combination of some ground-level predicates.

To describe how to build the set of operators for the abstract domain, in the : actions field, four kinds of mapping can be expressed:

• an action remains unchanged or some of its parame­ ters are disregarded;
• an action is removed;
• an action is expressed as a combination of actions belonging to the ground domain;
• a new operator is defined from scratch.

3.3 Generating Abstractions

To facilitate the setting of abstract spaces, as an alterna­ tive to the hand-coded approach used in [Armano et a!., 2003] , a novel semi-automatic technique for generating abstraction hierarchies starting from ground-level domain descriptions has been devised and adopted.

From our particular perspective, performing abstrac­ tion basically involves executing two steps: (i) searching for macro-operator schemata through a priori or a poste­ riori analysis, (ii) selecting some of the schemata evi­ denced so far and translating them into abstract operators.

In this subsection, we concentrate on the task of find­ ing macro-operator schemata throughout an a-priori analysis performed on the given domain and problem, rather than adopting the a-posteriori technique illustrated in [Armano and Vargiu, 2001] , aimed at finding macro­ operator schemata according to a post-mortem analysis performed on plan "chunks".

Step (i) is performed by an algorithm for building and then pruning a directed graph, whose nodes represent operators and whose edges represent relations between effects of the source node and preconditions of the desti­ nation node. In particular, for each source node A and for each destination node B, representing operators defined in the given domain, the corresponding edge is labeled with a pair of non-negative numbers, denoted by <a b>. The pair accounts for how many predicates A can estab­ lish (a) and negate (b) that are also preconditions of B. It is worth noting that source and destination node may co­ incide, thus giving rise to a self-reference.

Pruning is performed according to the domain­ independent heuristics reported in Table I. Note that the pruned graph does not contain edges labeled <0 0>, the corresponding operators being completely independent.

At this point, the most promising macro-operator schemata can be easily extracted from the pruned graph, each path being related with a candidate macro-operator.

As an example, let us consider the well-known blocks­ world domain, encompassing four operators: stack, pick­ up, unstack, put-down. The corresponding graph is shown in Figure 2. Bearing in mind that the same mechanism has been applied to all operators' pairs, let us concentrate -for instance- on the relation that holds between stack (source node) and pick-up (destination node).

Considering that the effects of the stack operator are:

(not (holding ?x)) (not (clear ?y)) (clear ?x) (handempty) (on ?x ?y)

and that the preconditions of the pick-up operator are:

(clear ?x) (ontable ?~) (handempty)

we label the corresponding edge with the pair <2 1>. It is apparent that stack establishes two preconditions for pick-up, while negating another.

As for the pruning activity, Figure 3 shows the resulting graph for the blocks-world domain. 2 The resulting macro-operator schemata are (";" being used for concate­ nation): pick-up;stack, unstack;put-down, pick-up;put­ down, and stack;unstack.

Step (ii) is performed by selecting a subset of the re­ sulting macro-operator schemata, and by translating them into abstract operators. In principle, generating an ab­ stract operator is not a deterministic task; for this reason in the current implementation of the system this mecha­ nism has not yet been completely automated. Neverthe­ less, the simplest way of generating an abstract operator consists of deleting from the abstract level all predicates that do not occur among preconditions or effects of any selected macro-operator. This process influences (and is influenced by) the translation rules that apply to both types and predicates. For instance, the absence of a predicate as a precondition or effect of any induced ab­ stract operator entails its deletion from the abstract level.

As for the blocks-world example, two macro-operator schemata have been disregarded (i.e., stack;unstack and pick-up;put-down), as they do not alter the state of the domain (the resulting set of effects being empty). In fact, it is apparent that they are composed of complementary actions.

It is worth pointing out that the approach described above can be used also for generating abstractions tai­ lored to a given problem, by simply adding a dummy operator representing the goal(s) of the problem itself. This "goal" operator has only preconditions (its set of effects being empty), representing a logic conjunct of predicates that characterize the goal of the input problem. In this way, all sequences deemed relevant to solve the problem are easily put into evidence (as they end with the "goal" operator).

4 Experimental Results

The current prototype of the system has been imple­ mented in C++. Experiments have been performed with three planners: GRAPHPLAN [Blum and Furst, 1997], BLACKBOX [Kautz and Selman, 1998], and LPG [Ger­ evini and Serina, 2002]. In the following, GP, BB, and LPG shall be used to denote the GRAPHPLAN, BLACKBOX, and LPG algorithms, whereas HW[GP], HW[BB], and HW[LPG} shall be used to denote their hierarchical counterparts.

2 Since we are interested in finding macro-operators, we do not take into account self-references.

To assess the capability of abstraction to improve the search, we performed some tests on five domains taken from the 1998, 2000, and 2002 AlPS planning competi­ tions [Long, 1998; Bacchus, 2000; Long, 2002]: elevator, logistics, blocks-world, gripper, and zeno-travel. Experi­ ments were conducted on a machine powered by an Intel Celeron CPU, working at 1200 Mhz and equipped with 256Mb of RAM. A time bound of 1000 CPU seconds has also been adopted.

All domains have been structured according to a ground and an abstract level, the latter having been gen­ erated following the approach described in the previous subsection. For each domain, several tests have been per­ formed -characterized by increasing complexity. Table 2

compares the CPU time of each planner over the set of problems taken from the AlPS planning competitions. Dashes show problem instances that could not be solved by the corresponding system within the adopted time­ bound.

Elevator. Experiments show that -for GP and BB- the CPU time increases very rapidly while trying to solve problems of increasing length, whereas HW[GP] and HW[BB] keep solving problems with greater regularity (although the relation between number of steps and CPU time remains exponential). LPG is able to solve long plans in a very short time, thus doing away with the need to resort to HW[LPG} .

Logistics. In this domain GP easily solves problems up to a certain length, but it is unable to solve problems within the imposed time limits if a given threshold is ex­ ceeded. On the other hand, HW[GP} succeeds in solving problems of increasing length without encountering the above difficulties. BB performs better than HW[BB] for small problems, whereas HW[BB] outperforms BB on more complex problems. LPG is able to solve long plans in a few seconds at the most. For unknown reasons LPG was not able to refine any abstract operator when invoked by the engine of HW[LPG] .

Blocks-world. Tests performed on this domain reveal a similar trend for GP and HW[GP], although the latter performs slightly better than the former. BB performs better than HW[BB] for simple problems, whereas HW[BB] outperforms BB on problems of medium com­ plexity. LPG is able to solve problems whose solution length is limited to 100 steps. In this domain, HW[LPG} clearly outperforms LPG on more complex problems.

Zeno-travel. Unfortunately, in this domain, neither GP nor HW[GP] are able to successfully tackle most of the problems of this domain. An improvement of HW[BB}

over BB can be observed, similar to the one shown for the blocks-world domain. LPG is able to solve long plans in a few seconds at the most, thus avoiding the need to resort to HW[LPG] .

Gripper. For the gripper domain, both HW[GP] and HW{BB] clearly outperform their non-hierarchical coun­ terparts. LPG is able to solve long plans in a very short time.

For the sake of brevity, only two plots (i.e., Figures 45 concerning the blocks-world domain) of relative per­ formances -i.e. non hierarchical vs. hierarchical- are reported.

5 Conclusions and Future Work

In this paper a parametric system has been presented, devised to perform hierarchical planning by delegating the actual search to an external planner (the parameter). Aimed at giving a better insight of whether or not the exploitation of abstract spaces can be useful for solving complex planning problems, comparisons have been made between any instances of the hierarchical planner and its non-hierarchical counterpart.

To better investigate the significance of the results, three different planners have been used to make experi­ ments. To facilitate the setting of experiments, a novel semi-automatic technique for generating abstract spaces has been devised and adopted. Experimental results high­ light that abstraction is useful for classical planners, such as GP and BB. On the contrary, the usefulness of resort­ ing to hierarchical planning for the latest-generation planner used for experiments (i.e., LPG) clearly emerges only in the blocks-world domain.

As for future work, we are currently addressing the problem of automatically generating abstract operators.