# Relevance Score: A Landmark-Like Heuristic for Planning

Oliver Kim1,2, Mohan Sridharan1,3
1 University of Birmingham, 2 University of Melbourne, 3 University of
Edinburgh

###### 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. 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.

##  1 Introduction

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. However, the task of computing all landmarks for a
planning problem is expensive; it is known to be PSPACE-complete Porteous et
al., (2001). Systems that compute landmarks thus identify a subset of key
landmarks, often using a relaxed version of the planning problem Keyder et
al., (2010), but the cost of computing landmarks is still significant.

A common limitation of most approaches that compute and use landmarks to guide
planning is that such landmarks must exist for the planning problems under
consideration. In many complex domains where there are multiple possible
routes to the goal, the only simple (single fact) landmarks that exist may be
trivial, i.e., those present in the goal specification or already true in the
initial state. While complex logical formulae may serve as landmarks, it can
be challenging to compute and use such logical formulae in a heuristic. The
approach described in this paper avoids this limitation by computing a
relevance score, which also considers the value of achieving facts (or
actions) that appear in many but not all valid plans. The underlying
hypothesis is that this additional information will lead to a more efficient
search for a valid solution to the given planning problem. As the baseline
planner, we use LAMA Richter and Westphal, (2010), which uses a combination of
landmark counting and the Fast Forward system Hoffmann and Nebel, (2001), with
the shortest plan found using weighted $A^{*}$ search under delete relaxation
conditions. It has been considered state of the art at planning competitions
for over a decade.

Figure 1: Illustration of the distinction between landmarks and relevant facts
p1 is a landmark because all partial plans that achieve the goal g must use
one of actions A1, A2, or A3, for which it is a precondition. p2 is not a
landmark because the goal could be achieved by A1, but it is highly relevant
because there is a $\frac{2}{3}$ chance of it being present in any partial
plan to achieve the goal.

The key contribution of this paper is to define and describe an approach for
computing a novel ”Relevance Score” heuristic ($h_{\Xi})$. This heuristic that
generalizes the concept of a landmark, which must be true at some point in
_all_ plans (under delete relaxation), to relevance, which evaluates facts or
actions according to how often they appear in plans (also under the delete
relaxation). Figure 1 illustrates the information we aim to capture with the
relevance score, and how it relates to landmarks. For ease of comparison with
the baseline LAMA planner, we limit our focus to facts as the landmark-like
entities. We then demonstrate through experimental evaluation involving
individual and combinations of benchmark planning problems that while the
original landmark-based heuristic leads to better performance on problems with
well-defined landmarks, our approach based on relevance scores substantially
improves performance on problems that lack non-trivial landmarks.

The remainder of this paper is organized as follows. Section 2 motivates our
proposed approach by discussing related work. Section 3 describes our problem
formulation and the proposed heuristic, while Section 4 describes the
calculation of this heuristic and its use to compute plans. Experimental
results described in Section 5.2 form the basis of the discussion of next
steps in Section 6.

##  2 Related work

Landmarks as a heuristic were initially described in Porteous et al., (2001)
and developed further in Hoffmann et al., (2004), as an extension to goal
ordering. They sought to find and order facts that had to be achieved in any
valid plan. This partial ordering of landmarks was treated as a sequence of
sub-goals to break a planning problem into sub-problems. Landmarks are usually
found using a relaxed planning graph (RPG) Hoffmann and Nebel, (2001), which
performs reachability analysis under delete relaxation conditions and requires
multiple steps to check that landmarks and their order are sound.

Many researchers have used landmarks to guide heuristic search planners Zhu
and Givan, (2003); Helmert, (2006); Richter et al., (2008). Others extended
this idea to find cost-optimal plans and began to use actions and
propositional formulas of facts as potential landmarks Keyder and Geffner,
(2008); Karpas and Domshlak, (2009); Richter and Westphal, (2010). Most use a
landmark counting heuristic, which assumes that each landmark that has yet to
be reached will cost one action. The estimate of distance to the the goal is
then given by the number of landmarks remaining to be found. There has been
some work on heuristics that preserve action costs, and consider actions that
can simultaneously achieve multiple landmarks Helmert and Domshlak, (2009);
Karpas and Domshlak, (2009). These and other papers explored more efficient
ways to identify many landmarks Keyder et al., (2010).

Researchers have explored different ways to compute and use landmarks. One
example is the translation of Relaxed Planning Graphs (RPGs) into AND/OR
graphs for which landmarks are unique maximal solutions computed using
Bellman-Ford methods Keyder et al., (2010). Applying delete relaxation to a
planning problem involves a loss of information, and can lead to actions or
action sequences that are impossible in the original problem. One approach
compiles away negative preconditions and effects, while preserving the
information they contained Haslum, (2009). By considering pairs ($m=2$),
triplets ($m=3$) or larger conjunctions of facts, the requirement to achieve
them simultaneously is preserved, resulting in a larger problem $\Pi^{m}$ free
from negative preconditions or effects. Others have built on this idea Keyder
et al., (2010). Since the size of the problem grows exponentially with $m$,
and introducing new, compound facts into the domain poses other challenges,
methods that use landmarks often prefer to just accept the limitations of
delete relaxation.

There continues to be work on computing and using landmarks. This includes
computing landmarks using ungrounded or ”lifted” planning domain definitions,
which allows some of the complexity of disjunctive landmarks to be represented
in the range of possible groundings Wichlacz et al., (2022). It also includes
the use of ordering information to calculate a new heuristic, which improves
its accuracy Clemens and Keller, (2021). Landmark-based heuristics are also
used in many related fields such as goal recognition Pereira et al., (2017);
Vered et al., (2018) and contingent planning Maliah et al., (2018); Segovia-
Aguas et al., (2022).

##  3 Definitions and Background Knowledge

We begin by defining the notation and some concepts used in this paper,
followed by the definition of our proposed relevance score heuristic.

###  3.1 Classical planning problem

A classical planning problem is defined by the tuple Ghallab et al., (2004):

$\Pi=\langle F,A,I,G\rangle$

where $F$ is a finite set of ground predicates representing facts; $A$ is a
finite set of actions; $I\subseteq F$ is the set of facts true in the initial
state; and $G\subseteq F$ is the set of facts representing goals. A _state_
$\sigma$ is a set of facts that are true at a particular time. An action $a\in
A$ has preconditions $pre(a)$ and effects $ef\\!f(a)$, each of which is
subdivided into sets of positive and negative facts:
$pre^{+}(a),pre^{-}(a),ef\\!f^{+}(a),ef\\!f^{-}(a)$. If an action’s positive
(negative) preconditions are true (false) in a particular state, it is
applicable in that state:

$Applicable(a,\sigma)\iff\sigma\models pre^{+}(a)\cap\neg pre^{-}(a)$

When an action is applied to a state in which it is applicable, the resultant
state is given by:

$Result(a,\sigma)\models\sigma\cup ef\\!f^{+}(a)\setminus ef\\!f^{-}(a)$

A sequence of actions $[a_{1}...a_{n}]$ is applicable in a state if each
action is applicable in the state resulting from the previous sequence of
actions, i.e.,
$Applicable(a_{1},\sigma),Applicable(a_{2},Result(a_{1},\sigma))$ etc. The
result of applying a sequence of actions to a state in which it is applicable
is the result of applying each action in that sequence, i.e.,
$Result([a_{1}...a_{n}],\sigma)=Result(a_{n},Result(a_{n-1},...Result(a_{1},\sigma))$.

A plan$\pi^{\Pi}$ for problem $\Pi=\langle F,A,I,G\rangle$ is a sequence of
actions $[a_{1}...a_{n}]$ that is applicable in $I$ and results in a state
where all facts in $G$ are true, i.e., $Result(\pi^{\Pi},I)\models G$.

###  3.2 Landmarks

A landmark is defined as a propositional formula of facts that is true at some
point in the execution of all valid plans. Due to the difficulty in
identifying disjunctive landmarks, many planning systems including LAMA
Richter and Westphal, (2010) only make use of fact landmarks. These are single
facts that must be true at some point in the execution of all valid plans.
Each fact in the goal and the initial state is a landmark, but is of little
use to a planner; these are referred to as trivial landmarks. Facts that must
be true at some point other than at the start or end of a plan execution are
considered non-trivial.

The relevance score that we propose in this paper applicable to both fact-
based and action-based landmark-like heuristics. However, to facilitate use
and comparison with LAMA, we limit our discussion to facts in this paper.

###  3.3 Simplifying approximations

A classical planning problem can be simplified for computing heuristics that
will assist in solving the original problem Bonet and Geffner, (2001);
Hoffmann and Nebel, (2001). One such simplification is delete relaxation,
which removes all negative preconditions and negative effects from all
actions. Another simplification is often used for planning domains with
multiple goals. Specifically, the domain is modified by adding action
$achieveGoal$ that has a single positive effect
$ef\\!f^{+}(achieveGoal)=\\{success\\}$, and the problem’s goals as
preconditions $pre^{+}(achieveGoal)=G$. Then, $success$ is used as the goal
for computing heuristics, allowing all goals to be considered jointly.

###  3.4 Backtracking tree

A tree is a standard representation of a domain (and changes in the domain)
for a planning problem. A tree consists of nodes $\underline{n}$ and edges
$e$. A node $\underline{n}=\langle l,E\rangle$ consists of a label
$label(\underline{n})=l\in F\cup A$, which references a fact $f$ or action
$a$, and a set of edges $E$. An edge
$e=(\underline{n}\rightarrow\underline{c})$ links a parent node
$\underline{n}$ to a child node $\underline{c}$.

Given an edge $e=(\underline{n}\rightarrow\underline{c})$, the function
$parent(\underline{c})$ yields $\underline{n}$. The function
$children(\underline{n})$ yields a set of nodes such that for each node $c$,
$parent(\underline{c})=\underline{n}$. The root of a tree is the only node
with no parent, i.e., $parent(\underline{r})=None$.

A delete-relaxed planning problem $\Pi=\langle F,A,I,G\rangle$ defines a tree
$T_{\Pi}$. Node $\underline{r}$ is the root of $T_{\Pi}$ and has
$label(\underline{r})=achieveGoal$. An action node $\underline{a}$, i.e., a
node whose label is an action, has children whose labels are its preconditions
$f\in pre(label(\underline{a}))$. A fact node $\underline{f}$ has children
whose labels are actions $a$ such that $label(\underline{f})\in ef\\!f(a)$.

The function $L(l)$ maps a label $l$ to a tree’s nodes that have that label:

$\displaystyle L(l)$
$\displaystyle=\\{\forall\underline{n}:label(\underline{n})=l\\}$ The path of
a node is the sequence of alternating fact and action nodes that is generated
by adding the parent of the current node until the root is reached:
$\displaystyle T_{\Pi}^{path}(\underline{n})$
$\displaystyle=[\underline{n},parent(\underline{n}),...,\underline{r}]$ The
descendants of a node $\underline{n}$ are all nodes that have $\underline{n}$
in their path: $\displaystyle T_{\Pi}^{desc}(\underline{n})$
$\displaystyle=\\{\forall\underline{d}:\underline{n}\in
T_{\Pi}^{path}(\underline{d})\\}$

Actions are excluded from the children of a fact node $\underline{f}$ if any
preconditions of that action appear as labels on any node in
$path(\underline{f})$. This prevents cycles, which would represent
unachievable requirements.

###  3.5 Non-deterministic agent

The aim of the relevance score heuristic is to estimate how frequently a fact
must become true in some distribution of partial plans. We use the behaviour
of a hypothetical Non-deterministic agent (NDA) do define this distribution. A
sub-tree $S_{\Pi}$ of $T_{\Pi}$, consists of some subset of nodes in $T_{\Pi}$
and their paths, chosen according to Algorithm 1. Applying the sequence of
actions represented by the path of each leaf-node within $S_{\Pi}$ will result
in the satisfaction of the goal. Thus, $S_{\Pi}$ may be considered a partial
plan under delete-relaxation conditions.

Our interpretation, which we pursue in this paper, is that a high probability
of being sampled by such an NDA indicates that a fact is highly relevant to
achieving the goal. Facts that appear in all partial plans that could be
sampled must be in all plans, and so are landmarks.

1: Let $S_{\Pi}\leftarrow\\{\underline{root}\\}$

2: Let $frontier$ be a stack

3: $frontier.push(\underline{root})$

4: while $frontier$ is not empty do

5: $\underline{n}\leftarrow frontier.pop()$

6: if $label(\underline{n})\in F$ then

7: Let $\underline{m}\leftarrow choose(children(\underline{n}))$

8: $frontier.push(\underline{m})$

9: Add $\underline{m}$ to $S_{\Pi}$

10: else

11: for $\underline{m}\in children(\underline{n})$ do

12: $frontier.push(\underline{m})$

13: Add $\underline{m}$ to $S_{\Pi}$

14: end for

15: end if

16: Remove $\underline{n}$ from frontier

17: end while

Algorithm 1 An NDA sampling sub-tree $S_{\Pi}$ from $T_{\Pi}$. Lines 4 \- 16
add required sub-goals and actions that require them until either a sub-goal
is TRUE in the state, or there is no action available that could achieve it.
Lines 6 \- 9 choose one action that achieves the required fact. Lines 10 \- 14
require all preconditions of an action.

###  3.6 Relevance score

Let the _relevance score_ $\Xi(l)$ represent the probability that a node with
label $l$ would be sampled by the NDA:

$\displaystyle\Xi(l)$ $\displaystyle=P\left(\exists\underline{l}\in
S_{\Pi}|label(\underline{l})=l\right)$

Let the _local relevance score_ $\Xi(l,\underline{n})$ represent the
probability that a node with label $l$ would be sampled by the NDA, given that
node $\underline{n}$ (and thus $S_{\Pi}^{path}(\underline{n})$) has been
sampled.

$\displaystyle\Xi(l,\underline{n})$
$\displaystyle=P\left(\exists\underline{l}\in
S_{\Pi}^{desc}(\underline{n})|label(\underline{l})=l\right)$ (1)

If $label(\underline{n})$ is a fact, any one of its children could be sampled,
and may have a node with label $l$ among its descendants:

$\texttt{if }label(n)\in F:$ $\displaystyle\Xi(l,\underline{n})$
$\displaystyle=\sum_{\underline{c}\in
children(\underline{n})}P\left(\underline{c}\in
S_{\Pi}^{desc}(\underline{n})\right)\times\Xi(l,\underline{c})$

The NDA chooses one child of a fact node with uniform probability, which
implies:

$\displaystyle\Xi(l,\underline{n})$ $\displaystyle=\sum_{\underline{c}\in
children(\underline{n})}\frac{\Xi(l,\underline{c})}{\left|children(\underline{n})\right|}$
(2)

If $label(\underline{n})$ is an action, then all its children will be sampled.
$\Xi(l,\underline{n})$ is thus 1 minus the probability that none of their
sampled descendants have label $l$:

$\texttt{if }label(n)\in A:$ $\displaystyle\Xi(l,\underline{n})$
$\displaystyle=1-\prod_{\underline{c}\in
children(\underline{n})}\left(1-\Xi(l,\underline{c})\right)$ (3)

###  3.7 Choices counter

The probability of a node $\underline{n}$ being sampled by the NDA,
$\xi(\underline{n})=P(\underline{n}\in S_{\Pi})$ depends on the number of
alternative action choices that could have been made instead of those that
reach that node. The tree’s root will always be sampled:

$\displaystyle\xi(\underline{r})$ $\displaystyle=1$

Between an action and its preconditions, the NDA has no choices to make, so
$\xi$ is passed down unchanged:

$\displaystyle\xi(\underline{f})$ $\displaystyle=\xi(parent(\underline{f}))$

The NDA chooses one action that could supply a fact from the set of actions
that make up $children(f)$:

$\displaystyle\xi(\underline{a})$
$\displaystyle=\frac{\xi(parent(\underline{a}))}{\left|children(parent(\underline{a}))\right|}$
(4)

where $\underline{r}$, $\underline{f}$, $\underline{a}$ are root, fact, and
action nodes respectively.

###  3.8 Lowest common ancestors

The Lowest Common Ancestor (LCA) of two nodes $\underline{n}$ and
$\underline{m}$ is the lowest node in the tree which is an ancestor of both
nodes:

$LCA(\underline{n},\underline{m})=\underset{\underline{i}\in
T^{path}_{\Pi}(\underline{n})\cap
T^{path}_{\Pi}(\underline{m})}{argmax}(|T^{path}_{\Pi}(\underline{i})|)$

This computation is associative and can generalize to any number of nodes.

##  4 Calculating the Relevance Score

Next, we describe our approach to compute the proposed relevance score
heuristic. We begin with some basics. The code used to implement and test this
will be made available
111https://github.com/relevancescoreplanning/relevance˙score.git.

Equation 1 allows us consider the descendants of a node independent of other
branches arising from its ancestors. This can be applied recursively to
calculate the local relevance score of the tree’s root:
$\Xi(l,\underline{r})=\Xi(l)$.

The following statements are obviously true, and allow us to ignore the local
relevance score $\Xi(l,\underline{n})$ for any nodes without descendants that
have $label(\underline{n})=l$:

$\texttt{if }label(\underline{n})=l$ $\displaystyle\implies$
$\displaystyle\Xi(l,\underline{n})=$ $\displaystyle 1$ $\texttt{if
}T^{desc}_{\Pi}(\underline{n})\cap L(l)=\emptyset$ $\displaystyle\implies$
$\displaystyle\Xi(l,\underline{n})=$ $\displaystyle 0$

Consider a node $\underline{n}$ and one of its descendants d such that all
nodes with label $l$ that are a descendant of one are also a descendant of the
other:

$\texttt{if }T^{desc}_{\Pi}(\underline{n})\cap
L(l)=T^{desc}_{\Pi}(\underline{d})\cap L(l)$ $\displaystyle\implies$
$\displaystyle\Xi(l,\underline{n})=$ $\displaystyle P\left(\underline{d}\in
S_{\Pi}^{desc}(\underline{n})\right)$
$\displaystyle\times\Xi(l,\underline{d})$ $\displaystyle=$ $\displaystyle
P\left(\underline{d}\in S_{\Pi}|\underline{n}\in S_{\Pi}\right)$
$\displaystyle\times\Xi(l,\underline{d})$ $\displaystyle=$
$\displaystyle\frac{\xi(\underline{d})}{\xi(\underline{n})}$
$\displaystyle\times\Xi(l,\underline{d})$ (7)

###  4.1 Derivation

Now, consider Equation 2 when each child $\underline{c}$ of a fact node
$\underline{f}$ has a single descendant $\underline{d}$ with
$label(\underline{d})~{}=~{}l$:

$\displaystyle\Xi(l,\underline{f})=$ $\displaystyle\sum_{\underline{c}\in
children(\underline{f})}\frac{\Xi(l,\underline{c})}{\left|children(\underline{f})\right|}$

Using Equation 4, this can be written as:

$\displaystyle=$ $\displaystyle\sum_{\underline{c}\in
children(\underline{f})}\frac{\Xi(l,\underline{c})}{\frac{\xi(\underline{f})}{\xi(\underline{c})}}$
$\displaystyle=$ $\displaystyle\sum_{\underline{c}\in
children(\underline{f})}\frac{\Xi(l,\underline{c})\times\xi(\underline{c})}{\xi(\underline{f})}$

Next, using Equation 7, this can be rewritten as:

$\displaystyle=$ $\displaystyle\sum_{\begin{subarray}{c}\underline{c}\in
children(\underline{f})\\\ \underline{l}~{}\models
T_{\Pi}^{desc}(\underline{c})~{}\cap~{}L(l)\end{subarray}}\frac{\frac{\xi(\underline{l})}{\xi(\underline{c})}\times\Xi(l,\underline{l})\times\xi(\underline{c})}{\xi(\underline{f})}$
$\displaystyle=$
$\displaystyle\sum_{\underline{l}~{}\in~{}T_{\Pi}^{desc}(\underline{f})~{}\cap~{}L(l)}\frac{\xi(\underline{l})}{\xi(\underline{f})}$
$\displaystyle=$
$\displaystyle\frac{1}{\xi(\underline{f})}\sum_{\underline{l}~{}\in~{}T_{\Pi}^{desc}(\underline{f})~{}\cap~{}L(l)}\xi(\underline{l})$
(8)

If all descendants of a node $\underline{d}\in T_{\Pi}^{desc}(\underline{n})$
are either such that $label(\underline{d})~{}=~{}l$, or are fact nodes for
which Equation 8 applies, this process can be repeated, causing further
$\frac{1}{\xi(\underline{c})}$ terms to cancel. If some nodes with
$label(\underline{d_{i}})~{}=~{}l$ have an
$LCA(\underline{d_{1}},\underline{d_{2}})~{}=~{}\underline{a}$ that is an
action (i.e., aLCA; see below), then Equation 7 does not apply between between
$\underline{c_{i}}$ and $\underline{d_{i}}$. It will apply between
$\underline{a_{i}}$ and $\underline{c_{i}}$, but $\Xi(l,~{}\underline{a})$
must be computed according to Equation 3:

$\displaystyle\Xi(l,\underline{f})=$
$\displaystyle\frac{1}{\xi(\underline{f})}\sum_{\underline{l}\in
fLCAs}\xi(\underline{l})+\sum_{\underline{a}\in
aLCAs}\frac{\xi(\underline{a})}{\xi(\underline{f})}\times\Xi(l,\underline{a})$
$\displaystyle=$
$\displaystyle\frac{1}{\xi(\underline{f})}\left(\sum_{\underline{l}\in
fLCAs}\xi(\underline{l})\right.+\left.\sum_{\underline{a}\in
aLCAs}\xi(\underline{a})\times\Xi(l,\underline{a})\right)$ (9)

where:

  * •

aLCAs - action Lowest Common Ancestors: any action nodes that are the LCA of
any subset of $L(l)\cap T_{\Pi}^{desc}(\underline{f})$

  * •

fLCAs - fact Lowest Common Ancestors: any nodes with label $l$ whose paths
diverge at fact nodes:
$fLCAs=\left\\{\forall\underline{l}\in
L(l):LCA(\underline{l}_{i},\underline{l}_{j})\in F\cap
T_{\Pi}^{desc}(\underline{f})\right\\}$

$\Xi(l)$ can be calculated from $L(l)$ by identifying the aLCAs, calculating
$\Xi(l,\underline{c})$ for their direct children with Equation 9, and
combining them according to Equation 3.

###  4.2 Exploration

For practical problems, $T_{\Pi}$ is potentially very large, prohibiting its
full representation. A lower bound for $\Xi(l)$ can be found using a partially
explored tree $\overline{T_{\Pi}}$. Nodes for which $\xi(\underline{n})$ is
small contribute less to $\Xi(l)$, and are found further from the root,
causing this lower bound to converge quickly upwards as the region of the tree
close to the root is explored.

We use Algorithm 2 to sample $\overline{T_{\Pi}}$ from $T_{\Pi}$. The
exploration threshold $\rho$ is an estimate of the ratio of how much
information is present in the frontier compared to the explored tree. We found
that the performance of $h_{\Xi}$ as a heuristic is not sensitive to small
changes in the value of $\rho$. Unless stated otherwise, we use $\rho=0.2$ in
the remainder of this paper. The first term of the condition in the outer
while loop in Algorithm 2 ensures that the sampling does not terminate early
due to the volatility of its terms when small.

Note that this sampling procedure differs from the sampling performed by the
hypothetical NDA. Both sampling procedures select actions that satisfy a
frontier fact at random, but the NDA explores all facts that are preconditions
for these actions, whereas the sampling procedure in Algorithm 2 selects a
single precondition. This ensures that the $T_{\Pi}$ is sampled more diversely
without too much focus on a few samples close to the root that branch widely,
leading to their siblings being ignored.

1: Let $frontier\leftarrow\\{goal\\}$

2: Let $\overline{T_{\Pi}}\leftarrow\\{goal\\}$

3: while $|\overline{T_{\Pi}}|<100000$ OR
$sumxi(frontier)/sumxi(\overline{T_{\Pi}})>\rho$ do

4: Let $\underline{n}\leftarrow choose(frontier)$

5: while $\underline{n}$ has children do

6: Remove $\underline{n}$ from $frontier$

7: Add $children(\underline{n})$ to $frontier$

8: Add $children(\underline{n})$ to $\overline{T_{\Pi}}$

9: Let $\underline{n}\leftarrow choose(children(\underline{n}))$

10: end while

11: end while

function $sumxi(\texttt{K}):\\\
\textbf{return}\sum_{\forall\underline{n}\in\texttt{K}}\xi(\underline{n})$

function $choose(options):$
return $\underline{m_{i}}\sim
P(\underline{m_{i}})=\xi(\underline{m})/\sum_{options}\xi(m_{i})$

Algorithm 2 Back-jumping depth-first tree search Lines 3 \- 10 start by
exploring a minimum of 100000 nodes, and continue until the ratio of the sum
of $\xi(\underline{n})$ in the frontier to that in the explored tree is less
than $\rho$. Line 4 selects a node $\underline{n}$ from which to perform the
next depth-first dive with probability proportional to $\xi(\underline{n})$.
Lines 5 \- 9 perform a depth-first dive, adding the children of nodes explored
to $\overline{T_{\Pi}}$, but choosing one to explore at each depth.

###  4.3 Finding LCAs

Much research has gone into finding the LCA of a pair of nodes in a tree. This
problem has been translated into that of calculating Range Minimum Querys
Fischer and Heun, (2006). Its complexity is $O(h)$ to pre-process the tree,
where $h$ is the height of the tree, and then $O(1)$ for each query on a pair
of nodes. This approach would thus cost $O(h+n^{2})$ to find LCAs for each
pair of nodes, where $n$ is the number of nodes whose LCAs we want to find.

Instead of this established procedure, we can take advantage of the fact that
many LCAs will be shared by multiple pairs; there are at most $hn$ unique
LCAs. We first sort the nodes by their paths (with complexity $O(hn\log(n))$
). The order does not matter, just that nodes with the same path up to a
certain distance from the goal are in a contiguous group, so nodes are treated
as symbols in a sequence (i.e., the path starting at the goal) and sorted
alphabetically by their labels. Traversing along the sorted paths (with worst
case complexity $O(hn)$), checking for differences between nodes in paths (and
whether or not they are action nodes) that are adjacent in the sort order
yields an ordered list of action LCAs (aLCAs). Sets of aLCAs are computed once
for each fact, and then filtered by $\sigma$ when $h_{\Xi}(\sigma)$ needs to
be calculated.

###  4.4 Use as a heuristic

In any particular state $\sigma$, all facts in the state $f\in\sigma$ are true
and do not need to be achieved by the planner. The state aware relevance score
for a given label, $\Xi_{\sigma}(l)$, should not consider parts of
$\overline{T_{\Pi}}$ that achieve these facts to be relevant. The relevance
score applied to a state $\Xi_{\sigma}(l)$ represents the probability that a
node with label $l$ would be sampled by the NDA, if it stops at nodes that are
true in state $\sigma$ (because they do not need an action to supply them). It
is calculated according to Equations 9 and 3 applied to the tree truncated at
nodes with labels in $\sigma$:

$\overline{T_{\Pi}/\sigma}=\overline{T_{\Pi}}\left/\bigcup_{\begin{subarray}{c}\forall\underline{f}\in
L(f)\\\ \forall f\in\sigma\end{subarray}}T^{desc}_{\Pi}(\underline{f})\right.$

This is found for all facts, and the heuristic for a state is calculated as:

$h_{\Xi}(\sigma)=\sum_{l\in F}\Xi_{\sigma}(l)$

As the relevance score heuristic is a sum of probabilities,
$h_{\Xi}(\sigma)\in\mathbf{R}$. The LAMA planning system, on the other hand,
requires heuristics to return an integer value. To allow for use and
comparison with LAMA, our approach rounds $h_{\Xi}(\sigma)$ to the nearest
integer, unfortunately losing some information in the process.

##  5 Experimental Setup and Results

We experimentally evaluated the following hypotheses:

  * H1

The relevance score heuristic S1 is slower than the landmark counting
heuristic S2 at solving standard planning problems, but is able to find a plan
most of the time; and

  * H2

The relevance score heuristic S1 substantially improves the ability to find
plans compared with the landmark counting heuristic S2 in domains without non-
trivial landmarks.

Hypothesis H1 is based on the understanding that when the tree is fully
explored (i.e. $\overline{T_{\Pi}}=T_{\Pi}$), landmarks will have a relevance
score $\Xi(l)=1$ and facts that do not appear in any valid plans will have a
relevance score $\Xi(l)=0$. In other words, the use of the relevance score
provides access to all the information available to a planning algorithm using
the landmark counting heuristic, while also considering additional information
about relevant but non-essential facts, which will result in additional
computation. H2 is valid because, while landmark counting heuristic S2 will
have no non-trivial landmarks to guide its search, the relevance score S1 will
still have an informative heuristic gradient to follow, with the potential to
lead to (better) solutions to the planning problems.

These hypotheses were evaluated using the architecture of the LAMA planner
Richter and Westphal, (2010)222 https://github.com/rock-planning/planning-
lama.git, with either our relevance score heuristic S1 or the existing
landmark counting heuristic S2; the use of S2 was our baseline. LAMA uses a
weighted $A^{*}$ search procedure (using the default weight = 10) with one of
the heuristics (S1 or S2). All searches were subject to a RAM limit of 8GB.
Their performance at solving all 674 problems defined in the examples folder
of the HSP2 repository Bonet and Geffner, (2001) 333
https://github.com/bonetblai/hsp-planners/tree/master/hsp2-1.0/examples was
compared according to the following performance measures:

  1. M1

Proportion of problems solved/not-solved;

  2. M2

Time spent searching for a plan before finding one;

  3. M3

Number of states expanded before finding a plan; and

  4. M4

Length of plan found.

These are well-established measures for evaluating the performance of these
planning problems.

###  5.1 Problems without non-trivial landmarks

In order to evaluate H2, we generated new PDDL specifications for domains that
contain no landmarks other than facts in the goal and initial state. This was
achieved by merging a pair of problems, $\pi_{1}$, $\pi_{2}$ that were
consistently solved using both heuristics in such a way as to prevent them
from interacting. This ensures that each new problem can be solved by at least
2 plans that have no overlap between the facts or actions involved in them.

To generate $merged(\Pi_{1},\Pi_{2})$, all domain or problem specific elements
(types, constants, predicates, actions, objects) in each problem were
prepended with a label unique to that problem. This ensured that no element
shared a name with elements in the problem they are being merged with. If a
problem did not use types, a new type consisting of just its unique label was
applied to all constants and objects within it. The new merged problem is then
comprised of all labeled elements from the two source problemss, with the
following modifications:

  * •

Two new actions are defined:
$a_{1}:pre(a_{1})=G_{1};ef\\!f(a_{1})=\\{winning\\}$
$a_{2}:pre(a_{2})=G_{2};ef\\!f(a_{2})=\\{winning\\}$.

  * •

The merged problem has a single goal:
$G_{merged}=\\{winning\\}$

A total of 500 problems were generated with this procedure by randomly
selecting a pair of problems from the pool of those solved individually by
both S1 and S2. The script used for this is unable to handle PDDL that, while
valid, does not follow certain conventions. Whenever this occurred, a new pair
was randomly selected for experimental evaluation.

###  5.2 Results: Standard Problems

Of the 674 planning problems in the HSP2 examples repository, Table 1 shows
how many were solved using each heuristic (i.e., S1, S2) with the LAMA
planner. Note that S2 performed better but S1 was able to find plans for most
of the problems solved by S2.

Solved by | S1 | S2 | Both | Neither
---|---|---|---|---
Number of | 273 | 370 | 261 | 147
problems | (51.61%) | (69.94%) | (49.34%) | (27.79%)
Table 1: Number of standard problems solved using S1 and S2 individually. S2
performed better but S1 was able to find plans most of the time.

Figure 2 shows that S2 resulted in better performance than S1 according to
measures M2, M3, and M4 for a majority of these problems. For problems that
were solved by both heuristics:

  * •

the average ratio between search times (s) for
$\textbf{S1}/\textbf{S2}=951.34\pm 3303.31$;

  * •

the average ratio between the number of states expanded for
$\textbf{S1}/\textbf{S2}=6.86\pm 29.53$; and

  * •

the average ratio between the length of plan found for
$\textbf{S1}/\textbf{S2}=1.13\pm 0.29$.

These results were along expected lines and strongly support hypothesis H1.

Figure 2: Standard problems (674): for each measure, a lower value is better.
S2 (landmark-counting) is better than S1 (relevance score) based on most
measures; results support hypothesis H1.

###  5.3 Results: Landmark-free problems

Of the 500 problems generated according to the procedure outlined in Section
5.1, Table 2 summarizes how many were solved using each heuristic (i.e., S1,
S2) with the LAMA planner. Note that performance was better using S1 compared
with S2.

Solved by | S1 | S2 | Both | Neither
---|---|---|---|---
Number of | 335 | 122 | 108 | 151
problems | (67%) | (24.4%) | (21.6%) | (30.2%)
Table 2: Number of merged problems solved using S1 and S2 individually. S1
performed much better than S2, substantially improving the ability to solve
the problems and find better plans. Figure 3: Landmark free problems (500):
for each measure, a lower value is better. S1 (relevance score) is better than
S2 (landmark-counting) based on most measures; results support hypothesis H2.

Figure 3 shows that S1 was measured to be much better than S2 according to
performance measures M2, M3, and M4 for the majority of these merged problems.
S2 fails to solve most of this class of problems. For problems that were
solved by both heuristics:

  * •

the average ratio between search times (s) for
$\textbf{S1}/\textbf{S2}=123.08\pm 295.25$;

  * •

the average ratio between the number of states expanded for
$\textbf{S1}/\textbf{S2}=0.64\pm 1.77$; and

  * •

the average ratio between the length of plan found for
$\textbf{S1}/\textbf{S2}=2.17\pm 2.40$.

These results strongly support hypothesis H2.

##  6 Discussion

The experimental results provide some interesting insights. The relevance
score calculated for a fully explored tree ($\overline{T_{\Pi}}=T_{\Pi}$ ) is
the number of facts that are landmarks for plans originating from $\sigma$
(for which $\Xi_{\sigma}(l)=1$ ), added to the relevance calculated for other
facts. In the case of standard planning problems, in addition to taking longer
to compute and use this extra information (M2), the use of our proposed
heuristic seems to impair the planners ability to find a plan within the
resource limits imposed. Our explanation for this is that the relevant but not
essential facts, for which $\Xi_{\sigma}(l)$ is high but less than 1, guide
the planner towards potentially competing plans. This ”distraction” causes it
to find plans that include elements of other partial plans that it could have
found, leading to longer plans M4. In problems where there is less overlap
between potential plans, the ratio of plan lengths (when both S1 and S2 find
one) is greater. Plans found by S1 in landmark-free problems contain actions
from both source problems, whereas plans found by S2 do not. The distracting
information also increases the cost of exploration (M2 and M3) which, causes
more problems to be unsolvable within resource (RAM) limits.

For landmark-free problems, S2 can only tell that a partial plan might be good
when it finds one of the goal facts. Until then, it searches a flat surface,
increasing the distance from the initial state in all directions. By contrast,
S1, i.e., our proposed relevance score heuristic, is able to climb an
informative surface that guides it toward potential plans. Because S1 rewards
the planner for finding facts that are relevant to alternative, but
potentially separate plans, it has a tendency to include some actions in the
final plan that did not contribute to achieving the goal. We believe this
explains why it finds longer plans than S2, particularly on problems that are
known to be solvable by disjoint plans. This is an unintentional byproduct of
the way these domains were created that may not be the case on problems
generated in other ways.

Overall, the key observation is that our relevance score heuristic is able to
guide the LAMA planner toward solving a class of planning problems for which
landmark counting is ineffective. This comes at the cost of being more
expensive to compute, and worse performance on standard problems. It can
therefore only be recommended on the class of problems for which it is
superior; those with few or no non-trivial landmarks. Note, however, that
landmarks are identified before a plan search procedure begins, which means
that there is an easy and natural way to leverage both heuristics: choose
landmark-counting on problems with well-defined landmarks, and use our
relevance score heuristic for problems that only have trivial landmarks. In
future work, we hope to explore these insights further with additional (and
more complex) planning problems.

## References

  * Bonet and Geffner, (2001) Bonet, B. and Geffner, H. (2001).  Planning as heuristic search.  Artificial Intelligence, 129(1-2):5–33.
  * Clemens and Keller, (2021) Clemens, B. and Keller, T. (2021).  LM-BFS : A Framework for Landmarks in Planning.  ICAPS 2021 Workshop on Heuristics and Search for Domain-independent Planning.
  * Fischer and Heun, (2006) Fischer, J. and Heun, V. (2006).  Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4009 LNCS:36–48.
  * Ghallab et al., (2004) Ghallab, M., Nau, D., and Traverso, P. (2004).  Chapter 2 - representations for classical planning.  In Ghallab, M., Nau, D., and Traverso, P., editors, Automated Planning, The Morgan Kaufmann Series in Artificial Intelligence, pages 19 – 53\. Morgan Kaufmann, Burlington.
  * Haslum, (2009) Haslum, P. (2009).  h^m( P ) = h^1(P^m): Alternative Characterisations of the Generalisation From h^{max} To h^m.  Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling, pages 354–357.
  * Helmert, (2006) Helmert, M. (2006).  The fast downward planning system.  Journal of Artificial Intelligence Research, 26:191–246.
  * Helmert and Domshlak, (2009) Helmert, M. and Domshlak, C. (2009).  Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway?  Proceedings of the 19th International Conference on Automated Planning and Scheduling, pages 162–169.
  * Hoffmann and Nebel, (2001) Hoffmann, J. and Nebel, B. (2001).  The FF planning system: Fast plan generation through heuristic search.  Journal of Artificial Intelligence Research, 14:253–302.
  * Hoffmann et al., (2004) Hoffmann, J., Porteous, J., and Sebastia, L. (2004).  Ordered Landmarks in Planning.  Journal of Artificial Intelligence Research, 22:215–278.
  * Karpas and Domshlak, (2009) Karpas, E. and Domshlak, C. (2009).  Cost-optimal planning with landmarks.  IJCAI International Joint Conference on Artificial Intelligence, pages 1728–1733.
  * Keyder and Geffner, (2008) Keyder, E. and Geffner, H. (2008).  Heuristics for Planning with Action Costs Revisited.  ECAI, pages 588—-592.
  * Keyder et al., (2010) Keyder, E., Richter, S., and Helmert, M. (2010).  Sound and complete landmarks for And/Or graphs.  ECAI, pages 335—-340.
  * Maliah et al., (2018) Maliah, S., Shani, G., and Brafman, R. I. (2018).  Landmark-based heuristic online contingent planning.  Autonomous Agents and Multi-Agent Systems, 32(5):602–634.
  * Pereira et al., (2017) Pereira, R. F., Oren, N., and Meneguzzi, F. (2017).  Landmark-Based Heuristics for Goal Recognition.  Proceedings of the 31th Conference on Artificial Intelligence, pages 3622–3628.
  * Porteous et al., (2001) Porteous, J., Sebastia, L., and Hoffmann, J. (2001).  On the Extraction, Ordering, and Usage of Landmarks in Planning.  Proceedings of ECP01, 129:37–48.
  * Richter et al., (2008) Richter, S., Helmert, M., and Westphal, M. (2008).  Landmarks revisited.  Proceedings of the National Conference on Artificial Intelligence, 2:975–982.
  * Richter and Westphal, (2010) Richter, S. and Westphal, M. (2010).  The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks.  Journal of Artificial Intelligence Research (JAIR), 39:127–177.
  * Segovia-Aguas et al., (2022) Segovia-Aguas, J., Jiménez Celorrio, S., Sebastiá, L., and Jonsson, A. (2022).  Scaling-Up Generalized Planning as Heuristic Search with Landmarks.  Proceedings of the International Symposium on Combinatorial Search, 15(1):171–179.
  * Vered et al., (2018) Vered, M., Pereira, R. F., Magnaguagno, M. C., Kaminka, G. A., and Meneguzzi, F. (2018).  Towards Online Goal Recognition Combining Goal Mirroring and Landmarks.  Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 2112–2114.
  * Wichlacz et al., (2022) Wichlacz, J., Höller, D., and Hoffmann, J. (2022).  Landmark Heuristics for Lifted Classical Planning.  IJCAI International Joint Conference on Artificial Intelligence, pages 4665–4671.
  * Zhu and Givan, (2003) Zhu, L. and Givan, R. (2003).  Landmark Extraction via Planning Graph Propagation.  ICAPS Doctoral Consortium, pages 156—-160.