8.7 References and Further Reading

The STRIPS representation was developed by Fikes and Nilsson (1971).

There is much ongoing research into how to plan sequences of actions. Yang (1997) presents a textbook overview of planning. For a collection of classic papers, see Allen et al. (1990).

Forward planning has been used successfully for planning in the blocks world, where some good heuristics have been identified by [Bacchus and Kabanza (1996)]. (See Exercise 8.6.)

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)]. The treatment of planning as a CSP is also investigated by Lopez and Bacchus (2003) and van Beek and Chen (1999). Bryce and Kambhampati (2007) give a recent survey.

Partial-order planning was introduced in [Sacerdoti (1975)]'s NOAH and followed up in [Tate (1977)]'s NONLIN system, [Chapman (1987)]'s TWEAK algorithm, and [McAllester and Rosenblitt (1991)]'s 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 8.15).

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.