--- title: "New Metrics and Algorithms for Stochastic Goal Recognition Design Problems" authors: - "Christabel Wayllace" - "Ping Hou" - "William Yeoh" doi: "10.24963/ijcai.2017/622" url: "https://ijcai.org/proceedings/2017/622" pdf: "https://ijcai.org/proceedings/2017/0622.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "4455-4462" track: "Main track" keywords: - "Planning and Scheduling: Markov Decisions Processes" - "Planning and Scheduling: Activity and Plan Recognition" --- # New Metrics and Algorithms for Stochastic Goal Recognition Design Problems Christabel Wayllace, Ping Hou, William Yeoh *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 4455-4462. DOI: [10.24963/ijcai.2017/622](https://doi.org/10.24963/ijcai.2017/622) ## Abstract Goal Recognition Design (GRD) problems involve identifying the best ways to modify the underlying environment that agents operate in, typically by making a subset of feasible actions infeasible, in such a way that agents are forced to reveal their goals as early as possible. The Stochastic GRD (S-GRD) model is an important extension that introduced stochasticity to the outcome of agent actions. Unfortunately, the worst-case distinctiveness (wcd) metric proposed for S-GRDs has a formal definition that is inconsistent with its intuitive definition, which is the maximal number of actions an agent can take, in the expectation, before its goal is revealed. In this paper, we make the following contributions: (1) We propose a new wcd metric, called all-goals wcd (wcdag), that remedies this inconsistency; (2) We introduce a new metric, called expected-case distinctiveness (ecd), that weighs the possible goals based on their importance; (3) We provide theoretical results comparing these different metrics as well as the complexity of computing them optimally; and (4) We describe new efficient algorithms to compute the wcdag and ecd values. ## Full text ## 1 Introduction Discovering the objective of an agent based on observations of its behavior is a problem that has interested both AI and psychology researchers for many years [Schmidt et al., 1978; Kautz, 1987]. In AI, this problem is known as goal recognition or, more generally, plan recognition [Sukthankar et al., 2014], and it has been used to model a number of applications ranging from software personal assistants [Oh et al., 2010; 2011a; 2011b]; robots that interact with humans in social settings such as homes, offices, and hospitals [Tavakkoli et al., 2007; Kelley et al., 2012]; intelligent tutoring systems that recognize sources of confusion or misunderstanding ∗This research is partially supported by NSF grant 1550662. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the sponsoring organizations, agencies, or the U.S. government. ## William Yeoh Computer Science Department New Mexico State University Las Cruces, NM 88003, USA wyeoh@cs.nmsu.edu in students through their interactions with the system [McQuiggan et al., 2008; Johnson, 2010; Lee et al., 2012; Min et al., 2014]; and security applications that recognize the plan or goal of terrorists [Jarvis et al., 2005]. Researchers have recently introduced a newly formulated problem that is aimed towards helping the objective of goal recognition by performing an offline analysis of the model. The problem, proposed by Keren et al. [2014], is called goal recognition design (GRD) and it is intended to reduce the complexity of the online goal recognition task by modifying the underlying environment that the agent operates in. The goal is to find a subset of modifications that forces the agent to reveal its goal as early as possible. This problem finds itself relevant in many of the same applications of goal recognition because, typically, the underlying environment can be easily modified. Buoyed by this new model, researchers have extended the GRD problem to a number of extensions with accompanying algorithms to solve them [Keren et al., 2015; 2016a; 2016b; 2017; Son et al., 2016]. One of these extensions is the Stochastic GRD (S-GRD) problem, where the outcomes of the agent's actions are stochastic [Wayllace et al., 2016]. In all these problems, the "goodness" of a solution is measured using the worst-case distinctiveness (wcd) metric, which, intuitively, measures the maximal number of actions an agent can take before its goal is revealed. Unfortunately, the formal wcd definition proposed by Wayllace et al. [2016] for S-GRDs is inconsistent with this intuitive definition; we provide an example later in Section 3.1 that highlights this inconsistency. Based on this finding, we propose a new wcd metric, called all-goals wcd (wcdag), that remedies this inconsistency as well as new efficient algorithms to compute them. Additionally, another deficiency of the existing wcd metric for all GRD variants is its implicit assumption that there is no prior information about the agent's true goal. While this assumption is reasonable in many problems, it may be the case that this information is available in some applications, thereby allowing the observer to assign different weights to the possible goals. We thus propose a new metric for S-GRDs, called the expected-case distinctiveness (ecd), that weighs the length of a path to a goal by the likelihood of that goal being the true goal. 1 This new ecd metric will thus allow practitioners to better incorporate domain knowledge into the S-GRD model and, combined with the updated wcd metric, will allow them to better understand the tradeoffs between different S-GRD solutions. 1 While we only describe this metric for S-GRDs, it can be easily extended for other GRD variants as well. ## 2 Background ## 2.1 Markov Decision Process (MDP) A Stochastic Shortest Path Markov Decision Process (SSPMDP) [Mausam and Kolobov, 2012] is represented as a tuple 〈S, s0,A,T,C,G〉. It consists of a set of states S; a start state s0 ∈ S; a set of actions A; a transition function T : S × A × S → [0, 1] that gives the probability T (s, a, s′ ) of transitioning from state s to s′ when action a is executed; a cost function C : S × A × S → R that gives the cost C(s, a, s′ ) of executing action a in state s and arriving in state s′ ; and a set of goal states G ⊆ S. The goal states are terminal, that is, T(g, a, g) = 1 and C(g, a, g) = 0 for all goal states g ∈ G and actions a ∈ A. An SSP-MDP must also satisfy the following two conditions: (1) There must exist a proper policy, which is a mapping from states to actions with which an agent can reach a goal state from any state with probability 1. (2) Every improper policy must incur an accumulated cost of ∞ from all states from which it cannot reach the goal with probability 1. In this paper, we will focus on SSP-MDPs and will thus use the term MDPs to refer to SSP-MDPs. A "solution" to an MDP is a policy π, which maps states to actions. Solving an MDP is to find an optimal policy, that is, a policy with the smallest expected cost. Finally, we use the term "optimal actions" to refer to actions in an optimal policy. ## 2.2 Value Iteration (VI) and Topological VI (TVI) Value Iteration (VI) [Bellman, 1957] is one of the fundamental algorithms to find an optimal policy. It uses a value function V to represent expected costs. The expected cost of an optimal policy π∗ for the starting state s0 ∈ S is the expected cost V (s0), and the expected cost V (s) for all states s ∈ S is calculated using the Bellman equation [Bellman, 1957]: The action chosen by the policy for each state s is then the one that minimizes V (s). VI suffers from a limitation that it updates each state in every iteration even if the expected cost of some states have converged. Topological VI (TVI) [Dai et al., 2011] addresses this limitation by repeatedly updating the states in only one strongly connected component (SCC) until their values converge before updating the states in another SCC. Since the SCCs form a directed acyclic graph, states in an SCC only affect the states in upstream SCCs. Thus, by choosing the SCCs in reverse topological sort order, it no longer needs to consider SCCs whose states have converged in a previous iteration. ## 2.3 Goal Recognition Design (GRD) and Stochastic GRD (S-GRD) A Goal Recognition Design (GRD) problem [Keren et al., 2014] is represented as a tuple P = 〈D,G〉, where D = 〈S, s0,A,T,C〉 captures the domain information and G is a set of possible goal states of the agent. The elements in the tuple D are as they are described in MDPs, except that the transition function T is deterministic and the cost function C is restricted to positive costs. 2 In this paper, we assume that the cost of all actions is 1 for simplicity. The worst case distinctiveness (wcd) of problem P is the length of a longest sequence of actions π = 〈a1, . . . , ak〉 that is the prefix in cost-minimal plans π∗ g1 and π∗ g2 to distinct goals g1, g2 ∈ G. Intuitively, as long as the agent executes π, it does not reveal its goal to be either g1 or g2. The objective in GRD is to find a subset of actions such that if they are removed from the domain, the wcd of the resulting problem is minimized. This optimization problem is subject to the requirement that the cost of cost-minimal plans to achieve each goal g ∈ G is the same before and after removing the subset of actions. A Stochastic Goal Recognition Design (S-GRD) problem [Wayllace et al., 2016] is an extension of a GRD problem that assumes the actions executed by the agent have stochastic outcomes. It is represented as a tuple P = 〈D,G〉, where, like in GRDs, D = 〈S, s0, A, T, C〉 captures the domain information and G is a set of possible goal states of the agent. The elements in the tuple D are as they are described in GRDs, except that the transition function T is now stochastic. The worst case distinctiveness (wcd) of problem P is the largest expected cost incurred by the agent over all nondistinctive policy prefixes. A non-distinctive policy prefix is an optimal policy common to a pair of goals. Like in GRDs, the objective in S-GRD is to find a subset of actions ˆA∗ ⊂ A such that if they are removed from the set of actions A, then the wcd of the resulting problem is minimized. This optimization problem is subject to the requirement that the expected cost of the optimal policies to achieve each goal g ∈ G is the same before and after removing the subset of actions and that the number of reduced actions is less than or equal to a user-defined parameter k. More specifically, the objective is to find: where ˆ P = 〈 ˆD,G〉 is the problem with domain ˆD = 〈S, s0,A \ ˆA,T,C〉 after removing actions ˆA, π∗ g is an optimal policy to achieve goal g in the original problem P, and ˆπ∗ g is an optimal policy to achieve goal g in problem ˆ P . ## 3 Redefining the wcd Metric for S-GRDs The intuition behind the worst case distinctiveness (wcd) is that it measures the longest path (i.e., a path with the largest cost) an agent can take without revealing its goal. Figure 1 illustrates a small example, where the agent starts at state s0 and has one of three possible goals g0, g1, or g2. 2 The domain information D was originally described by Keren et al. [2014] using a classical planning model [Geffner and Bonet, 2013]. Figure 1: Example ![Image](https://ijcai.org/proceedings/2017/fulltext/622/image_000000_c64f58343345534e8dc21cfe0497fdec17a104c933bfb3df9397b4523d316ed6.png) All actions are deterministic except for action a0 out of s0, which can transition to either s1 or s2 with equal probability. All actions also have the same cost of 1. In this example, there are two possible paths, each with two actions, that the agent can take before it has to reveal its goal in the third action. The two paths are denoted by bold arrows in the figure. For the first path, starting at s0, the agent has to take action a0 as it is the only action available. If it transitions to s1, then it can take action a1 to transition to s2. At this point, its goal can be either g1 or g2. From s2, it reveals its goal to be g1 if it takes action a2 and goal g2 if it takes action a3. Note that its goal cannot be g0 as it would otherwise have taken action a4 instead of a1 when it was in s1. For the second path, starting at s0, the agent may transition to s2 after taking action a0. Then, it can take action a3 to transition to s3, at which point its goal can be either g0 or g2. From s3, it reveals its goal to be g0 if it takes action a5 and goal g2 if it takes action a6. Note that the cost of both paths is 2 since they both have two actions each. Consequently, the wcd of this problem should be 2 intuitively. However, using the wcd definition proposed by Wayllace et al. [2016], the wcd is 1.5! Therefore, we now describe the reason for this inconsistency and propose a new updated definition for wcd that is more in line with its intuitive definition. Wayllace et al. [2016] defined the wcd as "the largest expected cost to reach a boundary state from the start state over all possible non-distinctive policy prefixes," where for a pair of distinct goals gi and gj, (1) a non-distinctive policy prefix is an optimal policy common to those two goals, and (2) boundary states are states where an agent, through its next action, will reveal its goal to be either one of those two goals. Figure 2(a) shows the same example again but with the non-distinctive policy prefixes for pairs of goals 〈g0, g2〉. Here, s1 and s3 are boundary states (shaded in grey), and the expected cost of this policy prefix is 1.5 (= 0.5 ∗ 1+0.5 ∗ (1 + 1)). Figures 2(b) and 2(c) show the same example but for pairs of goals 〈g0, g1〉 and 〈g1, g2〉, respectively. The expected cost is 1 for the former and 1.5 for the latter. The wcd of this problem is thus 1.5, the largest expected cost over all pairs of goals. This definition fails to capture the intuitive paths of cost 2 because it considers only pairs of goals in its wcd, nondistinctive policy prefix, and boundary state definitions. Instead, it needs to consider a tuple of all goals in its definitions. For example, for the pair of goals 〈g0, g2〉, s1 is a boundary state and s2 is a regular state in a non-distinctive policy prefix (i.e., the agent reveals its goal when taking an action from s1 but may conceal its goal when taking an action from s2). In contrast, for the pair 〈g1, g2〉, the situation is reversed, where s2 is a boundary state and s1 is a regular state in a non-distinctive policy prefix. Therefore, when considering all three goals, neither s1 nor s2 are actual boundary states. In other words, the agent can still conceal its goal to be either g1 or g2 in state s1 or either g0 or g2 in state s2. The definition of Wayllace et al. [2016] fails to capture this scenario. ## 3.1 All-Goals wcd (wcdag) We now propose a new wcd definition, called All-Goals wcd (wcdag), that captures the above scenario and is more consistent with its intuitive definition. In addition to the need to consider all goals at the same time instead of pairs of goals, we also make another key observation: that the set of possible goals for a particular state can differ based on the observed path of the agent to that state. Using Figure 1 as an example again, if the agent arrives at state s3 through path 〈s0, s2, s3〉, then its goal is either g0 and g2. However, if it arrives at state s3 through path 〈s0, s1, s2, s3〉, then its goal is definitely g2. This observation causes a challenge in that, unlike the previous wcd definition, the set of possible goals of the agent in this new definition is no longer Markovian as it depends on the entire history of states visited. We address this challenge by modeling the problem using augmented MDPs instead of regular MDPs, where each augmented state in the augmented MDP is a tuple 〈s,G′ 〉 that consists of the actual state s of the MDP and the set of goals G′ ⊆ G that are possible goals for that state. Therefore, in the scenario above, we will have two different augmented states 〈s3, {g0, g2}〉 and 〈s3, {g2}〉, and different actions can be attributed to the two augmented states. In this augmented MDP formulation, the set of possible goals of the agent is now Markovian again. We now describe the other elements of this augmented MDP, defined as the tuple 〈˜S, ˜ s0, ˜A, ˜T, ˜C, ˜G〉, and how to construct them from S-GRDs, whose domain information is modeled as regular MDPs. The augmented start state is now ˜ s0 = 〈s0,G〉, where s0 is the start state and G is the set of all possible goals in the S-GRD problem. Each augmented action ˜a ∈ ˜A is a tuple 〈a,G′ 〉, where a ∈ A is an action in the regular MDP and G′ is the set of all goals for which that action is an optimal action. The new transition function ˜T : ˜S × ˜A× ˜S → [0, 1] gives the probability ˜ T (˜ s, ˜a, ˜ s′ ) of transitioning from augmented state ˜ s to ˜ s′ when augmented action ˜a is executed. This transition probability equals the transition probability ˜ T (˜ s, ˜a, ˜ s′ ) = T(s, a, s′ ) in the regular MDP for ˜ s = 〈s,G′ 〉, ˜a = 〈a,G′′ 〉, and ˜ s′ = 〈s′ ,G′ ∩G′′ 〉 if |G′ ∩G′′ | > 1 and equals 0 otherwise. The cost function ˜ C : ˜ S × ˜ A× ˜ S →R+ gives the cost ˜ C(˜ s, ˜a, ˜ s′ ) of executing action ˜a in augmented state ˜ s and arriving in ˜ s′ . This cost equals the cost ˜ C(˜ s, ˜a, ˜ s′ ) = C(s, a, s′ ) for the same case for the transition probabilities above. Finally, the augmented goal states ˜G ⊆ ˜S are those augmented states 〈s,G′ 〉 that are boundary states - in other words, any augmented action from those states will transition to an augmented state 〈s′ ,G′′′ 〉 with one goal or no goals (i.e., |G′′′ | ≤ 1) in the regular MDP. We provide the formal definition for augmented MDPs below. Figure 2: wcd Example ![Image](https://ijcai.org/proceedings/2017/fulltext/622/image_000001_16998654610b234dd155b3ea515ebf8029e6717ab2fcc37facd59569c4c0275f.png) Figure 3: Reachable Augmented MDP ![Image](https://ijcai.org/proceedings/2017/fulltext/622/image_000002_23343cb9dbef701f4c03ad0610f6958600189520c5396618b0a94429510fc497.png) Definition 1 (AugmentedMDP) For an S-GRD problem P = 〈D, G〉 with domain information D = 〈S, s0, A, T, C〉, an augmented MDP is defined by a tuple 〈˜S, ˜ s0, ˜A, ˜T, ˜C, ˜G〉 that consists of the following: - a set of augmented states ˜S = 〈s,G′ 〉, where s ∈ S and G′ ⊆ G; - an augmented start state ˜ s0 = 〈s0, G〉; - a set of augmented actions ˜A = 〈a,G′′ 〉, where G′′ is the set of all goals for which a ∈ A is an optimal action; - a transition function ˜T : ˜S × ˜A× ˜S → [0, 1] that gives the probability ˜ T(〈s,G′ 〉, 〈a,G′′ 〉, 〈s′ ,G′ ∩G′′ 〉) of transitioning from augmented state 〈s,G′ 〉 to augmented state 〈s′ , G′ ∩G′′ 〉 when augmented action 〈a, G′′ 〉 is executed; this probability equals T(s, a, s′ ) if |G′ ∩ G′′ | > 1 and equals 0 otherwise; - a cost function ˜C : ˜S × ˜A× ˜S → R+ that gives the cost C(〈s, G′ 〉, 〈a, G′′ 〉, 〈s′ , G′ ∩G′′ 〉) = C(s, a, s′ ) of executing augmented action 〈a,G′′ 〉 in augmented state 〈s,G′ 〉 and arriving in augmented state 〈s′ ,G′ ∩G′′ 〉; and - the set of augmented goals ˜G ⊂ ˜S = {〈s,G′ 〉 | ∀ ˜ T(〈s,G′ 〉, 〈a,G′′ 〉, 〈s′ ,G′ ∩ G′′ 〉) > 0 ⇒ (|G′ | ≥ 2 ∧ |G′ ∩ G′′ | < 2)}. Figure 3 shows the reachable portion of the augmented MDP that corresponds to the regular MDP shown in Figure 1, where each node corresponds to an augmented state and each hyper-edge corresponds to an augmented action. The elements in the sets for a node/hyper-edge are the possible goals for that augmented state/action. Finally, the objective here is to find an augmented policy (i.e., a policy that maps augmented states to augmented actions) with the largest expected cost. Note that this objective is different from that in regular MDPs, which seek to find the policy with the smallest expected cost. Definition 2 (All-Goals wcd) The new All-Goals wcd (wcdag) of an S-GRD problem P is defined as: where ˜Π is the set of augmented policies in the augmented MDP and V˜π(˜ s0) is the expected cost for s0 with augmented policy ˜π computed recursively using Equation 4. Observe that Equation 3 is analogous to the brute force algorithm to solve an MDP [Mausam and Kolobov, 2012] that performs a policy evaluation over all enumerated policies to return the best policy. As Value Iteration (VI) is faster in regular MDPs, we aim to also optimize over the value function space in augmented MDPs. This value function optimization can be done using a Bellman-like equation: but note that it uses the maximization operator instead of the minimization operator for regular MDPs. This difference will cause an issue if there are infinite cost cycles, which are cycles in the graph where the optimal policy is to stay in the cycles and accumulate an infinite cost. Fortunately, our augmented MDP does not have infinite cost cycles, and Equation 5 will thus return the correct finite value upon convergence. These properties are formalized in Lemma 1 and Theorem 1, where proof sketches are provided. Lemma 1 The augmented MDP does not have infinite cost cycles. Proof Sketch: We prove that an infinite cost cycle between two augmented states cannot exist by contradiction. Assume that such a cycle exists. Thus, ˜ T (˜ s, ˜a, ˜ s′ ) + ˜ T (˜ s, ˜a, ˜ s) = 1 and ˜ T (˜ s′ , ˜a, ˜ s′ ) + ˜ T (˜ s′ , ˜a, ˜ s) = 1 for some augmented states ˜ s = 〈s,G1〉 and ˜ s′ = 〈s′ ,G2〉, and augmented actions ˜a = 〈a,G3〉 and ˜a′ = 〈a′ ,G4〉. Since they form an infinite cost cycle, then G1 = G2. Let g ∈ G1 be one of the possible goals. Then, there must exist the actions π∗ g (s) = a that transitions from s to s′ , and π∗ g (s′ ) = a′ that transitions from s′ to s in the optimal policy π∗ g for goal g, which forms an infinite cost cycle in the optimal policy. This is not possible for optimal policies of SSP-MDPs [Mausam and Kolobov, 2012], which contradicts our assumption. Theorem 1 wcdag = V ∗ ˜π (˜ s0), which can be computed recursively via Equation 5. Proof Sketch: Equation 5 is, like the original Bellman equation [Bellman, 1957], a contracting operator. As such, it will eventually converge to the true optimal value. The only exception is if there are infinite cost cycles, which will cause the value of some states to converge to infinity. However, since there are no infinite cost cycles in our augmented MDP (Lemma 1), they will converge to finite values. Theorem 2 wcdag ≥ wcd as defined by Wayllace et al. [2016]. Proof Sketch: One can view the augmented MDP for wcdag as a union of all the augmented MDPs for regular wcd. For example, the subgraph formed by the actions in bold and their predecessor and successor states of Figure 1 is a union of all three subgraphs in Figure 2. Since both definitions of wcdag and wcd maximizes the expected cost in their respective subgraphs, it must be the case that wcdag ≥ wcd since the subgraph of the former is a union of all the subgraphs for the latter. Corollary 1 If there are only two possible goals in the SGRD, then wcdag = wcd. ## 4 Expected-Case Distinctiveness (ecd) An implicit assumption made by the worst-case distinctiveness (wcd) metric is that there is no prior information on which is the true agent's goal. While this assumption is reasonable in many problems, it may be the case that some information is available. For example, in human-computer interaction applications, user profiles may be used to assign different weights to each goal, where the weights correspond to the prior probabilities of an agent choosing its goal. Further, it may often be the case where the wcd cannot be reduced (i.e., the longest non-distinctive path cannot be shortened). However, other shorter non-distinctive paths can be shortened. Thus, intuitively, one should prefer the solution that shortens the shorter non-distinctive paths. In such a scenario, the wcd metric fails to distinguish between these solutions as the wcd remains the same in both cases. This situation is further exacerbated when the longest path are to goals with low weights! Therefore, in response to these two observations, we propose a new metric, called the expected-case distinctiveness (ecd), for S-GRDs that weighs the length of a path to a goal by the probability of an agent choosing that goal and takes the sum of all the weighted path lengths. ## Definition 3 (expected-case distinctiveness) (7) where wi > 0 is the probability of the agent choosing goal gi and Z is the normalization constant such that ∑˜a∈˜A P(˜a) = 1. Intuitively, Equation 8 associates a probability P(˜a) to each augmented action ˜a based on the number of goals for which that action is an optimal action as well as the probabilities of those goals being the true goal. Then, Equation 7 recursively defines the expected cost of each augmented state ˜ s based on the probability of each augmented action and the expected cost of each successor state. Finally, the ecd of the problem is the expected cost of the augmented start state. This definition also has the added benefit that the ecd computation is straightforward and efficient. The runtime to compute it is similar to the runtime of VI as it requires multiple iterations of a Bellman-like equation until the expected costs of all states have converged. Proof Sketch: wcdag is the expected cost of the worst policy to reach an augmented goal state in the augmented MDP, while ecd is the expected cost over all policies. Therefore, ecd(P ) ≤ wcdag (P ) Corollary 2 If there is exactly one policy in the augmented MDP, then ecd(P) = wcdag(P). ## 5 Algorithms To compute the wcdag and ecd of each problem, one can use a VI-like algorithm that runs iterations of the Bellmanlike update of Equations 5 and 7, respectively. Additionally, we make the observation that the augmented state space of the augmented MDP can often be segmented into strongly connected components (SCCs) - each SCC contains the augmented states with the same set of possible goals, and the set of possible goals is non-increasing. Therefore, we also propose a TVI-like algorithm that uses Tarjan's algorithm [Tarjan, 1972] to segment the augmented state space into SCCs first before running VI on each SCC in reverse topological order. This should significantly speed up the solving time if there are large numbers of SCCs, but may have the opposite effect if there are few SCCs due to the overhead incurred by Tarjan's algorithm. Optimally computing wcdag is P-complete in the number of reachable augmented states as it is equivalent to optimally solving an augmented MDP, which is P-complete [Mausam and Kolobov, 2012]. Optimally computing ecd is easier as it is equivalent to evaluating a single policy in the augmented MDP. It is thus in P, but not P-hard. Similar to Wayllace et al. [2016], to reduce the wcdag or ecd of a problem, we enumerate through all possible combinations of actions to remove, compute the resulting wcdag or ecd, and store the best solution. Additionally, we can use Theorem 4 to make useful inferences. Theorem 4 If there are no combination of k actions in an S-GRD that can reduce its ecd, then there are also no such combinations that can reduce its wcdag. Table 1: Experimental Results for k = 1 | Domain Instances | Domain Instances | wcdag - Reduction | Runtime (s) - ENUM | Runtime (s) - VI | Runtime (s) - TVI | wcd - Reduction | Runtime (s) R-W(O) | ecd - Reduction | Runtime (s) - VI | Runtime (s) - TVI | |-----------------------|--------------------|---------------------|----------------------|--------------------|---------------------|-------------------|----------------------|-------------------|--------------------|---------------------| | ROOM | 8-8-3 | 6.2 → 6.2 | 1 | 1 | 1 | 6.0 → 6.0 | 1 | 6.2 → 6.2 | 1 | 1 | | ROOM | 32-32-2 | 86.6→86.6 | 184 | 101 | 85 | 86.6→86.6 | 18,526 | 86.6→86.6 | 98 | 86 | | ROOM | 32-32-3 | 86.6→86.6 | 324 | 164 | 140 | 86.6→86.6 | 38,367 | 86.6→86.6 | 161 | 156 | | ROOM | 44-44-5 | 73.8→73.8 | timeout | 946 | 878 | 73.8→73.8 | 16,959 | 73.8→73.8 | 923 | 928 | | GRID-NA- VIGATION | 5-5-3 | 4.4 → 3.3 | 1 | 1 | 1 | 4.4 → 3.3 | 1 | 3.7 → 2.9 | 1 | 1 | | GRID-NA- VIGATION | 4-12-3 | 10→10 | timeout | 3 | 3 | 10 → 10 | 789 | 10 → 8.9 | 3 | 3 | | GRID-NA- VIGATION | 4-12-3 | 5.6 → 5.6 | 13 | 3 | 3 | 5.6 → 5.6 | 4 | 4.9 → 4.4 | 3 | 3 | | GRID-NA- VIGATION | 4-12-3 | 6.7 → 5.6 | 18 | 3 | 3 | 6.7 → 5.6 | 4 | 6.7 → 5.1 | 3 | 3 | | GRID-NA- VIGATION | 4-12-6 | 13.3→12.2 | timeout | 3 | 3 | 13.3→12.2 | 25 | 9.4 → 9.1 | 4 | 4 | | BLOCKS- WORLD | 5-3 | 1.3 → 1.3 | 1 | 2 | 1 | 1.3 → 1.3 | 1 | 1.3 → 1.3 | 1 | 1 | | BLOCKS- WORLD | 6-5 | 4.9 → 4.9 | 582 | 575 | 626 | - | timeout | 3.7 → 3.7 | 644 | 659 | | BLOCKS- WORLD | 6-3 | 3.4 → 3.4 | 374 | 351 | 353 | - | timeout | 3.1 → 3.1 | 379 | 378 | | COLORED BLOCKS- WORLD | 3-2-2 | 2.8 → 2.8 | 1 | 1 | 1 | 2.8 → 2.8 | 1 | 2.8 → 2.8 | 1 | 1 | | COLORED BLOCKS- WORLD | 5-2-3 | 4.1 → 4.1 | 20 | 17 | 17 | 4.1 → 4.1 | 19 | 4.1 → 4.1 | 16 | 17 | | COLORED BLOCKS- WORLD | 5-3-3 | 4.9→3.5 | timeout | 16 | 17 | - | timeout | 4.9 → 3.5 | 18 | 18 | | COLORED BLOCKS- WORLD | 6-2-3 | 14.6→14.6 | timeout | 390 | 390 | - | timeout | 10.2→8.3 | 406 | 414 | | COLORED BLOCKS- WORLD | 6-3-3 | 6.3→5.3 | timeout | 408 | 420 | - | timeout | 5.9 → 5.3 | 410 | 420 | | BOXWORLD | 2-1-1-5-3 | 4.1→4.1 | 29 | 29 | 32 | 4.1 → 4.1 | 30 | 4.1 → 4.1 | 33 | 32 | | BOXWORLD | 2-1-1-6-3 | 4.3→4.3 | 10 | 10 | 10 | 4.1 → 4.1 | 10 | 4.3 → 4.3 | 12 | 9 | | BOXWORLD | 3-1-1-6-3 | 5.2→5.2 | 413 | 414 | 402 | 4.9 → 4.9 | 414 | 5.2 → 5.2 | 398 | 478 | | BOXWORLD | 3-1-1-6-5 | 8.1→8.1 | 653 | 642 | 404 | 7.3 → 7.3 | 593 | 7.8 → 7.8 | 400 | 593 | | BOXWORLD | 3-2-1-6-3 | 5.2→5.2 | 50,204 | 49,028 | 48,955 | 5.2 → 5.2 | 49,082 | 5.2→5.2 | 49,003 | 48,861 | Proof Sketch: Since the ecd is the expected cost over all policies in the augmented MDP, if it cannot be reduced, then it must mean that every policy in the augmented MDP for the original problem cannot be modified; modifying them would affect the optimal cost to one of the possible goals in the regular MDP. And since all policies cannot be modified, the wcdag, which is the expected cost of the worst policy, will also remain unchanged. ## 6 Experimental Results The first domain is called ROOM, which is used in the NonDeterministic Track of the 2006 ICAPS International Planning Competition. 3 It is a grid world where the actions as well as the transition probabilities are defined individually for each state. The actions allow the agent to move in the four cardinal directions but after taking one action the agent has some probability to end up in other adjacent cells including a diagonal one. Each instance of this domain is defined by the x- and y-dimensions of the room and the number of possible goals. The second domain, GRID-NAVIGATION, is also a grid world where the transitions are defined equally for all the states; the agent has a 90% probability to move to a cell indicated by the deterministic outcome of the action and a 10% probability to stay in the same cell. The instances are defined in the same way as in the ROOM domain. 3 http://idm-lab.org/wiki/icaps/ipc2006/probabilistic/ The remaining domains were used in the Probabilistic Track of 2004 ICAPS International Planning Competition: 4 BLOCKSWORLD is the traditional domain with a 25% probability of slippage each time a block is picked up or put down; the goal state defines the last position of every block. Each instance is defined by the number of blocks and the number of possible goals. COLORED-BLOCKSWORLD is a modification of BLOCKSWORLD where each block has a color and the goal is specified in terms of colors. Thus, more than one state can represent the same goal. Instances in this domain are defined by the number of blocks, number of colors, and number of goals. BOXWORLD is a modified LOGISTICS domain where the only action that introduces noise is "drive-truck" and there is a 20% probability that the truck ends up in one of three wrong cities. Each instance in this domain is defined by the number of boxes, trucks, airplanes, cities and goals. Tables 1 and 2 tabulate the results when the number of actions that can be blocked (k) is 1 and 2, respectively. The experiments were conducted on a 3.1GHz quad-core machine with 6GB of RAM and we imposed a timeout of 2 days. We compared three algorithms to compute the wcdag: ENUM, which explicitly enumerates through all policies using Equation 4 and both VI and TVI as described in Section 5. We also computed the wcd using the REDUCE-WCD algorithm with optimization [Wayllace et al., 2016] (labeled as R-W(O)). To compute the ecd, we only compared VI and TVI because explicit enumeration of policies is not needed as it is equivalent to evaluating a single policy. Finally, we assumed that all goals have equal weights when computing the ecd in order to have a fair comparison with wcdag. 4 http://www.cs.rutgers.edu/∼mlittman/topics/ipc04-pt/ Table 2: Experimental Results for k = 2 | Domain - Instances | Domain - Instances | wcdag - Reduction | Runtime (s) - ENUM | Runtime (s) - VI | Runtime (s) - TVI | wcd - Reduction | Runtime (s) R-W(O) | ecd - Reduction | Runtime (s) - VI | Runtime (s) - TVI | |-----------------------|----------------------|---------------------|----------------------|--------------------|---------------------|-------------------|----------------------|-------------------|--------------------|---------------------| | ROOM | 8-8-3 | 6.2 → 6.2 | 7 | 8 | 8 | 6.0 → 6.0 | 6.4 | 6.2 → 6.2 | 8 | 8 | | ROOM | 32-32-2 | 86.6→86.6 | 234,126 | 50,609 | 40,303 | - | timeout | 86.6→86.6 | 47,690 | 42,057 | | ROOM | 32-32-3 | 86.6→86.6 | timeout | timeout | 78,245 | - | timeout | 86.6→86.6 | 85,417 | 84,134 | | ROOM | 44-44-5 | - | timeout | timeout | timeout | - | timeout | - | timeout | timeout | | GRID-NA- VIGATION | 5-5-3 | 4.4 → 2.2 | 2 | 1 | 1 | 4.4 → 2.2 | 1 | 3.7 → 2.2 | 1 | 1 | | GRID-NA- VIGATION | 4-12-3 | 10→8.9 | timeout | 14 | 5 | 10 → 8.9 | 13,739 | 10 → 7.8 | 12 | 5 | | GRID-NA- VIGATION | 4-12-3 | 5.6 → 4.4 | 246 | 5 | 5 | 5.6 → 4.4 | 8 | 4.9 → 3.9 | 6 | 6 | | GRID-NA- VIGATION | 4-12-3 | 6.7 → 4.4 | 418 | 5 | 5 | 6.7 → 4.4 | 32 | 6.7 → 4.4 | 5 | 6 | | GRID-NA- VIGATION | 4-12-6 | 13.3→12.2 | timeout | 7 | 7 | 13.3→12.2 | 8,095 | 9.4 → 8.4 | 8 | 8 | | BLOCKS- WORLD | 5-3 | 1.3 → 1.3 | 2 | 2 | 1 | 1.3 → 1.3 | 2 | 1.3 → 1.3 | 1 | 1 | | BLOCKS- WORLD | 6-5 | 4.9→4.9 | 10,883 | 10,836 | 9,832 | - | timeout | 3.7 → 3.7 | 9,586 | 10,313 | | BLOCKS- WORLD | 6-3 | 3.4 → 3.4 | 6,776 | 6,721 | 5,027 | - | timeout | 3.1 → 3.1 | 4,464 | 4,368 | | COLORED BLOCKS- WORLD | 3-2-2 | 2.8 → 2.8 | 1 | 1 | 1 | 2.8 → 2.8 | 1 | 2.8 → 2.8 | 1 | 1 | | COLORED BLOCKS- WORLD | 5-2-3 | 4.1→2.8 | timeout | 448 | 429 | - | timeout | 4.1 → 2.8 | 453 | 426 | | COLORED BLOCKS- WORLD | 5-3-3 | 4.9→3.5 | timeout | 380 | 385 | - | timeout | 4.9 → 3.5 | 383 | 393 | | COLORED BLOCKS- WORLD | 6-2-3 | 14.6→14.6 | timeout | 17,539 | 16,553 | - | timeout | 10.2→7.9 | 16,665 | 17,378 | | COLORED BLOCKS- WORLD | 6-3-3 | 6.3→5.3 | timeout | 16,778 | 16,132 | - | timeout | 5.9→5.3 | 15,667 | 16,888 | | | 2-1-1-5-3 | 4.1→4.1 | 43 | 37 | 128 | 4.1 → 4.1 | 56 | 4.1 → 4.1 | 133 | 132 | | | 2-1-1-6-3 | 4.3→4.3 | 51 | 51 | 14 | 4.1 → 4.1 | 17 | 4.3 → 4.3 | 14 | 14 | | | 3-1-1-6-3 | 5.2→5.2 | 1,011 | 976 | 482 | 4.9 → 4.9 | 519 | 5.2 → 5.2 | 667 | 584 | | BOXWORLD | 3-1-1-6-5 | 8.1→8.1 | 12,003 | 1,164 | 735 | 7.3 → 7.3 | 823 | 7.8 → 7.8 | 738 | 736 | | | 3-2-1-6-3 | 5.2→5.2 | 57,807 | 53,001 | 55,788 | 5.2 → 5.2 | 75,546 | 5.2→5.2 | 59,778 | 59,715 | We make the following observations: - As expected, when k increases, the runtimes increased but the wcdag and ecd were reduced in more instances. In the ROOM, BLOCKSWORLD, and BOXWORLD domains, the wcdag and ecd remained unchanged. The reason is that, in all three domains, each goal has only very few (either 1 or 2) optimal policies and removing any action that affects these policies will increase the expected cost to that goal, which is prohibited by the definition of S-GRDs. - In general, consistent with the trends in regular MDPs with multiple SCCs [Dai et al., 2011], TVI is often faster than VI, which is faster than ENUM. The reason is that TVI does not need to perform Bellman updates on states outside the SCC being considered, thereby reducing the runtime of each iteration. - Computing wcdag is up to three orders of magnitude faster than computing wcd. The reason is that the wcd computation needs to iterate through all possible pairs of goals and all possible enumerated policies, each of which must be solved via VI, while the wcdag computation solves the whole problem in a single shot via VI or TVI. The wcdag and wcd values are the same in all instances except for four instances, indicating that the wcd metric is intuitively correct except for those four instances. - There are several instances where the ecd is reduced but the wcdag remains unchanged. The reason is that it is possible to shorten some of the paths to the goals before the agent is forced to reveal its action, but not the longest path. There- fore, one can use ecd as a tie-breaking metric between two solutions with identical wcdag values, which is important given that wcdag usually remains unchanged for small values of k. ## 7 Conclusions and FutureWork The Stochastic Goal Recognition Design (S-GRD) model is an important variant of the GRD model. Unfortunately, the original wcd metric proposed has a formal definition that is inconsistent with its intuitive definition. Further, the wcd definitions for all the GRD variants make the implicit assumption that all goals have equal likelihood of being the true goal, which is unrealistic in many practical applications. Therefore, in this paper, we proposed a new wcd metric, called allgoals wcd (wcdag), that remedies the inconsistency above as well as a new expected-case distinctiveness (ecd) metric that weighs the possible goals based on their likelihood of being the true goal. We further show the complexity of computing these metrics and introduced efficient algorithms to compute them. Experimental results show that it is possible to reduce the ecd in several cases where the wcdag remained unchanged. This result highlights the need for more metrics that can be better used by practitioners to trade off the different possible solutions. Future work includes the generalization of the ecd metric to the other GRD variants as well as the investigation of heuristic search techniques to compute the wcdag and ecd values. We suspect that such techniques may be useful in cases one can prune significant portions of the search space due to the differences in the weights of the goals. ## References 1. [Bellman, 1957] Richard Bellman. Dynamic Programming. Princeton University Press, 1957. 2. [Dai et al., 2011] Peng Dai, Mausam, Daniel S Weld, and Judy Goldsmith. Topological value iteration algorithms. Journal of Artificial Intelligence Research, 42:181-209, 2011. 3. [Geffner and Bonet, 2013] Hector Geffner and Blai Bonet. A Concise Introduction to Models and Methods for Auto- mated Planning. Morgan & Claypool Publishers, 2013. 4. [Jarvis et al., 2005] Peter Jarvis, Teresa Lunt, and Karen Myers. Identifying terrorist activity with AI plan recog- nition technology. AI Magazine, 26(3):73-81, 2005. 5. [Johnson, 2010] W. Lewis Johnson. Serious use of a seri- ous game for language learning. International Journal of Artificial Intelligence in Education, 20(2):175-195, 2010. 6. [Kautz, 1987] Henry A Kautz. A Formal Theory of Plan Recognition. PhD thesis, Bell Laboratories, 1987. 7. [Kelley et al., 2012] Richard Kelley, Liesl Wigand, Brian Hamilton, Katie Browne, Monica Nicolescu, and Mircea Nicolescu. Deep networks for predicting human intent with respect to objects. In Proceedings of the Inter- national Conference on Human-Robot Interaction (HRI), pages 171-172, 2012. 8. [Keren et al., 2014] Sarah Keren, Avigdor Gal, and Erez Karpas. Goal recognition design. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pages 154-162, 2014. 9. [Keren et al., 2015] Sarah Keren, Avigdor Gal, and Erez Karpas. Goal recognition design for non-optimal agents. In Proceedings of the AAAI Conference on Artificial Intel- ligence (AAAI), pages 3298-3304, 2015. 10. [Keren et al., 2016a] Sarah Keren, Avigdor Gal, and Erez Karpas. Goal recognition design with non-observable ac- tions. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 3152-3158, 2016. 11. [Keren et al., 2016b] Sarah Keren, Avigdor Gal, and Erez Karpas. Privacy preserving plans in partially observable environments. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 3170- 3176, 2016. 12. [Keren et al., 2017] Sarah Keren, Luis Pineda, Avigdor Gal, Erez Karpas, and Shlomo Zilberstein. Redesigning stochastic environments for maximized utility. In Proceed- ings of the International Joint Conference on Artificial In- telligence (IJCAI), 2017. 13. [Lee et al., 2012] Seung Lee, Bradford Mott, and James Lester. Real-time narrative-centered tutorial planning for story-based learning. In Proceedings of the International Conference on Intelligent Tutoring Systems (ITS), pages 476-481, 2012. 14. [Mausam and Kolobov, 2012] Mausam and Andrey Kolobov. Planning with Markov Decision Processes: An AI Perspective. Synthesis Lectures on Artificial Intelligence and Machine Learning. 15. Morgan & Claypool Publishers, 2012. [McQuiggan et al., 2008] 16. Scott McQuiggan, Jonathan Rowe, Sunyoung Lee, and James Lester. Story-based learning: The impact of narrative on learning experiences and outcomes. In Proceedings of the International Conference on Intelligent Tutoring Systems (ITS), pages 530-539, 2008. 17. [Min et al., 2014] Wookhee Min, Eunyoung Ha, Jonathan Rowe, Bradford Mott, and James Lester. Deep learning- based goal recognition in open-ended digital games. In Proceedings of the AAAI Conference on Artificial Intel- ligence and Interactive Digital Entertainment (AIIDE), pages 37-43, 2014. 18. [Oh et al., 2010] Jean Oh, Felipe Meneguzzi, Katia Sycara, and Timothy Norman. ANTIPA: An agent architecture for intelligent information assistance. In Proceedings of the European Conference on Artificial Intelligence (ECAI), pages 1055-1056, 2010. 19. [Oh et al., 2011a] Jean Oh, Felipe Meneguzzi, Katia Sycara, and Timothy Norman. An agent architecture for prognos- tic reasoning assistance. In Proceedings of the Interna- tional Joint Conference on Artificial Intelligence (IJCAI), pages 2513-2518, 2011. 20. [Oh et al., 2011b] Jean Oh, Felipe Meneguzzi, Katia Sycara, and Timothy Norman. Probabilistic plan recognition for intelligent information agents: Towards proactive software assistant agents. In Proceedings of the International Con- ference on Agents and Artificial Intelligence (ICAART), pages 281-287, 2011. 21. [Schmidt et al., 1978] Charles Schmidt, N. Sridharan, and John Goodson. The plan recognition problem: An inter- section of psychology and artificial intelligence. Artificial Intelligence, 11(1-2):45-83, 1978. 22. [Son et al., 2016] Tran Cao Son, Orkunt Sabuncu, Christian Schulz-Hanke, Torsten Schaub, and William Yeoh. Solv- ing goal recognition design using ASP. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 3181-3187, 2016. 23. [Sukthankar et al., 2014] Gita Sukthankar, Christopher Geib, Hung Hai Bui, David Pynadath, and Robert P Goldman. Plan, activity, and intent recognition: Theory and practice. Newnes, 2014. 24. [Tarjan, 1972] Robert Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146- 160, 1972. 25. [Tavakkoli et al., 2007] Alireza Tavakkoli, Richard Kelley, Christopher King, Mircea Nicolescu, Monica Nicolescu, and George Bebis. A vision-based architecture for intent recognition. In Proceedings of the International Sympo- sium on Advances in Visual Computing, pages 173-182, 2007. 26. [Wayllace et al., 2016] Christabel Wayllace, Ping Hou, William Yeoh, and Tran Cao Son. Goal recognition design with stochastic agent action outcomes. In Proceed- ings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 3279-3285, 2016.