Theory and algorithms for plan merging (Q1199918)

The two-fold goal of the paper is to present a formalism and a computational theory for optimal and approximate plan merging. Using the strips operator definitions, the paper proposes a formalization of the conditions under which operators in a plan can be merged. A dynamic programming algorithm is applied to obtain the optimal solution by reducing the plan merging problem to the shortest common supersequence problem (met in operation research theory). To preserve the traditional AI planning context, the paper extends the dynamic programming method to handle partially ordered plans. Since for practical (large) problems the dynamic programming technique becomes intractable, the paper proposes four approximation algorithms to compute high quality plans at low cost. Worst- and average-case complexity analyses of the approximation algorithm outputs are given, and shown that all these algorithms have linear time complexity in the number of input plan operators. Promising experimental results are exposed for the investigated heuristic methods.