SINERGY: A linear planner based on genetic programming

Abstract. In this paper we describe SINERGY, which is a highly parallelizable, linear planning system that is based on the genetic programming paradigm. Rather than reasoning about the world it is planning for, SINERGY uses artificial selection, recombination and fitness measure to generate linear plans that solve conjunctive goals. We ran SINERGY on several domains (e.g., the briefcase problem and a few variants of the robot navigation problem), and the experimental results show that our planner is capable of handling problem instances that are one to two orders of magnitude larger than the ones solved by UCPOP. In order to facilitate the search reduction and to enhance the expressive power of SINERGY, we also propose two major extensions to our planning system: a formalism for using hierarchical planning operators, and a framework for planning in dynamic environments.