I shan't cover this in detail, so this section just gives a brief summary. It sets one reading, again on Newell's work. However, there are numerous footnotes in case you ever want to follow these topics further.
It's worth knowing that the word ``planning'' usually refers to the following type of problem. You start with the world in a given (known) state. You are able to perform various elementary actions, each of which changes the world in a known way. Your task is to generate some sequence of actions or plan which will get the world into some goal state. It's generally assumed that the start state, the goal state, and the effect of each action can be described in logic.
One example is chemical synthesis. Your goal is a product or set of
products. Your start state is a set of reagents. Your actions are
chemical reactions. A one-person game, or the missionary-and-cannibals
problem
is another example.
The simplest way to tackle planning is by search. However, even with heuristics, that's very inefficient: they don't provide enough information about your progress towards a goal. An alternative method is problem reduction. You break your original goal into a set of simpler subgoals. If a subgoal can be achieved by one of the elementary actions, then you've solved that part of the problem. Otherwise, you break it up into yet simpler subgoals ...and so on until you've solved them all. In this formulation, it's necessary to have some knowledge of how likely each elementary action is to take you towards a goal.
The first planning program is generally taken to be the General Problem
Solver, usually known just as GPS. It was a descendant of the
Logic Theorist, and also designed in part by Newell, both as a cognitive
model and as an exercise in problem-solving techniques. For an account
of GPS, please read GPS, a program that simulates human thought,
in [Computers and Thought 1963]. Concentrate on Newell's
motivations (note the conclusion on p 293); if you have problems
understanding the program description, try the footnote references.
Another planner, written just after GPS and using essentially the same
techniques, was Strips. After these came many more, with names like
Abstrips, Noah, Nonlin, and so on.
It gradually came to be realised that such programs did not perform
terribly well when faced with the real world of robotics, partly because
of imprecision in sensing and moving, but not least because even when
everything is known exactly, the methods are still horribly inefficient.
Later work in planning and problem-solving has moved away from these
a-priori logic-based methods, and has gone in other directions. One of
these, case-based planning, entails storing details of existing
solutions in memory, and trying to adapt them.
Some people have been even more radical. The classical planning researchers all assumed that their programs would, via some kind of perceptual system, build up a symbolic model of the world in memory. From this world model, together with symbolic representations of its goals, it would derive a plan which would then by executed by a motor system. Some researchers have repudiated entirely the classical assumption that the program should build faithful symbolic descriptions of its environment. I'll set some readings on this at the end of these notes.