ola-abstract.shtml
Ph D abstract - Patrik Haslum
Admissible Heuristics for Automated Planning
Akademisk avhandling som för avläggande av teknologie
doktorsexamen vid
Linköpings universitet kommer att offentligt försvaras i
Visionen, hus
B, Linköpings universitet, 15 mars 2006, kl 13.15.
Abstract
The problem of domain-independent automated planning has been a topic of
research in Artificial Intelligence since the very beginnings of the
field.
Due to the desire not to rely on vast quantities of problem specific
knowledge, the most widely adopted approach to automated planning is
search.
The topic of this thesis is the development of methods for achieving
effective search control for domain-independent optimal planning through
the construction of admissible heuristics. The particular planning
problem
considered is the so called ``classical'' AI planning problem, which
makes
several restricting assumptions.
Optimality with respect to two measures of plan cost are considered:
in planning with additive cost, the cost of a plan is the sum of the
costs
of the actions that make up the plan, which are assumed independent,
while
in planning with time, the cost of a plan is the total execution time --
makespan -- of the plan. The makespan optimization objective can not, in
general, be formulated as a sum of independent action costs and
therefore
necessitates a problem model slightly different from the classical one.
A further small extension to the classical model is made with the
introduction of two forms of capacitated resources.
Heuristics are developed mainly for regression planning, but based on
principles general enough that heuristics for other planning search
spaces can be derived on the same basis.
The thesis describes a collection of methods, including the $h^m$,
additive
$h^m$ and improved pattern database heuristics, and the relaxed search
and
boosting techniques for improving heuristics through limited search, and
presents two extended experimental analyses of the developed methods,
one
comparing heuristics for planning with additive cost and the other
concerning
the relaxed search technique in the context of planning with time,
aimed at
discovering the characteristics of problem domains that determine the
relative effectiveness of the compared methods. Results indicate that
some
plausible such characteristics have been found, but are not entirely
conclusive.
|
