Using Available Memory to Transform Graphplan's Search

1 Motivation and Approach

Despite the recent dominance of heuristic state-search planners over Graphplan-style planners, the Graphplan approach [Blum and Furst 1997] is still one of the most effective ways to generate so-called "optimal parallel plans". While state-space planners are drowned by the exponential branching factors of the search space of par­ allel plans, Graphplan excels due to the way it combines an IDA* style iterative search [Bonet and Geffner, 1999] with a highly efficient CSP-based, incremental generation of valid action subsets . We present here a system called PEGG, that addresses weaknesses in Graphplan's ap­ proach by employing avai lable memory to: 1) reduce the redundant search Graphplan conducts in consecutive it­ erations, and 2) more importantly, to transform Graph­ plan's IDA* search into iterative expansion of a select set of states that can be traversed any order.

A shortfall of the IDA *'s approach to search is the fact that it regenerates many of the same nodes in each of its !terations. This can be traced to using too little memory m many cases; the only information carried over from one iteration to the next is the upper bound on the f­ value. Given that consecutive iterations of search over­ lap significantly, we investigated using additional mem­ ory to store a trace of the explored search tree to avoid repeated re-generation of search nodes . With a represen­ tation of the explored search space, we can transform the way this space is extended during the next iteration. In particular, we can (a) expand search trace nodes in the order of their heuristic merit and (b) we may also con­ sider iteratively expanding a select set of states. This strategy is too costly for normal IDA* search, but Graph­ plan's type of IDA* search is particularly well-suited to these changes as the kth level planning graph provides a compact way of representing the search space traversed by the corresponding IDA* search in its kth iterat ion. The state space view provided by the search trace allows us to transform Graphplan's search from its depth-first default to a more informed traversal of the space.

2 Design and Experiments

As would be expected for IDA* search there is great similarity (redundancy) in the search space for successive search episodes as the plan graph is extended. In fact, the search conducted at any level k+ 1 of the graph is essen­ tially a replay of the search conducted at the previous level k with certain well-defined extensions. Specifi­ cally, every set of subgoals reached in the backward search of episode n, starting at level k, will be generated again by Graphplan in episode n+ 1 starting at level k+ 1.

Figure 1 depicts the state space tree structure correspond­ ing to Graphplan's search over three consecutive search iterations on a hypothetical problem. The dark shaded sta~es are first produced during Graphplan's attempt to satisfy the XYZ goal at level 7. They are generated again in the next episode, each at one level higher, along with some new states (shown in lighter shade). Finally, in the third episode Graphplan regenerates the dark and lighter shaded states, attempting to satisfy XYZ at level 9, and finds a solution.

EGBG [Zimmerman, Kambhampati, 1999] used memory to aggressively record the experi­ ence in each search episode, essentially avoid­ ing all redundant effort. That approach con­ fronted memory constraints on larger problems, but it suggests a more powerful use for a pared­ down search trace : exploiting the snapshot view of the entire search space of a Graphplan itera­ tion to focus on the most promising areas. This transformation frees us from the depth-first na­ ture of Graphplan's search, permitting move­ ment about the search space to focus on its most promising sections first -or even exclusively.

A summary of PEGG (for details; [Zimmer­ man and Kambhampati, 2003]) relies on these definitions: Search segment: a state generated during Graphplan's regression search from the goal state, indexed to a specific plan graph level. It holds the state's goal list, a pointer to the parent search segment, and the actions as­ signed in satisfying the parent's goals. Search trace (ST): the linked set of search segments (states) representing the search space visited in a Graphplan backward search episode. The sets of states in each of the three shadings of Figure I can be seen as the ST after each of the three episodes. Transposition: The extant trace of search segments (states) after search episode n is transposed up one planning graph level for episode n+ 1 as follows : For each ST search

segment associated with graph level j associate it with level j + 1 for episode n+ 1. Visiting a search segment: the goals of segment SP are memo checked at their associated level and if valid, PEGG initiates Graphplan's CSP-style search to satisfy them. The process is enhanced by a cadre of efficiency techniques such as a bi-level plan graph, domain preprocessing, explanation based learning (EBL), dependency directed backtracking (DDB), and Table 1. PEGG vs. Graphplan and enhanced Graphplan (GP-e) GP-e: enhanced Graphplan (see text) so-PEXE. step-optimal, search via the ST. PEGG: beam search on best 20% of search segments in ST -indicates failure in 30 min limit, cpu time Parentheses next to cpu time give# of steps/ # of actions in solution.

Allegro Lisp, runtimes (excl. gc time) on Pentium 900 mhz, 384 MB RAM

goal & action ordering. Whenever the goals of Sp are val­ idly assigned, a child segment is created containing Sp's goals regressed over the assigned actions, and linked to S (thus extending the ST).

The PEGG algorithm: the graph is built until the prob­ lem goals appear non-mutex, and the first regression search episode is conducted ala Graphplan fashion. Dur­ ing this search, the initial trace is constructed, concisely capturing all 'states' generated during the search process. If no solution is found, the ST directs the search process for future iterations. This search is 2-phased: select a promising ST state, then Graphplan's depth-first, CSP­ type search on the state's subgoals is conducted. Another ST search segment is heuristically selected if search fails. Since the ST provides a state space view, PEGG can use 'distance based' heuristics (c.f. HSP-R [Bonet and Geff­ ner, 1999] and AltAlt [Nguyen and Kambhampati, 2000]). For results reported here, the 'adjusted sum' heuristic from the latter is used.

Table 1 compares PEGG against standard Graphplan and a highly enhanced version (GP-e), which has been augmented with the efficiency methods mentioned above. Two PEGG modes of operation are reported; 1) ~PE��: make-span optimal, ST search segments ordered accord­ ing to a state space heuristic, all segments visited, 2) PEGG: Ordering the ST search segments as for 1, beam search on only the heuristically 'best' fraction. The first approach maintains Graphplan's guarantee of step .opti­ mality while the latter sacrifices the guarantee of optimal­ ity in favor of pruning search in all search episodes and bounds the size of the search trace that is maintained in memory. Empirically we find that optimal make-span plans are generally found by PEGG regardless, (one ex­ ception shown in bold) and speedups as high as two or­ ders of magnitude over enhanced Graphplan are achieved.