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 language | English |
---|---|
Title of host publication | Proceedings of the 25th International Florida Artificial Intelligence Research Society Conference, FLAIRS-25 |
Pages | 14-19 |
Number of pages | 6 |
Publication status | Published - 2012 |
Event | 25th International Florida Artificial Intelligence Research Society Conference - Marco Island, United States Duration: 23 May 2012 → 25 May 2012 Conference number: 25 |
Conference
Conference | 25th International Florida Artificial Intelligence Research Society Conference |
---|---|
Abbreviated title | FLAIRS-25 |
Country/Territory | United States |
City | Marco Island |
Period | 23/05/12 → 25/05/12 |