A Quantitative Theory for Plan Merging

David E. Foulser; Ming Li; Qiang Yang

A Quantitative Theory for Plan Merging

David E. Foulser, Ming Li, Qiang Yang

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

Abstract

Merging operators in a plan can yield significant savings in the cost to execute a plan. Past research in planning has concentrated on handling harmful interactions among plans, but the understanding of positive ones has remained at a qualitative, heuristic level. This paper provides a quantitative study for plan optimization and presents both optimal and approximate algorithms for finding minimum-cost merged plans. With worst and average case complexity analysis and empirical tests, we demonstrate that efficient and well-behaved approximation algorithms are applicable for optimizing general plans with large sizes.

Original language	English
Title of host publication	Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991
Publisher	AAAI Press
Pages	673-678
Number of pages	6
ISBN (Electronic)	0262510596, 9780262510592
Publication status	Published - 1991
Externally published	Yes
Event	9th National Conference on Artificial Intelligence, AAAI 1991 - Anaheim, United States Duration: 14 Jul 1991 → 19 Jul 1991

Publication series

Name	Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991
Volume	2

Conference

Conference	9th National Conference on Artificial Intelligence, AAAI 1991
Country/Territory	United States
City	Anaheim
Period	14/07/91 → 19/07/91

Bibliographical note

Publisher Copyright:
© 1991, AAAI (www.aaai.org). All rights reserved.

Access to Document

https://hdl.handle.net/1783.1/41893

Cite this

@inproceedings{d843e13ffa6649ce93eb4f2a47a31d31,

title = "A Quantitative Theory for Plan Merging",

abstract = "Merging operators in a plan can yield significant savings in the cost to execute a plan. Past research in planning has concentrated on handling harmful interactions among plans, but the understanding of positive ones has remained at a qualitative, heuristic level. This paper provides a quantitative study for plan optimization and presents both optimal and approximate algorithms for finding minimum-cost merged plans. With worst and average case complexity analysis and empirical tests, we demonstrate that efficient and well-behaved approximation algorithms are applicable for optimizing general plans with large sizes.",

author = "Foulser, \{David E.\} and Ming Li and Qiang Yang",

note = "Publisher Copyright: {\textcopyright} 1991, AAAI (www.aaai.org). All rights reserved.; 9th National Conference on Artificial Intelligence, AAAI 1991 ; Conference date: 14-07-1991 Through 19-07-1991",

year = "1991",

language = "English",

series = "Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991",

publisher = "AAAI Press",

pages = "673--678",

booktitle = "Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991",

}

Foulser, DE, Li, M & Yang, Q 1991, A Quantitative Theory for Plan Merging. in Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991. Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991, vol. 2, AAAI Press, pp. 673-678, 9th National Conference on Artificial Intelligence, AAAI 1991, Anaheim, United States, 14/07/91. <https://hdl.handle.net/1783.1/41893>

A Quantitative Theory for Plan Merging. / Foulser, David E.; Li, Ming; Yang, Qiang.
Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991. AAAI Press, 1991. p. 673-678 (Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991; Vol. 2).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - A Quantitative Theory for Plan Merging

AU - Foulser, David E.

AU - Li, Ming

AU - Yang, Qiang

PY - 1991

Y1 - 1991

N2 - Merging operators in a plan can yield significant savings in the cost to execute a plan. Past research in planning has concentrated on handling harmful interactions among plans, but the understanding of positive ones has remained at a qualitative, heuristic level. This paper provides a quantitative study for plan optimization and presents both optimal and approximate algorithms for finding minimum-cost merged plans. With worst and average case complexity analysis and empirical tests, we demonstrate that efficient and well-behaved approximation algorithms are applicable for optimizing general plans with large sizes.

AB - Merging operators in a plan can yield significant savings in the cost to execute a plan. Past research in planning has concentrated on handling harmful interactions among plans, but the understanding of positive ones has remained at a qualitative, heuristic level. This paper provides a quantitative study for plan optimization and presents both optimal and approximate algorithms for finding minimum-cost merged plans. With worst and average case complexity analysis and empirical tests, we demonstrate that efficient and well-behaved approximation algorithms are applicable for optimizing general plans with large sizes.

UR - https://www.scopus.com/pages/publications/30244492113

M3 - Conference Paper published in a book

AN - SCOPUS:30244492113

T3 - Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991

SP - 673

EP - 678

BT - Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991

PB - AAAI Press

T2 - 9th National Conference on Artificial Intelligence, AAAI 1991

Y2 - 14 July 1991 through 19 July 1991

ER -

A Quantitative Theory for Plan Merging

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this