Re-evaluating the Full Landmark Extraction Algorithm

Re-evaluating the Full Landmark Extraction Algorithm: A Performance Analysis of FULL

Tjoen, Noah (TU Delft Electrical Engineering, Mathematics and Computer Science)

Dumančić, S. (mentor)
Hanou, I.K. (mentor)
Cruz, Luis (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2024-02-01

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.

Landmarks
Planning

http://resolver.tudelft.nl/uuid:28d13e2d-c7ee-4fdf-a50b-3dfa842b79b6

Student theses

bachelor thesis

© 2024 Noah Tjoen