On the completeness of replacing primitive actions with macro-actions and its generalization to planning operators and macro-operators

Abstract

Automated planning, which deals with the problem of generating sequences of actions, is an emerging research topic due to its potentially wide range of real-world application domains. As well as developing and improving planning engines, the acquisition of domain-specific knowledge is a promising way to improve the planning process. Domain-specific knowledge can be encoded into the modelling language that a range of planning engines can accept. This makes encoding domain-specific knowledge planner-independent, and entails reformulating the domain models and/or problem specifications. While many encouraging practical results have been derived from such reformulation methods (e.g. learning macro-actions), little attention has been paid to the theoretical properties such as completeness (keeping solvability of reformulated problems). In this paper, we focus on a special case – removing primitive actions replaced by macro-actions. We provide a theoretical study and come up with conditions under which it is safe to remove primitive actions, so completeness of reformulation is preserved. We extend this study also for planning operators (actions are instances of operators).

Keywords

AI planning problem reformulation macro-actions action elimination

Get full access to this article

View all access options for this article.

References

[1]

M.A.

Alhossaini and

J.C.

Beck, Instance-specific remodelling of planning domains by adding macros and removing operators, in: Proceedings of SARA, 2013, pp. 16–24.

[2]

Bäckström and

Jonsson, Algorithms and limits for compact plan representations, Journal of Artificial Intelligence Research (JAIR) 44 (2012), 141–177.

[3]

Blum and

Furst, Fast planning through planning graph analysis, Artificial Intelligence 90(1,2) (1997), 281–300.

[4]

Bonet and

Geffner, Planning as heuristic search, Artificial Intelligence 129 (2001), 5–33.

[5]

Botea,

Enzenberger,

Müller and

Schaeffer, Macro-FF: Improving AI planning with automatically learned macro-operators, Journal of Artificial Intelligence Research (JAIR) 24 (2005), 581–621.

[6]

Bylander, The computational complexity of propositional STRIPS planning, Artificial Intelligence 69 (1994), 165–204.

[7]

Chrpa, Generation of macro-operators via investigation of action dependencies in plans, Knowledge Engineering Review 25(3) (2010), 281–297.

[8]

Chrpa, Theoretical aspects of using learning techniques for problem reformulation in classical planning, in: Proceedings of PlanSIG, 2011, pp. 23–30.

[9]

Chrpa and

Barták, Reformulating planning problems by eliminating unpromising actions, in: Proceedings of SARA, 2009, pp. 50–57.

10.

[10]

Chrpa,

T.L.

McCluskey and

Osborne, Reformulating planning problems: A theoretical point of view, in: Proceedings of FLAIRS, 2012, pp. 14–19.

11.

[11]

Chrpa,

Vallati and

T.L.

McCluskey, Determining linearity of optimal plans by operator schema analysis, in: Proceedings of SARA, 2013, pp. 34–41.

12.

[12]

Coles and

Smith, Marvin: A heuristic search planner with online macro-action learning, Journal of Artificial Intelligence Research (JAIR) 28 (2007), 119–156.

13.

[13]

Dawson and

Siklóssy, The role of preprocessing in problem solving systems, in: Proceedings of IJCAI, 1977, pp. 465–471.

14.

[14]

Dvořák,

Toropila and

Barták, Towards AI planning efficiency: Finite-domain state variable reformulation, in: Proceedings of SARA, 2013, pp. 50–56.

15.

[15]

Fikes and

N.J.

Nilsson, STRIPS: a new approach to the application of theorem proving to problem solving, Artificial Intelligence 2(3,4) (1971), 189–208.

16.

[16]

Ghallab,

C.K.

Isi,

Penberthy,

D.E.

Smith,

Sun and

Weld, PDDL – The planning domain definition language, Technical report, 1998.

17.

[17]

Ghallab,

Nau and

Traverso, Automated Planning: Theory and Practice, Morgan Kaufmann, 2004.

18.

[18]

Haslum, Reducing accidental complexity in planning problems, in: Proceedings of IJCAI, 2007, pp. 1898–1903.

19.

[19]

Haslum,

Helmert and

Jonsson, Safe, strong, and tractable relevance analysis for planning, in: Proceedings of ICAPS, 2013, pp. 317–321.

20.

[20]

Haslum and

Jonsson, Planning with reduced operator sets, in: Proceedings of AIPS, 2000, pp. 150–158.

21.

[21]

Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence 143(2) (2003), 219–262.

22.

[22]

Helmert, The fast downward planning system, Journal of Artificial Intelligence Research (JAIR) 26 (2006), 191–246.

23.

[23]

Helmert and

Domshlak, Landmarks, critical paths and abstractions: What’s the difference anyway? in: Proceedings of ICAPS, 2009, pp. 162–169.

24.

[24]

Hoffmann, Analyzing search topology without running any search: On the connection between causal graphs and

h^{+}

, Journal of Artificial Intelligence Research (JAIR) 41 (2011), 155–229.

25.

[25]

Hoffmann and

Nebel, The FF planning system: Fast plan generation through heuristic search, Journal of Artificial Intelligence Research (JAIR) 14 (2001), 253–302.

26.

[26]

Jonsson, The role of macros in tractable planning, Journal of Artificial Intelligence Research (JAIR) 36 (2009), 471–511.

27.

[27]

Korf, Macro-operators: A weak method for learning, Artificial Intelligence 26(1) (1985), 35–77.

28.

[28]

T.L.

McCluskey and

J.M.

Porteous, Engineering and compiling planning domain models to promote validity and efficiency, Artificial Intelligence 95(1) (1997), 1–65.

29.

[29]

Mehlhorn, Data Structures and Algorithms 2: Graph Algorithms and NP-Completeness, Springer, 1984.

30.

[30]

M.A.H.

Newton,

Levine,

Fox and

Long, Learning macro-actions for arbitrary planners and domains, in: Proceedings of ICAPS, 2007, pp. 256–263.

31.

[31]

Richter and

Westphal, The LAMA planner: Guiding cost-based anytime planning with landmarks, Journal of Artificial Intelligence Research (JAIR) 39 (2010), 127–177.

32.

[32]

Scholz, Reducing planning problems by path reduction, PhD thesis, Darmstadt University of Technology, 2004.

33.

[33]

Slaney and

Thiébaux, Blocks world revisited, Artificial Intelligence 125(1,2) (2001), 119–153.

34.

[34]

Wickler, Using planning domain features to facilitate knowledge engineering, in: Workshop of Knowledge Engineering for Planning and Scheduling (KEPS), 2011.