The Relevance Score: a landmark-like heuristic for automated planning

Kim, Oliver Edward ORCID: 0009-0000-2324-8074 (2025). The Relevance Score: a landmark-like heuristic for automated planning. University of Birmingham. Ph.D.

Preview

Kim2025PhD.pdf
Text
Available under License All rights reserved.
Download (1MB) | Preview

Abstract

Landmarks are facts or actions that appear in all valid solutions of a planning problem. They have been used successfully to calculate heuristics that guide the search for a plan. The potential uses for landmarks are limited by their definition relying on the existence of at least one valid plan. We investigate an extension to this concept by defining a novel relevance score Ξ(l) that quantifies how often a fact or action will appear in partial plans. We describe a method to compute this relevance score that makes no reference to the initial state of a problem, ensuring that it is applicable even if no plans exist.

We define a heuristic h\(_Ξ\) that counts the amount of relevance between a state and the goal, that is analagous to landmark counting heuristics h\(_{LC}\). We experimentally compare the performance of our approach to that of a state of the art landmark-based heuristic planning approach, using benchmark planning problems. While the original landmark-based heuristic leads to better performance on problems with well-defined landmarks, our approach substantially improves performance on problems that lack non-trivial landmarks.

Diagnosis can be described as finding explanations for observations that are not supported by an agent’s model of the world. This can be treated as a planning problem, where the world model must be fixed by assuming facts, and explained by a sequence of actions that connects the new world model to the observations (ie a plan). Previous attempts at this have relied on providing the system with candidates for assumption. We show that because the relevance score is calculable in planning problems that do not permit a plan, it can also be used to identify potential candidates. This is achieved by defining an assumability score τ(α) that uses the relevance score to assess fixes that are linked to the goal by backtracking actions.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):