Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T17:57:44.601Z Has data issue: false hasContentIssue false

Generation of macro-operators via investigation of action dependencies in plans

Published online by Cambridge University Press:  01 September 2010

Lukáš Chrpa*
Affiliation:
Faculty of Mathematics and Physics, Department of Theoretical Computer Science and Mathematical Logic, Charles University in Prague, Malostranské náměsti 25, 118 00, Prague 1, Czech Republic e-mail: chrpa@kti.mff.cuni.cz
Rights & Permissions [Opens in a new window]

Abstract

There are many approaches for solving planning problems. Many of these approaches are based on ‘brute force’ search methods and they usually do not care about structures of plans previously computed in particular planning domains. By analyzing these structures, we can obtain useful knowledge that can help us find solutions to more complex planning problems. The method described in this paper is designed for gathering macro-operators by analyzing training plans. This sort of analysis is based on the investigation of action dependencies in training plans. Knowledge gained by our method can be passed directly to planning algorithms to improve their efficiency.

Information

Type
Articles
Copyright
Copyright © Cambridge University Press 2010
Figure 0

Figure 1Four different situations for moving the intermediate actions (gray-filled) before or behind one of the boundary actions (black-filled)

Figure 1

Figure 2Algorithm for detecting pairs of actions that can be assembled

Figure 2

Figure 3Algorithm for creating the matrix of candidates for assemblage

Figure 3

Figure 4Example of PICKUP-STACK macro-operator

Figure 4

Figure 5Algorithm for generation of macro-operators

Figure 5

Table 1Suggestion of our method—the best results for the particular domains

Figure 6

Table 2Comparison of running times and plans lengths (we assume that macro-actions are unfolded into primitive actions) for SGPLAN (left-hand side) and SATPLAN (right-hand side)

Figure 7

Table 3Comparison of running times and plans lengths (we assume that macro-actions are unfolded into primitive actions) for LAMA (left-hand side) and FDP (right-hand side)