Affiliations:
University of Brescia, Brescia, Italy
Correspondence:
[*]
Corresponding author: Ivan Serina, University of Brescia, via Branze 38, I-25123 Brescia, Italy. Tel.: +39 030 3715521; Fax: +39 030 3715450; E-mail: [email protected].
Abstract: Domain-Independent planning is known to be a very hard search problem, and in the last three decades many search techniques and heuristics have been developed with the aim of efficiently solving such a task. These techniques and heuristics include the usage of landmarks, which are logical expressions consisting of facts that become true or actions that are executed in any solution plan. We propose the usage of landmarks for speeding up the search of the planner LPG, a system implementing a planning approach based on the use of local search in the space of the action graphs of the planning problem. The results of an experimental evaluation of the proposed techniques show that these techniques can improve the performance of LPG, obtaining a planning system that performs similarly to the state-of-the-art planner LAMA. Moreover, we introduce and experimentally evaluate the concept of “quasi-landmarks”; these are facts that are likely to become true in every solution plan, or facts that must become true in a subset of the solution plans.
Keywords: AI planning, local search, heuristic search, landmarks techniques
