The actual paper in ps form: dean1996.ps. Here is the homepage of T. Dean.
An algorithmic planning system has three parts:
exogenous events: events outside control of the planner.
state variables: used to describe the state of a system.
state transition function: takes the state and an action and
returns the resulting state.
The planner can assume that the plan executor can observe the
environment it is in.
If the state transitions involve some randomness, then there are state transition and output conditional probability distributions. This is computationally expensive in theory, but in practice it in not so bad: not all state variables are important for all transitions, and some state variables are independent. (p5)
If a plan is dependent on observations at a current state, then that plan is conditional, and work in a closed loop.. If it is dependent on time, then the plan is time variant, else it is stationary. (p7) Any plan that igores the results of past actions in open loop.
Plans describe state histories. In conditional plans there is a probability distribution over them. Each history gets a real value. You can calculate the expected value of a plan given all of its histories, their probabilities and values, and the cost of getting from one state to another. ?? (p8)
refinement: taking an existing plan and adding detail.
repair: modifying an existing plan for better performance
The paper defines two operators over state-variable assignments: they look like circles around a + and -, respectively. In this outline I will use + and - to refer to them.
y - v means the set of assignments in y that are not also in v.
y + v returns the union of consistent assignments.
Actions are defined in terms of assignments. thus state transitions
are defined as:
f(s,a) = s (if s and the precondition of a are inconsistent, else)
post(a) + (s - post(a))
a state s satisfies a goal if the state's assignments are a superset
of the goal's assignments. You can make partial plans that do a subset
of the work, and you can have constraints that apply to that partial
plan. You can work forward through the plan (progression) or backwards
from the goal (regression). (p17) State different heuristics choose a
path based on the difference between the result state and the goal.
means-ends analysis
If the preconditions of a good operator are not met, then you can make
those preconditions a subgoal (means ends analysis). (p18)
One problem with this is that premature committment to order of steps can lead to extensive backtracking.
plan space refinement
Satisfy one variable requirement at a time. (p19) A potential problem
is that in satisfying one you may undo progress already made. This can
be helped by protecting conditions already satisfied. (p20)
task reduction
Break large tasks into subtasks. This helps because you might know
that subtask x is unattainable, and thus not waste time working on the
details of subtask y. Also breaking the long task into a series of
independent shorter tasks reduces the complexity of the search. (p21)
Sometimes you can gloss over details of a plan, make a simple plan
test and debug it.
constraint satisfaction in scheduling
A scheduling solution can be described as a set of states.(p26) It is
often true that order of variables considered (for example start with
the variables with the fewest values) makes a big difference in
efficiency. One way to solve these problems is to start with an
inadequate assignment and repair.
Lin and Kernighan's algorithm uses a local repair method. It works like this: start with a configuration like abcde. Then, for each four-tuple, like abcd, see if it is faster to go acbd. This method actually gets to within 10% of optimality for many practical problems. (p28)
One problem with local repair methods is that they can get to local optima based perhaps on maximizing one of the performance variables. Such solutions are often bad. One way to combat this is with simulated annealing, which is to take a random repair. Doing this might get the algorithm out of a rut.
In case based planning, the planner saves previously made plans and their explanations so that later it can use parts of them when it encounters similar problems. (p29) By analyzing past experience the planner can learn new search control rules.
To evaluate plans stochastic in stochastic domains, you take a random sample of possible plans. The average of many of these samples gives a fairly accurate estimate of the plan quality. (p31)