Relevance Score: A Landmark-Like Heuristic for Planning

The use of heuristics to guide search and limit the search space is an important component of modern planning systems. There is a well-established literature of methods that use heuristics to improve the computational efficiency of computing plans. The existence of a sound heuristic that can be computed quickly makes path planning in Euclidean space much more efficient than the more abstract search spaces used for task planning. One of the successful heuristics used for task planning is a count of the "landmarks" that remain to be reached from a given state Zhu and Givan (2003); Hoffmann et al. (2004); Richter and Westphal (2010); Keyder et al. (2010), where a landmark is a fact, action, or a logical formula over facts and/or actions, that is present in all valid solutions (i.e., sequence of actions) for a planning problem. This leads to a preference for actions (in plans) that are a landmark or achieve one.