Planning and Problem Solving

 

• [Russel and Norvig1995] (*) Artificial Intelligence, a Modern Approach, Chapters 11-13.
  Long, Up to date. They cover most of the advances in the last 15 years in planning, but they are sometimes over detailed. Notice that they call SNLP POP, UCPOP POP-DUNC, and CNLP CPOP. Besides that, be sure to read their Bibliographical and Historical Notes at the end of every chapter. Take the first paragraph in the discussion 13.4 as your test for understanding the main ideas in current core planning.
• [Nilsson1980] Principles of Artificial Intelligence, Chapters 7, 8.
  Long, Basic. A summary of classical planning techniques including STRIPS, RSTRIPS, DCOMP, ABSTRIPS, and STRIPS execution monitor (based on PLANEX (Fikes 72')).
• [Chapman1987] Planning for conjunctive goals.
  Medium, Advanced. Read Section 1. Skim Section 2 and the start of Section 3, looking at how the planning problem is formalized and at the theorems (especially the complexity results). You may also want to look at the how TWEAK solves the Sussman anomaly (Section 2.4), and the historical perspective on planning (Sections 3.3-3.4).
• [Lifschitz1986] On the semantics of STRIPS.
  Short, Basic. Lifschitz points out that the STRIPS representation of actions as ADD / DELETE rules is highly sensitive to seemingly minor modifications. A semantic characterization of these rules is given, which delineates the acceptable applications of STRIPS style rules.
• [McDermott1992] Robot Planning.
  Medium, Up to date. A good survey article, but mostly for Robot Planning (as its name suggests).

• [Barr and Feigenbaum1981] Handbook of Artificial Intelligence, Volume 1, Chapter 2.
  Section D1: the Logic Theorist
  Section D2: GPS
  Section D6: ABSTRIPS
  The Logic Theorist is primarily of historical interest. It and GPS were two of the earliest attempts at automated problem solving, and both adopt a search-oriented approach. A better explanation of means-ends analysis is provided by some of the other references, but D2 is still worth reading. The ABSTRIPS program should be learned well.
• [Cohen and Feigenbaum1982] The Handbook of Artificial Intelligence, Volume 3, Chapter 15.
  This reference outline some more classical planning work. Skip the STRIPS and ABSTRIPS section -- the other references for them are much better. The remainder of the chapter should be read carefully,
• [D. A. McAllester1991] (*) Systematic Nonlinear Planning.
  Short, Up to date. The original SNLP paper. Complements the description in Russel & Norvig.