Paper deep dive
Planning as Goal Recognition: Deriving Heuristics from Intention Models - Extended Version
Giacomo Rosa, Jean Honorio, Nir Lipovetzky, Sebastian Sardina
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 92%
Last extracted: 3/22/2026, 5:15:02 AM
Summary
The paper introduces a novel framework for classical planning by deriving heuristics from goal recognition (GR) intention models. By treating planning as a goal recognition problem, the authors define 'goal-intentionality' to rank trajectories, resulting in efficiently-computable heuristics that improve the performance of classical planners.
Entities (4)
Relation Signals (2)
IRPL Model → derives → Intention-based Heuristics
confidence 90% · Our plan-library model and proposed heuristics are both shown to belong to this family of estimators.
Goal Recognition → informs → Classical Planning
confidence 85% · We come full circle, and study the adoption and properties of GR-derived heuristics for seeking solutions to classical planning problems.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Classical planning aims to find a sequence of actions, a plan, that maps a starting state into one of the goal states. If a trajectory appears to be leading to the goal, should we prioritise exploring it? Seminal work in goal recognition (GR) has defined GR in terms of a classical planning problem, adopting classical solvers and heuristics to recognise plans. We come full circle, and study the adoption and properties of GR-derived heuristics for seeking solutions to classical planning problems. We propose a new framework for assessing goal intention, which informs a new class of efficiently-computable heuristics. As a proof of concept, we derive two such heuristics, and show that they can already yield improvements for top-scoring classical planners. Our work provides foundational knowledge for understanding and deriving probabilistic intention-based heuristics for planning.
Tags
Links
- Source: https://arxiv.org/abs/2603.14824v1
- Canonical: https://arxiv.org/abs/2603.14824v1
Trouble viewing inline? Open PDF directly →
Full Text
61,090 characters extracted from source content.
Expand or collapse full text
Planning as Goal Recognition: Deriving Heuristics from Intention Models Giacomo Rosa22footnotemark: 2,11footnotemark: 1, Jean Honorio22footnotemark: 2,11footnotemark: 1, Nir Lipovetzky22footnotemark: 2,11footnotemark: 1, Sebastian Sardina33footnotemark: 3,444Agile score is 1 for problems solved in T≤1sT≤ 1s, and 1−log(T)log(300)1- (T) (300) for 1<T≤3001<T≤ 300. Abstract Classical Planning aims to find a sequence of actions, a plan, that maps a starting state into one of the goal states. If a trajectory appears to be leading to the goal, should we prioritise exploring it? Seminal work in goal recognition (GR) has defined GR in terms of a classical planning problem, adopting classical solvers and heuristics to recognise plans. We come full circle, and study the adoption and properties of GR-derived heuristics for seeking solutions to classical planning problems. We propose a new framework for assessing goal intention, which informs a new class of efficiently-computable heuristics. As a proof of concept, we derive two such heuristics, and show that they can already yield improvements for top-scoring classical planners. Our work provides foundational knowledge for understanding and deriving probabilistic intention-based heuristics for planning. Introduction We study the connection between goal recognition (GR) and classical planning by characterizing planning heuristics as mechanisms for assessing their “goal-intentionality,” thus doing a full loop from Ramirez and Geffner (2009, 2010)’s seminal work on GR as planning. Classical planning is the field of AI that seeks to find a sequence of actions, a plan, that maps an initial state in a problem into a state that satisfies a specific goal condition. In classical planning, actions are deterministic, states are fully observable and represented through binary variables (facts), and no other actions occur outside the plan (i.e., static environment). A common strategy adopted by solvers is to perform a search over the state space, using heuristics which estimate the distance to the goal, such as the F (Bonet and Geffner 2001; Hoffmann and Nebel 2001) and Landmark (Porteous et al. 2001) heuristics, to guide the search. Other techniques have also proven to be effective in enhancing search efficiency. These include identifying helpful actions (Hoffmann and Nebel 2001), which prioritise operators likely to contribute to goal achievement, leveraging novelty measures (Lipovetzky and Geffner 2012, 2017), which favor exploration of states exhibiting previously unseen combinations of features, and dominance pruning (Torralba and Hoffmann 2015), which prunes states that provably cannot yield better solutions than previously explored states. These techniques do not estimate goal distance directly; rather, they prioritize states or nodes that aid the search through alternative mechanisms. The goal recognition task involves an observer inferring an acting agent’s goals or plans based on partial observations of its behaviour (Sukthankar et al. 2014).111Other common terms are Plan Recognition (PR) or Intention Recognition (IR). While subtle differences exists among them, in this paper, we shall use these terms interchangeably. Traditional approaches rely on a predefined plan library, which encodes known plans for implicit goals, allowing recognition through matching observed actions to entries in the library (Kautz and Allen 1986). More recent formulations, such as goal recognition as planning (Ramirez and Geffner 2009, 2010), cast recognition as a planning problem itself: a (declarative) goal is considered more likely if the observed actions align with an optimal or near-optimal plan to achieve it. Recent contributions have extended this paradigm to account for irrational behaviour of agents (Masters and Sardiña 2021), as well as adopting estimated measures and using information contained in the effects of observed actions to recognise goals and plans (Pereira et al. 2017; Wilken et al. 2024). In light of these recent developments, we revisit search for resource-bounded agents that seek to perform an intelligent exploration. Due to resource limitations, such agents bias the search towards some fragment of all possible traces (Pollack 1992; Bratman et al. 1988). We analyze the intentionality of these traces with the lens of work in GR, under the intuition that some traces are seen as observations that are “more intended” towards the goal than others, and push our search algorithms to explore “more intended paths”. This process is framed as a GR problem where, rather than estimating the intentionality of one observation towards multiple goals, we aim to assign and compare the intentionality of different observations towards a distinguished goal. Contributions. Our primary objective is to establish a novel conceptual framework that views heuristics as judges of the intentionality of discovered trajectories in a planning problem. We first present a plan-library model of GR for a resource-bounded agent in a planning domain. This allows us to define the “goal-intentionality” of observed traces, and study the properties of solvers that use this quantity to seek plans. A core contribution that separates our work from prior GR approaches is a new formulation of intentionality in which the likelihood is derived from the divergence between information in the observation, and a description of goal-intended information. Our plan-library model and proposed heuristics are both shown to belong to this family of estimators. Our theory then informs a new class of intention-based heuristics for classical planning. As a proof of concept, we present two such heuristics, which we show help improve the state of the art in classical planning benchmarks. We tie our results to our framework, providing experimental evidence of theorised properties of our search paradigm. Preliminaries The classical planning model is defined as Φ=⟨S,s0,SG,A,f⟩ = S,s_0,S_G,A,f , where S is the discrete finite state space, s0∈Ss_0∈ S is the initial state, SG⊆S_G S is the set of goal states, A is the set of (deterministic) actions, and f:A×S↦Sf:A× S S denotes the model partial transition function, with f(a,s)f(a,s) denoting the next state s′∈Ss ∈ S after applying action a∈Aa∈ A in state s∈Ss∈ S. When f is undefined, the action is not applicable in the state. We write A(s)A(s) to denote the set of actions applicable in state s, i.e., A(s)=a∈A∣f(a,s) is definedA(s)=\a∈ A f(a,s) is defined\. A solution to a classical planning model is given by a plan, a sequence of actions ⟨a0,…,am⟩ a_0,…,a_m that induces a state sequence ⟨s0,…,sm+1⟩ s_0,…,s_m+1 such that ai∈A(si)a_i∈ A(s_i), si+1=f(ai,si)s_i+1=f(a_i,s_i), and sm+1∈SGs_m+1∈ S_G for i∈0,…,mi∈\0,…,m\. A STRIPS222Stanford Research Institute Problem Solver (Fikes and Nilsson 1971) problem is defined through tuple =⟨F,A,I,G⟩P= F,A,I,G , where F denotes the set of boolean variables, or fluents, A is the set of actions a, I⊆FI F is the set of atoms that fully describe the initial state, and G⊆FG F is the partial assignment that describes goal states. We assume unit cost actions in this work. Planning Model Notation. Given a Classical Planning problem P, a trajectory denotes a sequence of alternating states and actions ⟨sk,ak,sk+1,ak+1,…,sm,am,sm+1⟩ s_k,a_k,s_k+1,a_k+1,…,s_m,a_m,s_m+1 , where both the first and last elements are states, such that si∈Ss_i∈ S, ai∈A(si)a_i∈ A(s_i), and si+1=f(si,ai)s_i+1=f(s_i,a_i); where k≤i<m+1k≤ i<m+1. Every trajectory induces two projections: an a-trajectory, which is the sequence of actions ⟨ak,ak+1,…,am⟩ a_k,a_k+1,…,a_m , and an s-trajectory, which is the sequence of states ⟨sk,sk+1,…,sm+1⟩ s_k,s_k+1,…,s_m+1 . We use (si,π)T(s_i,π) to represent the s-trajectory induced by an a-trajectory π applied from state sis_i. We use ℒ(s,π)L(s,π) to denote the last state sm+1∈Ss_m+1∈ S in the s-trajectory (s,π)T(s,π). For simplicity, when s is s0s_0 (the initial state of P as per I), we just write (π)T(π) and ℒ(π)L(π), resp. We place two constraints on considered trajectories: 1) acyclic: no state may appear more than once in a trajectory; and 2) non-goal-extending: goal states can only appear as the last state of the trajectory. These are reasonable assumptions, as any cycle is redundant and extending a-trajectories beyond a goal state is superfluous for finding plans towards a single goal. Given Si,Sj⊆S_i,S_j S, we use Π(Si,Sj) (S_i,S_j) to denote the set of acyclic and non-goal-extending a-trajectories that can be applied to a state si∈Sis_i∈ S_i to yield a valid s-trajectory that begins at state sis_i and ends at state sj∈Sjs_j∈ S_j. A plan is then an a-trajectory π∈Π(s0,SG)π∈ (\s_0\,S_G); in other words, an a-trajectory that, when applied to s0s_0, reaches a valid goal state sg∈SGs_g∈ S_G. Note that more than one sequence of actions (a-trajectories) may yield the same history of states (s-trajectories). Similarly, we use I-reachable a-trajectory to refer to all a-trajectories π∈Π(s0,S)π∈ (\s_0\,S). We adopt the definition of an observation sequence from previous plan and goal recognition literature (Ramirez and Geffner 2009; Masters and Sardiña 2021) as any sequence of actions ⟨o1,…,om⟩ o_1,...,o_m , with oi∈Ao_i∈ A. An action sequence satisfies an observation sequence iff it embeds it, meaning that there is a monotonic function g that maps each observation oi∈Ao_i∈ A to the index of an identical action in the action sequence such that g(oi)<g(oj)g(o_i)<g(o_j) for all j>ij>i. It follows from the above definitions that, given the set O of all possible observation sequences for problem P, Π(s0,SG)⊆Π(s0,S)⊆Π(S,S)⊆ (\s_0\,S_G) (\s_0\,S) (S,S) . An a-trajectory π′π contains a-trajectory π, written π⊑π′π π , iff there exist, possibly empty, sequences of actions α and β such that π′=α⋅π⋅βπ =α·π·β. This relation is reflexive, i.e., an a-trajectory contains itself. An a-trajectory π′π extends an a-trajectory π, written π⊑pfxπ′π _pfxπ , iff there exists a, possibly empty, suffix β such that π′=π⋅βπ =π·β. We define the set of maximal a-trajectories ℳM as the set of I-reachable a-trajectories that are not extended by any other I-reachable a-trajectory in Π(s0,S):ℳ=π∈Π(s0,S)∣∀π′∈(Π(s0,S)∖π),π⋢pfxπ′ (\s_0\,S):M=\π∈ (\s_0\,S) \ ∀π ∈( (\s_0\,S) \π\),\ π _pfxπ \. Thus, Π(s0,SG)⊆ℳ⊆Π(s0,S) (\s_0\,S_G) (\s_0\,S). We also define the operator ∝rank _rank, which indicates that two quantities induce the same ranking (the ordering is preserved): k∝rankl:=k(x)<k(y)⇔l(x)<l(y).k _rankl\;:=\;k(x)<k(y) l(x)<l(y). Intention-Based Search Goal recognition problems assume two agents: an acting agent, which follows a (hidden) trajectory, and an observer agent, whose task is to infer the intention of the acting agent given an observation, a partial trace of the actor’s full trajectory. We adapt this idea to the search problem in planning by imagining a one-vs-all GR problem, where the actor is either directed or not directed towards a single goal, and with known initial state. The observer must determine whether the actor is following a plan that satisfies the problem’s goal given a partial trace, and can therefore be thought of as a heuristic that determines the goal intention of an observation. Given multiple observations in an open list, we can then rank them based on their assigned probability of being intended towards the goal, preferring higher ranked observations for expansion as a means of guiding the search. We begin by assuming that the observer may be resource bounded, and as such may not have knowledge of all maximal a-trajectories starting from s0s_0. Rather, it has prior knowledge of a non-empty subset ℳ^⊆ℳ M of sampled candidate maximal a-trajectories, which it uses to infer the actor’s goal-intention. The observer is also subject to beliefs regarding the behaviour of the acting agent, which are expressed by assigning a weight to every maximal a-trajectory, a measure of “preference” for that a-trajectory. For example, if the observer believes that the actor is rational, it will assume that it is more likely to follow optimal or near-optimal paths towards its objective, and as such assign greater weights to shorter maximal a-trajectories. Alternatively, it may assign uniform weights if its belief is that the actor prioritizes all maximal a-trajectories equally. IRPL Model We provide the I-Reachable Plan-Library (IRPL) model, that only considers I-reachable a-trajectories in a planning problem as valid observation sequences, and derives probabilities relative to an implicit library of sampled maximal a-trajectories, and the subset of those a-trajectories that constitute plans. This allows us to illustrate the usefulness of adopting such probabilities as “heuristic signals” in a planning problem, under the simplified scenario where probabilistic events are explicitly observable. Given problem description ⟨F,A,I,G⟩ F,A,I,G and the set of all I-reachable a-trajectories Π(s0,S) (\s_0\,S), the observer samples a set ℳ M of known maximal a-trajectories starting at the initial state s0s_0, and assigns a weight to each maximal a-trajectory according to a weight function w:ℳ→ℝ+w:M +. Let the set of sampled plans be ℳ^G=Π(s0,SG)∩ℳ M_G= (\s_0\,S_G)∩ M. For I-reachable a-trajectories O∈Π(s0,S)O∈ (\s_0\,S), let C(O)=π′∈ℳ^∣O⊑pfxπ′C(O)=\π ∈ M O _pfxπ \ be the set of all sampled maximal a-trajectories that extend O. Let CG(O)=π′∈ℳ^G∣O⊑pfxπ′C_G(O)=\π ∈ M_G O _pfxπ \ be the set of sampled plans that extend O, and C¬G(O)=π′∈(ℳ^∖ℳ^G)∣O⊑pfxπ′C_ G(O)=\π ∈( M M_G) O _pfxπ \ be the sampled maximal non-plans extending O, such that CG(O)⋃C¬G(O)=C(O)C_G(O) C_ G(O)=C(O) and CG(O)⋂C¬G(O)=∅C_G(O) C_ G(O)= . We define sets of maximal a-trajectories ℰ⊆ℳ^E M that imply underlying events of interest, with probability P(ℰ)=∑π′∈ℰw(π′)/∑π′∈ℳ^w(π′)P(E)= _π w(π )/ _π ∈ Mw(π ) Thus, P(G)P(G) is the event that π∈ℳ^π∈ M is a plan: P(G):=P(ℳ^G)=∑π′∈ℳ^Gw(π′)/∑π′∈ℳ^w(π′)P(G):=P( M_G)= _π ∈ M_Gw(π )/ _π ∈ Mw(π ) (1) Similarly, P(¬G):=P(ℳ^∖ℳ^G)P( G):=P( M M_G). P(O)P(O) is the event that π∈ℳ^π∈ M extends O: P(O):=P(C(O))=∑π′∈C(O)w(π′)/∑π′∈ℳ^w(π′) P(O):=P(C(O))= _π ∈ C(O)w(π )/ _π ∈ Mw(π ) (2) We can then obtain conditional probability P(O∣G):=P(C(O)∣ℳ^G)P(O G):=P(C(O) M_G): P(O∣G)=∑π′∈CG(O)w(π′)/∑π′∈ℳ^Gw(π′)P(O G)= _π ∈ C_G(O)w(π )/ _π ∈ M_Gw(π ) (3) where CG(O)=C(O)⋂ℳ^GC_G(O)=C(O) M_G.333These probabilities are well-defined: P(G)+P(¬G)=1P(G)+P( G)=1, and P(O)+P(¬O)=1P(O)+P( O)=1, where P(¬O):=P(ℳ^∖C(O))P( O):=P( M C(O)); calculating P(O,G)=P(O∣G)⋅P(G)P(O,G)=P(O G)· P(G) and using P(¬G)P( G) to obtain P(O,¬G)P(O, G), then P(O,G)+P(O,¬G)=P(O)P(O,G)+P(O, G)=P(O). Finally, Bayesian posterior P(G∣O)P(G O) becomes the weight of all sampled plans to the goal extending O, over the weight of all sampled maximal a-trajectories extending O: P(G∣O)=p(O∣G)p(G)p(O)=∑π′∈CG(O)w(π′)∑π′∈C(O)w(π′)P(G O)= p(O G)p(G)p(O)= _π ∈ C_G(O)w(π ) _π ∈ C(O)w(π ) (4) For any set of a-trajectories for which probabilities P(O∣G)P(O G) and P(G∣O)P(G O) are defined for all elements in the set, we can then obtain a ranking through either of equations 5 or 6, argmaxOP(O∣G)=argmaxO∑π′∈CG(O)w(π′) *arg\,max_OP(O G)= *arg\,max_O _π ∈ C_G(O)w(π ) (5) argmaxOP(G∣O)=argmaxOP(O∣G)P(O∣¬G) *arg\,max_OP(G O)= *arg\,max_O P(O G)P(O G) (6) where equation 6 is obtained by simplifying argmaxOP(G∣O)/P(¬G∣O) *arg\,max_OP(G O)/P( G O) and noting that P(G)P(G) and P(¬G)P( G) are constant when considering a single goal in planning problems. When extending the domain of conditional probabilities to the set of all possible observations in a planning problem, we adopt the convention of setting undefined probabilities to 0. This reflects an observer that assumes unknown trajectories are not goal directed. Framework Properties We first state the results, followed by analysis. Claim 1. Given non-empty ℳ M and ℳ^G M_G, any w, and a-trajectories OeO_e extending an a-trajectory OpO_p by one action, P(Oe∣G)≤P(Op∣G)P(O_e G)≤ P(O_p G), as CG(Oe)⊆CG(Op)C_G(O_e) C_G(O_p). Claim 2. P(O∣G)=0P(O G)=0 and P(G∣O)=0P(G O)=0 for all a-trajectories O that are not extended by any plan π′∈ℳ^Gπ ∈ M_G. Lemma 1. Given non-empty ℳ M and ℳ^G M_G, and any w, maxOeP(G∣Oe)≥P(G∣Op) _O_eP(G O_e)≥ P(G O_p). Proof sketch. Every maximal a-trajectory extending OpO_p extends exactly one child OeO_e; hence C(Op)=⋃OeC(Oe)C(O_p)= _O_eC(O_e) and CG(Op)=⋃OeCG(Oe)C_G(O_p)= _O_eC_G(O_e), and these unions are disjoint. Let X(O)=∑π′∈C(O)w(π′)X(O)= _π ∈ C(O)w(π ) and define XG(O)X_G(O) analogously. Then X(Op)=∑OeX(Oe)X(O_p)= _O_eX(O_e) and XG(Op)=∑OeXG(Oe)X_G(O_p)= _O_eX_G(O_e), so P(G∣Op)=XG(Op)X(Op)=∑OeX(Oe)X(Op)XG(Oe)X(Oe).P(G O_p)= X_G(O_p)X(O_p)= _O_e X(O_e)X(O_p) X_G(O_e)X(O_e). Thus P(G∣Op)P(G O_p) is a weighted average of its children and therefore cannot exceed all of them. ∎ Theorem 1. Given non-empty ℳ M and ℳ^G M_G, and any w, a planner that expands maxP(G∣O) P(G O) and breaks ties by greater trajectory length, will find a plan in number of expansions m≤maxπ′∈ℳ^G|π′|m≤ _π ∈ M_G|π |. Proof. The first expanded node has P(G∣O)P(G O) greater than or equal to all others. Since P(G∣O)>0P(G O)>0, Claim 2 ensures that at least one plan to the goal exists, and by Lemma 1 its best child has probability ≥ that of its parent. Since it also has greater trajectory length, it is expanded next; induction completes the argument. ∎ Lemma 2. Let |ℳ^G|>0| M_G|>0. Suppose w is a weight function such that w(π)>w(π′)⇔cost(π)<cost(π′)w(π)>w(π ) (π)<cost(π ). For a planner that expands a-trajectories in order of maxP(O∣G) P(O G), the first expanded goal node is guaranteed to be a minimal-cost plan among all plans in the sample ℳ M. The result also holds under the weaker condition cost(π)≤cost(π′)⇒w(π)≥w(π′)cost(π) (π ) w(π)≥ w(π ), provided ties in P(O∣G)P(O G) are broken by preferring shorter trajectories. Proof sketch. Assume the first goal-reaching a-trajectory π expanded is not minimal cost, and let π∗π^* be a cheaper plan. If π∗π^* is fully generated, then P(π∗∣G)>P(π∣G)P(π^* G)>P(π G) since w(π∗)>w(π)w(π^*)>w(π), contradicting that π was expanded first. If instead only its prefix ρ is generated, then P(ρ∣G)≥P(π∗∣G)P(ρ G)≥ P(π^* G) because prefixes aggregate the weight of all their extensions and these values decrease monotonically with depth. Thus ρ (or π∗π^* when complete) would have been expanded before π. Hence the first expanded goal-achieving trajectory must correspond to a minimal-cost plan. When different-cost plans have equal weight, tie-breaking by shorter length selects the minimal-cost one first. ∎ Lemma 3. A planner that expands a-trajectories in order of maxP(O∣G) P(O G) will expand at most ∑π∈ℳ^G(|π|−1)+1 _π∈ M_G(|π|-1)+1 nodes before expanding a goal, and ∑π∈ℳ^G(|π|−2)+1 _π∈ M_G(|π|-2)+1 nodes before generating a goal. Proof. Follows from Claim 2 that at most all non-goal nodes in s-trajectories implied by plans in ℳ^G M_G will be expanded before expanding a goal node. In the worst case, plans in ℳ^G M_G do not overlap and only share the initial state, which is counted once. ∎ Theorem 2. Given non-empty ℳ M and ℳ^G M_G. For a planner that expands a-trajectories in order of maxP(O∣G) P(O G); as samples are added to ℳ^G M_G, the length of the first expanded plan is non-increasing, and the worst-case number of expansions is non-decreasing. Proof. Follows from previous Lemmas 2 and 3, and considering that as samples are added, the minimum plan cost in the set can only decrease. ∎ Remarks. We briefly summarise general properties derived from the presented theorems. Claim 2 implies that following any a-trajectory with both P(O∣G)>0P(O G)>0 and P(G∣O)>0P(G O)>0 is a valid strategy for reaching a goal. Theorem 1 shows that expanding nodes according to Equation 6 follows a hill climbing strategy when ties are broken by larger g and is strongly goal directed. If ties are broken by smaller g, then it may perform local searches when ties are encountered, until it finds an exit to the plateau. In contrast, Equation 5 follows the maximum a posteriori path, inducing an exploratory strategy akin to an A* search with a consistent heuristic, as shorter a-trajectories tend to have higher P(O∣G)P(O G) probability, noted in Claim 1. This approach expands sampled solution trajectories until it selects a sample optimal plan. Theorem 2 reflects the sampling exploration-exploitation trade-off for P(O∣G)P(O G): increasing the number of samples in ℳ^G M_G can improve solution quality, but also increases the worst case number of expansions, reflecting the larger exploratory effort required. Uniform Regimes In what follows, we introduce and analyze the properties of two “basic” weight functions. We consider these as the two general uniform weighting processes, where we assign equal probability to, respectively (1) every sampled maximal a-trajectory, (2) every action choice in state transitions. We define a Uniform Maximal a-trajectory Probability (UMP) weight function as a weight function w(π)=cw(π)=c where c is a non-zero constant, implying a uniform preference of the agent towards any sampled maximal a-trajectory in ℳ M. Let us define quantities NT=|ℳ^|N_T=| M|, NG=|ℳ^G|N_G=| M_G|, NC(O)=|C(O)|N_C(O)=|C(O)|, and NCG(O)=|CG(O)|N_CG(O)=|C_G(O)|. Corollary 1. Given non-empty ℳ M and ℳ^G M_G, and a UMP weight function w, the probabilities obtained become P(O)=NC(O)NTP(O)= N_C(O)N_T, P(G)=NGNTP(G)= N_GN_T, P(O∣G)=NCG(O)NG∝NCG(O)P(O G)= N_CG(O)N_G N_CG(O), P(G∣O)=p(O∣G)p(G)p(O)=NCG(O)NC(O)P(G O)= p(O G)p(G)p(O)= N_CG(O)N_C(O). Proof. Follows from Equations 1,2,3, and 4; setting weight function w(π)=1w(π)=1, then the value of each summation is equivalent to the number of elements in the relevant sets. ∎ Corollary 1 shows that under a UMP weight function, P(O∣G)P(O G) is proportional to the number of plans extending O, and ordering the open list by argmaxP(O∣G) *arg\,maxP(O G) favours such prefixes. Ordering by argmaxP(G∣O) *arg\,maxP(G O) favours prefixes with a higher ratio of plan completions to non-plan continuations. Both quantities can be seen as measures of robustness of a partial solution, biasing the search towards directions with more valid outcomes. A Uniform Transition Probability (UTP) weight function assigns to a maximal I-reachable a-trajectory π=⟨a0,…,ak−1⟩π= a_0,…,a_k-1 the product of uniform action probabilities at each step, w(π)=∏i=0k−1[|A(si)|]−1w(π)= _i=0^k-1 [|A(s_i)| ]^-1, where s0s_0 is the initial state, si+1=f(ai,si)s_i+1=f(a_i,s_i), and A(si)A(s_i) is the set of applicable actions at state sis_i. That is, at each step the agent selects an applicable action with uniform probability. Lemma 4. Given non-empty ℳ M and ℳ^G M_G, a UTP weight function w, and an a-trajectory O that is extended by single solution plan πs _s, the number of nodes generated to find πs _s by a planner that expands according to maxP(O∣G) P(O G) is lower bounded by −ln[P(O∣G)⋅P(G)]⋅e∝−ln[P(O∣G)]- [P(O G)· P(G)]· e - [P(O G)]. Proof. The lower bound on nodes generated is given by the minimum possible number of nodes generated while following πs _s that achieves UTP weight w(πs)=P(O∣G)⋅P(G)w( _s)=P(O G)· P(G). For each expanded state si∈(πs)s_i ( _s), the number of generated nodes increases by |A(si)||A(s_i)|, and the weight of the a-trajectory to sis_i is multiplied by 1|A(si)| 1|A(s_i)|. For w(πs)=1Xw( _s)= 1X the minimum number of generated nodes is thus given by solving min∑si∈(πs)(|A(si)|) _s_i ( _s)(|A(s_i)|) s.t. ∏si∈(πs)|A(si)|=X _s_i ( _s)|A(s_i)|=X. A lower bound to the integer solution is achieved by solving the real version of the problem, which can be solved analytically through the AM-GM Inequality to yield e⋅ln(X)e· (X). ∎ Theorem 3. Given non-empty ℳ M and ℳ^G M_G, a UTP weight function w, and a planner that expands according to maxP(O∣G) P(O G), a lower-bound number of node generations required to achieve any plan that extends O is −ln[P(O∣G)⋅P(G)]⋅e- [P(O G)\ · P(G)]· e. Proof. P(O∣G)P(O G) is equivalent to the sum of the weight of all plans extending O, over a common denominator. From Lemma 4, it follows that the number of node generations required to solve any plan increases inversely to the plan’s weight. Thus, the minimum number of node generations occurs when a single solution plan extends O. ∎ Theorem 3 shows that expanding nodes according to Equation 5 with a UTP weight function follows the a-trajectory that minimises the best-case number of node generations to find a plan in ℳ M. This strategy can be seen as optimistic in the face of uncertainty, where uncertainty refers to unexplored regions of the state space. It assumes the subgraph extending the selected trajectory has an ideal shape; as new information is revealed, this estimate may worsen, leading the search to prefer other sub-graphs. Such a bound cannot be obtained with a UMP weight function, as uniform weights are not tied to the number of node generations. Estimating Measures of Goal Intention The IRPL model helps us characterize intention-based heuristics and their search behaviour. The prior knowledge we have assumed so far is, however, unrealistic, as we cannot expect to have access to a maximal trajectory library ℳ M and plan library ℳ^G M_G. To obtain a practically relevant framework, we need to account for an observer that estimates goal intentionality using approximate measures. Existing work in GR-as-planning defines the likelihood P(O∣G)P(O G) through the use of cost estimates (Ramirez and Geffner 2010; Masters and Sardiña 2021). Intuitively they assume that rational agents are more likely to prefer lower-cost plans to their selected goal, basing their estimation process then on the sub-optimality of plans to each goal that incorporate observed events. We avoid following this direction, because adopting such formulations would lead us back to using (heuristic) cost estimates to direct the search. Instead, we propose a novel formulation for approximating and interpreting goal intentionality which provides: 1) a theoretical background for alternative directions for estimating heuristics in classical planning, and 2) a generalisation of the IRPL model in terms of a larger class of approximate goal-intended models. General Model of Divergence-based Likelihood We define a divergence-based generalisation of goal-intended likelihood through Equation 7, P~(O∣G):=e−DKL(dO,G∥dG) P(O G):=e^-D_KL(d_O,G d_G) (7) dGd_G denotes a distribution that estimates goal-intended outcome probabilities (intuitively capturing likelihoods of outcomes in ℳGM_G, P(π∣G)P(π G)), and dO,Gd_O,G denotes a specific posterior distribution over the same space obtained by incorporating observed evidence (intuitively capturing updated likelihoods of outcomes given observation O, P(π∣O,G)P(π O,G)). To illustrate the characteristics of the adopted probability distributions with respect to their domains, consider the following simplified example of rolling a dice 10 times, where the goal G is a total sum of values >30>30. A complete outcome is the sequence r=(r1,…,r10)r=(r_1,…,r_10) of the random variable R=(R1,…,R10)R=(R_1,…,R_10), where each rir_i denotes the value of one roll, and the distribution dG:=ρ(r∣G)d_G:=ρ(r G) assigns probabilities to all such sequences. An observation reveals the values of a subset of these variables, e.g., (R1=3,R2=5)(R_1=3,R_2=5), and observations are non-exclusive: observing (3,5)(3,5) does not exclude observing (3,5,4)(3,5,4) as a longer trace. The observation instead belongs to the marginal domain induced by the variables it reveals, with the marginal distribution ρ(r1,r2∣G)ρ(r_1,r_2 G) assigning probabilities to the exclusive outcomes of that sub-domain. The posterior distribution then incorporates observations: dO,G:=ρ(r∣R1=3,R2=5,G)d_O,G:=ρ(r R_1=3,R_2=5,G). Whereas in the IRPL model observations are defined as i-reachable a-trajectories, now the domain of dGd_G defines the outcomes that determine the events in observations. To illustrate this, following the previous example, assume each roll outcome rir_i no longer represents the value of the dice roll, but rather whether the roll gives a number >3>3. Observations would then take the form (R1=true,R2=false,…)(R_1=true,R_2=false,...). While approximate, such events still contain useful information for estimating goal achievement. A well-defined KL-divergence requires matching the domains of dO,Gd_O,G and dGd_G. So far we have described dO,Gd_O,G over the domain of dGd_G, but this need not be the case. Since the notation O does not specify the domain of the observation, we instead adopt x∈x , y∈y , and z∈z to denote outcomes explicitly associated with their domains. Let =1×⋯×vX=X_1×·s×X_v be the domain of complete outcomes, with x=(x1,…,xv)x=(x_1,…,x_v) denoting a full outcome. For any index sets ⊆K⊆1,…,vJ K \1,…,v\, define the marginal domains =×i∈iY= _i X_i and =×i∈KiZ= _i∈ KX_i , with tuples y=(xi)i∈y=(x_i)_i and z=(xi)i∈Kz=(x_i)_i∈ K, xi∈ix_i _i, denoting outcomes in Y and Z. We write ρ(x)ρ(x) for the distribution over complete outcomes, and ρ(y)ρ(y) and ρ(z)ρ(z) for the corresponding marginals. Let y∗∈y^* be the discrete deterministic observation O. We add superscripts to specify the domain of dO,Gd_O,G and dGd_G. Let dG:=ρ(x∣G)d_G^X:=ρ(x G) and dO,G:=ρ(y∣y∗,G)d_O,G^Y:=ρ(y y^*,G). Let dGd_G^Z and dO,Gd_O,G^Z denote any domain-matched representation of dGd_G^X and dO,Gd_O,G^Y on an intermediate domain Z. dGd_G^Z is marginalisation ρ(z∣G)=ρ(z∣x,G)⋅ρ(x∣G)ρ(x∣z,G)ρ(z G)= ρ(z x,G)·ρ(x G)ρ(x z,G); dO,Gd_O,G^Z is Bayesian update ρ(z∣y∗,G)=ρ(y∗∣z,G)⋅ρ(z∣G)ρ(y∗∣G)ρ(z y^*,G)= ρ(y^* z,G)·ρ(z G)ρ(y^* G). Theorem 4. The KL divergence is invariant to the choice of Z, and coincides with the negative log-likelihood of the observation conditional on the goal: DKL(dO,G∥dG)=−logρ(y∗∣G)D_KL(d_O,G^Z\,\|\,d_G^Z)\;=\;- ρ(y^* G) Proof. Expanding ρ(z∣y∗,G)ρ(z y^*,G), simplifying, and marginalising, we have DKL(dO,G∥dG)=∑z∈ρ(z∣y∗,G)logρ(z∣y∗,G)ρ(z∣G) D_KL(d_O,G^Z d_G^Z)= _z ρ(z y^*,G) ρ(z y^*,G)ρ(z G) =∑z∈[ρ(z∣y∗,G)logρ(y∗∣z,G)]−logρ(y∗∣G) = _z [ρ(z y^*,G) ρ(y^* z,G) ]- ρ(y^* G) Since y∗y^* is a projection of some z onto observed coordinates, for all z∈z if any variable value in y∗y^* is different from the corresponding variable in z, ρ(z∣y∗,G)=0ρ(z y^*,G)=0, and if all variables in y∗y^* have same value with corresponding variables in z, ρ(y∗∣z,G)=1ρ(y^* z,G)=1, so logρ(y∗∣z,G)=0 ρ(y^* z,G)=0. Thus, DKL(dO,G∥dG)=−logρ(y∗∣G)∎D_KL(d_O,G^Z d_G^Z)=- ρ(y^* G) Through Theorem 4, the specific choice of intermediate domain used to align distributions, required for computing the KL-divergence, does not affect the derivation of −logρ(y∗∣G)- ρ(y^* G). This justifies Equation 7, and points at multiple possible strategies to estimate −logρ(y∗|G)- ρ(y^*|G). Special cases. We briefly present cases of interest: 1) Marginalising dGd_G^X to Y. We can make dGd_G^X match the marginal distribution of dO,Gd_O,G^Y by marginalising all domain factors not in Y, directly obtaining likelihood dG:=ρ(y∣G)=ρ(y|x,G)⋅dGρ(x∣y,G)=∑xρ(y,x|G)d_G^Y:=ρ(y G)= ρ(y|x,G)· d_G^Xρ(x y,G)= _xρ(y,x|G); dO,Gd_O,G^Y is then a degenerate PMF ρ(y∣y∗,G)ρ(y y^*,G), i.e., a one-hot distribution over its domain, assigning 1 to observation y∗y^*, and 0 to all others. 2) Mapping dO,Gd_O,G to X. We can map the observation distribution to the full domain X through Bayesian update dO:=ρ(x∣y∗,G)=ρ(y∗|x,G)⋅ρ(x∣G)ρ(y∗∣G)d_O^X:=ρ(x y^*,G)= ρ(y^*|x,G)·ρ(x G)ρ(y^* G). 3) Consistency with IRPL Model. When dGd_G^X perfectly describes the plan library, through a bijective mapping of every sampled plan to a possible outcome with its relative weight as probability, and dO,Gd_O,G^Y describes an observed I-reachable a-trajectory, Equation 7 then derives the IRPL likelihood. It thus generalises Equation 3. Assumptions. The result holds whenever (i) the observation is discrete and deterministic over Y, i.e., dO,G(y)=[y=y∗]d_O,G^Y(y)=1[y=y^*], and (i) the observation map m:→m:X is surjective onto its image, ensuring that at least one complete trace is consistent with y∗y^*. These are consistent with the GR model. Interpretation. The cost based formulation of goal recognition (Ramirez and Geffner 2010; Masters and Sardiña 2021) is grounded in the assumption of agent rationality: observations that align with near optimal plans are considered evidence of goal intended behaviour. Similarly, Equation 7 interprets rationality in terms of the divergence of observed information dO,Gd_O,G from the distribution dGd_G, which captures statistical evidence of goal intendedness from estimated solution paths. It is intuitive that observations consistent with goal intended behaviour, when normalised by the likelihood of the observation, reflect intent towards a goal. In our experiments, we show that estimating such information can provide a signal for informing an efficient state-space exploration and traversal, whose behaviour still correlates with results from the simpler and “ideal” IRPL model. Planning Heuristics We demonstrate the practical relevance of our conceptual framework by proposing two variants of a novel intention-based heuristic which align with our theory, allowing us to correlate results with our predictions of search behaviour obtained through analysis of the IRPL model. We follow recent work in GR (Pereira et al. 2017; Wilken et al. 2024), which represents observations through the facts implied by underlying action sequences or trajectories. In a GR setting, this would represent facts added by actions in action sequence O. In a planning context, it may also include facts present in the initial state. Our heuristic uses fact observation probability estimation as described in (Wilken et al. 2024) to estimate, for each fact q∈Fq∈ F, a Bernoulli distribution q∼Bernoulli(Prel(q∣G))q (P_rel(q G)), representing the probability that q is achieved at any point in a delete-relaxed plan. Prel(q∣G)P_rel(q G) then refers to the conditional probability in the relaxed problem. This is done by first sampling a set of delete-relaxed plans to the goal to obtain the probability of observing each action in a sampled relaxed plan. The probability of observing facts is then indirectly derived as the probability of not observing any supporter action for the fact in a relaxed plan; thus, even if a fact is supported in all sampled relaxed plans, it may still get an observation probability less than 1. Pseudocode for the original algorithm, and a few modifications we make, are included in Appendix B. This estimation technique was shown to be effective in GR problems, where fact observation probabilities weight vectors in a feature space, and the Euclidean norm of the vectors is then used to estimate the distance covered by an agent towards a goal. Our divergence-based interpretation of goal intendedness instead informs us to use fact observation probabilities to directly estimate the likelihood. Likelihood Estimation. Let OFO^F represent a set of observed facts. If we assume conditional independence between fact occurrences, the likelihood is simply P~(OF∣G)=∏q∈OFPrel(q∣G) P(O^F G)= _q∈ O^FP_rel(q G) According to our model, this likelihood can be interpreted in terms of a Boltzmann distribution of the marginalisation of dG:=ρ~(q1,…,q|F|)=∏q∈FBernoulli(Prel(q∣G))d_G:= ρ(q_1,...,q_|F|)= _q∈ FBernoulli(P_rel(q G)) with respect to facts in OFO^F. It represents the divergence between distribution ρ~(q1,…,q|F|) ρ(q_1,...,q_|F|) and the observation OFO^F, and is thus in the same “class” of divergence-based measures as the IRPL likelihood. This aspect justifies our comparison of solver behaviour with theory from our IRPL analysis. In practice, we calculate the relative ranking of observations through the sum of log-probabilities. As the fact occurrence probability computation is only performed once at the beginning of the search (at the initial state), P~(OF∣G) P(O^F G) is then computable in time linear in |OF||O^F| during the search, providing quick evaluation. In our experiments, we set the number of sampled relaxed plans to 100. This value was selected through analysis of results in the context of GR in (Wilken et al. 2024), and empirical testing. We refer to this heuristic as relaxed plan observation likelihood (olrp). Posterior Estimation. A Bayesian posterior is also derived from P(G∣O)∝rankP(O∣G)P(O∣¬G)P(G O) _rank P(O G)P(O G) (from Equation 6): P~(G∣OF)∝rank∑q∈OFlogPrel(q∣G)−logPrel(q∣¬G) P(G O^F) _rank _q∈ O^F P_rel(q G)- P_rel(q G) This requires an additional estimation of Prel(q∣¬G)P_rel(q G), which uses a modification of the procedure used to obtain Prel(q∣G)P_rel(q G): rather than sampling delete-relaxed plans, the heuristic samples delete-relaxed action sequences that achieve all non-goal facts in the instance. Fact probabilities Prel(q∣¬G)P_rel(q G) are then extracted from this set of supporter actions. We still sample 100 fact sets each for both Prel(q∣G)P_rel(q G) and Prel(q∣¬G)P_rel(q G), and call this variant relaxed plan observation posterior (oprp). f5f5 !15f5f5-olrrp^rp_r f5f5 !15f5f5-oprrp^rp_r !15f5f5-olrrp^rp_r !15f5f5-oprrp^rp_r Coverage (1831) 1510 11560 (5.03) 1510 11556 (1.5) 11560 (5.03) 1556 (1.5) % Score 76.77% 180.20% (0.35) 76.77% 179.90% (0.15) 180.20% (0.35) 79.90% (0.15) N Fewer Expansions 368.2 (6.7) 11134.4 (8.7) 341.4 (9.1) 11159.4 (8.0) 412.0 (7.3) 1716.6 (6.5) N Lower Time 582.4 (99.5) 1897.0 (92.2) 658.8 (117.3) 1814.6 (102.4) 1811.8 (130.1) 658.0 (122.6) N Lower Plan Cost 1 760.6 (8.9) 369.6 (7.6) 1763.6 (2.9) 375.8 (1.7) 1375.2 (4.5) 349.2 (13.4) Average EpS 40111 35680 40111 33626 35680 33626 Table 1: Performance comparison between BFWS(f5f5) and variants with olrrp^rp_r and oprrp^rp_r heuristics. % score is the average of the % of instances solved in each problem domain. Results for comparisons and solvers with a randomised component represent the mean, and include the standard deviation across 5 measurements. N Fewer Expansions, N Lower Time and N Lower Plan Cost represent the number of problems where a variant scores better in the respective metrics (ignoring ties). Avg. EpS represents the average number of expansions per second across problems solved by all planners, and proxies computational overhead. Results indicate that olrrp^rp_r and oprrp^rp_r reduce the number of expansions across a significant portion of problems, on average improving also coverage and solution time. Such improvements come at the cost of on average worse plan quality compared to the baseline. Adding Goal-intentionality to BFWS We integrate our proposed heuristics with a BFWS solver (Lipovetzky and Geffner 2017), which balances exploration of the search space and exploitation of heuristics, to evaluate improvements in its search behaviour. BFWS(f5f5) uses Partitioned Novelty (Lipovetzky and Geffner 2017) as primary heuristic to partition each planning problem into multiple sub-problems and prioritize exploration, and the goal-count heuristic hGCh^GC, that counts the number of unachieved goal facts, is used both to inform such partitioning, and as tie-breaking heuristic. These heuristics are quickly computable, but often not very granular, creating a large number of ties. Minimum distance g is used to break final ties, and has a big impact on the overall performance of the planner. We implement our proposed variants as third tie-breakers after hGCh^GC to provide a fast but more informed tie-breaking mechanism that seeks progress by directing the search towards the goal. Our aim is for this to lead to states that improve the other heuristics more effectively than g. Following our reasoning from the IRPL model, olrp is supposed to exhibit an A*-like exploratory behaviour, “augmenting” the original tie-breaking mechanism, whereas oprp should induce a more greedy and goal-directed search. Partial Observation Trajectories. We adapt olrp and oprp to BFWS through olrp-restart (olrpr_r^rp) and oprp-restart (oprpr_r^rp). These adaptations add log probabilities from facts that have been observed only in the trajectory from the last state that improved hGCh^GC, as opposed to all facts achieved from the start. By “restarting” at the most recent hGCh^GC improvement, it regains informedness in the cases where it was lost. Otherwise, if a fact that did not appear in any sampled relaxed plan to the goal is observed, it would strongly penalise the probability of all descendant nodes. This helps account for inaccuracies in fact occurrence estimates introduced by adopting distributions derived from relaxed plans. Experimental Results We run our experiments on an AMD EPYC 7763 processor, with each test running on a single core. We adopt Downward Lab’s experiment module (Seipp et al. 2017), whereas our proposed solvers and heuristics are implemented in C++ using the LAPKT planning module (Ramirez et al. 2015). Our adopted branch of LAPKT uses the FD grounder (Helmert 2009), with the exception of problems that produce axioms, which are not currently supported in LAPKT. In such problems, our planners automatically fallback to the Tarski grounder (Francés et al. 2018; Singh et al. 2021a). All experiments are limited to 1800 seconds and 8 GB time and memory constraints, following the satisficing track of the International Planning Competition (IPC) (Taitler et al. 2024). The problem set is composed of all IPC satisficing track benchmarks, selecting the latest problem sets for recurrent domains. Experimental Analysis. Table 1 highlights performance gains from our proposed techniques. Both olrpr_r^rp and oprpr_r^rp improve coverage and reduce the number of expansions on a significant portion of problems compared to BFWS(f5f5) baseline. This confirms that the goal-intendedness encoded by our heuristics induces a more efficient exploration of the state space. In direct comparison, oprrpop_r^rp shows a small advantage over olrrpol_r^rp in node expansions, aligning with our IRPL analysis that P(G∣O)P(G O) drives a more goal directed greedy search. However, the more exploratory nature of P(O∣G)P(O G) leads olrrpol_r^rp to solve more instances overall. In regards to the exploration-exploitation dilemma, it is reasonable to expect that that the effectiveness of exploitation declines as the quality of the underlying estimate worsens. Thus, the more exploratory heuristic may be better suited to handle the approximation noise. The additional overhead from computing fact observation probabilities is offset by improved search efficiency, resulting in lower average solution times than BFWS(f5f5). By contrast, the extra computation of P(O∣¬G)P(O G) required by oprrpop_r^rp introduces a small penalty relative to olrrpol_r^rp, but differences are within the measurements’ standard deviation. The main drawback of both techniques is their effect on plan cost, which is expected due to the bias toward shorter plans induced by the original g tie-breaker. Suboptimal plan costs may also be influenced by the trajectory-restart policy of olrrpol_r^rp, which loses the “global” negative bias towards shorter trajectories from Claim 1. SOTA Variants. Our best performing BFWS solver BFWS(f5f5)-Landmarks-olrpr_r^rp (OLrpr_r^rp) substitutes hGCh^GC with the Landmarks heuristic (Porteous et al. 2001), and uses a single trimmed open list (Rosa and Lipovetzky 2024) for greater memory efficiency. We note that both the coverage and average solution time gap between olrrpol_r^rp and oprrpop_r^rp widen when using this configuration. We also test variant OLrpr_r^rp-UTP with modified fact observation probability sampling, to highlight the practical impact of the weighting scheme in the IRPL model. When calculating supporter action probabilities for olrpr_r^rp, each sampled relaxed plan is given an equal weight. OLrpr_r^rp-UTP re-weights sampled relaxed plans according to a UTP weight function, giving more importance to relaxed plans with greater UTP weight. Lastly, we provide a comparison with recent high-coverage dual strategy solvers −- that run an initial search and, if this fails, fall back to a backend solver −- by replacing the frontend solver in BFNoS-Dual (Rosa and Lipovetzky 2024) with OLrpr_r^rp (OLrpr_r^rp-Dual). Planner Coverage (1831) % score Agile score Dual-BFWS 1607 83.6% 1200.8 ApxNoveltyT 1611 (3.5) 83.8% (0.2) 21233.7 (0.2) LAMA 1535 79.1% 1192.3 Scorpion-M 1591 82.9% 1206.4 !15OLrpr_r^rp 31621 (3.2) 384.6% (0.3) 1229.4 (3.4) !15OLrpr_r^rp-UTP 1616 (2.1) 84.2% (0.1) 11236.0 (1.9) BFNoS-Dual 21641 (0.6) 286.2% (0.1) 1173.3 (3.5) !15OLrpr_r^rp-Dual 11655 (1.5) 187.0% (0.1) 31232.6 (2.9) Table 2: Mean coverage and Agile score555Agile score is 1 for problems solved in T≤1sT≤ 1s, and 1−log(T)log(300)1- (T) (300) for 1<T≤3001<T≤ 300. Agile 1800 substitutes the previous quantity with 1−log(T)log(1800)1- (T) (1800) for 1<T≤18001<T≤ 1800. of our proposed planners. OLrpr_r^rp and OLrpr_r^rp-UTP refer to BFWSt-f5f5-Landmarks adopting the respective heuristics. OLrpr_r^rp-Dual is a modification of BFNoS-Dual that replaces the BFNoS frontend with OLrpr_r^rp. Our enhancements of BFWS(f5)f5) outperform SoTA planners, on average solving more problems, more quickly, without using multiple open lists or runs. OLrpr_r^rp-Dual then provides an improved dual-strategy solver. Results. Table 2 compares the best-performing variants with multiple SoTA Novelty planners BFNoS-Dual (Rosa and Lipovetzky 2024), Dual-BFWS (Lipovetzky and Geffner 2017), and Approximate Novelty Tarski (Singh et al. 2021b), as well as past IPC satisficing track winners LAMA (Richter and Westphal 2010) and Scorpion-Maidu (Corrêa et al. 2023). Results indicate improved coverage of our proposed modifications of BFWS(f5f5). OLrrp^rp_r-UTP also improves Agile score over the base OLrrp^rp_r, at the cost of some problem coverage. Agile score is a performance metric that jointly evaluates coverage and runtime. We further note correlation between our experimental results for OLrrp^rp_r-UTP and Theorem 3, suggesting that prioritising sampled relaxed plans with better estimated bounds on the number of node generations to find the goal can accelerate the search, albeit at the expense of problem coverage, losing some of the robustness mentioned in the discussion of Corollary 1. UTP weights promote a more “committed” search, whereby a focus on optimistic relaxed plan samples can solve problems earlier when these estimates are accurate, but also mislead the search when they are not. The latter case may occur when sampled relaxed plans diverge from correct plans, potentially missing important actions or facts. As fact probability extraction relies on the sampling of relaxed plans, we expect the quality of approximations to align with that of well-studied relaxed heuristics. For instance, our planners perform strongly on Settlers (Long and Fox 2003), a challenging domain where relaxed-plan-heuristic planners LAMA and Maidu outperform BFWS baselines (Appendix D). We also note sets of relatively poor plan-cost cases for variants in Table 1 appear to be domain-specific. We do not exclude that additional mechanisms related to the probability estimation process, such as observing sets of facts rather than a-trajectories, may impact per-domain amenability, informing future directions to improve proposed heuristics. Concluding Remarks We introduce a model that provides an intuitive description of goal-intendedness given a set of underlying plans in an instance, and use it to study the behaviour of planners that adopt goal intentionality as heuristic signal. Our model and proposed heuristics are shown to belong to a general class of divergence-based goal recognition estimates. As a proof of concept, we propose two heuristics which improve the base performance of BFWS, matching complex IPC planners in Agile scores, while exceeding their coverage. We provide empirical evidence of correlation between our results and the theorised properties of our search paradigm. Our proposed planning-as-goal-recognition theoretical framework offers a new perspective on heuristic search, interpreting evaluation functions as processes that infer the intention of trajectories to the current state with respect to the goal. Such trajectories, therefore, do not only reveal the cost so far, but also their goal intendedness. This aspect may also provide a new perspective for analysing properties of well-established classical planning heuristics. The one-off time cost of the information extraction phase opens the door to potentially more informed and expensive estimation methods to further improve problem solving capability. The probabilistic nature of the intentionality framework can also lead to new solutions in related problems, such as learned heuristics for planning, and facilitate connections between planning, goal recognition, and non-symbolic fields of AI, such as statistical machine learning. Acknowledgments We thank the reviewers for their valuable feedback. Giacomo Rosa is supported by the Melbourne Research Scholarship established by the University of Melbourne. This research was supported by use of the Nectar Research Cloud and by the Melbourne Research Cloud. The Nectar Research Cloud is a collaborative Australian research platform supported by the NCRIS-funded Australian Research Data Commons (ARDC). References B. Bonet and H. Geffner (2001) Planning as heuristic search. Artificial Intelligence 129 (1-2), p. 5–33. Cited by: Introduction. M. E. Bratman, D. J. Israel, and M. E. Pollack (1988) Plans and resource-bounded practical reasoning. COMPINT 4 (3), p. 349–355. Cited by: Introduction. A. B. Corrêa, G. Francès, M. Hecher, D. M. Longo, and J. Seipp (2023) Scorpion Maidu: width search in the Scorpion planning system. In Tenth International Planning Competition (IPC-10): Planner Abstracts, Cited by: Experimental Results. R. E. Fikes and N. J. Nilsson (1971) STRIPS: a new approach to the application of theorem proving to problem solving. Artificial intelligence 2 (3-4), p. 189–208. Cited by: Preliminaries. G. Francés, M. Ramirez, and Collaborators (2018) Tarski: an AI planning modeling framework. GitHub. Note: https://github.com/aig-upf/tarski Cited by: Experimental Results. M. Helmert (2009) Concise finite-domain representations for PDDL planning tasks. Artificial Intelligence 173 (5-6), p. 503–535. Cited by: Experimental Results. J. Hoffmann and B. Nebel (2001) The F planning system: fast plan generation through heuristic search. Journal of Artificial Intelligence Research 14, p. 253–302. Cited by: Introduction. H. A. Kautz and J. F. Allen (1986) Generalized plan recognition. In AAAI, p. 32–37. Cited by: Introduction. N. Lipovetzky and H. Geffner (2012) Width and serialization of classical planning problems. In ECAI 2012, p. 540–545. Cited by: Introduction. N. Lipovetzky and H. Geffner (2017) Best-first width search: exploration and exploitation in classical planning. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 31. Cited by: Introduction, Adding Goal-intentionality to BFWS, Experimental Results. D. Long and M. Fox (2003) The 3rd international planning competition: results and analysis. Journal of Artificial Intelligence Research 20, p. 1–59. Cited by: Experimental Results. P. Masters and S. Sardiña (2021) Expecting the unexpected: goal recognition for rational and irrational agents. AIJ 297, p. 103490. External Links: Link, Document Cited by: Introduction, Planning Model Notation., General Model of Divergence-based Likelihood, Estimating Measures of Goal Intention. R. Pereira, N. Oren, and F. Meneguzzi (2017) Landmark-based heuristics for goal recognition. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 31. Cited by: Introduction, Planning Heuristics. M. E. Pollack (1992) The uses of plans. AIJ 57 (1), p. 43–68. Cited by: Introduction. J. Porteous, L. Sebastia, and J. Hoffmann (2001) On the extraction, ordering, and usage of landmarks in planning. In Proc. ECP, Vol. 1. Cited by: Introduction, Experimental Results. M. Ramirez and H. Geffner (2009) Plan recognition as planning. In IJCAI, p. 1778–1783. Cited by: Introduction, Introduction, Planning Model Notation.. M. Ramirez and H. Geffner (2010) Probabilistic plan recognition using off-the-shelf classical planners. In AAAI, p. 1121–1126. Cited by: Introduction, Introduction, General Model of Divergence-based Likelihood, Estimating Measures of Goal Intention. M. Ramirez, N. Lipovetzky, A. Singh, and C. Muise (2015) Lightweight Automated Planning ToolKiT. Note: http://lapkt.org/Accessed: 2025 Cited by: Experimental Results. S. Richter and M. Westphal (2010) The LAMA planner: guiding cost-based anytime planning with landmarks. Journal of Artificial Intelligence Research 39, p. 127–177. Cited by: Experimental Results. G. Rosa and N. Lipovetzky (2024) Count-based novelty exploration in classical planning. In Proceedings of the European Conference on Artificial Intelligence, Vol. 392, p. 4181–4189. Cited by: Experimental Results, Experimental Results. J. Seipp, F. Pommerening, S. Sievers, and M. Helmert (2017) Downward lab. Cited by: Experimental Results. A. Singh, N. Lipovetzky, M. Ramirez, J. Segovia-Aguas, and G. Frances (2021a) Grounding schematic representation with gringo for width-based search. Cited by: Experimental Results. A. Singh, N. Lipovetzky, M. Ramirez, and J. Segovia-Aguas (2021b) Approximate novelty search. In Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 31, p. 349–357. Cited by: Experimental Results. G. Sukthankar, C. Geib, H. H. Bui, D. Pynadath, and R. P. Goldman (2014) Plan, activity, and intent recognition: theory and practice. Newnes. Cited by: Introduction. A. Taitler, R. Alford, J. Espasa, G. Behnke, D. Fišer, M. Gimelfarb, F. Pommerening, S. Sanner, E. Scala, D. Schreiber, et al. (2024) The 2023 international planning competition. Wiley Online Library. Cited by: Experimental Results. A. Torralba and J. Hoffmann (2015) Simulation-based admissible dominance pruning.. In IJCAI, p. 1689–1695. Cited by: Introduction. N. Wilken, L. Cohausz, C. Bartelt, and H. Stuckenschmidt (2024) Fact probability vector based goal recognition. In ECAI 2024, p. 4254–4261. Cited by: Introduction, Planning Heuristics, Planning Heuristics, Planning Heuristics.