Planning --- the early days

The point of this section is to show what planning is, and how it (some of it, anyway) proceeded from search and GPS. Apart from GPS, none of the planning methods described are intended as psychological models --- they're all exercises in getting machines to plan, exercises which uncovered more and more difficulties in what originally seemed a simple problem. This lack of psychological relevance isn't a criticism, of course; AI is concerned not only with existing natural intelligences, but also with the structure of all possible intelligences, existing or not. But although none of these post-GPS planners are intended as cognitive models, some of them have undoubtedly taken inspiration from human problem solving. And they have enabled us to clarify and formalise problems (such as interacting subgoals) which all planners must solve, whether human or computer.

I want to introduce these ideas, for each of which I'll give some references.

1. What is planning? Some terminology.

2. The blocks world.

3. Planning as state-space search.

4. Means-end analysis.

5. Planning with abstraction hierarchies.

6. The linearity assumption and interaction between goals.

Here are the references. When reading, concentrate on the concepts, rather than on technicalities. Remember that in Finals, you will have at most an hour to talk about planning. You should be able, by comparing and contrasting different planners, to write an essay on the problems of planning and the way in which people have tried to solve them. It will be helpful to have a little example ready for each, to illustrate the way in which each planner might work with a problem; but you won't be expected (I hope) to go into tremendous detail. (Having said this, if you think that abstraction spaces, for instance, is a really beautiful concept, don't feel inhibited from taking it as far as you want.)

Planning and terminology.

Essentially, a plan is a set of actions which, when executed, will (barring failures) enable some agent to achieve its goal or goals, given the current state of the world. Most simply, a goal is (as in state-space search and GPS) just a new state of the world. But there may be other types of goal. The planner needs to know how the agent's actions will affect the world; and it may have to deal with other changes or events.

Start by finding Readings in Planning (now in the Psychology library) edited by Allen, Hendler and Tate. Go to the first article --- Planning --- and read enough of sections 1, 2, 2.1 and 3, 3.1, 4, and 4.1 to acquaint yourself with the terms action, state, event, execution, planning, plan structure and subplans, atomic actions or plans, partial plan, goal, agent, and multi-agent planning. These are fairly well-defined terms, and papers on planning will often use them without further ado. Note the different types of goal that are described in section 3.

This and the next paper A Review of AI Planning Techniques form a general introduction to planning, and you may find some parts of both useful throughout this set of readings (though other parts will be too mathematical). Note the family tree on page 27.

The blocks world.

Many early planners planned for an agent living in the blocks world. Make sure you know what is meant by this --- what objects are found in a typical blocks world, and what actions can you perform on them? Almost any book on AI mentions the blocks world; AI and Natural Man is as good as any. What are the differences between the blocks world and real life?

Planning as state-space search.

The simplest way to plan is to search all possible states of the world until you find the one you want. This is state-space search, which I'll assume you've done in the Conventional AI: Search tutorial. Consider a typical problem, Missionaries and Cannibals for example. What might a solution plan look like? What are the defects of planning this way?

Means-end analysis.

After search came GPS. Again, I'll assume you've covered this in the Conventional AI: GPS tutorial. What were the problems with it?

Planning with abstraction hierarchies.

One of the problems with GPS was that it couldn't defer details. If it set itself a subgoal to satisfy a particular operator, it had to plan how to fulfil all the preconditions of that operator before it could go any further. So it might keep going down and down, building ever more finicky subplans, before ever getting past that operator.

To avoid this problem, the idea of planning at various levels of abstraction was introduced, the first planner that used it being ABSTRIPS. Three references, in increasing order of detail: Winston page 154; AI and Natural Man pages 357--360 (end of ¶ 1); Planning in a Hierarchy of Abstraction Spaces in Readings in Planning, particularly pages 98--100.

The linearity assumption and interaction between goals.

The methods above all worked on the linearity (or additivity) assumption: that subgoals could be tackled independently and the subplans for each pasted together to form a total plan. But that won't always work: sometimes interactions between goals make it impossible to consider each in isolation.

The first program to attempt interacting goals was Hacker. It, essentially, planned as though the goals were independent, and then tried to correct faults in the resulting plans. It could not deal with all interacting goal problems this way: for example, Sussman's problem (illustrated in the references below).

For this section, I shall concentrate on Hacker, and then refer you to a goal-interaction problem that it couldn't solve, and ask you to accept it as the motivation for further work.

Start with the Introduction to Chapter 3 of Readings in Planning, pages 108--109. Then, for Hacker, read pages 286--297 of AI and Natural Man; if you want more, read The Virtuous Nature of Bugs in Readings in Planning. Finally, AI and Natural Man pages 360--366.