RIFO

Removing Irrelevant Operators and Initial Facts from Planning Problems

How RIFO works

To limit search to those facts and operators only, which are indeed necessary to generate a solution plan, most common planning systems start searching from the goals. Graphplan and IPP, however, build a "planning graph" starting from the initial facts. This has been a very successful approach, but can lead to ineffective graph expansion and search processes if the planning task specification contains irrelevant information.

RIFO tries to determine such irrelevant information (ground operators and initial facts) using a "backchaining" process and removes them from the planning task. While trying to reach the goals recursively, sets of possibly relevant objects and initial facts are built. In order to prevent this procedure from becoming a complete planning process a simple heuristics is used: Try to achieve ALL goals (AND nodes) by backchaining and branching on different ground operators (OR nodes), which achieve one of the goals. The process is repeated recursively using operator preconditions and effect conditions as new goals, which generates a so called "fact generation tree", in which potential conflicts between goals and operators are ignored.

Depending on the heuristic and union method chosen, different kinds of "possibility sets" of relevant objects and facts are created. These sets can be used in different ways to decide over relevance or irrelevance of ground operators and initial facts.

Using RIFO

To remove irrelevant information as a planning preprocess, start IPP with option -rr 1. Option -rr 2 stops IPP after RIFO and can be used to trace RIFO processing. As a default, RIFO will not be used (option -rr 0). All other RIFO options are listed when calling IPP with option -rh. A drawback of this RIFO implementation for conditional effects is the insufficient filtering of facts from the initial state. We do not do any filtering in order to guarantee soundness (otherwise interactions between conditional effects could remain undetected during search), but in fact more sophisticated filtering strategies (e.g. removing all facts not occuring in effect conditions) could be implemented.

Finetuning the Discovery of Irrelevants

RIFO provides different heuristics to remove irrelevants. Some are very powerful, reducing planning time by orders of magnitude (as shown below), but do not work in some cases, i.e. too many ground operators and initial facts have been removed such that the planning task becomes unsolvable. But since RIFO provides an efficient preprocessor and IPP usually terminates rather quickly on unsolvable planning problems, one possible way to use RIFO is to iteratively try out heuristics of decreasing degree of strength and to turn off RIFO only if all of them fail.

• Option -rm (-u in IPP 4.1) : Union Method

  A "possibility set", i.e. a set of possibly relevant initial facts and objects is usually composed out of several sets. The -rm option specifies how to build one final possibility set out of these sets.

  • -rm 1: Use all considered initial facts; do not distinguish sets of sets, but consider the union over all elements from all sets.

  • -rm 2: Build the final possibilty set as the union over all sets found.

  • -rm 3: Build the union over all best (cardinality-minimal) sets (DEFAULT).

  • -rm 4: Take one best (cardinality-minimal) set.

• Option -rl (-r in IPP 4.1): Filtering Strength - Selecting Initials and Operators

  Decide what to do with the set of possibly relevant facts and determine which of the ground operators will be used by IPP.

  • -rl 1: Filter out relevant objects. Select initial facts and ground operators that use only relevant objects (DEFAULT).

  • -rl 2: Select initial facts appearing in the possibility set. Operators are selected as with -rl 1.

  • -rl 3: Use only ground operators that appeared in the fact generation tree, i.e. that have been selected while backchaining from the goals. This provides the strongest filter leading to a very powerful heuristic because the number of operators (and this way the size of the graph) is significantly reduced.

  In IPP 4.1 we only have the options -r 1, which filters operators using relevant objects and -r 2, which filters only operators appearing in the fact generation tree. No filtering of initital facts is performed, because we have true negation and removing initial facts can lead to incorrect plans.

ipp -rr 1 -rm 4 -rl 3
ipp -rr 1 -rm 3 -rl 3
ipp -rr 1 -rm 3 -rl 2
ipp -rr 1 -rm 3 -rl 1
ipp -rr 1 -rm 1 -rl 1
ipp -rr 0

Try those calls one after another until IPP finds a plan - usually this will happen during the first three calls.

A few Results:

• Blocksworld: This seems to be a perfect domain for RIFO. The strongest combination of union method and heuristic could be used (options -rm 4 -rl 3) in all tested cases. Here is one example taken from the SATPLAN test suite: bw_large_b.fct

  	IPP	RIFO
  Operators	242	72
  Initial facts	26	22
  time used	129.32 secs	0.89 secs

  Using RIFO, IPP can handle the problem not only much faster, but also needs much less memory because the size of the planning graph is significantly reduced.

• Manhattan: McDermott's Manhattan world provides a huge number of initial facts and operators leading to unsolvability for Graphplan and IPP because both systems run out of memory even on a machine with 1 Gigabyte main memory. Obviously, only a small number of the operators and facts is needed in the solution plan and RIFO is successful in filtering them out. This makes it possible for both planners to solve the problem mh.fct in under 30 seconds!

  	IPP	RIFO
  Operators	1948	93
  Initial facts	31	257
  time used	unsolvable	26.83 secs

• Rocket: Another example from the SATPLAN test suite showing that even when operator-based selection is not possible, more "permissive" heuristics may nevertheless lead to very good results.
  Setting the parameters to -rr 1 -rm 4, a successful heuristic leading to a plan in the rocket_a.fct example results. Using the meta-heuristic given above, two unsuccessful trials were made before a plan is found by IPP. The failing trials take only additional 0.11 secs + 0.13 secs = 0.24 secs planning time. Time including those unsuccessful calls is given in braces.

  	IPP	RIFO
  Operators	186	93
  Initial facts	30	27
  time used	161.78 secs	0.39 secs (0.63 secs)

  IMPORTANT: As described in the paper by Nebel, Dimopoulos and Koehler, using RIFO in this domain may lead to longer plans because useful (but not necessary) information might be deleted. This is the case in our example, too. The original plan found by IPP without RIFO needs one time step less than the one with RIFO.