--- title: "Online Probabilistic Goal Recognition over Nominal Models" authors: - "Ramon Fraga Pereira" - "Mor Vered" - "Felipe Meneguzzi" - "Miquel Ramírez" doi: "10.24963/ijcai.2019/770" url: "https://ijcai.org/proceedings/2019/770" pdf: "https://ijcai.org/proceedings/2019/0770.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "5547-5553" track: "Main track" keywords: - "Planning and Scheduling: Activity and Plan Recognition" - "Planning and Scheduling: Temporal and Hybrid planning" --- # Online Probabilistic Goal Recognition over Nominal Models Ramon Fraga Pereira, Mor Vered, Felipe Meneguzzi, Miquel Ramírez *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 5547-5553. DOI: [10.24963/ijcai.2019/770](https://doi.org/10.24963/ijcai.2019/770) ## Abstract This paper revisits probabilistic, model-based goal recognition to study the implications of the use of nominal models to estimate the posterior probability distribution over a finite set of hypothetical goals. Existing model-based approaches rely on expert knowledge to produce symbolic descriptions of the dynamic constraints domain objects are subject to, and these are assumed to produce correct predictions. We abandon this assumption to consider the use of nominal models that are learnt from observations on transitions of systems with unknown dynamics. Leveraging existing work on the acquisition of domain models via learning for Hybrid Planning we adapt and evaluate existing goal recognition approaches to analyze how prediction errors, inherent to system dynamics identification and model learning techniques have an impact over recognition error rates. ## Full text ## 1 Introduction Goal recognition consists of identifying the correct goal of an observed agent, given a model of the environment dynamics in which the agent operates and a sample of observations about its behaviour [Sukthankar et al., 2014]. Most approaches to goal recognition rely on carefully engineered domain models, often in the form of a plan library [Sukthankar et al., 2014, Chapter 1] or over a domain theory and a given set of hypothetical goals [Ram´ırez and Geffner, 2009; Ram´ırez and Geffner, 2010]. While much effort focuses on improving the recognition algorithms themselves [Martin et al., 2015; Pereira et al., 2017], recent research has looked critically into the availability and quality of the domain models [Pereira and Meneguzzi, 2018; Amado et al., 2018] used to drive such algorithms. In this paper, we explore how existing and suitable reformulations of well known approaches to goal recognition perform over domain models which have been obtained with the application of machine learning techniques to datasets consisting of transitions between states annotated with actions. For this, we leverage recent results on Planning [Say et al., 2017; Wu et al., 2017] that combine Deep Learning [Goodfellow et al., 2016] to obtain a nominal model [Ljung, 1998], and apply gradient-based optimisation [Calafiore and El-Ghaoui, 2014] algorithms using such models to compute plans. ∗This work was developed during an internship at The University of Melbourne under the supervision of Dr. Miquel Ram´ırez. This paper makes three main contributions. First, we propose a general framework for goal and plan recognition based on a computational model, Finite-Horizon Optimal Control (FHOC) problems [Bertsekas, 2017], that support continuous action spaces and uses arbitrary cost functions to define plans, offering more expressiveness that previous models [Baker et al., 2009; Ram´ırez and Geffner, 2010] yet remaining computationally feasible when optimal solutions are approximated. The two other contributions we make, discussed in Sections 4.1 and 4.2, reformulate two well-known recent approaches to goal recognition [Ram´ırez and Geffner, 2010; Vered et al., 2016; Kaminka et al., 2018] that seek alternative ways to enforce constraints on the transition function, which in our setting, is not directly accessible and represented with a "black box" neural network. We evaluate the proposed recognition algorithms empirically in Section 5, using three benchmark domains based on the constrained Linear-Quadratic Regulator (LQR) problem [Bemporad et al., 2002], with increasing dimensions of state and action spaces. We build synthetic datasets for these domains and show that the first of the proposed algorithms performs quite well and infers the correct hidden goals when on the actual transition function of the domain, gracefully degrading over nominal models, due to the sometimes poor generalisation ability of the neural networks obtained. ## 2 Background We now introduce the Finite-Horizon Optimal Control (FHOC) problems, whose solutions we use to model the range of possible agent behaviour, and discuss how we use Deep Neural Networks (DNNs) to approximate the dynamics constraints in FHOCs. ## 2.1 Finite Horizon Optimal Control Problems We follow for the most part Bertsekas' [2017] presentation of FHOC problems, incorporating some elements typically used by the literature on Control [Borrelli et al., 2017] and Planning [Bonet and Geffner, 2013] to account for constraints and goals 1 . Transitions between states are described by a stationary, discrete-time dynamical system where for each time point k ∈ [0, N], xk is the state, uk is the control input and wk is a random variable with a probability distribution that does not depend on past wj , j < k. For now, we make no further assumptions on the specific way states, inputs and perturbations interact. States xk, controls uk, and disturbances wk are required to be part of spaces S ⊂ Rd , C ⊂ Rp , and D ⊆ Rd+p . Controls uk are further required to belong to the set U(xk) ⊂ C, for each state xk and time step k. We note that the latter accounts for both the notion of preconditions and bounds on inputs. Observed agents seek to transform initial states x0 into states xN with specific properties. These properties are given as logical formulas over the components of states xk, and the set of states SG ⊆ S are those where the desired property G, or goal, holds. The preferences of observed agents to pursue specific trajectories are accounted for with cost functions of the form g(xN) is the terminal cost, and g(xk, uk,wk) is the stage cost. We define Finite Horizon Optimal Control problems as an optimisation problem whose solutions describe the range of possible optimal behaviours of observed agents where I, the initial state, is an arbitrary element of S. Solutions to Equations 3-6 are policies π and µk is a function mapping states xk into controls uk ∈ C. When π is such that µi = µj for every i, j ∈ [0, N], we say π is stationary. We note that terminal constraints xN ∈ SG can be dropped, replacing them by terms in g(xk, uk,wk) that encode some measure of distance to SG. Costs g(xN) are typically set to 0 when terminal constraints are enforced, yet this is a convention, and establishing preferences for specific states in SG over others is perfectly possible. ## 2.2 DNNs as Nominal Models Learning the dynamics or the transition between states of a domain model from data can be formalised as the problem of finding the parameters θ for a function that minimise a given loss function L(D, θ) over a dataset D = { (x, u, y) | y = f(x, u,w), y ∈ S }. In the experiments reported on in this paper, we chose to use the procedure and neural architecture reported by Say et al. [2017] to acquire ˆ f, a DNN using Rectified Linear Units (ReLUs) [Nair and Hinton, 2010] as the activation function, given by h(x) = max(x, 0). The DNN is densely connected, as recommended by [Say et al., 2017], so for a DNN consisting of L layers, θ = (W, b), where W ∈ Rd×d×L and b ∈ R1×L. We use the loss function proposed by Say et al. [2017] 1 Referred to as target regions in control. where ˆ yj = ˆ f(xj, uj; θ) and λ is a Tikhonov L2 - regularisation hyper-parameter [Goodfellow et al., 2016]. In the context of optimisation for Machine Learning, using this regularisation technique induces the optimisation algorithm to overestimate the variance of the dataset, so weights associated with unimportant directions of the gradient of L decay away during training. As also noted by Goodfellow et al. [2016], RELU networks represent very succinctly a number of linear approximation surfaces that is exponential in the number of layers L [Montufar et al., 2014]. This strongly suggests that RELU networks can displace Gaussian process estimation [Rasmussen and Williams, 2006] as a good initial choice to approximate complex non-linear stationary random processes, such as those in Equation 1, with the further advantage that, as demonstrated by [Yamaguchi and Atkeson, 2016; Say et al., 2017], DNNs can be directly used in Equation 5, so existing optimisation algorithms can be used off-the-shelf. ## 3 Goal Recognition over Nominal Models Most existing approaches to goal and plan recognition assume that the domain model is both complete and correct, relying on what we call actual models. Such assumptions are widely considered by the literature on Control and Robotics [Mitrovic et al., 2010] to be too strong to hold in real-world, practical applications, where uncertainty on key model parameters is unknown, or these change over time due to wear and tear. We adopt this stance to define the task of goal and plan recognition over nominal models, that are estimated or recovered from past observed state transitions. These measurements of the underlying system dynamics can be obtained from observations on the behaviour of other agents, random excitation, or the simulation of plans and control trajectories derived from idealised models. We formally define the task of goal recognition over FHOCs and nominal models as follows. Definition 1 (Goal Recognition Problem). A goal recognition problem over nominal models is given by an estimated transition function ˆ f(xk, uk,wk), s.t. ˆ f (xk, uk, wk) = ˆxk+1, where xk is a state, uk a control input, and wk is a random variable; a cost function J; an initial state I (i.e., an arbitrary element of S); a set of hypothetical goals G; the hidden goal G∗ ∈ G; a sequence of observations O = 〈o1, o2, ..., om〉; and a horizon H. We further define the sequence of observations O to be a partially observed trajectory of states x ∈ S induced by a policy π that minimises J. In general, a finite but indeterminate number of intermediate states may be missing between any two observations oi, oi+1 ∈ O. We draw a distinction between online [Baker et al., 2009; Vered et al., 2016] and offline goal recognition, in which the former is a sequence of m Goal Recognition problems where O is obtained incrementally, while in the later O is available up front. We borrow the term judgement point from [Baker et al., 2009] to refer to the act of solving each of the m goal recognition problems that follow from the arrival of each new observation. Informally, solving a goal recognition problem requires to select a candidate goal ˆG∈ G such that ˆG = G∗ , on the basis of how well ˆG predicts or explains the observation sequence O [Baker et al., 2009; Ram´ırez and Geffner, 2010]. Typically, this cannot be done exactly, but it is possible to produce a probability distribution over the goals G ∈ G and O, where the goals that best explain O are the most probable ones. ## 3.1 Probabilistic Goal Recognition We follow Ramirez and Geffner [2010] (RG10) and adopt the modern probabilistic interpretation of Dennet's principle of rationality [1983], the so-called Bayesian Theory of Mind, as introduced by a series of ground-breaking cognitive science studies by Baker et al. [2009][2014, Chapter 7]. RG10 set the probability distribution over G and O introduced above to be the Bayesian posterior conditional probability where P(G) is the probability assigned a priori to goal G, α is a normalisation factor inversely proportional to the probability of O, and P(O|G) is P(O|π) is the probability of obtaining O by executing a policy π and P (π|G) is the probability of an agent pursuing G to select π. In the next section, we discuss two well-known existing approaches to approximate Equation 8, both reasoning over counterfactuals [Pearl, 2009] in different ways. These approaches frame in a probabilistic setting the so-called butfor test of causality [Halpern, 2016]. That is, if a candidate goal G is to be considered the cause for observations O to happen, evidence of G being necessary for O to happen is required. The changes to existing approaches are motivated by us wanting to retain the ability to compute counterfactual trajectories when transition functions cannot be directly manipulated. ## 4 Adapting Goal Recognition to Nominal Models ## 4.1 Goal Recognition as Goal Mirroring Mirroring [Vered et al., 2016] is an online goal recognition approach that works on both continuous and discrete domain models. For each of the candidate goals in G, Halpern's butfor test is implemented by comparing two plans: an ideal plan and the observation-matching plan (O-plan). Ideal plans are optimal ones computed for every pairing of I and candidate goals G, which are pre-computed before the recognition process starts. The O-plan is also computed for every pair I, G, and it is required to visit every state in O. O-plans are made of a prefix, that results from concatenating the O-plans computed for previous judgement points [Baker et al., 2009], and a suffix, a plan computed from the last observed state to each candidate goal G. The but-for test is implemented by making of use of Theorem 7 in [Ram´ırez and Geffner, 2009], that amounts to consider a candidate G to be necessary for O to happen, if the cost of optimal plans and those consistent with the observation O are the same. Vered et al. [2016] show that O-plans are indeed consistent with O so Ramirez and Geffner's results apply. The test was later cast in a probabilistic framework by Kaminka et al. [2018], with Equation 8 becoming ϵ(πO,G, πG) above is the matching error of πG, the ideal plan for Gw.r.t. πO,G, the O-plan for the observations. Under the assumption that w is a random variable w ∼ N(0, σ) with values given by a Gaussian distribution with mean 0 and standard deviation σ, ϵ can be used to account for the influence of w as long as σ remains an order of magnitude smaller than the values given by f(x, u, 0). Kaminka et al. [2018] define ϵ as the sum of the squared errors between states in the trajectory of πG, and those found along the trajectory of πO,G. Under the second assumption that the selected ideal plans for a goal G are the most likely too, Kaminka et al. ϵ is an unbiased estimator for the likelihood of πO,G. Having established the suitability of Kaminka et al. means to bring about the but-for test to FHOCs, we now describe how we depart from their method to obtain O-plans πO,G. In this paper, we construct πO,G by calling a planner once for each new observation o added to O and candidate goal G, rather than just once per candidate goal G as Kaminka et al. proposed. Doing so allows us to "enforce" consistency with observations O, since the couplings between states, inputs and perturbation in ˆ f(x, u,w) are no longer available so we can influence them with additional constraints, but are rather "hidden" in the network parameters. As the first observation o1 is obtained, we call a planner to solve Equations 3-6 setting the initial state x0 to I and xN to xo1 , the state embedded in o1. The resulting trajectory m1O is then used to initialise πO,G = 〈m1〉. We then invoke the planner again, this time setting x0 = xo1 and some suitably defined constraints s.t. xN ∈ SG for every candidate goal G. The resulting trajectories m1G are used to define the O-plans πO,G = πO,G ⊕ m1G, which are compared with the pre-computed ideal plans πG to evaluate P(O|G) as per Equation 9. As further observations oi, i > 1, are received, we obtain trajectories miO as above but setting x0 = xoi-1 and xN to xoi , which are used to update πO,G setting πO,G = πO,G ⊕ miO . Trajectories miG are obtained by setting initial states to xoi , and concatenated to the updated πO,G to obtain the O-plan for the i-th judgement point. We use as a baseline Vered et al.'s [2016] original mirroring algorithm, which requires |G| calls to a planner per observation, and |G| + (|G||O|) calls overall. The approach above requires |G| + 1 calls to a planner per observation, and |G| + |O| + (|G||O|) calls overall. This is a slight overhead which, on the basis of the results in Section 5, seems to be amortised enough by the accuracy and robustness of the new method. ## 4.2 Goal Recognition Based on Cost Differences We now present a novel goal recognition algorithm based on cost differences, inspired by RG10's probabilistic framework. RG10 implement Halpern's but-for test [2016] by determining whether plans exist that, while achieving G, either guarantee that O happens, or prevent it from happening, the later being the counterfactual plan [Pearl, 2009]. When no such plans exist, a proof of G (not) being sufficient cause for O is obtained. Typically though, goals remain feasible, yet costs of plans change, making G less likely to be the cause of O whenever the cost of achieving G is lesser when O does not take place. We retain this definition of the test, yet we do not obtain such plans from the solution of a suitably modified version of ˆ f(x, u,w), as RG10 does, by manipulating preconditions and effects. That is not possible in our setting, since couplings between state variables, actions and perturbation are not represented explicitly. Instead, we modify the cost function J by introducing artificial potential fields [Warren, 1989] centered on each observation in O that increase or decrease costs for valid trajectories. Let Jπ(x0;G) be the cost functions for each of the hypothetical goals G ∈ G. For a given observation sequence O = (o1, . . ., om), we define cost functions h(x, o) is a potential field function where the exponent is given as some suitably defined function over the difference of vectors x and o. We note that both x and o ∈ Rd . For this paper, we have chosen the sum smooth abs functions where ui is the i-th component of the vector x - o and p is a parameter we set to 1. These functions have been reported by Tassa et al. [2012] to avoid numeric issues in trajectory optimisation over long horizons. The potential is used in Equation 10 to increase, w.r.t Jπ(x0;G), the cost of those trajectories that stay away from O. Conversely, in Equation 11 it reduces the cost for trajectories that avoid O. Let T + and T be sets of r best trajectories t+i , t-i for either cost function, we introduce where Jt-i (x0;G) (resp. Jt+i (x0;G) is the result of evaluating the original cost function Jπ(x0;G) setting π to be the deterministic policy that follows from trajectories t+i and t-i . We define the likelihood of O given G as RG10 do with the proviso that β needs to be adjusted so as to be the inverse of the order of magnitude of ∆(G, O). In comparison to the previous approach, our formulation of goal recognition over cost differences requires 2|G| calls per observation, and 2|G||O| calls overall. While all methods require a number of calls linear on |G||O|, evaluating Equation 14 tends to be more expensive, as J + and J - contain several non-linear terms and their derivatives are also costlier to compute. This is relevant as most if not all of the optimisation algorithms that we can use to solve Equation 3-6 are based on gradientbased techniques [Calafiore and El-Ghaoui, 2014]. ## 5 Experiments and Evaluation We now present the empirical evaluations we carried out of the algorithms proposed in the previous section. Sections 5.1 and 5.2 introduce the benchmark domains we used and describe how we generated the datasets for learning the transition function and the goal recognition tasks. Sections 5.3 and 5.4 report the quality of nominal models obtained and the performance of our goal recognition algorithms over both nominal and actual models. ## 5.1 Domains For experiments and evaluation, we use three benchmark domains based on the constrained LQR problem [Bemporad et al., 2002], a general and well-understood class of optimal control problems with countless practical applications. Specifically, we use a discrete-time deterministic, linear dynamical system: and trajectories must minimise the quadratic cost function where Q ∈ Rd×d and R ∈ Rp×p . All matrices are set to I of appropriate dimensions, but R which is set to 10-2 I. Actions (inputs) uk are subject to simple "box" constraints of the form lb(u) ≤ uk ≤ ub(u). We note that the unconstrained LQR problem has an analytical solution [Bertsekas, 2017] as the cost function is globally convex and dynamics are linear, this simplifies the analysis of the behaviour of optimisation algorithms for training DNNs and computing trajectories. We consider two types of tasks. In the first domain, which we call 1D-Navigation, states xk ∈ R2 represent the position and velocity of a particle, control inputs uk ∈ R represent instant acceleration. Goal states require reaching a given position, yet leave terminal velocities unconstrained. The second domain, 2D Navigation, has higher dimensionality as states xk ∈ R4n represent position and velocities of n vehicles on a plane, and control inputs uk ∈ R2n represent instant accelerations along the x and y axis. As in the previous domain, goal states only require reaching specific positions. ## 5.2 Learning and Recognition Datasets To build the datasets and learn the system dynamics for the domains discussed previously, we generated 500 different navigation tasks i.e. pairs of states x0 and xG. We set the horizon H = 100, resulting in three different datasets with 50, 000 transitions each. To generate the trajectories for each of the tasks, we first encoded the FHOCs for each of the domains using the RDDL domain description language [Sanner, 2011]. This enabled us to use the suite of hybrid planners recently proposed by Bueno et al. [2019], which we refer to as TF-PLAN. These planners rely on state-of-the-art gradient-based optimisation techniques that obtain the gradients directly from the symbolic RDDL encoding, and have been shown to offer good performance on linear and nonlinear dynamics with complex non-linear cost functions. We use a benchmark consisting of 30 problems for 1DNavigation and 30 each for 2D-Navigation setting n to 1 and 2. We ensure the initial states and hypothetical goals are significantly different from the ones used to obtain the nominal models. Each task considers at most 5 goals hypotheses G, and observations O comprise either 5 or 10 states, i.e., 5% and 10% of trajectories when H = 100. To generate O, we used TF-PLAN to find a best trajectory from each initial state I to the hidden goal G∗ ∈ G. All states in the trajectories found have the same probability of appearing in any given O. ## 5.3 Learning Results We use the approach of Say et al. [2017] to learn models of the system dynamics (transition function) of our domains from data. For the training stage, we configured the DNN proposed by [Say et al., 2017] to use the same hyper-parameters. Namely, 1 hidden layer, a batch size of 128 transitions, we set the learning rate to 0.01 and dropout rate to 0.1. Training was stopped for all domains after 300 epochs. We used exactly the same DNN configuration to learn the system dynamics for all of our domains. The Mean Squared Error (MSE) for the best DNN out of 10 trials, using 300 epochs for training, were 4.5 · 10-5 for 1D-Navigation, 1.7 · 10-4 for 2DNavigation with n = 1, and 9.6 · 10-6 for the same domain but n = 2. From these errors we conclude that using offthe-shelf the learning approach of Say et al. [2017] results in nominal models of very high quality, as judged by the loss function they propose. ## 5.4 Goal Recognition Results We now show the experimental results of our recognition approaches over both actual and nominal models. For recognising goals over actual models we used the implementation of the TF-PLAN planner used in [Bueno et al., 2019] that takes as input a domain model formalised in RDDL. For nominal models we used the implementation of TF-PLAN in [Wu et al., 2017] that takes as input a domain model represented as a DNN. For both planners we set the learning rate to 0.01, batch size equals to 128, and the number of epochs to 300. Table 1: Experimental results of our approaches over both actual and nominal models. M represents the model type, % O is observation level, and N is the number of observed states. Note that the average number of goal hypothesis |G| in the datasets is 5. | Approach | M | %O | ONLINE - N | ONLINE - Top-2 TPR FPR | OFFLINE - N Top-2 | OFFLINE - TPR FPR | 1ST OBSERVATION - Top-2 | 1ST OBSERVATION - TPR FPR | |------------|-----|------|--------------|--------------------------|---------------------|---------------------|---------------------------|-----------------------------| | ηMIRRORING | A | 5 | 450 0.87 | 0.77 0.05 | 90 0.97 | 0.93 0.01 | 0.67 | 0.44 0.12 | | ∆(O,G) | A | 5 | 450 0.49 | 0.24 0.16 | 90 0.49 | 0.30 0.15 | 0.49 | 0.26 0.16 | | ηMIRRORING | A | 10 | 900 0.90 | 0.78 0.05 | 90 0.98 | 0.96 0.01 | 0.64 | 0.32 0.15 | | ∆(O,G) | A | 10 | 900 0.45 | 0.26 0.16 | 90 0.44 | 0.28 0.15 | 0.47 | 0.28 0.15 | | ηMIRRORING | N | 5 | 450 0.66 | 0.46 0.12 | 90 0.83 | 0.67 0.07 | 0.44 | 0.24 0.17 | | ∆(O,G) | N | 5 | 450 0.45 | 0.22 0.17 | 90 0.43 | 0.26 0.16 | 0.51 | 0.18 0.18 | | ηMIRRORING | N | 10 | 900 0.71 | 0.49 0.11 | 90 0.87 | 0.72 0.06 | 0.41 | 0.26 0.16 | | ∆(O,G) | N | 10 | 900 0.45 | 0.26 0.16 | 90 0.42 | 0.21 0.17 | 0.52 | 0.32 0.15 | To evaluate our recognition approaches, we use metrics already used in the literature in goal recognition [Pereira et al., 2017; Pereira and Meneguzzi, 2018]. These are the average True Positive Rate (TPR) and average False Positive Rate (FPR). TPR is given by the number of true positives (1 when G∗ maximises P(G|O), 0 otherwise) over the sum of true positives and false positives (the number of candidate goals maximising P(G|O)). A higher TPR indicates better performance, as it measures how often the true goal is calculated reliably. FPR is the average number of candidate goals G ̸= G∗ which maximise P(G|O), measuring how often goals other than the true one are found to be as good as or better explanation for O than G∗ . We also use the Top-k metric, typically used in machine learning to evaluate classifiers, setting k to 2, to measure the frequency in which G∗ was amongst the top k candidate goals as ranked by P(G|O), and complements the two previous measures. Table 1 shows the performance of the algorithms described in Section 4.1 (ηMIRRORING) and in Section 4.2 (∆(O, G)). We analyse performance in three different settings, from left to right: (1) online goal recognition, considering the response of the goal recognition algorithm for each judgement point corresponding to an observation in O; (2) offline goal recognition, when we consider only the last judgement point (i.e., all observed states in O); and (3) considering only the first judgement point (i.e., o1 ∈ O). With respect to recognition time, the average time per goal recognition problem for ηMIRRORINGover the datasets is ≈ 1,100 seconds, whereas for ∆(O, G) is ≈ 1,600 seconds. Under the parameters used for the planners, ηMIRRORING clearly dominates ∆(O,G) in all settings by a wide margin but when considering the first observation over nominal models. Seeking an explanation for the poor performance of ∆(O,G) we dug deeper into the experimental data 2 to find how often ηMIRRORING was superior to ∆(O,G) and vice versa. Interestingly, we found that ηMIRRORING is superior over ∆(O,G), according to the Top-2 measure, in 37% of the judgement points considered, ∆(O,G) is superior in 8.9% of the cases and both approaches are in agreement and correct in 42.1% of cases. This suggested to us that ∆(O,G) could be sensitive to one of the parameters used to calculate trajectories. Our ablation study detected that the number of epochs is the key parameter, as it directly affects how far from optimal are the trajectories found. We also observed that varying the number of epochs had counter-intuitive results, as the approximations to the optimal values of J + and J - do not get better or worse in a linear fashion. Instead, we often observed costs improve (or worsen) for either cost functions at different rates, sometimes changing the sign of ∆(O,G). We ran the ∆(O,G) recognising over a limited number of instances, setting the number of epochs to 3, 000 and we observed a significant improvement which brought it to be in agreement with ηMIRRORING if not sometimes superior. Of course, this entailed an increase of run times by a roughly an order of magnitude. This leads us to conclude that the relatively good results of ∆(O,G) in Table 1 are due to the fact that J + and J - are closer to the convex ideal in Equation 16, as they include less non-linear terms h(x, o), so TF-PLAN is less likely to get trapped in a local minima with adverse results for recognition accuracy early on. 2 Results and Jupyter notebooks are available in https://github.com/authors-ijcai19-3244/ijcai19-paper3244-results ## 6 RelatedWork Most model-based approaches to goal and plan recognition rely on complete and accurate models of actions, transitions or other constraints. Pereira and Meneguzzi [2018] tackles the issue of model uncertainty, and enhances landmark-based heuristics to work with Weber and Bryce's notion of incomplete models [2011], whereby uncertainty manifests in the preconditions and effects of the discrete planning operators. A transition function is still provided and fully accessible to the planner, yet in an incomplete form and possibly being incorrect, and this is indeed shown to have an impact on the accuracy of model-based goal recognition approaches. Recent work such as that of Say et al. [2017] and SanchezGonzalez et al. [2018] use DNNs [Goodfellow et al., 2016] to directly acquire models of dynamic constraints. These learnt constraints can then be readily used to formulate FHOC problems on top of them, which can be solved with a variety of dynamic programming or optimisation algorithms [Yamaguchi and Atkeson, 2016; Say et al., 2017; Wu et al., 2017; Bueno et al., 2019]. Compared to previous approaches combining dynamic programming and system identification [Mitrovic et al., 2010] based on Gaussian Process estimation [Rasmussen and Williams, 2006], DNNs have gradients which may be more straightforward to use for optimisation, yet show very quick rates of growth when it comes to their size. The FHOC model we define in Section 2.1 is a generalization [Bertsekas, 2017] of the Markov Decision Processes (MDPs) used in seminal work on model-based goal and plan recognition [Baker et al., 2009]. As noted in Section 3, we too adopt Bayesian probabilities as the language to express the degree of certainty on causal relationships between goals G and observations O. Our work separates from theirs in three respects. First, Baker et al. [2009] MDPs are defined over discrete action spaces, and we use continuous ones. Second, they assume observations O to be prefixes of trajectories, while we allow intermediate states to be missing. Finally, we explicitly perform a check of sufficiency to determine causal relations between goals and observations [Halpern, 2016], by computing counterfactual trajectories frommodels. These we use to derive probability measures of certainty of causal relation, rather than requiring explicit distributions relating goals and observations as Baker et al. [2009] do. ## 7 Discussion Model-based goal and plan recognition is a real-word, nontrivial and challenging application of causal reasoning, and this paper casts past approaches to model-based goal recognition as different implementations of Halpern's but-for test of sufficient causality. We also show that machine learning systems can be used to generate predictions which are good enough to enable the generation of meaningful counterfactuals and by extension "true" causal reasoning, in contrast with recent statements to the contrary [Pearl, 2019]. We look forward to further investigating three questions this paper leaves open. First, to what extent the proposed algorithms can handle increasing variance for w. Informal tests on Linear-Quadratic Gaussian [Bertsekas, 2017] problems derived from the ones presented in this paper show promise but we have yet to test these observations for significance. Second, we need to determine whether it is possible to modify the loss function used for training the nominal models in a way that takes into account the accumulated error along trajectories, rather than just the errors in predicting the next state. Last, as discussed in Section 5.4, cost based goal recognition is very sensitive of planners converging to an unhelpful local minimum, which seems to us an inherent characteristic of stochastic optimisation algorithms. We look forward to evaluating our recognition algorithms over planners relying on Differential Dynamic Programming (DDP) [Mitrovic et al., 2010; Yamaguchi and Atkeson, 2016], which may converge faster to better local minima of the cost function. We expect this paper to expand the applicability of modelbased goal and plan recognition by replacing carefully engineered models for carefully curated datasets. This work is also an example of how to exploit latent synergies between Planning, Control, Optimisation and Machine Learning, as we mix together algorithms, techniques and concepts to address in novel ways a high-level, transversal problem relevant to many fields in Artificial Intelligence. ## Acknowledgements We want to thank Prof. Judea Pearl and Prof. Benjamin Recht for their lively exchanges on Twitter which have provided significant inspiration to write this paper. We also thank Jo˜ao Paulo Aires for the invaluable discussions about DNNs. This material is based upon work partially supported by the Australian DST Group, ID8332. This work is also financed by the Coordenac¸ ˜ao de Aperfeic¸oamento de Pessoal de Nivel Superior (Brazil, Finance Code 001). Felipe acknowledges support from CNPq under project numbers 407058/2018-4 and 305969/2016-1. ## References 1. [Amado et al., 2018] Leonardo Amado, Ramon Fraga Pereira, Joao Paulo Aires, Mauricio Magnaguagno, Roger Granada, and Felipe Meneguzzi. Goal recognition in latent space. In IJCNN, 2018. 2. [Baker et al., 2009] Chris L. Baker, J. B. Joshua B. Tenen- baum, and Rebecca Saxe. Action understanding as inverse planning. Cognition, 113(3):329-349, 2009. 3. [Bemporad et al., 2002] Alberto Bemporad, Manfred Morari, Vivek Dua, and Efstratios N. Pistikopoulos. The explicit linear quadratic regulator for constrained systems. Automatica, 38:3-20, 01 2002. 4. [Bertsekas, 2017] Dmitri P. Bertsekas. Dynamic Program- ming and Optimal Control. Athena Scientific, 4th edition, 2017. 5. [Bonet and Geffner, 2013] Blai Bonet and Hector Geffner. A Concise Introduction to Models and Methods for Auto- mated Planning. Morgan & Claypool, 2013. 6. [Borrelli et al., 2017] Francesco Borrelli, Alberto Bempo- rad, and Manfred Morari. Predictive control for linear and hybrid systems. Cambridge University Press, 2017. 7. [Bueno et al., 2019] Thiago P. Bueno, Leliane Barros, De- nis D. Maua, and Scott Sanner. Deep reactive policies for planning in stochastic nonlinear domains. In AAAI, 2019. 8. [Calafiore and El-Ghaoui, 2014] Giuseppe C. Calafiore and Laurent El-Ghaoui. Optimization Models. Cambridge University Press, 2014. 9. [Dennett, 1983] D.C. Dennett. Intentional systems in cogni- tive ethology: The "panglossian paradigm defended". Be- havioral and Brain Sciences, 6:343-390, 1983. 10. [Goodfellow et al., 2016] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. 11. [Halpern, 2016] Joseph Y. Halpern. Actual Causality. The MIT Press, 2016. 12. [Kaminka et al., 2018] Gal A. Kaminka, Mor Vered, and Noa Agmon. Plan recognition in continuous domains. In AAAI, 2018. 13. [Ljung, 1998] Lennart Ljung. System identification. In Sig- nal Analysis and Prediction, pages 163-173. Springer, 1998. 14. [Martin et al., 2015] Yolanda Martin, Maria D. Moreno, and David E. Smith. A fast goal recognition technique based on interaction estimates. In IJCAI, 2015. 15. [Mitrovic et al., 2010] Djordje Mitrovic, Stefan Klanke, and Sethu Vijayakumar. Adaptive optimal feedback control with learned internal dynamics models. In From Mo- tor Learning to Interaction Learning in Robots. Springer, 2010. 16. [Montufar et al., 2014] Guido F. Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In NIPS, 2014. 17. [Nair and Hinton, 2010] Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann ma- chines. In ICML, 2010. [Pearl, 2009] Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, 2009. 18. [Pearl, 2019] Judea Pearl. On the interpretation of do(x). Technical report, University of California Los Angeles, 2019. 19. [Pereira and Meneguzzi, 2018] Ramon Fraga Pereira and Felipe Meneguzzi. Goal recognition in incomplete domain models. In AAAI, 2018. 20. [Pereira et al., 2017] Ramon Fraga Pereira, Nir Oren, and Felipe Meneguzzi. Landmark-based heuristics for goal recognition. In AAAI, 2017. 21. [Ramírez and Geffner, 2009] Miquel Ramírez and Hector Geffner. Plan recognition as planning. In IJCAI, 2009. 22. [Ramírez and Geffner, 2010] Miquel Ramírez and Hector Geffner. Probabilistic plan recognition using off-the-shelf classical planners. In AAAI, 2010. 23. [Rasmussen and Williams, 2006] Carl E. Rasmussen and Christopher K. I. Williams. Gaussian Processes for Ma- chine Learning. MIT Press, 2006. 24. [Sanchez-Gonzalez et al., 2018] Alvaro Sanchez-Gonzalez, Nicolas Hess, Jost Tobias Springenberg, Josh Merel, Mar- tin Riedmiller, Raia Hadsell, and Peter Battaglia. Graph networks as learnable physics engines for inference and control. In ICML, 2018. 25. [Sanner, 2011] Scott Sanner. Relational dynamic influence diagram language (rddl): Language description. Technical report, Australian National University, 2011. 26. [Say et al., 2017] Buser Say, Ga Wu, Yu Qing Zhou, and Scott Sanner. Nonlinear hybrid planning with deep net learned transition models and mixed-integer linear pro- gramming. In IJCAI, 2017. 27. [Sukthankar et al., 2014] Gita Sukthankar, Robert P Gold- man, Christopher Geib, David V Pynadath, and Hung Hai Bui. Plan, Activity, and Intent Recognition: Theory and Practice. Elsevier, 2014. 28. [Tassa et al., 2012] Yuval Tassa, Tom Erez, and Emanuel Todorov. Synthesis and stabilization of complex be- haviours through online trajectory optimization. In Proc. of the IEEE/IROS, 2012. 29. [Vered et al., 2016] Mor Vered, Gal A Kaminka, and Sivan Biham. Online goal recognition through mirroring: Hu- mans and agents. In ACS, 2016. 30. [Warren, 1989] Charles W. Warren. Global path planning us- ing artificial potential fields. In ICRA, 1989. 31. [Weber and Bryce, 2011] Christopher Weber and Daniel Bryce. Planning and acting in incomplete domains. In ICAPS, 2011. 32. [Wu et al., 2017] Ga Wu, Buser Say, and Scott Sanner. Scal- able planning with tensorflow for hybrid nonlinear do- mains. In NIPS, 2017. 33. [Yamaguchi and Atkeson, 2016] Akihiko Yamaguchi and Christopher G. Atkeson. Neural networks and differential dynamic programming for reinforcement learning prob- lems. In ICRA, 2016.