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).

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

Planning
Macros

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)
Chrpa, Lukáš ; McCluskey, Thomas Leo ; Osborne, Hugh. / Reformulating planning problems : A theoretical point of view. Proceedings of the 25th International Florida Artificial Intelligence Research Society Conference, FLAIRS-25. 2012. pp. 14-19
@inproceedings{e0e8e9156fe54ba5ab347abb5b5aa0ee,
title = "Reformulating planning problems: A theoretical point of view",
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).",
author = "Luk{\'a}š Chrpa and McCluskey, {Thomas Leo} and Hugh Osborne",
year = "2012",
language = "English",
isbn = "9781577355588",
pages = "14--19",
booktitle = "Proceedings of the 25th International Florida Artificial Intelligence Research Society Conference, FLAIRS-25",

}

Chrpa, L, McCluskey, TL & 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, 25th International Florida Artificial Intelligence Research Society Conference, Marco Island, United States, 23/05/12.

Reformulating planning problems : A theoretical point of view. / Chrpa, Lukáš; McCluskey, Thomas Leo; Osborne, Hugh.

Proceedings of the 25th International Florida Artificial Intelligence Research Society Conference, FLAIRS-25. 2012. p. 14-19.

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

TY - GEN

T1 - Reformulating planning problems

T2 - A theoretical point of view

AU - Chrpa, Lukáš

AU - McCluskey, Thomas Leo

AU - Osborne, Hugh

PY - 2012

Y1 - 2012

N2 - 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).

AB - 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).

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

M3 - Conference contribution

SN - 9781577355588

SP - 14

EP - 19

BT - Proceedings of the 25th International Florida Artificial Intelligence Research Society Conference, FLAIRS-25

ER -

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