Cost-Based Goal Recognition for the Path-Planning Domain

1 Introduction

Goal recognition (GR) is the problem of identifying an agent's intent by observing her behaviour. The traditional approach involves matching observations to a pre-existing plan in a plan library [Kautz and Allen, 1986; Charniak and Goldman, 1991]. Recent developments, however, dispense with this overhead and treat the problem instead as one of "planning in reverse" [Ramirez and Geffner, 2009; Baker et al., 2009]. Using a classical planner and linking a goal's probability to the cost of a plan that achieves it, this approach draws on the intuition that a rational agent is most likely to be following the optimal (i.e., minimum cost) or least sub-optimal [Ramirez and Geffner, 2010] plan for goal.

In this paper, 1 we examine the probabilistic GR model for general task-planning, developed in [Ramirez and Geffner, 2010], and reframe it in the strict context of path-planning. We prove that a simpler account yields an almost identical result in less than half the time and with less computational effort. More surprisingly, we also show that a probability distribution that ranks candidate goals in the same order can be obtained without referencing any observations (other than the agent's starting point and current location).

2 Goal Recognition as Planning

We begin by presenting the technical background.

Ramirez and Geffner's GR framework operates in a classical task-planning environment. In STRIPS, a planning domain is a tuple D = 〈F,A〉, where F is a set of fluents and A a set of actions a, each with a precondition, add and delete list Pre(a), Add(a) and Del(a), all subsets of F . Action a can occur in state s if Pre(a) ⊆ s. The initial state is assumed fully observable and the domain deterministic: if a occurs in s, a new state s′ results such that s′ = (s ∪ Add(a)) \ Del(a). A planning problem 〈F, I, A, G〉 is a planning domain with specified initial and goal states I,G ⊆ F, and its solution is a plan π = a1, .., ak that maps I to G. Typically, each action has a cost c(a). The cost of π is defined cost(π) = ∑ c(ai) and an optimal plan is a solution with the lowest cost.

1 This paper is an abridgement of [Masters and Sardina, 2017] (with minor amendments), best student paper at AAMAS17.

Ramirez and Geffner (2009) defined a GR problem T = 〈D, G, I, O〉, where: D is a planning domain; G ̸= ∅ a set of possible goal states; I the initial state; and O = o1, .., ok, k ≥ 0, oi ∈ A, a sequence of observations. The solution to T is a set of goals, the optimal plans for which satisfy observations, and a plan π = a1, .., an satisfies observations o1, .., om if it embeds them in a way that preserves the order of actions.

A major drawback of the above framework is that it only identifies a goal if observations conform to an optimal plan, whereas, realistically, agents behave suboptimally; and in [Ramirez and Geffner, 2010] the authors presented an alternative probabilistic framework which addresses the problem.

A probabilistic GR problem is a GR problem plus a prior probability distribution. Its solution is a posterior probability distribution which prefers goals whose plans "best" satisfy observations. Basing their notion of "best" on the principle of rational action, Ramirez and Geffner (2010) capture this idea using the cost difference between the cheapest plan for goal, given the actions already observed, and the cheapest plan that could have achieved it, had the agent behaved differently. Comparing cost differences across goals, the authors arrive at a probability distribution with the following important property: the lower the cost difference, the higher the probability. Formally, cost difference is a function costdif : 2F ×A∗ ↦→ R:

where optc(G,O) and optc¬(G,O) denote the optimal cost of plans that do and do not embed observations, respectively. The probability distribution itself is computed using:

where X = costdif(G, O), α is a normalising constant across goals, and β a positive constant that modulates the shape of the distribution. 2

2 RG2, in code referenced from [Ramirez and Geffner, 2010], is

2.1 The Path-Planning Case

Reformulating the above approach in the context of pathplanning, fluents become tied to locations and actions relate to movements. Whereas in task-planning, a solution plan is described as a sequence of actions, in path-planning, it becomes a path: a sequence of connected nodes in a graph.

Definition 1. A path-planning domain is a triple D = 〈N,E, c〉 where: N ̸= ∅ is a set of nodes (or locations); E ⊆ N×N is a set of edges between nodes; and c : E ↦→ R+0 returns the non-negative cost of traversing each edge. ■

A path π in D is a sequence of locations π = n0, n1, . . . , nk such that (ni, ni+1) ∈ E, for each i ∈ {0, 1, . . . , k - 1}. πi denotes the i-th node ni in π, and |π| denotes the length of π, being the total number of edges k in π. π(i, j) = πi , πi+1 , . . . πj denotes the subpath of π fromπi to πj (inclusive). The cost of a path is the cost of traversing all edges in π, that is, cost(π) = ∑k-1 i=0 c(πi , πi+1 ). The set of all paths in the domain is denoted by Π, and the set of all paths π starting at π0 = n1 and ending at π|π| = n2 is denoted by Π(n1, n2). Definition 2. A path-planning problem is a tuple Q = 〈D, s, g〉, where: D is the path-planning domain; s ∈ N is the start location; and g ∈ N is the goal location. ■

The solution to Q is a path π in D such that π0 = s, π|π| = g; the set of all of them being Π(s, g). An optimal path is a solution with lowest cost. Π∗ (s, g) is the set of all such paths.

Waypoints are nodes that must be visited and a path via waypoints embeds them in a way that preserves their order. The optimal cost via waypoints W of a path from ni to nj is denoted by optc(ni, W, nj ). If W = ∅, we write optc(ni, nj ), and if π0 = w0 and π|π| = wk, we write optc(W). We generalise the set of all solution paths Π(s, g) to those embedding waypoints W as Π(s,W, g). Similarly, Π∗ (s,W, g) denotes paths that are optimal w.r.t. cost among paths in Π(s,W, g).

Definition 3. A path-planning GR problem is a tuple P = 〈D, G, s, O, Prob〉, where: D is a path-planning domain; G ⊆ N is the set of possible goals; s ∈ N is the start location; O = o1, . . . , ok, k ≥ 0, oi ∈ N, is a sequence of locations (not actions, nor necessarily a path) where the agent has been observed; and Prob is the prior probabilities of the goals. ■

The solution to P is a probability distribution across G obtained using a reformulation of (RG1), grounded in pathplanning as costdif RG : N ×N ×N ∗ ↦→ R:

where optc¬(s,O, g) denotes the optimal cost of navigating from s to g without embedding waypoints, that is:

Finally, the probability distribution is derived as for taskplanning, by taking X = costdif RG(s, g,O) into Equation (RG2). For legibility, we call the resulting function PRG:

provably equivalent to the account there and in [Ramirez, 2012].

3 We nowmake explicit the starting point s, implicit in (RG1).

3 A Simpler Cost Difference

We now present the first of our main technical contributions: a modified cost difference formula which is simpler to compute than (RG3) and faster to calculate. Based on the intuition that, in the great majority of cases, the optimal path that "does not pass through all observed locations" is the optimal path, instead of computing optc¬(s, O, g) we deduct the more readily available "optimal path cost", arriving at:

This alternative formulation is not only computationally less demanding (there is no requirement to reason negatively about the observations) but also, since the optimal path cost to each potential goal is not dependent on the observations, it can be pre-computed once at the outset. Note that if the potential start node and all candidate goal locations are known, as they are in the case of an airport terminal, for example, which has a fixed, finite number of entrances and boarding gates, then optc(s, g) for all g ∈ G can be pre-computed and stored for retrieval as needed in constant time.

As the following theorems state, formula (1) generates an identical result to formula (RG3)in all cases bar one; and even then, the difference has minimal impact on the overall probability distribution. Moreover, in one corner-case, (1) actually enables calculation of a posterior probability distribution when the original, more involved, formula (RG3) may not.

Theorem 1. Let O be an observation sequence such that optc(s, O, g) > optc(s, g) (i.e., the observed behaviour is not optimal). Then, costdif RG(s, g, O) = costdif1 (s, g, O).

In words, if the observed path is suboptimal-as, arguably, it would be most of the time-the simpler formula (1) yields exactly the same value as the original formula (RG3).

Theorem 2. Let O be an observation sequence such that optc(s,O, g) = optc(s, g) (i.e., the observed behaviour is optimal). If Π∗ (s, g) \ Π∗ (s,O, g) ̸= ∅, then costdif RG(s, g, O) = costdif1 (s, g, O).

In words, even if the observed behaviour is optimal, if there are other ways of behaving optimally, again formula (1) is exactly equivalent to the original formula (RG3).

Theorem 3 sets out the only case where the two formulas return different results. Consider the following example.

Example 1. One goal location is a house with front and back doors. An agent is observed at the front gate which is on the only optimal path. Using formula (1) the cost difference for this goal is zero (the observed path is the optimal path) but using formula (RG3) cost difference-assuming cost equates to distance-is a negative value (the optimal path not embedding observations is longer than the path that does embed them because it involves a detour to reach the back door). □

Theorem 3. Let O be an observation sequence and g ∈ G. Then, costdif RG(s, g, O) ̸= costdif1 (s, g, O) iff Π∗ (s, O, g) = Π∗ (s, g) (i.e., all optimal paths embed the observations).

This strengthens Theorem 2 by asserting that both formulas yield identical results in all cases bar one: when observations are not only sufficient for optimal behaviour, but also necessary, i.e., there is no other way of acting fully rationally.

In considering this corner case, recall that cost difference is just a stepping stone towards generating a probability distribution. Often, we do not need to know exactly how probable the goals are, only their relative order or, more particularly, which goal is most probable. With this in mind, we prove (in Theorem 4) that, even if an agent is observed taking an exclusively optimal path to a goal (i.e., all optimal paths embed the observations), unless observations also conform to an optimal path for some other goal, the relative ranking of goals by probability is unaffected by use of the simpler cost difference formula, which still results in successful identification of the most probable goal.

Before proceeding, we make the following auxiliary observation, which formally restates the intuition that the lower the cost difference, the more probable the goal.

Observation 1. Let f(g,O) be a cost difference function and PX a template of the probability distribution in (RG2). If f(g1, O) < f(g2, O), then Pf (g1|O) > Pf (g2|O).

Now, let PRG(·) be the probability distribution obtained from (RG2) when X = costdif RG(s, g,O) (Equation (RG3)) and P1(·) the distribution obtained when X = costdif1 (s, g, O) (Equation (1)).

Theorem 4. Let O be an observation sequence and suppose that, for some potential goal g ∈ G, it is the case that:

1. Π∗ (s,O, g) = Π∗ (s, g), that is, observations are exclusively optimal; and
2. for every g′ ∈ G \ {g}, optc(s,O, g′ ) > optc(s, g′ ), that is, observations would result in suboptimal paths to all the other possible goals.

Then, for all g1, g2 ∈ G and g1 ̸= g2, P1(g1|O) > P1(g2|O) if and only if PRG(g1|O) > PRG(g2|O).

There remains one variation of exclusive optimality so far excepted. It is the case where observations coincide with the only optimal path to multiple goals (rather than one). We have argued that exclusive optimality for one goal is unusual; clearly, for multiple goals, it is even more so. Should the situation arise, however, the complex formula (RG3) would return multiple (negative) cost differences, which could be ranked, whereas the simple formula (1) ranks all goals for which observations match the optimal path equally.

Arguably, this situation is not only extremely unlikely, it also concerns the very set of goals in which this probabilistic account [Ramirez and Geffner, 2010] is least interested.

Finally, in the extreme case, where observations conform not just to the only optimal path to a goal g but to the only path per se, the cost of a path that does not conform to observations is infinite (because no such path exists). In this case, as Ramirez and Geffner (2010) point out, (RG3) ought to return

-∞ giving g the highest possible probability within the distribution. However, since -∞ is not a number, the result may be undefined with the flow-on effect that normalised scores for the rest of the distribution may also be undefined.

In any practical implementation, of course, the problem is easily rectified by allocating some minimum value instead of

-∞ or treating this case separately. In an identical situation, however, Equation (1) (based on optimal cost from start to goal rather than "optimal cost given not the observations") returns zero and the issue does not arise.

To summarise the advantages of the simpler formula (1):

• costdif1 (s, g,O) returns the same result as costdif RG(s, g, O) in all cases bar one;
• the one case where the formulas do not return identical results relates to fully rational behaviour, which is precisely not the motivation of the probabilistic GR model;
• even when costdif1 (s, g,O) returns a different result, it is unlikely to impact the overall probability distribution;
• in the most extreme case-when no path to goal avoids the observations- it returns a meaningful result when costdif RG(s, g, O) may return no result at all; and
• costdif1 (s, g,O) is computationally advantageous: it requires no 'negative' reasoning (so any standard pathplanner can be used off-the-shelf); furthermore, in many domains, its second termmay be pre-computed.

4 Single-Observation 4 Recognition

We now come to our second core contribution. As shown, in all but one extreme corner case, formula (1) can be used interchangeably with (RG3). Here, we go further and demonstrate that-if the starting location is known (e.g., because there is one common entrance to a building or terminal)-the ranking of goals, as judged by the probability distribution P1(·) and generated using formula (1), can be achieved without reference to the observation sequence.

At first sight, the finding is counter-intuitive. Indeed, it implies that we can perform goal recognition without observing how the agent behaves over time! Nevertheless, if we know an agent's start location and the location of each candidate goal, we require only her current location in order to calculate a probability distribution within which goals are ranked in exactly the same order as if we had used formula (1).

Our single-observation formula, costdif2 : N ×N ×N ↦→ R is defined as:

where n stands for the most recently observed location of the agent whose destination we are trying to determine (i.e., n = O|O| ). Let P2(·) be the probability function obtained by taking X = costdif2 (s, g, n) in (RG3).

Theorem 5. Let O be an observation sequence. For all g1, g2 ∈ G, P1(g1|O) > P1(g2|O) iff P2(g1|O) > P2(g2).

Proof. From Observation 1, P1(g1|O) > P1(g2|O) if and only if costdif1 (s, g1,O) < costdif1 (s, g2,O). Recall, from Equation (1), that for each i ∈ {1, 2}:

where the first term can be written as:

4 We previously used the term "observation-free". However, the method does depend on observing one location (usually the agent's current location) with respect to which probabilities are required.

Let nl = O|O| be the last observation in O. From Observation 1, recall that the relative ranking between g1 and g2 with respect to their posterior probabilities can be deduced directly from the relative value of their cost difference formulas. So, let us expand that value:

costdif1 (s, g1, O) - costdif1 (s, g2, O) = [optc(s, O0 ) + optc(O) + optc(nl, g1) - optc(s, g1)]- [optc(s, O0 ) + optc(O) + optc(nl , g2) - optc(s, g2)] = optc(s, O0 ) + optc(O) + optc(nl , g1) - optc(s, g1)- optc(s, O0 ) - optc(O) - optc(nl , g2) + optc(s, g2) = optc(nl, g1) - optc(s, g1) - optc(nl, g2) + optc(s, g2) = [optc(nl, g1) - optc(s, g1)] - [optc(nl, g2) - optc(s, g2)] = costdif2 (s, g1, nl) - costdif2 (s, g2, nl).

It follows then that costdif1 (s, g1,O) > costdif1 (s, g2,O) iff costdif2 (s, g1, O) > costdif2 (s, g2, O). Thus, from Observation 1, P1(g1|O) > P1(g2|O) iff P2(g1|O) > P2(g2). □

The finding is useful and unexpected. All parameters are independent of the observation sequence (modulo where the agent is "now") and can be obtained using a standard pathplanner: no specialised path-finding system is needed to reason about observations. Furthermore, if all start and candidate goal locations are known-as would typically be the case in most domains-formula costdif2 (s, g, n) can be fully precomputed offline for any node n ∈ N in the domain.

The implications are significant. We can create a sort of "heat map" of the domain, showing the probability of each goal according to where the agent entered. If we have a goal of interest (e.g., a valuable location to monitor and protect), we can focus attention fully on locations where that goal becomes the most probable. That is, rather than tracking an agent's movements all over the terrain, we can just monitor the "hot" spots and only start tracking her in earnest if she arrives at one of them.

We close by noting that the above result is not dependent on formula (RG4) but is applicable whatever manipulation is used to derive the probability distribution, provided it satisfies the property that the lower the cost difference, the higher the probability, and relative cost differences are preserved.

5 Experimental Results

We tested formulas (RG3), (1) and (2) on 990 problems adapted from the well-known Moving-AI 5 path-planning benchmarks [Sturtevant, 2012] to confirm (a) that the case of exclusive optimality (as in Theorem 3) is rare and that otherwise the simpler formula yields identical posterior probability distributions to the more complex formula; (b) that all three accounts return posterior probability distributions that rank goals the same; and (c) using either of the modified formulas presented here cuts processing time by more than half.

We adapted the Moving-AI problems for GR by adding candidate goals at random locations, used Weighted-A* [Pohl, 1970] to generate a continuous path to the real goal then extracted observation sequences varied by: path quality (optimal, suboptimal, greedy), observation density (sparse 20%, medium 50%, dense 80%) and distribution (random locations along the path or a consecutive prefix beginning at the start).

5 http://movingai.com/

156 problems. Average goals: 4.35. Average path cost: 280.74. ∆ displays average difference for non-matches. We obtain P ∗ 2 as P2 but adding a constant to each cost difference.

We calculated optimal path costs using standard A* [Hart et al., 1968] 6 and obtained optimal costs "given not the observations" by modifying A* so that it pruned from consideration any path that encountered all observed locations.

Our results confirmed the hypotheses. Importantly, the corner case-where observations conform to the only optimal path-did not arise in any randomly generated scenario. Table 1 summarises a representative subset of our results. We found that formula (RG3) performed even more slowly than expected (perhaps reflecting the calculation's inherent complexity): in some cases the simpler formula (1) performed twelve times faster. Probabilities based on formula (1) always exactly matched those based on (RG3); probabilities generated using formula (2) were usually different but in all cases use of the single-observation formula successfully identified the same goal as having the highest, or equal highest, posterior probability as either other formula.

6 Conclusion

We have examined GR techniques introduced by Ramirez and Geffner (2010) and applied them in the context of pathplanning. We have shown that a simpler cost difference formula returns an identical result to the original in all but one case, which we characterise. We argue, in line with intuitions expressed in [Ramirez and Geffner, 2010], that this is a case of little interest and, in fact, it did not even arise in automated tests. Further, we have presented an alternative formula (2) that does not depend on the observation sequence but nevertheless generates a posterior probability distribution that exactly preserves the ranking of goals from the simplified account and, by extension, results in an identical ordering to formula (RG3) in all cases bar one. This formula has the benefit that it can be pre-computed in many realistic domains. So one can create a sort of "heat map" of posterior goal probabilities from which to identify a perimeter that should be monitored around any goal of interest, knowing that, at all locations within the perimeter, that goal is the most probable.

Acknowledgements

Australian Research Council (DP120100332) and Australian Government Research Training Program Scholarship.

6 We used a Python-based infrastructure, designed as a testbed for path-planning algorithms, which already included implementations of A* and Weighted A* in its library (https://tinyurl.com/p4sim).