Solving the abstract planning problem using genetic algorithms

The paper presents a new approach based on genetic algorithms to the abstract planning problem, which is the first stage of the web service composition problem. An abstract plan is defined as an equivalence class of sequences of service types that satisfy a user query. Intuitively, two sequences are equivalent if they are composed of the same service types, but not necessarily occurring in the same order. The objective of our genetic algorithm (GA) is to return representatives of abstract plans without generating all the equivalent sequences. The paper presents experimental results compared with the results obtained from SMT-solver, which show that GA finds solutions for very large sets of service types in a reasonable time.