Running FF
Installation
The available planners are all in the directory
/planners.
The easiest thing to do is use the command
module add /home/TDDC17/www-pub/info/labs/planning/planners.mod, which
will
include this directory in your path. After that, you can run them by just
typing the planners name.
Questions, Problems and Bugs
Through the
WWW links provided you can find out more about the planning systems, but
please, do not bother their authors with trivial
questions.
How FF Works
FF searches the state space forwards from the initial state, using a
variant of hill-climbing search and a non-admissible heuristic. The
heuristic is computed using a simplified form of the same graph
construction used by Graphplan, IPP and other planners. FF, however,
rebuilds the graph in each state: thus, it puts a lot of work into
expanding each node of the search tree, but when the heuristic works
well, it expands relatively few nodes.
In ordinary hill-climbing search, the best (according to the heuristic)
neighbouring node is chosen. The hill-climbing variant used by FF works
such that if all neighbouring nodes are worse than the current node, a
breadth-first search is started outwards from the current node and
continued until a better node is found.
FF also uses some cut-off techniques so that it does not have to
consider all neighbouring nodes when searching for a better node.
Before starting search, FF performs some analysis to try to simplify
the goal. If the goal simplifies to the constant FALSE, the
problem is provably unsolvable and the planner exits.
Plans found by FF are sequential, and not guaranteed to be the shortest
possible.
Input
FF accepts PDDL input, essentially the same subset as IPP (quantified and
conditional effects, quantified preconditions and goals and :typing,
but not type hierarchies).
There is also a version of FF (called Metric-FF) that can plan with
numerical state variables and effects.
Running FF
FF is started with the command
- ff -o <domain file> -f <problem file>
More options are available, most generating more verbose output: run
ff without arguments for a list.
The command to run Metric-FF is called ffm.
Output
Typically, FF's output will look like the following:
After some preamble (files read, etc.), hill-climbing search
starts ("goal distance" is the heuristic value of the current node):
Cueing down from goal distance: 31 into depth [1]
30 [1]
29 [1][2]
27 [1][2]
26 [1]
28 [1][2]
.
.
.
The number to the right is the depth of the breadth-first search
needed to find a better node. This continues until a plan is found:
ff: found legal plan as follows
step 0: LOAD PACKET3 TRUCK3 OFFICE3
1: LOAD PACKET4 TRUCK4 OFFICE4
.
.
.
Since hill-climbing can get stuck in "dead ends" of the search space,
the breadth-first search for a better node may fail. In this case,
FF reverts to plain best-first search from the initial state:
Enforced Hill-climbing failed !
switching to Best-first Search now.
advancing to distance : 5
4
.
.
.
Switching to best-first search is always "safe" (i.e. it makes
the planner complete), but it is too inefficient to be possible for larger
problems.
Besides cases when hill-climbing fails, the effectiveness of FF's
heuristic on a particular problem can be estimated by how deeply it
has to search for a better node at each hill-climbing step.
Known Problems
FF, like IPP, requires all the arguments to an operator to be different,
i.e. an action such as (move A B A) is considered
impossible regardless of the domain definition. This can cause a problem
in some domains: see
slidetile.pddl and
eight01.pddl for an example,
and eight01x.pddl for a
possible solution.
More about FF
- Homepage:
-
http://www.loria.fr/~hoffmanj/ff.html