GAM

Solving Complex Planning Tasks Through Extraction of Subproblems

• GAM-P using planning graphs to derive an ordering for conjunctive goals (updated 7/29/98).
  (relatively slow, but more powerful in STRIPS domains).

• GAM-O using an operator backchaining method to derive an ordering for conjunctive goals (updated 7/29/98).
  (much faster and more powerful in ADL domains).

• domain collection containing all examples that are described in the publications on GAM.

Papers describing GAM

1. J. Koehler, J. Hoffmann: On Reasonable and Forced Goal Orderings and their Use in an Incremental Planning Algorithm, Journal of Artificial Intelligence Research, forthcoming.

2. J. Koehler: Solving Complex Planning Tasks Through Extraction of Subproblems, Copyright AAAI Press, AIPS-98.

3. J. Koehler, J. Hoffmann: Planning with Goal Agendas, Technical Report 110.

4. J. Koehler, J. Hoffmann: On Reasonable and Forced Goal Orderings and their Use in an Incremental Planning Algorithm, Technical Report 132.

When solving complex planning tasks that are described by a set of conjunctive goals one observes that the search space usuallly grows exponentially in the size of the task. One idea to avoid searching the whole space is the following:

• Gain structural information about the task at hand as a preprocess;
• Use this information to order the goals such that the the task is divided into several small subproblems;
• Solve these subproblems;
• Generate a plan for the whole task out of the solutions to the small problems.

How GAM works

Given a planning problem as a set I of initially true atoms, a set of operators O and a set of goals G, GAM tries to create a "Goal Agenda" GA, which defines a total ordering between increasing subsets of G, i.e., GA = [1:G1 .. n:Gn] and G = Gn and each Gi is a subset of each Gi+1. The algorithm proceeds as follows:

• Generate a relation '<' over the goals in G, setting A '<' B for two goals A, B in G iff A "should be reached" before B.

• The '<' Relation defines a directed graph, where the nodes are the goals in G and the edges are the '<' Pairs.

• Compute the transitive closure of this graph and divide G into a linear ordered set of equivalence classes (for example, nodes that are in a cycle fall into the same equivalence class).

IPP using GAM is sound and complete, but in some domains, plans can contain superfluous actions.

Using GAM

To create a plan using a goal agenda, start IPP with option -g 1. Option -g 2 stops IPP after GAM finished computing the agenda, if it is only the agenda, not the plan, that you're interested in. As a default, GAM will not be used (option -g 0). Other GAM options are as follows:

• Option -L: Linearize entries of the goal agenda.

  In some domains, it does not matter in which order the goals are achieved. So it can be a good idea to tell the planner to reach them in any arbitrary order one by one, splitting one huge problem into several very small ones. Now, looking at the goals that make up one entry in the goal agenda, it is clear that indeed the order in which the planner achieves them shouldn't matter; otherwise they simply wouldn't be in the same agenda entry. After all, the entries make up equivalence classes wrt. order of achievement. Using the -L option makes GAM linearize the goals of each agenda entry in an arbitrary order, resulting in significant better performance of IPP on many domains.

• Option -D: Do intermediate computation.

  In most cases, in order to achieve some goal A, there are some goals, which we call intermediate goals for A, that have to be made true before A no matter how the planner is trying to achieve A. This is, for example, the case if you try to achieve on(A B) in the Blocksworld: no matter how you are achieving this goal, clear(B) and holding(A) must hold first. The intermediate goals can be computed in a way similar to the operator backchaining process used by RIFO. Once the intermediates are computed, they can be used to improve the goal agenda: if I is the set of intermediate goals computed for an entry A in the agenda, where the agenda has the form [n:B,n+1:A,B], place I between B and A. Planning proceeds as follows:

  • first plan for B and I;

  • if this fails (intermediate sets can be unsolvable sometimes), plan for B alone;

  • then plan for A,B.

  The Idea behind this is to avoid non-optimal plannning: making the planner achieve intermediate goals for A together with the goals in B, such that it won't delete any goals that may be necessary to achieve the goals in A, i.e., that would have to be re-established otherwise.

• The perfect planning domain to use GAM is the well known Blocksworld. Using GAM and RIFO, IPP can, for example, solve a huge stacking problem with 100 blocks in a few minutes. The performance on some more typical Blocksworld problems (the SATPLAN examples) where the planner has to transform some stacks of blocks into some other stacks of blocks is shown in the following table.

  	#actions	IPP +G	IPP +G+R
  bw-large.b	22	2.24	0.80
  bw-large.c	48	9.36	3.85
  bw-large.d	54	26.61	4.86

  Without GAM, IPP can only solve the first example, bw-large.b, for which it finds an optimal plan out of 18 actions. Using a goal agenda, the plans become slightly longer (22 instead of 18 actions for the first example), because some blocks are accidentally put in positions where they cut off goals that are still ahead in the agenda, but performance is increasing dramatically. A further speed-up is possible when RIFO is additionally used (IPP +G+R) to remove irrelevant information from all subproblems, because this reduces the size of planning graphs dramatically.

• Good results can also be achieved on a variant of the Tyreworld, where an increasing number of flat tyres needs to be replaced. The plans that are generated with GAM are slightly non-optimal, which is caused by superfluous jack-up and jack-down actions because wheels are mounted on the hubs, but do not need to be secured immediately with nuts. However, to add the nuts, a hub must be jacked-up. This problem is caused by the original domain representation - adapting the operators to the problem of fixing several tires, the optimal plans are generated.

  #wheels	IPP	IPP +G+R	IPP +G+R+L
  1	0.10	0.23	0.24
  2	17.47	0.74	0.53
  3	-	9.62	0.92
  4	-	-	1.57
  10	-	-	18.83

  The -L option is especially useful on these problems because one entry in the generated goal agenda contains the subproblem of actually changing the wheels. Since this can be done in any order, linearizing the agenda entries leeds to a dramatic performance improvement. In the case of 10 wheels only 2662 actions are tried to generate a plan of 136 actions within 0.14 s. It takes 0.54 (!) seconds to generate the goal agenda, 14.22 s to remove irrelevant information from all subproblems, 3.82 s to generate the various planning graphs, and 0.11 s to compute the initial state for each subproblem.

• Finally, in the Briefcaseworld, where we have a conditional move operator (all objects in the briefcase are moved together with the briefcase when they are inside) as well as a put-in and a take-out operator, some significant improvements can be made using intermediate goals. The problem is to make a "tour", i.e. we have n objects at n different places and want to carry them home.

  #objects	IPP	IPP +G+L
  4	4.42	0.23
  5	311.95	0.44
  6	-	0.78
  10	-	4.42

  Without any help of GAM, this becomes impossible for IPP for more than five objects. Using GAM with option -D, the in(obj) predicates for the objects are generated as intermediate goals for the at-home(obj) predicates, which were the original goals stated in the planning task. Now, if we also use -L, the planner gets one in(obj) goal after the other, and for each object simply goes to the right place and collects it. After all objects are collected, it only has to do one more step, i.e., move home, and the problem is solved. Doing it this way, even 10 objects can be brought home in a matter of seconds, while still generating the optimal plan.