Re-evaluating the Full Landmark Extraction Algorithm
A Performance Analysis of FULL
N.J. Tjoen (TU Delft - Electrical Engineering, Mathematics and Computer Science)
S. Dumancic – Mentor (TU Delft - Algorithmics)
I.K. Hanou – Mentor (TU Delft - Algorithmics)
Luis Cruz – Graduation committee member (TU Delft - Software Engineering)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Landmarks are propositions or actions that must be true at some point in every valid solution plan [16]. Using landmarks, planners can develop solutions more efficiently. Different algorithms exist to extract landmarks from a planning problem. The one used in this study is FULL [13], a landmark extraction algorithm by Marzal et al. from 2011.
In this research, the performance of the FULL algorithm is analysed by comparing the total number of landmarks found to two other landmark extraction algorithms, namely forward propagation by Zhu and Givan [22] and backward propagation by Porteous et al. [16].
The original FULL algorithm is slightly modified, by removing orderings and disjunctive landmark extraction. FULL is implemented using Julia and was run on five different domains from the International Planning Competitions.
All of these domains are logical and 15 problems were randomly selected from them.
FULL managed to extract more landmarks in two out of the five domains, Grid and Logistics, compared to the two aforementioned algorithms.
In the three other domains, FULL matched the number of landmarks found by the best out of the two. The two domains where FULL performed well, were both transportation domains and this is where FULL's performance excels.
Runtime was not an issue when extracting landmarks in four of the five domains. Freecell consistently exceeded the timeout put in place, likely due to a bug.
Furthermore, a higher number of landmarks is also a desired outcome due to its use in planners, either as heuristics or intermediary goals.