Fast Planning Through Greedy Action Graphs

Abstract

Domain-independent planning is a notoriously hard search problem. Several systematic search techniques have been proposed in the context of various for-malisms. However, despite their theoretical complete-ness, in practice these algorithms are incomplete be-cause for many problems the search space is too large to be (even partially) explored. In this paper we propose a new search method in the context of Blum and Furst’s planning graph ap-proach, which is based on local search. Local search techniques are incomplete, but in practice they can efficiently solve problems that are unsolvable for cur-rent systematic search methods. We introduce three heuristics to guide the local search (Walkplan, Tabu-plan and T-Walkplan), and we propose two methods for combining local and systematic search. Our techniques are implemented in a system called GPG, which can be used for both plan-generation and plan-adaptation tasks. Experimental results show that GPG can efficiently solve problems that are very hard for current planners based on planning graphs.