Planning has achieved significant progress in recent years. Among the various approaches to scale up plan synthesis, the use of macro-actions has been widely explored. As a first stage towards the development of a solution to learn on-line macro-actions, we propose an algorithm to identify useful macro-actions based on data mining techniques. The integration in the planning search of these learned macro-actions shows significant improvements over six classical planning benchmarks.
Other approaches presented an algorithm @cite_13 to decompose a domain in several subproblems to then solve them. After, the algorithm stores each generated partial plan in memory as a macro which allows to retrieve and use it as part of the solution for a different problem that contains it. Masataro and Fukunaga introduced a similar work in @cite_8 which automatically identifies subproblems, generate macros from subplans and integrate the subplans by solving the augmented problem.
@cite_13 @cite_8
2121366087 2401064609
This paper presents several new tractability results for planning based on macros. We describe an algorithm that optimally solves planning problems in a class that we call inverted tree reducible, and is provably tractable for several subclasses of this class. By using macros to store partial plans that recur frequently in the solution, the algorithm is polynomial in time and space even for exponentially long plans. We generalize the inverted tree reducible class in several ways and describe modifications of the algorithm to deal with these new classes. Theoretical results are validated in experiments. Large-scale classical planning problems such as factory assembly problems pose a significant challenge for domain-independent planners. We propose a macro-based planner which automatically identifies subproblems, generate macros from subplans and integrate the subplans by solving the whole augmented problem. We show experimentally that our approach can be used to solve large problem instances that are beyond the reach of current state-of-the-art satisficing planners.