6 Planning with Certainty

6.7 References and Further Reading

There is much ongoing research into how to plan sequences of actions. Geffner and Bonet [2013] and Yang [1997] present overviews of automated planning.

The STRIPS representation was developed by Fikes and Nilsson [1971].

Forward planning with good heuristics [Bacchus and Kabanza, 1996] is the basis for the most efficient algorithms [Geffner and Bonet, 2013]. (See Exercise 4.)

Regression planning was pioneered by Waldinger [1977]. The use of weakest preconditions is based on the work of Dijkstra [1976], where it was used to define the semantics of imperative programming languages. This should not be too surprising because the commands of an imperative language are actions that change the state of the computer.

Planning as CSP is based on Graphplan [Blum and Furst, 1997] and Satplan [Kautz and Selman, 1996] and is also investigated by Lopez and Bacchus [2003] and van Beek and Chen [1999]. Bryce and Kambhampati [2007] surveys the field.

Partial-order planning was introduced in Sacerdoti’s [1975] NOAH and followed up in Tate’s [1977] NONLIN system, Chapman’s [1987] TWEAK algorithm, and McAllester and Rosenblitt’s [1991] systematic non-linear planning (SNLP) algorithm. See Weld [1994] for an overview of partial-order planning and see Kambhampati et al. [1995] for a comparison of the algorithms. The version presented here is basically SNLP (but see Exercise 14).

See Wilkins [1988] for a discussion on practical issues in planning. See Weld [1999], McDermott and Hendler [1995], and Nau [2007] and associated papers for a recent overview.