Investigation into the use of evolutionary algorithms for fully automated planning
View/ Open
Date
2006Author
Westerberg, Carl Henrik
Metadata
Abstract
This thesis presents a new approach to the Arti cial Intelligence (AI) problem of fully
automated planning. Planning is the act of deliberation before acting that guides rational
behaviour and is a core area of AI. Many practical real-world problems can be
classed as planning problems, therefore practical and theoretical developments in AI
planning are well motivated. Unfortunately, planning for even toy domains is hard,
many different search algorithms have been proposed, and new approaches are actively
encouraged.
The approach taken in this thesis is to adopt ideas from Evolutionary Algorithms
(EAs) and apply the techniques to fully automated plan synthesis. EA methods have
enjoyed great success in many problem areas of AI. They are a new kind of search
technique that have their foundation in evolution. Previous attempts to apply EAs to
plan synthesis have promised encouraging results, but have been ad-hoc and piecemeal.
This thesis thoroughly investigates the approach of applying evolutionary search
to the fully automated planning problem. This is achieved by developing and modifying
a proof of concept planner called GENPLAN. Before EA-based systems can be
used, a thorough examination of various parameter settings must be explored. Once
this was completed, the performance of GENPLAN was evaluated using a selection of
benchmark domains and other competition style planners. The dif culties raised by
the benchmark domains and the extent to which they cause problems for the approach
are highlighted along with problems associated with EA search. Modi cations are proposed
and experimented with in an attempt to alleviate some of the identi ed problems.
EAs offer a exible framework for fully automated planning, but demonstrate a clear
weakness across a range of currently used benchmark domains for plan synthesis.
Collections
The following license files are associated with this item: