Fast Planning through Greedy Action Graphs

Domain-independentplanning is a notoriously hard search problem. Several systematic search techniques have been proposed in the context of various formalisms. However, despite their theoretical completeness, in practice these algorithms are incompletebecause for many problemsthe search space is too large to be (evenpartially) explored. In this paper we propose a newsearch method in the context of Blumand Furst’s planning graph approach, whichis based on local search. Local search techniques are incomplete, but in practice they can efficiently solve problemsthat are unsolvablefor current systematic search methods. Weintroduce three heuristics to guide the local search (Walkplan, Tabuplan and T-Walkplan), and we propose two methods for combininglocal andsystematic search. Our techniques are implementedin a system called GPG, which can be used for both plan-generation and plan-adaptation tasks. Experimentalresults show that GPG can efficiently solve problemsthat are very hard for current planners based on planning graphs.

Authors

• Alfonso Gerevini University of Brescia
• Ivan Serina Paolo Toninelli
• Univeritá di Brescia

Keywords

No keywords are indexed for this paper.