On exploiting structures of classical planning problems

Generalizing entanglements

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Citations (Scopus)

Abstract

Much progress has been made in the research and development of automated planning algorithms in recent years. Though incremental improvements in algorithm design are still desirable, complementary approaches such as problem reformulation are important in tackling the high computational complexity of planning. While machine learning and adaptive techniques have been usefully applied to automated planning, these advances are often tied to a particular planner or class of planners that are coded to exploit that learned knowledge. A promising research direction is in exploiting knowledge engineering techniques such as reformulating the planning domain and/or the planning problem to make the problem easier to solve for general, state-of-the-art planners. Learning (outer) entanglements is one such technique, where relations between planning operators and initial or goal atoms are learned, and used to reformulate a domain by removing unneeded operator instances. Here we generalize this approach significantly to cover relations between atoms and pairs of operators themselves, and develop a technique for producing inner entanglements. We present methods for detecting inner entanglements and for using them to do problem reformulation. We provide a theoretical treatment of the area, and an empirical evaluation of the methods using standard planning benchmarks and state-of-the-art planners.

Original languageEnglish
Title of host publicationECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration
PublisherIOS Press
Pages240-245
Number of pages6
Volume242
ISBN (Print)9781614990970
DOIs
Publication statusPublished - 2012

Publication series

NameFrontiers in Artificial Intelligence and Applications
Volume242
ISSN (Print)09226389

Fingerprint

Planning
Atoms
Knowledge engineering
Learning systems
Computational complexity

Cite this

Chrpa, L., & McCluskey, T. L. (2012). On exploiting structures of classical planning problems: Generalizing entanglements. In ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration (Vol. 242, pp. 240-245). (Frontiers in Artificial Intelligence and Applications; Vol. 242). IOS Press. https://doi.org/10.3233/978-1-61499-098-7-240
Chrpa, Lukas ; McCluskey, Thomas Leo. / On exploiting structures of classical planning problems : Generalizing entanglements. ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration. Vol. 242 IOS Press, 2012. pp. 240-245 (Frontiers in Artificial Intelligence and Applications).
@inproceedings{60a9a11b51fd41c6a299e2ac38fa4647,
title = "On exploiting structures of classical planning problems: Generalizing entanglements",
abstract = "Much progress has been made in the research and development of automated planning algorithms in recent years. Though incremental improvements in algorithm design are still desirable, complementary approaches such as problem reformulation are important in tackling the high computational complexity of planning. While machine learning and adaptive techniques have been usefully applied to automated planning, these advances are often tied to a particular planner or class of planners that are coded to exploit that learned knowledge. A promising research direction is in exploiting knowledge engineering techniques such as reformulating the planning domain and/or the planning problem to make the problem easier to solve for general, state-of-the-art planners. Learning (outer) entanglements is one such technique, where relations between planning operators and initial or goal atoms are learned, and used to reformulate a domain by removing unneeded operator instances. Here we generalize this approach significantly to cover relations between atoms and pairs of operators themselves, and develop a technique for producing inner entanglements. We present methods for detecting inner entanglements and for using them to do problem reformulation. We provide a theoretical treatment of the area, and an empirical evaluation of the methods using standard planning benchmarks and state-of-the-art planners.",
author = "Lukas Chrpa and McCluskey, {Thomas Leo}",
year = "2012",
doi = "10.3233/978-1-61499-098-7-240",
language = "English",
isbn = "9781614990970",
volume = "242",
series = "Frontiers in Artificial Intelligence and Applications",
publisher = "IOS Press",
pages = "240--245",
booktitle = "ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration",
address = "Netherlands",

}

Chrpa, L & McCluskey, TL 2012, On exploiting structures of classical planning problems: Generalizing entanglements. in ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration. vol. 242, Frontiers in Artificial Intelligence and Applications, vol. 242, IOS Press, pp. 240-245. https://doi.org/10.3233/978-1-61499-098-7-240

On exploiting structures of classical planning problems : Generalizing entanglements. / Chrpa, Lukas; McCluskey, Thomas Leo.

ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration. Vol. 242 IOS Press, 2012. p. 240-245 (Frontiers in Artificial Intelligence and Applications; Vol. 242).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - On exploiting structures of classical planning problems

T2 - Generalizing entanglements

AU - Chrpa, Lukas

AU - McCluskey, Thomas Leo

PY - 2012

Y1 - 2012

N2 - Much progress has been made in the research and development of automated planning algorithms in recent years. Though incremental improvements in algorithm design are still desirable, complementary approaches such as problem reformulation are important in tackling the high computational complexity of planning. While machine learning and adaptive techniques have been usefully applied to automated planning, these advances are often tied to a particular planner or class of planners that are coded to exploit that learned knowledge. A promising research direction is in exploiting knowledge engineering techniques such as reformulating the planning domain and/or the planning problem to make the problem easier to solve for general, state-of-the-art planners. Learning (outer) entanglements is one such technique, where relations between planning operators and initial or goal atoms are learned, and used to reformulate a domain by removing unneeded operator instances. Here we generalize this approach significantly to cover relations between atoms and pairs of operators themselves, and develop a technique for producing inner entanglements. We present methods for detecting inner entanglements and for using them to do problem reformulation. We provide a theoretical treatment of the area, and an empirical evaluation of the methods using standard planning benchmarks and state-of-the-art planners.

AB - Much progress has been made in the research and development of automated planning algorithms in recent years. Though incremental improvements in algorithm design are still desirable, complementary approaches such as problem reformulation are important in tackling the high computational complexity of planning. While machine learning and adaptive techniques have been usefully applied to automated planning, these advances are often tied to a particular planner or class of planners that are coded to exploit that learned knowledge. A promising research direction is in exploiting knowledge engineering techniques such as reformulating the planning domain and/or the planning problem to make the problem easier to solve for general, state-of-the-art planners. Learning (outer) entanglements is one such technique, where relations between planning operators and initial or goal atoms are learned, and used to reformulate a domain by removing unneeded operator instances. Here we generalize this approach significantly to cover relations between atoms and pairs of operators themselves, and develop a technique for producing inner entanglements. We present methods for detecting inner entanglements and for using them to do problem reformulation. We provide a theoretical treatment of the area, and an empirical evaluation of the methods using standard planning benchmarks and state-of-the-art planners.

UR - http://www.scopus.com/inward/record.url?scp=84878810138&partnerID=8YFLogxK

U2 - 10.3233/978-1-61499-098-7-240

DO - 10.3233/978-1-61499-098-7-240

M3 - Conference contribution

SN - 9781614990970

VL - 242

T3 - Frontiers in Artificial Intelligence and Applications

SP - 240

EP - 245

BT - ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration

PB - IOS Press

ER -

Chrpa L, McCluskey TL. On exploiting structures of classical planning problems: Generalizing entanglements. In ECAI 2012 - 20th European Conference on Artificial Intelligence, 27-31 August 2012, Montpellier, France - Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstration. Vol. 242. IOS Press. 2012. p. 240-245. (Frontiers in Artificial Intelligence and Applications). https://doi.org/10.3233/978-1-61499-098-7-240