Levine, John

Westerberg, Carl Henrik

2015-11-26T12:26:54Z

2015-11-26T12:26:54Z

2006

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.

http://hdl.handle.net/1842/11824

en

The University of Edinburgh

CC0 1.0 Universal

http://creativecommons.org/publicdomain/zero/1.0/

Artifcial Intelligence

Investigation into the use of evolutionary algorithms for fully automated planning

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy