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

David McAllester and David Rosenblitt's paper, "Systematic Nonlinear Planning" (published This commentary by Daniel S. Weld describes 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.