PhD thesis,
Programacion Genetica de Heuristicas para Planificacion
Facultad de Informatica de la Universidad Politecnica de Madrid, Spain, (July 1999)
Abstract
The aim of this thesis is to use and extend the
machine learning genetic programming (GP) paradigm to
learn control knowledge for domain independent
planning. GP will be used as a standalone technique and
as part of a multi-strategy system.
Planning is the problem of finding a sequence of steps
to transform an initial state in a final state. Finding
a correct plan is NP-hard. A solution proposed by
Artificial Intelligence is to augment a domain
independent planner with control knowledge, to improve
its efficiency. Machine learning techniques are used
for that purpose. However, although a lot has been
achieved, the domain independent planning problem has
not been solved completely, therefore there is still
room for research.
The reason for using GP to learn planning control
knowledge is twofold. First, it is intended for
exploring the control knowledge space in a less biased
way than other techniques. Besides, learning search
control knowledge with GP will consider the planning
system, the domain theory, planning search and
efficiency measures in a global manner, all at the same
time. Second, GP flexibility will be used to add useful
biases and characteristics to another learning method
that lacks them (that is, a multi-strategy GP based
system). In the present work, Prodigy will be used as
the base planner and Hamlet will be used as the
learning system to which useful characteristics will be
added through GP. In other words, GP will be used to
solve some of Hamlet limitations by adding new
biases/characteristics to Hamlet.
In addition to the main goal, this thesis will design
and experiment with methods to add background knowledge
to a GP system, without modifying its basic algorithm.
The first method seeds the initial population with
individuals obtained by another method (Hamlet).
Actually, this is the multi-strategy system discussed
in the later paragraph. The second method uses a new
genetic operator (instance based crossover) that is
able to use instances/examples to bias its search, like
other machine learning techniques.
To test the validity of the methods proposed, extensive
empirical and statistical validation will be carried
out.
