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):
This can then lead into a presentation/discussion of situation calculus . Also, a good point to introduce various planning problems:
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).
Each node in the graph denoted a state of the world. Arcs in the graph
correspond to the execution of a specific action. The planning problem
is to find a path from the initial state to the goal state. There
are two algorithms:
Each node in the graph represents partial plans. Arcs
denote plan refinement operations. One can search for a
plan with a totally-ordered sequence of actions (total order
planning), or a plan with a partially ordered set of actions
(partial order planning (POP) or least commitment
planning).
Partial Order Planning (POP): A partial order plan has
three components:
{eat-breakfast, take-shower, wake-up, go-to-work}.
{wake-up before eat-breakfast,
wake-up ---awake---> eat-breakfast
is a link from the action, wake-up to the action eat-breakfast.
When the action wake-up is added to the plan, the above causal
link is recorded, along with the ordering
constraint
[wake-up before eat-breatfast], because wake-up's effect
that the individual is awake is a precondition of eat-breakfast.
Causal links help detect inconsistencies whenever
a partial plan is refined.
Present a complete partial order
planning algorithm.
The key is to find good similarity metrics.
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.
Please write back to the author for any corrections/additions
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.
Planning Algorithms
Introduce planning as search . There are two approaches:
Both the algorithms are sound (if a plan is returned, will
it work?) and complete (if a plan exists, does the algorithm
guarantees that it will find it?). In most situations regression
is a better strategy.
wake-up before take-shower,
wake-up before go-to-work,
take-shower before go-to-work} 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.
Reactive Approaches
Planners think , executors do .
Classical planning is done off-line. The generated plan is then
fed to the on-line execution module.
Reaction rules encode sense-act cycles.
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.
------------------------------------------------------------------------------
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.
Bratko : PROLOG Programming for Artificial Intelligence,
Second Edition, Addison Wesley, 1990.
Last updated: June 5, 1995.
Deepak Kumar
Bryn Mawr College
dkumar@cc.brynmawr.edu