Theory and algorithms for plan merging

DOI10.1016/0004-3702(92)90016-QMaRDI QIDQ1199918zbMATH OpenOpenAlexWikidataFDO

Authors David E. Foulser, Ming Li, Qiang Yang

Publication date 17 January 1993

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(92)90016-q

zbMATH Keywords

approximation algorithmdynamic programmingplan merging

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Review text

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.

Recommendations

• Fast planning through planning graph analysis
• scientific article; zbMATH DE number 49438
• Approximate planning
• scientific article; zbMATH DE number 3570374
• FROM PLANNING TO SEARCHING FOR THE SHORTEST PLAN: AN OPTIMAL TRANSITION

Cites work

• scientific article; zbMATH DE number 4174365 (Why is no real title available?)
• scientific article; zbMATH DE number 4086981 (Why is no real title available?)
• scientific article; zbMATH DE number 3599517 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1448981 (Why is no real title available?)
• Planning for conjunctive goals

Cited in

(17)

• Improved heuristics and a genetic algorithm for finding short supersequences
• Approximate planning
• A resource logic for multi-agent plan merging
• A beam search for the shortest common supersequence problem guided by an approximate expected length calculation
• The multi-spreader crane scheduling problem: partitions and supersequences
• Backdoors to planning
• Minimum cost multi-product flow lines
• Hybridizations of metaheuristics with branch \& bound derivates
• scientific article; zbMATH DE number 4174365 (Why is no real title available?)
• The multiple sequence sets: Problem and heuristic algorithms
• scientific article; zbMATH DE number 1216125 (Why is no real title available?)
• On the approximation of shortest common supersequences and longest common subsequences
• Integrating planning and learning: the PRODIGY architecture
• Average-case analysis via incompressibility
• Merge-and-shrink: a compositional theory of transformations of factored transition systems
• Finding optimal plans for multiple teams of robots through a mediator: a logic-based approach
• On the approximation of longest common nonsupersequences and shortest common nonsubsequences

This page was built for publication: Theory and algorithms for plan merging

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199918)