Theory and algorithms for plan merging (Q1199918)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Theory and algorithms for plan merging |
scientific article |
Statements
Theory and algorithms for plan merging (English)
0 references
17 January 1993
0 references
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.
0 references
plan merging
0 references
dynamic programming
0 references
approximation algorithm
0 references