Landmarks in Planning

Using landmarks as Intermediary Golas or as a Pseudo-Heuristic

Bachelor thesis (2024)

Authors

B.J. van Maris Electrical Engineering, Mathematics and Computer Science

Contributors

I.K. Hanou Algorithmics - EEMCS (mentor)
S. Dumančić Algorithmics - EEMCS (mentor)
Luis Cruz Software Engineering - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2024 Bart van Maris
More Info
expand_more

Published Date

01-02-2024

Language

English

Reuse Rights

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Algorithmic planners occasionally waste effort and thus computing time trying to solve certain tasks, as they often lack the human ability to recognize essential paths. These essential paths, termed landmarks, are vital for optimizing planning processes. This study revisits landmark-based planning methods introduced by Richter, Helmert, and Westphal in their 2008 paper, adapting and implementing them within a different framework, SymbolicPlanners, using the Julia programming language. The primary research question explores the performance of using landmarks as intermediary goals and pseudo-heuristics in the SymbolicPlanner framework. Sub-questions delve into the effectiveness of specific planning strategies, such as A∗ Planner with GoalCount and HAdd heuristics, as well as planners utilizing landmarks. Evaluation over diverse domains reveals that LMLocal  and LMLocalSmart outperform the basic GoalCount
heuristic and are on par with the HAdd heuristic. LMCount, despite solving fewer instances, exhibits speed improvements over GoalCount in the instances that they both solve. Discussion highlights limitations, such as the non-exhaustive interference check in LMLocalSmart and limiting factors in the SymbolicPlanner framework.