p.1 Planning is the reasoning side of acting. It is an abstract, explicit deliberation
process that chooses and organizes actions by anticipating their expected outcomes. This deliberation aims at achieving
as best as possible some prestated objectives. Automated planning is an area of Artificial Intelligence (AI) that
studies this deliberation process computationally...
A purposeful activity requires deliberation when it addresses new situations or complex tasks and
objectives or when it relies on less familiar actions. Planning is also needed when the adaptation of actions is constrained,
for example, by a critical environment involving high risk or high cost... Since planning is a very complicated, time-consuming,
and costly process, we resort to planning only when it is strictly needed or when the trade-off of its cost versus its benefit
compels us to plan.
p.2 Planning is an important component of rational behavior. If one purpose of AI is to
grasp the computational aspects of intelligence, then certainly planning, as the reasoning side of acting, is a key element
in such a purpose. The challenge here is to study planning not as an independent abstract process but as a fully integrated
component of deliberative behavior.
p.3 Perception planning is concerned with plans involving sensing actions for gathering information.
It arises in tasks such as modeling environments or objects... or more generally identifying the current state of the environment...
Perception planning address questions such as which information is needed and when it is needed, where to look for
it, which sensors are most adequate for this particular task, and how to use them. It requires models of available
sensors and their capabilities and constraints. It relies on decision theory for problems of which and when information is
needed, on mathematical programming and constraint satisfaction for the viewpoint selection and the sensor modalities.
p.5 A conceptual model is a simple theoretical device for describing the main elements of a problem.
It can depart significantly from the computational concerns and algorithmic approaches for solving that problem. However,
it can be very useful for explaining basic concepts, for clarifying restrictive assumptions, for analyzing requirements on
representations and trade-offs, and for proving semantic properties.
Since planning is concerned with choosing and organizing actions for changing the state of
a system, a conceptual model for planning requires a general model for a dynamic system.
p.171 In general, removing a constraint c from [finite set of constraints] C... corresponds
to relaxing the CSP [Constraint Satisfaction Problem] unless that constraint c is redundant.
p.199-200 A node-selection heuristic is any way of ranking a set of nodes in order of their
relative desirability. We will model this heuristic as a function h that can be used to compute a numeric
evaluation h(u) for each candidate node u... Node-selection heuristics are used for resolving
nondeterministic choices... a node-selection heuristic is usually not foolproof, in the sense that the node
recommended by the heuristic is not always guaranteed to be the best choice: this node may not always lead to the
best solution or even to any solution at all. However, we would like the heuristic to be as informative as
possible, i.e., to be as close as possible to an oracle that knows the right choice... We also want
h to be easily computable, so that there will be a clear benefit in computing it and using it for making
choices... There is usually a trade-off between how informative h is and how easy it is to compute.
Node-selection heuristics are often based on the following relaxation principle: in
order to assess how desirable a node u is, one considers a simpler problem that is obtained from the original one
by making simplifying assumptions and by relaxing constraints. One estimates how desirable u is by using u
to solve the simpler relaxed problem and using that solution as an estimate of the solution one would get if one used u
to solve the original problem. The closer the relaxed problem is to the original one, the more informative the estimate
will be. On the other hand, the more simplified the relaxed problem is, the easier it will be to compute
the heuristic. Unfortunately, most of the time it is not easy to find the best trade-off between relaxation and informativeness
of the heuristic: to do that requires a knowledge of the structure of the problem.
p.217 In the Abstract-search procedure in figure III.1, the purpose of the Prune function is to
detect unpromising nodes and prune them from the search space. The efficiency of a planning procedure can often be
improved dramatically if a good way can be found to do this - for example, in some cases it may enable a procedure to solve
problems in polynomial [a shorter period of] time that might otherwise take exponential [a longer period of] time.
Deciding whether a node can be pruned often involves a collection of highly domain-specific
tests to detect situations in which we can be confident that the solutions that lie below a node are less desirable than the
solutions that lie below nodes elsewhere in the search space.
