Back to search

University of Birmingham

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

Abstract

dc:description.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 hLC. 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.

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kim, Oliver Edward
ORCID person:identifier.orcid

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kim, Oliver Edward. The Relevance Score: a landmark-like heuristic for automated planning. d_ph thesis, University of Birmingham, 2025.