THEORY AND ALGORITHMS FOR PLAN MERGING

被引：77

作者：

FOULSER, DE

LI, M

YANG, Q

机构：

[1] UNIV WATERLOO,DEPT COMP SCI,WATERLOO N2L 3G1,ONTARIO,CANADA

[2] SILICON GRAPH COMP SYST,MT VIEW,CA 94039

来源：

ARTIFICIAL INTELLIGENCE | 1992年 / 57卷 / 2-3期

基金：

加拿大自然科学与工程研究理事会; 美国国家卫生研究院;

关键词：

D O I：

10.1016/0004-3702(92)90016-Q

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Merging operators in a plan can yield significant savings in the cost to execute a plan. This paper provides a formal theory for plan merging and presents both optimal and efficient heuristic algorithms for finding minimum cost merged plans. The optimal plan merging algorithm applies a dynamic programming method to handle multiple linear plans and is extended to partially ordered plans in a novel way. Furthermore, with worst-case and average-case complexity analysis and empirical tests, we demonstrate that efficient and well-behaved approximation algorithms are applicable for optimizing plans with large sizes.

引用

页码：143 / 181

页数：39

共 19 条

[1] PLANNING FOR CONJUNCTIVE GOALS [J].

CHAPMAN, D .

ARTIFICIAL INTELLIGENCE, 1987, 32 (03) :333-377

[2]

DERFEE EH, 1987, P IJCAI 87 MILAN, P875

[3]

Garey MR., 1979, COMPUTERS INTRACTABI

[4]

HAYES CC, 1989, P IJCAI 89 DETROIT

[5] A VALIDATION-STRUCTURE-BASED THEORY OF PLAN MODIFICATION AND REUSE [J].

KAMBHAMPATI, S ;

HENDLER, JA .

ARTIFICIAL INTELLIGENCE, 1992, 55 (2-3) :193-258

[6]

KAMBHAMPATI S, 1990, P AAAI 90 BOSTON

[7]

KARINTHI R, IN PRESS J APPL ARTI

[8]

KNOBLOCK CA, 1991, P AAAI 91 ANAHEIM

[9]

LI M, 1988, 3RD P IEEE C STRUCT, P80

[10]

NAU DS, 1990, 1990 P DARPA WORKSH, P160

← 1 2 →