Planning



Introduction

I like to open this topic by giving a general introduction to problem solving and then putting planning, scheduling, learning, etc. in the context of problem solving.

Planning = How do I get from here to there?

There have been various formulations that attempt to solve the planning problem:

Logic-based Planning

Also sometimes categorized as change-based planning . This is best introduced by the following figure taken from Genesereth & Nilsson (page 286, see References & Resources below):


See Chapter 12, page 286, Figure 12.1 in Genesereth
& Nilsson's text.
Given the following: The planner will try to generate a plan, \Gamma which, when executed by the acting module or the executor when the system is in the state i satisfying the initial state description, will result in the state g satisfying the goal state description.

This can then lead into a presentation/discussion of situation calculus . Also, a good point to introduce various planning problems:

Another good place to introduce nonmonotonic logics (circumscription, default logic, modal logic, etc.) .

Operator-based Planning

Actions are represented as operators . This approach, also called, the STRIPS approach , utilizes various operator schema and plan representations . The frame problem is solved by using the STRIPS assumption. The major points to be presented in this context are: It is also a good idea to show an example of the kind of planning done by STRIPS (a nice combination of heuristic state space search and resolution theorem proving). Bratko's text presents a PROLOG implementation of STRIPS (and more). Forms a nice basis if your course (or students) is PROLOG literate.

Additionally, one or more advanced aspects of Planning algorithms can be presented. Several texts now have detailed discussions on partial-order planning algorithms, etc. (see below).

Planning Algorithms

Introduce planning as search . There are two approaches:

Case-based Planning

Given a new problem, a goal, and a description of an initial state.
Look into the library of cases to recall a similar problem, with similar initial and goal states.
Modify the retrieved solution for the new problem.

The key is to find good similarity metrics.

Reactive Approaches

Scheduling vs. Planning

Planning is deciding what to do.
Scheduling is deciding when to do it.

Planning in AI Texts

The chapter on Planning in Ginsberg's text starts by introducing the frame, qualification, and ramification problems in the context of reasoning about action. It gives a short overview of action description models. The chapter concludes with a description of a STRIPS-like planning algorithm.

Tanimoto's text concentrates on operator-based planning. First, it presents a simple linear planner (in Common Lisp) that uses iterative deepening depth first search. This is then used to motivate hierarchical planning and STRIPS-based operator schema. A planning algorithm that uses a propositional representation for facts and STRIPS-like operators is presented (in Common Lisp). Nonlinear planning is then introduced in the context of partial-order planning. A detailed algorithm and its Common Lisp implementation is also included. Exercises at the back are based upon the programs in the chapter.

By way of using the agent-oriented approach, Russell & Norvig 's text has acting (and thereby planning) as a running theme in several chapters. There are also 3 chapters devoted specifically to acting logically as well as one chapter on robotics . The first chapter deals with situation calculus-based planning, STRIPS representations, and presents a partial-order planning algorithm (which is based on SNLP). The blocksworld and SHAKEY world are described. The planning algorithm is further used as a basis for introducing hierarchical planning, conditional effects, and other issues in Practical planning . There is also some discussion of the algorithmic complexity of planning. The refined version on the planning algorithm presented is based on the UCPOP algorithm (of which SNLP is a forerunner). The third chapter is devoted to conditional planning (an algorithm based on CNLP is presented), replanning, and planning and acting.

While there isn't a specific chapter devoted to planning in Luger & Stubblefield , there is a section in one of the search chapters. It presents predicate-calculus-based planning (a PROLOG implementation is included in a later chapter), and STRIPS-based operator representations, and triangle tables.

The chapter in Rich & Knight covers situation calculus, STRIPS-based planning, and nonlinear planning (a TWEAK-based algorithm is presented).

Dean, Allen, & Aloimonos present a general discussion of various approaches to the planning problem. Partial-order planning, hierarchical planning, adaptive planning, and conditional planning are given detailed treatment (with Lisp code as well as complexity measures and analyses).

Below is a table showing a survey of six AI texts and their coverage of Planning. Pairs of numbers indicate the approximate number of pages of text, and an estimate of the number of lectures that will typically be required to cover all the material in the text. Each lecture is assumed to be 75 minutes long. A typical semester has about 13 weeks of lectures, each week having two 75 minute lectures, giving a total of 26 lectures.

------------------------------------------------------------------------------
              Dean,
              Allen &,               Russell &            Rich &  Luger &
              Aloimonos   Ginsberg   Norvig     Tanimoto  Knight  Stubblefield
------------------------------------------------------------------------------
Overall Text  500/40      400/24     850/52     760/42    580/40   700/40
------------------------------------------------------------------------------
Planning       50/4        20/2       80/6       55/5      38/2     12/1
------------------------------------------------------------------------------

References & Resources


Clicking below on names will take you to the individual's home page. Generally a good starting point for locating current information. Clicking below on titles of the publications will take you to homepages of the documents where other resources like code, instructional materials, and related software may be available.

Please write back to the author for any corrections/additions


Bratko : PROLOG Programming for Artificial Intelligence, Second Edition, Addison Wesley, 1990.

Dean, Allen, & Aloimonos : Artificial Intelligence -Theory and Practice, Benjamin Cummings Publishing Company, 1995.

Genesereth & Nilsson : Logical Foundations of Artificial Intelligence , Morgan Kaufmann Publishers, Los Altos, CA, 1987.

Georgeff : Planning, in Annual Reviews of Computer Science, Annual Reviews Inc., pages 359-400, 1987. (A nice survey)

Ginsberg : Essentials of Artificial Intelligence, Morgan Kaufmann Publishers, 1993.

Artificial Intelligence: Structures and Strategies for Complex problem Solving, Second Edition, Benjamin Cummings Publishing Company, 1993.

Rich & Knight : Artificial Intelligence, Second Edition, McGraw Hill, 1991.

Russell & Norvig : Artificial Intelligence: A Modern Approach, Prentice Hall, 1995.

Shapiro : The Encyclopedia of Artificial Intelligence, Second Edition, John Wiley & Sons, Inc., 1992.

Tanimoto : The Elements of Artificial Intelligence Using Common Lisp, Second Edition, Computer Science press, 1995.

Software: UCPOP : A partial-order planner developed by Daniel Weld, runs under Common Lisp (preferably with CLIM), available by anonymous FTP.

CMU Software Repository: This link points to planning-related software contained in the CMU AI Repository maintained by Mark Kantrowitz.


Last updated: June 5, 1995.
Deepak Kumar
Bryn Mawr College
dkumar@cc.brynmawr.edu