# 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 approaches
• Operator-based approaches
• Time-based approaches
• Case-based approaches
• Constraint-based approaches
• Distributed Planning
• Reactive approaches

## 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):

Given the following:
• \alpha designating an initial state
• \Gamma designating a set of actions
• \rho designating a goal
• \Omega is a database of sentences about the initial state
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:

• Frame Problem
After you drive your 4-door car from point A to point B
what is its color?
how many doors does it have?
...etc.
• Qualification Problem
If you turn the ignition key of your car the engine will start...
unless the battery is dead...
or it is out of gas...
or there is a potato blocking the tailpipe...
...etc.
• Ramification Problem
If you drive your car from point A to point B, then as a result
your car is now at B...
so is its engine...
its tires...
...etc.
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:
• Design of the operator schema
Add-delete lists, procedural vs declarative representations (NONLIN vs NOAH), etc.
• Design of plan representations
Linear plans, non-linear plans, hierarchical (abstract) plans, partial-order plans, conditional plans, etc.
• Planning Algorithms
Planning as search, world-space vs. plan-space, partial-order planning, total-order planning, progression, goal-regression, etc.
The computational complexity of planning.
• Plan Critiquing
Plan reformulation, repair, total-ordering, etc.
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.

## Planning Algorithms

Introduce planning as search . There are two approaches:
• Searching a World Space:

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:

• Progression: An algorithm that searches for the goal state by searching through the states generated by actions that can be performed in the given state, starting from the initial state.
• Regression: An algorithm that searches backward from the goal state by finding actions whose effects satisfy one or more of the posted goals, and posting the chosen action's preconditions as goals ( goal regression).
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.

• Searching a Plan Space:

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:

• A set of actions: For example,

{eat-breakfast, take-shower, wake-up, go-to-work}.

• A set of ordering constraints: For example,

{wake-up before eat-breakfast,
wake-up before take-shower,
wake-up before go-to-work,
take-shower before go-to-work}

• A set of causal links: For example,

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.

## 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

• Planning & Execution
Planners think , executors do .
• Predictability (thinking) vs. Reactivity (doing)
• on-line vs. off-line planning
Classical planning is done off-line. The generated plan is then fed to the on-line execution module.
• Closed vs. open-loops
Reaction rules encode sense-act cycles.
• Triangle Tables
• Universal Plans
• Situated Automata
• Action Nets
• Reactive Action Packages
• Task Control Architectures
• Subsumption Architectures

## 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