The Effect of Decomposition Rule Modeling on the Efficiency of Hierarchical Planners

Abstract

Hierarchical planning is a widely used approach in automated planning that breaks down complex tasks into manageable subtasks, facilitating more efficient problem-solving. The task decomposition is modelled via decomposition rules that resemble rewriting rules of context-free grammars. Normal forms for rewriting rules, namely Chomsky Normal Form and Greibach Normal Form, have been proposed in the context of formal grammars and also applied to hierarchical planning models, specifically for hierarchical plan verification. This paper examines whether the format of decomposition rules also influences the efficiency of hierarchical planners.