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

Article type: Research Article

Authors: Chrpa, Lukáš^{; *} | McCluskey, Thomas Leo | Osborne, Hugh

Affiliations: PARK Research Group, School of Computing and Engineering, University of Huddersfield, Huddersfield, UK. E-mails: l.chrpa@hud.ac.uk, t.l.mccluskey@hud.ac.uk, h.r.osborne@hud.ac.uk

Correspondence: [*] Corresponding author. E-mail: l.chrpa@hud.ac.uk.

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

DOI: 10.3233/AIC-150679

Journal: AI Communications, vol. 29, no. 1, pp. 163-183, 2016