Least-commitment action selection
Marc Friedman, Daniel S. Weld · 1996
The principle of least commitment was embraced early in planning research. Hierarchical task networks (HTNs) reason about high-level tasks without commit-ting to specific low-level steps. Partial-order planning arose from a complementary desire to avoid unnec-essary 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 com-mon features, computation may be duplicated unnec-essarily on the various branches. The FABIAN planner attempts to avoid such waste. FABIAN separates the decision to add a step from the choice of which step to add. FABIAN supports an open condition by adding an abstract action to the plan representing the disjunc-tion 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 sav-ings, 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.