Introduction

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

Operator-based Planning

• 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.

• 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

• 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 in AI Texts

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

Please write back to the author for any corrections/additions