SSP Group Meeting
Wednesday, June 13th, 11am-12pm
Division of Informatics, 80 South Bridge, Room F13


Optimising Plans using Genetic Programming

Henrik Westerberg

Finding the shortest plan for a given planning problem is extremely hard. The fastest domain independent and domain dependent planners, at the recent AIPS 2000 competition, often fail to find optimal plans. We present a domain independent approach for plan optimisation based on Genetic Programming. The Genetic Planning algorithm is seeded with correct plans created by a heuristic policy set. The plans are very unlikely to be optimal but are created quickly. The sub-optimal plans are then evolved using a generational algorithm, with mutation and crossover, towards the optimal plan. The population could equally be seeded by anything producing linear plans, such as TALplanner or FF. We present initial results from Blocks World and Briefcase Domain and found that GP method almost always improved sub-optimal plans, often drastically.