Further Reading

Most of the ideas and methods in this chapter have been known for decades. Most of the search algorithms of Section 2.2 are covered in algorithms literature as graph search [243,404,692,857] and in AI literature as planning or search methods [551,743,744,777,839,975]. Many historical references to search in AI appear in [839]. Bidirectional search was introduced in [797,798] and is closely related to means-end analysis [735]; more discussion of bidirectional search appears in [185,184,497,569,839]. The development of good search heuristics is critical to many applications of discrete planning. For substantial material on this topic, see [382,550,777]. For the relationship between planning and scheduling, see [266,382,896].

The dynamic programming principle forms the basis of optimal control theory and many algorithms in computer science. The main ideas follow from Bellman's principle of optimality [84,85]. These classic works led directly to the value-iteration methods of Section 2.3. For more recent material on this topic, see [95], which includes Dijkstra's algorithm and its generalization to label-correcting algorithms. An important special version of Dijkstra's algorithm is Dial's algorithm [272] (see [946] and Section 8.2.3). Throughout this book, there are close connections between planning methods and control theory. One step in this direction was taken earlier in [267].

The foundations of logic-based planning emerged from early work of Nilsson [337,743], which contains most of the concepts introduced in Section 2.4. Over the last few decades, an enormous body of literature has been developed. Section 2.5 briefly surveyed some of the highlights; however, several more chapters would be needed to do this subject justice. For a comprehensive, recent treatment of logic-based planning, see [382]; topics beyond those covered here include constraint-satisfaction planning, scheduling, and temporal logic. Other sources for logic-based planning include [378,839,963,984]. A critique of benchmarks used for comparisons of logic-based planning algorithms appears in [464].

Too add uncertainty or multiple decision makers to the problems covered in this chapter, jump ahead to Chapter 10 (this may require some background from Chapter 9). To move from searching in discrete to continuous spaces, try Chapters 5 and 6 (some background from Chapters 3 and 4 is required).