Relevance Score: A Landmark-Like Heuristic for Planning
This work addresses planning efficiency for AI systems in domains with ambiguous or incomplete landmarks, representing an incremental advancement over existing heuristic methods.
The paper tackles the problem of planning in domains lacking well-defined landmarks by introducing a 'relevance score' heuristic that identifies facts or actions appearing in most but not all plans, and it shows substantial performance improvements on such problems compared to a state-of-the-art landmark-based approach.
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. We investigate an extension to this concept by defining a novel "relevance score" that helps identify facts or actions that appear in most but not all plans to achieve any given goal. We describe an approach to compute this relevance score and use it as a heuristic in the search for a plan. We experimentally compare the performance of our approach with 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.