FABIAN

Overview

FABIAN is a partial-order planner that reasons about disjunctions of actions. To establish a precondition, it adds a generalized action representing the disjunction of all possible actions that could be added to a plan to establish that precondition. This separates the decision to add a step from the choice of which step to add (which is made later). In many cases, when operators have a lot in common, their shared properties (preconditions and effects) can then be dealt with all at once, rather than one possible operator at a time. This eliminates the duplication of this reasoning on all the branches in the search space.

A paper in Artificial Intelligence Planning Systems '96 presents the algorithm, its theoretical properties, and performance results. The abstract and a link to the postscript paper are below.

Least-Commitment Action Selection

The principle of least commitment was embraced early in planning research. Hierarchical task networks (HTNs) reason about high-level tasks without committing to specific low-level steps. Partial-order planning arose from a complementary desire to avoid unnecessary ordering commitments. But most of today's partial-order planning algorithms commit to a single producing step when supporting an open condition --- even when multiple alternatives exist. Each possibility results in a different child plan, and therefore a branch in the search tree. If the various choices have common features, computation may be duplicated unnecessarily on the various branches. The FABIAN planner attempts to avoid such waste. FABIAN supports an open condition by adding an abstract action to the plan representing the disjunction of possible new supporting steps; only later does it refine this choice to a particular concrete action. We show that this abstraction can lead to exponential savings, and argue that in the worst case FABIAN never explores more than a slightly larger space of plans than does a traditional planner such as SNLP.

More Info

For an introduction to partial order planning, see Russell and Norvig, Artificial Intelligence: A Modern Approach , sections 11.6 and 11.7. Or look at McAllister and Rosenblitt's "Systematic Nonlinear Planning," online . Russell's POP is essentially drawn from McAllester's SNLP.

Publications

• Friedman and Weld. Least-Commitment Action Selection. In Proceedings of AIPS '96. 1996.