{"id":{"repo_id":"birmingham","oai_identifier":"oai:etheses.bham.ac.uk:16294"},"canonical_url":"https://search.ndltd.org/etd/birmingham/oai:etheses.bham.ac.uk:16294","repository":{"repo_id":"birmingham","name":"University of Birmingham","base_url":"https://etheses.bham.ac.uk/cgi/oai2"},"display":{"title":"The Relevance Score: a landmark-like heuristic for automated planning","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.","abstract_html":"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<span class=\"etd-inline-math\"><sub>Ξ</sub></span> that counts the amount of relevance between a state and the goal, that is analagous to landmark counting heuristics h<span class=\"etd-inline-math\"><sub>LC</sub></span>. 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.","abstract_has_math":true,"creators":["Kim, Oliver Edward"],"institution":"University of Birmingham","degree_name":"d_ph","degree_level":"d_ph","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-07","date_published":"2025-07","updated_at":"2026-11-19T09:33:12Z","subjects":["QA75 Electronic computers. Computer science"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[{"key":"person:identifier.orcid","label":"ORCID","values":["0009000023248074"],"render_values":[{"text":"0009-0000-2324-8074","href":"https://orcid.org/0009-0000-2324-8074","code":true}]}]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null,"record_url":null,"record_label":null,"record_kind":null,"record_source":null,"download_url":"http://etheses.bham.ac.uk//id/eprint/16294/1/Kim2025PhD.pdf","download_label":"Download PDF","download_source":"dc:identifier.uri","access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://etheses.bham.ac.uk/cgi/oai2?verb=GetRecord&metadataPrefix=uketd_dc&identifier=oai%3Aetheses.bham.ac.uk%3A16294","prefix":"uketd_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.sponsor","label":"Sponsor","values":["other"]},{"key":"dc:creator","label":"Author","values":["Kim, Oliver Edward"]},{"key":"person:identifier.orcid","label":"ORCID","values":["0009000023248074"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-07-15"]},{"key":"dc:date.issued","label":"Date","values":["2025-07"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["College of Engineering & Physical Sciences","School of Computer Science"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Birmingham"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["http://etheses.bham.ac.uk//id/eprint/16294/"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["d_ph"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["d_ph"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["QA75 Electronic computers. Computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.dcterms_iso639_2","label":"Language (ISO 639-2)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://etheses.bham.ac.uk//id/eprint/16294/1/Kim2025PhD.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["text"]},{"key":"dcterms:accessrights","label":"Dcterms Accessrights","values":["public"]},{"key":"dc:title","label":"Title","values":["The Relevance Score: a landmark-like heuristic for automated planning"]}]}],"canonical_facts":{"dc:contributor.sponsor":["other"],"dc:creator":["Kim, Oliver Edward"],"dc:date":["2025-07-15"],"dc:date.issued":["2025-07"],"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 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."],"dc:format":["text"],"dc:identifier.uri":["http://etheses.bham.ac.uk//id/eprint/16294/1/Kim2025PhD.pdf"],"dc:language.dcterms_iso639_2":["eng"],"dc:publisher.department":["College of Engineering & Physical Sciences","School of Computer Science"],"dc:publisher.institution":["University of Birmingham"],"dc:relation.isreferencedby":["http://etheses.bham.ac.uk//id/eprint/16294/"],"dc:subject":["QA75 Electronic computers. Computer science"],"dcterms:accessrights":["public"],"dc:title":["The Relevance Score: a landmark-like heuristic for automated planning"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["d_ph"],"dc:type.qualificationname":["d_ph"],"person:identifier.orcid":["0009000023248074"]},"updated_at":"2026-11-19T09:33:12Z"}