Reformulating planning problems: A theoretical point of view

Lukáš Chrpa, Thomas Leo McCluskey, Hugh Osborne

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

7 Citations (Scopus)

Abstract

Automated planning is a well studied research topic thanks to its wide range of real-world applications. Despite significant progress in this area many planning problems still remain hard and challenging. Some techniques such as learning macro-operators improve the planning process by reformulating the (original) planning problem. While many encouraging practical results have been derived from such reformulation methods, little attention has been paid to the theoretical properties of reformulation such as soundness, completeness, and algorithmic complexity. In this paper we build up a theoretical framework describing reformulation schemes such as action elimination or creating macroactions. Using this framework, we show that finding entanglements (relationships useful for action elimination) is as hard as planning itself. Moreover, we design a tractable algorithm for checking under what conditions it is safe to reformulate a problem by removing primitive operators (assembled to a macro-operator).

Original languageEnglish
Title of host publicationProceedings of the 25th International Florida Artificial Intelligence Research Society Conference, FLAIRS-25
Pages14-19
Number of pages6
Publication statusPublished - 2012
Event25th International Florida Artificial Intelligence Research Society Conference - Marco Island, United States
Duration: 23 May 201225 May 2012
Conference number: 25

Conference

Conference25th International Florida Artificial Intelligence Research Society Conference
Abbreviated titleFLAIRS-25
CountryUnited States
CityMarco Island
Period23/05/1225/05/12

Fingerprint Dive into the research topics of 'Reformulating planning problems: A theoretical point of view'. Together they form a unique fingerprint.

  • Cite this

    Chrpa, L., McCluskey, T. L., & Osborne, H. (2012). Reformulating planning problems: A theoretical point of view. In Proceedings of the 25th International Florida Artificial Intelligence Research Society Conference, FLAIRS-25 (pp. 14-19)