Magazine article AI Magazine

AAAI-10 Classic Paper Award: Systematic Nonlinear Planning: A Commentary

Magazine article AI Magazine

AAAI-10 Classic Paper Award: Systematic Nonlinear Planning: A Commentary

Article excerpt

David McAllester and David Rosenblitt's paper, "Systematic Nonlinear Planning" (published in the Proceedings of the Ninth National Conference on Artificial Intelligence [AAAI- 91]), won the AAAI-10 classic paper award. This commentary by Daniel S. Weld describes the two major impacts the paper had on the field of automated planning.

The field of automated planning seeks to develop fast methods for generating programs of action that allow an agent to achieve goals or maximize rewards. Initially, researchers made many simplifying assumptions, defining the classical planning problem: produce a sequence of atomic actions that will achieve a logically specified goal in a completely known world where action effects are certain. David McAllester and David Rosenblitt's paper, "Systematic Nonlinear Planning" (McAllester and Rosenblitt 1991), presented 19 years ago at the Ninth National Conference on Artificial Intelligence (AAAI-91), had two major impacts on the field: (1) an elegant algorithm and (2) endorsement of the lifting technique. The paper's biggest impact stems from its extremely clear and simple presentation of a sound and complete algorithm (known as SNLP or POP) for classical planning. While it is easy to define such an algorithm as search through the space of world states, SNLP is a "partialorder" planner, meaning it searches the space of partially specified plans, where only partial constraints on action arguments and ordering decisions are maintained. Here, McAllester and Rosenblitt benefited from David Chapman's elegant TWEAK planner, which greatly clarified previous partial-order algorithms (Chapman 1985). SNLP's key feature is the use of a data structure, called a causal link, to record the planner's commitment to establish a precondition of one action with the postcondition of another. While the notion of causal link wasn't novel, originating much earlier in Austin Tate's NONLIN planner (Tate 1977), SNLP was so much simpler than NONLIN that McAllester and Rosenblitt could prove it was sound and complete. A bonanza of research results followed. Penberthy and Weld's (1992) UCPOP planner handled actions modeled in an expressive language and was widely distributed. Other extensions included temporal planning, planning with metric resources, contingent planning in response to uncertain effects, methods for guiding the planner's nondeterministic search, and so on.

A second contribution of McAllester and Rosenblitt's paper was its clear realization that partialorder planning was not aimed at finding partially ordered plans, but rather lifting the underlying search from operator sequences to equivalence classes over operator sequences (represented by a set of ordering constraints). This insight allowed the authors to steer away from "necessary and sufficient conditions for correctness of partially ordered plans," as formalized by Chapman as the modal truth criterion, and to provide conditions under which the search is systematic, that is, that the equivalence classes don't overlap.

The desire to speed planning led many to abandon partial-order planning in the late 1990s. The impetus for change came from three alternative approaches to planning, each of which appeared to dominate the SNLP family. Avrim Blum and Merrick Furst's Graphplan (Blum and Furst 1995) was the first on the scene. Graphplan operates in two phases - first, in polynomial time it constructs a leveled graph whose nodes are either actions or propositions and whose edges are akin to causal links. In the second phase, Graphplan searches backwards from the graph's final level, looking for a consistent set of actions to achieve the goal. The following year, two more planning algorithms diverted attention from partial-order planners. Using a Graphplanlike, leveled-graph model, SATPLAN (Kautz and Selman 1996) showed that planning problems could be compiled into SAT problems, which modern SAT solvers could solve to create plans, blazingly quickly. …

Search by... Author
Show... All Results Primary Sources Peer-reviewed

Oops!

An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.