Automatic Selection of Macro-Events for Heuristic-Search Temporal Planning

Abstract

One of the major techniques to tackle temporal planning problems is heuristic search augmented with a symbolic representation of time in the states. Augmenting the problem with composite actions (macro-actions) is a simple and powerful approach to create "shortcuts" in the search space, at the cost of augmenting the branching factor of the problem and thus the expansion time of a heuristic search planner. Hence, it is of paramount importance to select the right macro-actions and minimize the number of such actions to optimize the planner performance. In this paper, we first discuss a simple, yet powerful, model similar to macro-actions for the case of temporal planning, and we call these macro-events. Then, we present a novel ranking function to extract and select a suitable set of macro-events from a dataset of valid plans. In our ranking approach, we consider an estimation of the hypothetical search space for a blind search including a candidate set of macro-events under four different exploitation schemata. Finally, we experimentally demonstrate that the proposed approach yields a substantial performance improvement for a state-of-the-art temporal planner.