Section 1 : Planning problems and algorithms

Commentary

Section Goals

• To introduce planning problems and their representation.
• To discuss planning approaches, such as planning with state-space search, partial order planning, and planning graphs.
• To discuss the key issues of the above approaches, such as the heuristics and algorithms.

Section Notes

• Parts of this section may be skipped by those who have studied planning. However, even for those students, further study of the in-depth issues in this section is encouraged to pave the way for the future sections and units.

Learning Objectives

Learning Objective 1

• Outline and exemplify the representations of planning problems, including goals, actions, and states.
• Explain forward and backward state-space searching, and how heuristics are involved in them.
• Explain the principles of partial-order planning.
• Exemplify partial-order planning.
• Discuss planning graphs, and the graph-plan algorithm.
• Explain the following concepts or terms:
  • Problem decomposition
  • Action schema
  • Add list and delete list
  • STRIPS or PDDL language
  • Progression planning
  • Repression planning
  • Least commitment strategy
  • Ordering constraints
  • Planning graph

Objective Readings

Required readings:

Reading topics:

Automated Planning (see Chapter 10 of AIMA3ed).

Objective Questions

• What kind of roles does first-order logic play in the planning approaches introduced in this section?
• How are conflicts solved in partial-order planning?
• What are the limitations of the planning graph method?

Objective Activities

• Complete Exercise 10.3 of AIMA3ed.
• Complete Exercise 10.7 of AIMA3ed.