A Survey on Goal Recognition as Planning

1 Introduction

Goal Recognition is a task related to Automated Planning, where an agent employs abductive reasoning to infer the most likely desired goal from a sequence of observations of the observed agent's plan instead of deducing a plan from an initial state towards a goal using some kind of domain theory. Research on goal recognition is often situated among Plan, Activity, and Intent Recognition [Sukthankar et al., 2014] and employs distinct inference techniques to recognize the ultimate goals of agents under observation. While goal recognition is related to the problem of Plan Recognition [Mirsky et al., 2021], which consists of trying to infer the actual plan being carried out by the observed agent, this survey focuses squarely on goal recognition. The task of goal recognition has a number of potential and actual applications, including assisting the handicapped [Geib, 2002], activities of daily living (e.g., cooking) [Granada et al., 2017], workplace safety [Inam et al., 2018], smart home [Hegde and Kenchannavar, 2019], among others [Singh et al., 2020; Wayllace et al., 2020]. As research on goal recognition evolves into ever more complex domain models and better approaches, we expect the state-of-the-art to advance substantially and new application domains to be broken into.

Thus, we survey advances on goal recognition achieved primarily in the last decade, defining a common formal framework in Section 2, and exploring key aspects that distinguish current approaches. We formalize types of domain models that modern goal recognition approaches process in Section 3, followed by an analysis of the effect of different types of observations in Section 4. Section 5 looks into the assumptions each recognition approach makes about the agent being observed, especially regarding the awareness of the agent to the observer and how optimal the observed agent is. We evaluate the internal mechanism through which goal recognition approaches infer goals from observations in Section 6. Finally, we discuss various problems related to goal recognition in Section 7, and organize the approaches surveyed in this paper, pointing how future work can solve many of the limitations in the current state-of-the-art in Section 8.

2 Goal Recognition as Planning

We lay out the formal foundations of the problem we survey using a top-down approach and frame goal recognition in the context of automated planning, outlining the basic environment model, which we refine throughout the paper to match the specific approaches we discuss. We then formalize the task of goal recognition itself based on a planning model, which we also refine throughout the survey.

2.1 Automated Planning

Planning aims to select what an agent does next, given a model of the environment specifying how actions and sensors work, a current situation, and what is the goal to be achieved [Geffner and Bonet, 2013]. Such problem can be seen as a directed graph in which nodes represent states, edges represent the transition between states (caused by applying actions), and the solution is a path (i.e., plan) between two particular nodes (i.e., initial state and goal state) in this directed graph. Such graph is induced by a planning task following Definition 1.

Definition 1 (Planning Task) A planning task Π = ⟨Ξ, s0,G⟩ is a tuple composed of a domain definition Ξ, an initial state s0, and a goal state specification G. A solution to a planning task is a plan or policy π that reaches a goal state G starting from the initial state s0 by following the transitions defined in the domain definition Ξ.

2.2 Goal Recognition

Goal Recognition is the task of recognizing which goal an agent aims to achieve by observing its interactions in an environment [Sukthankar et al., 2014, Chapter 1, Page 3]. Such observed interactions (i.e., observations) constitute the evidence to recognize goals, and can be executed actions in the environment (e.g., a simple movement, cook, drive), and changing properties in an environment (e.g., at home, at work, resting). In this survey, we consider a goal recognition task by following the original problem defined by Ram´ırez and Geffner [2009]. As we formalize in Definition 2, a goal recognition task follows the same structure of a planning task (Definition 1), but instead of having a single goal condition, it has a set of goal hypotheses, and a sequence of observations induced by the actions executed by the observed agent. Definition 2 does not detail what a solution to a goal recognition problem is, as different approaches provide different solution concepts, which we define in Section 6.2.

Definition 2 (Goal Recognition Task) A goal recognition task ΠΩG = ⟨Ξ, s0, G,Ω⟩ is a tuple composed of a domain definition Ξ, an initial state s0, a set of goal hypotheses G, and a sequence of observations Ω.

Most goal recognition tasks assume there is at least one correct intended goal G * ∈ G among the hypotheses. However, as we see in Section 6.1, how exactly to present such solutions varies with the specific approach. Our definitions so far are vague into exactly what constitutes a domain definition, and what form the observations take. This is a deliberate presentation choice, as goal recognition approaches assume a variety of different models and observation types. Thus, we use Ξ to refer to any type of domain model, and pin down these types in Section 3. Likewise, we use Ω to refer to any observation sequence so we can define recognition problems independently of the observations, which we detail in Section 4. Example 1 illustrates a goal recognition task.

Example 1 Figure 1 illustrates a navigation environment where a robot can move and pick up objects to achieve its goals. The goal recognition task presented in the example is composed of an initial state s0 (e.g., robot position), a set of goal hypotheses G = ⟨G0,G1,G2⟩, and a sequence of observations Ω (e.g., a sequence of movements, represented by the dashed blue arrows). The domain definition Ξ can vary according to the domain type used to formalize the environment dynamics, e.g., a deterministic discrete domain model, a stochastic domain model, among others. For this example, we consider that Ξ is a deterministic discrete domain model 1 . A goal state specification G for this example can be defined as the robot be at a certain location holding an object (e.g., G1 represents the robot holding the ball in the upper right corner of the environment). Thus, based on the goal recognition task depicted in Figure 1, it is possible to infer that, most likely, the robot aims to achieve the goal condition G2 (e.g., holding the box in the bottom right corner of the environment).

1 In a deterministic discrete domain model the properties are defined as propositional facts and the transition between states has only one outcome, so every possible action has only one outcome.

3 DomainModel Types

Most of the early goal and plan recognition approaches treat the problem as one of parsing, assuming the domain knowledge includes not only the state transition function, but also production rules restricting the space of possible plans [Geib and Steedman, 2007]. To the best of our knowledge, the first practical goal recognition approach using a domain model recognizable by current approaches goes back to Lesh and Etzioni [1995]. This approach, instead of abstracting plans to strings from a grammar, uses a state transition system induced by a planning domain much like that of Definition 1. In effect, such planning domains induce graphs ⟨S,A⟩ via their transition function γ, with vertices S and edges A as in [Hong, 2001]. Definition 1 abstracts the specifics of the domain definition and what constitutes a state and a transition system. Indeed, Ξ induces a number of elements of a planning task, including a state space S, an action space A, and a transition function γ. Throughout this survey we refine domain model types defining what exactly states, actions, and transition systems can be.

3.1 Classical Planning DomainModels

The most common domain model in goal recognition research consists of the STRIPS fragment of PDDL [Fox and Long, 2003], as used by the seminal work of Ram´ırez and Geffner [2009] and much subsequent work [Mart´ın et al., 2015; Sohrabi et al., 2016; Pereira et al., 2017; Pereira et al., 2020] 2 . In Classical Planning, the state space is often represented as a set of propositional facts F (i.e., instantiated predicates) denoting what is true in the environment, or, alternatively, as multivalued variables in a finite domain representation [Helmert, 2009]. Regardless of the specific representation, a state comprises a set of variables V with a finite domain and the state space S is finite and well-defined. Likewise, in this setting, the action space A comprises STRIPS-style actions of the form a = ⟨name(a), pre(a), eff(a), cost(a)⟩ with conjunctive preconditions pre(a), and effects eff(a) = eff +(a) ∪ eff - (a) comprising both positive eff +(a) and negated facts eff - (a). Such actions induce a transition function γ : S ×A ↦→ S such that γ(s, a) = s ′ , where s ′ = (s ∪ eff +(a))-eff - (a). A Classical Planning domain model is deterministic and discrete.

For example, for the navigation environment depicted in Example 1, a Classical Planning task Π comprises a set of instantiated facts, representing the state properties of this navigation environment, where the robot and the objects are situated (e.g., (at robot loc-0-0), (at box loc-0-5)), and what objects the robot is holding (e.g., (holding ball)), the action space A = ⟨move, pick-up⟩ (we omit pre and eff + to save space), s0 = ⟨(at robot loc-0-0) (at box loc-0-5) . . .⟩, and G0 = ⟨(and (at robot loc-2-5) (holding ball))⟩.

2 While space limitations prevent us from providing details of the PDDL format, we refer to Haslum et al. [2019]

3.2 Stochastic DomainModels

By contrast, stochastic domains are often modeled in terms of (Partially Observable) Markov Decision Processes (POMDPs and MDPs), as in the approaches of Ram´ırez and Geffner [2011] and Oh et al. [2011]. In such models, MDPs transition functions γ are stochastic and such that s ′ ∼ γ(s, a), i.e., subsequent states are sampled following a stochastic function P [s ′ | s, a] for s, s′ ∈ S, a ∈ A.

3.3 Continuous DomainModels

Vered and Kaminka [2017a; 2017b] formally define the task of goal recognition by using the formalism of Continuous Motion Planning. In this setting, the state space S of a domain model Ξ is represented in a multi-dimensional Euclidean space, where S ⊂ Rn , such that n ≥ 2. This type of domain model usually represents environments with two or three dimensions. The action space A is a discrete (possibly infinite) set of actions, encoding a transition function γ between states. This transition function γ allows transforming one state (s) into another (s ′ ) via paths through the state space (e.g., a straight-line from s to s ′ ), rather than a discrete state, as defined in Classical Planning. We note that other recognition approaches in the literature also adopt this type of domain model, such as [Masters and Sardina, 2017; Vered et al., 2018; Kaminka et al., 2018; Masters and Sardina, 2019a; Masters and Sardina, 2019b]. For the navigation environment depicted in Example 1, a Continuous Motion Planning task Π could be defined with three dimensions (x, y, z), so the actions space A = ⟨move, pick-up⟩ would be performed over continuous values in x, y, and z, whereas s0 and G would be represented as a pose (e.g., position and orientation) of the robot r and the objects in the environment, for instance, the robot pose would be x(r) = 0.28, y(r) = 1.44, z(r) = 0.93, θ(r) = 45◦ .

3.4 Optimal Control DomainModels

Optimal Control aims to control a dynamical system such that its output follows a desired value, which may be a fixed or changing value [Bertsekas, 2017]. Pereira et al. [2019b] use concepts of Optimal Control for recognizing goals in approximate continuous domain models. To model Optimal Control problems and the range of possible agent behavior, the authors adopt the formalism of Finite-Horizon Optimal Control (FHOC) [Bertsekas, 2017] problems, incorporating and combining some terminologies of Control [Borrelli et al., 2017] and Automated Planning [Geffner and Bonet, 2013] to account for constraints and goal conditions (also referred to as target regions in the Control literature).

In this setting, transitions between states follow a stationary, discrete-time dynamical system xk+1 = γ(xk, uk, wk), 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. States xk ∈ S, controls uk ∈ U, and disturbances wk ∈ W are required to be part of Rn . For extracting trajectories, 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 J (x0) = E{g(xN ) + ∑N-1 k=0 g(xk, uk,wk)}, where g(xN) is the terminal cost, and g(xk, uk,wk) is the stage cost. FHOC problems are defined as an optimization problem whose solutions are trajectories (i.e., policies) that describe the range of possible optimal behaviors of observed agents.

3.5 Approximate, Incomplete, and Learned Domain Models

Regardless of the nature of the underlying model, one of the key bottlenecks in planning, and by extension, goal recognition, is the acquisition of a model Π from either structured or unstructured data. While research on reinforcement learning yielded reliable model acquisition techniques for stochastic domains driven by reward functions [Sutton and Barto, 2018], relatively less emphasis has been given to the automatic learning of Classical Planning models, with few techniques capable of generating the type of lifted PDDL models used by most of the approaches described in this survey. Nevertheless, there is renewed focus on developing mechanisms to learn classical planning models from structured [Aineto et al., 2019b; Su´arez-Hern´andez et al., 2020] and unstructured data [Asai and Fukunaga, 2018].

These advances have led to a number of approaches for goal recognition using automatically derived models. Amado et al. [2018] develop a goal recognition approach that learns PDDL models from unstructured data allowing symbolic approaches [Pereira et al., 2017] to quickly solve problems encoded in images. Similarly, Pereira et al. [2019a] adapt existing landmark-based goal recognition approaches to deal with incomplete STRIPS domain models [Weber and Bryce, 2011; Nguyen et al., 2017], which assume that the model available to the recognizer might contain imprecisions (possible preconditions and effects) due to imperfect model acquisition. Pereira et al. [2019b] develop a goal recognition approach for continuous control domains that uses an approximate learned transition function and an optimal policy to infer goals by adapting existing symbolic techniques [Vered et al., 2016]. Both approaches achieve a level of accuracy comparable to traditional approaches that rely on authored domains 3 , indicating that traditional recognition approaches can be augmented to cope with learned models, even when the models themselves might have flaws from the learning process.

4 Observation Types

Observations constitute the key piece of evidence for agent behavior in goal recognition problems. In practice, observations are an indirect projection of an observed agent's behavior, and can be thought of as whatever the sensing capabilities of the agent performing goal recognition can provide. As we see in Section 6.2, the model we assume drives agent behavior influences the nature of how observations are generated. Such dependency on the model leads us to use Definition 3 as an intermediary structure between an agent's behavior model and the generation of observations.

3 Authored domains are domain models written by a human using a specification language like PDDL.

Definition 3 (Trajectories) Let π be a solution to a planning task Π, ⃗π is a trajectory induced by π. For Classical Planning tasks, ⃗π is a sequential plan π; for MDPs and stochastic problems ⃗π is sequence of transitions from s0 to G following policy π while complying with the transition function; and for Continuous Planning or Control tasks, ⃗π is a sequence of poses or configurations (e.g., coordinates ⟨x, y, z⟩ and a velocity) between which there are infinite intermediary poses.

Having defined trajectories, we can formally define how actual observations are generated in Definition 4.

Definition 4 (Observations) Let ⃗π = ⟨⃗a1, . . . , ⃗an⟩ be a trajectory for planning task Π = ⟨Ξ, s0,G⟩. An action projection function tp(s,⃗a) : S ×A ↦→ ⃗A is a function that maps actions to sequences of zero or more observations. An observation sequence generation function op(s0, ⃗π) is a function mapping a trajectory ⃗π into an observation sequence:

Then, a sequence of observations Ω is a sequence projected from ⃗π into observation state ⃗A maintaining their order.

The sensors available to the observer impose limitations on types of observations. While most approaches construe observations as action descriptions of some sort, this is not necessarily the most realistic abstraction of how sensor data may be supplied to a goal recognizer. For instance, modern computer vision approaches to object detection [Wang et al., 2020] may provide a more reliable representation of the current status of objects in an image than action identification. Indeed, recent work on goal recognition as planning [Sohrabi et al., 2016] explicitly handles observations as states, the difference of which we formally define as follows.

Definition 5 (Action and State Observations) Let ⃗π = ⟨⃗a1, . . . ,⃗an⟩ be a trajectory for the planning task Π and tp(·, ·) be an action projection. A sequence of observations Ω⃗π is a sequence of actions from ⃗π if tp(·, ·) : S ×A ↦→ A, i.e., if ⃗A = A. Alternatively, a sequence of state observations Ωs is a sequence of states from S⃗π if tp(·, ·) : S ×A ↦→ S, i.e., if ⃗A = S. We denote the observation corresponding to action ai as ⃗ ai and that corresponding to state si as ⃗ si

For the navigation environment depicted in Example 1, action observations in the Classical Planning setting could be ⟨ ⃗ a0 = (move loc-0-0 loc-0-1), ⃗ a1 = (move loc-0-1 loc-0-2), . . .⟩, and state observations in Continuous Motion Planning setting could be ⟨⃗ s0 = x(r) = 0.28, y(r) = 1.44, z(r) = 0.93, θ(r) = 45◦ , ⃗ s1 = x(r) = 0.55, y(r) = 3.73, z(r) = 1.12, θ(r) = 90◦ , . . .⟩.

Given limitations in the sensing capability of the recognizer, observations may contain flaws, from missing to outright wrong/noisy observations, formalized in Definition 6.

Definition 6 (Missing and Noisy Observations) Let Π be a planning task, π be a valid plan for Π and Ω be an observation sequence induced by an observation generation function op(s0, ·) with an action projection function tp(·, ·). An observation sequence Ω misses observations (is a partial observation sequence) with respect to the plan π if the tp(·, ·) function contains a mapping a ↦→ ⟨⟩ for some action a, i.e., it maps one or more actions into the empty sequence. An observation sequence Ω contains noisy observations with respect to the plan π if the tp(si-1, ai) function maps ai into a non-empty sequence containing either one or more: (i) actions aj ̸= ai (for action observations); or (ii) states si ̸∈ γ(si-1, ai).

Indeed, most early approaches deal with missing observations implicitly by imposing a sequential constraint on the occurrence of elements of Ω in the plans considered plausible for a goal hypothesis G [Ram´ırez and Geffner, 2009], or ignoring most observations focusing on the overlap with necessary conditions [Pereira et al., 2017]. Most approaches also deal with noisy observations either implicitly [Ram´ırez and Geffner, 2010; Pereira et al., 2020], or not at all [Ram´ırez and Geffner, 2009]. In contrast, Sohrabi et al. [2016] compile Π into a single planning task with special predicates representing compliance with observations and achievement of goal hypotheses, as well as additional actions to achieve such predicates. This compilation ensures that goals whose plans have the least cost while complying with the most observations have higher probability. An optimal sequence of observations is extracted from an optimal plan and a sub-optimal sequence of observations from extracted of a sub-optimal plan.

5 Agent Assumptions

There are two key types of assumption regarding the observed agent that most approaches take into account during the recognition process: awareness, and optimality.

5.1 Awareness

The awareness assumption determines whether the agent is aware of it being monitored and what the attitude of the agent is towards the observer. Research on goal recognition characterize such awareness during the recognition process as follows [Armentano and Amandi, 2007; Sukthankar et al., 2014]. Intended Recognition is the recognition process in which the observed agent is aware of the process of recognition. Therefore, in this type of recognition process the observed agent usually cooperates with the process by notifying the recognizer about its interactions in the environment. Obstructed Recognition, by contrast, is such that the observed agent is aware of the process of recognition and obstructs purposely the process, so the agent intentionally does not cooperate with the recognition process. Keyhole Recognition is a recognition process in which the observed agent is unaware of the process of recognition, and the interactions performed by the observed agent are partially observable inputs to the recognition process. This type of assumption on recognition process is the most common, since it allows the recognizer to ignore any process of interpretation of the actions by the observed agent as either adversarial or trying to be cooperative. Indeed, using such minimal level assumptions has led to many of the current state-of-the-art recognition approaches to be vulnerable to either changes in target agent behavior or outright misdirection, especially when taking into consideration inferred agent preferences [Masters et al., 2021].

5.2 Optimality

We now examine what is likely to be the most common assumption among goal recognition models, which is that the agent under observation either behaves optimally (i.e., perfectly rationally), or at least approximately optimally. The reason for this assumption is grounded on the fact that most early approaches to goal recognition, and indeed many more recent ones, carry out recognition by generating valid plans for all goal hypotheses G. Since it is possible for planning problems to have infinitely many arbitrary plans that achieve G (e.g., by introducing irrelevant actions), methods that filter plausible goals by generating plans must assume optimality to bound the computation of such plans.

By contrast, methods that yield a probability distribution for P [G | Ω] must have a criterion to assign probabilities to goal hypotheses, which often follows the assumption that agents under observation are approximately optimal having P [G | Ω] proportional to how the plans that can project Ω are close to optimal plans towards G [Ram´ırez and Geffner, 2010; Sohrabi et al., 2016], or, alternatively, optimal policies [Ram´ırez and Geffner, 2011]. Conversely, Pereira et al. [2017] reasons over necessary conditions to achieve goals G, instead of considering distributions over the possible plans an agent might choose to achieve G. In this case, no assumptions are made regarding agent optimality and probabilities are assigned by the degree to which the observations can account for such necessary conditions.

Indeed, Masters and Sardina [2019b] explore how the pervasiveness of the rationality assumption leads to errors in goal recognition, introducing a mechanism to automatically gauge rationality and modulate earlier formulas to compute P [G | Ω]. Assuming rationality and honesty from the agents leads to a number of other weaknesses in recognition accuracy [Masters et al., 2021], allowing agents to act irrationally to bias recognition away from the actual goal of the agent.

Zhi-Xuan et al. [2020] relax the optimality (rationality) assumption, and introduce an approach that deals with sub-optimal behavior by modeling the observed agents as boundedly-rational planners. Here, bounded-rationality restricts the amount of resources available to an agent for planning, restricting how much the observed agent can plan. The resulting approach performs online Bayesian inference of goals and plans by interleaving resource-limited plan search with agent observations. This boundedly-rational approach accurately infers goals from both optimal and non-optimal behaviors involving failure and back-tracking.

6 Goal Recognition Approaches

We now explore approaches in terms of the underlying mechanisms to infer the correct goal, the algorithms underpinning each approach, and how they process observations.

6.1 Filtering vs. Ranking and Probabilities

One of the key assumptions of goal recognition tasks is that there is a single intented goal G * among the goal hypotheses G. Nevertheless, most realistic goal recognition problems impose constraints on the quality of the observations and the level of observability afforded by the recognizer. This means that inferring goals can be fraught with uncertainty when observations suffer from flaws such as noisy and missing observations. Thus, while one may consider the problem of goal recognition as a filtering process aimed at providing all goal hypotheses G consistent with Ω [Ram´ırez and Geffner, 2009], such set of goals may be empty when Ω is too noisy, or encompass all hypothesis space G when Ω is too small. In such cases, it is useful to infer a set of potentially correct goals, either ranked by some preference relation, or, ideally, a probability distribution P [G * = G], ∀G ∈ G.

Ram´ırez and Geffner [2010] formulate a probabilistic interpretation of goal recognition whereby the solution is probability P [G | Ω] of a given goal G, given observations Ω. Instead of computing that probability directly, most approaches use Bayes rule, which stipulates that P [G | Ω] = P[Ω|G]P[G] P[Ω] , and compute P [Ω | G]. The conditional probability of observations given a goal is directly related to the probability of the observed agent choosing a plan π for a particular goal G, which leads to the most common assumption for plan preference, which is that observed agents are approximately optimal and prefer plans close to optimal, and thus P [G | Ω] ∝ (cost(Ω) - cost(π* )). Mart´ın et al. [2015] develop a probabilistic approach to goal recognition that relies on planning graphs. Sohrabi et al. [2016] compute the probability P [π | G] of the top-k plans π consistent with G while complying with observations Ω as a proxy for P [Ω | G]. Masters and Sardina [2017; 2019a] reformulate the probabilistic interpretation of Ram´ırez and Geffner [2010] in the context of path-planning, and show that a single-observation recognition yields similar results in less than half of the recognition time. In contrast, Pereira et al. [2020] rank hypotheses G following a heuristic based on the number of landmarks inferred from observations, returning a set of goals within a θ threshold of the highest ranking hypothesis. While probabilistic approaches notionally incorporate a prior probability P [G] indicating agent preferences over goals, most approaches actually ignore such prior, and instead assume a uniform prior over the goals, leading to potential vulnerability to deception [Masters et al., 2021].

6.2 Search vs. Heuristic Computation

While seminal goal recognition approaches rely on various graph analysis algorithms [Lesh and Etzioni, 1995; Hong, 2001], the approaches that have dominated the state-of-theart in recent years can be broadly divided into two categories.

The first category relies on compilations of the goal recognition task into Classical Planning tasks, running the search procedure of a planner once or more and comparing the resulting plans to extract G * [Ram´ırez and Geffner, 2010; Sohrabi et al., 2016]. The second category uses the structure of planning tasks derived from ΠΩG by adapting planning techniques to compute G * either through the computation of a heuristic or by comparing heuristic values computed for each goal hypothesis. Typical examples of the first category include Ram´ırez and Geffner [2009] and Sohrabi et al. [2016]. Ram´ırez and Geffner [2009] generate a planning task Π from ΠΩG by compiling away the observations such that when a plan tries to solve Π, it must generate plans compatible with the observations Ω. By contrast, typical examples of the second category include the approaches developed by Pattison and Long [2010], Mart´ın et al. [2015], Pereira et al. [2017], Vered and Kaminka [2017b], and Santos [2021]. Pattison and Long [2010] propose a probabilistic recognition approach that uses heuristic estimation and domain analysis to determine which goals an agent is pursuing. Mart´ın et al. [2015] develop a heuristic estimation approach that relies on planning graphs. Pereira et al. [2017] compute the set of landmarks [Hoffmann et al., 2004] for each goal hypothesis G ∈ G and computing which landmarks have definitely been reached by plans that comply with the observations. Vered and Kaminka [2017b] propose a very effective recognition heuristic for continuous domain models. Recently, Santos et al. [2021] compute a goal ranking using linear programming over operator counting constraints on the problems induced by the goal hypothesis.

6.3 Online and Offline

Approaches to goal recognition differ in the way that the observations are perceived and revealed from the perspective of the recognizer. Most seminal approaches perform the recognition task offline [Ram´ırez and Geffner, 2009; Ram´ırez and Geffner, 2010; Mart´ın et al., 2015; Sohrabi et al., 2016; Pereira et al., 2017; Masters and Sardina, 2019a], in which the observations Ω are all revealed at once and up front, before starting the recognition process. The converse way to perform the recognition task is online, in which the observations Ω are revealed incrementally and recognition takes place multiple times, as each observation is revealed.

Online and offline goal recognition are not only different in the way that the observations are perceived and revealed, but also in the way the approaches are designed to perform the recognition task. Online goal recognition approaches are designed to be efficient and deal with incremental observations. Essentially, it is possible to perform online goal recognition by repeatedly calling an offline recognition approach for every new revealed observation. However, as proven by Vered and Kaminka in [2017a; 2017b], this is quite inefficient. In particular, they develop an online goal recognition that requires at best one call to a planner per goal hypothesis and at most half the calls of the seminal offline approach of Ram´ırez and Geffner [2010].

7 Related Problems

Goal Recognition can be seen as a sub-problem of Plan Recognition, and it is closely related to a variety of problems in the literature. Besides what we survey in this paper, which focuses on Planning models, other lines of research in Goal and Plan Recognition rely on different domain settings, such as context-free grammars [Geib and Goldman, 2009], plan libraries [Avrahami-Zilberbrand and Kaminka, 2005;

Zhuo and Li, 2011; Mirsky et al., 2016; Mirsky et al., 2019], among others. Given the space limitations, we focus on existing research closely related to Goal Recognition as Planning.

To the best of our knowledge, the first practical goal recognition approach using a domain model is the work of Lesh and Etzioni [1995]. However, the first approach that explicitly addresses goal inference and action understanding as "inverse" planning is that of Baker et al. [2009]. In this work, the authors develop a probabilistic framework based on Bayesian "inverse" planning for modeling human action understanding. This probabilistic framework attempts to approximate the principle of rationality, which expects that the observed agents plan approximately rationally to achieve their goals. Ram´ırez and Geffner [2009; 2010] follow Baker et al. [2009], and formally define Plan Recognition as Planning, claiming that Plan Recognition can be defined as Planning in "reverse". Recent research extends the original problem formulation of Ram´ırez and Geffner for recognizing plans in a variety of domain models, such as continuous domain models [Kaminka et al., 2018] and epistemic planning problems [Shvo et al., 2020]. Alternatively, Aineto et al. [2019a] introduce Model Recognition as Planning, a novel recognition task that aims to identify the model that best explains a sequence of observations.

Keren et al. [2014; 2020] provide an alternate view of the goal recognition task called Goal Recognition Design that focuses on modifying the domain model in order to facilitate the goal recognition process. The aim of this task is optimizing the domain design so that recognition approaches can disambiguate goals with as few observations as possible. Over the past years, a variety of goal recognition design (and derived) approaches have been developed over distinct types of domain models and settings, such as [Wayllace et al., 2016; Shvo and McIlraith, 2020].

Pozanco et al. [2018] develop a Counterplanning approach that relies on techniques from goal recognition and planning to prevent observed agents from achieving their goals. Most recently, Bernardini et al. [2020] develop a set of strategies for Goal Obfuscation, in which the observed agent aims to maintain its goal private, without revealing it to an observer. In contrast to Goal Obfuscation, MacNally et al. [2018] formalize Transparent Planning, in which agents aim to implicitly communicate their true intended goal to observers, facilitating goal (and intention) recognition. Analogously, Legible Planning addresses the task of generating plans that best disambiguate their goals from a set of other goal hypothesis from an observer's perspective. This task has been first introduced in the context of Robot Motion Planning by Dragan et al. [2013], and then extended to other planning settings [Kulkarni et al., 2019; Persiani and Hellstr¨om, 2021].

8 Conclusions and Perspectives

We have surveyed advances in Goal Recognition as Planning from recent years, classifying the various aspects that distinguish the approaches, including the types of domains being handled, how observations are handled, what assumptions are being made about the agent under observation, culminating in the algorithms that underpin such approaches. We summarize this classification in Table 1, where Technique refers to the underlying approach, Model refers to the type of model that describes the tasks (whether authored or learned, and the domain description), Observation Flaws refer to the potential flaws in the observations, Agent Assumption refers to the assumptions made about the agent, and finally, Solution refers to the type of solution provided by the approach.

Despite the substantial progress in the approaches we survey, many research challenges remain. Existing approaches assume pure models in some sense, so models are either continuous or symbolic. Thus, future research should focus on what Ram´ırez calls interesting domains, e.g., models described in PDDL+ [Fox and Long, 2006], or temporal planning [Fox and Long, 2003]. Similarly, few approaches deal with multi-agent domains, which we do not survey [Shvo et al., 2017; Argenta et al., 2017; Zhuo, 2019]. Expanding the types and complexity of the domains handled by goal recognition approaches is fundamental for the application of such technologies. Such applications include detecting deviation from safety procedures for work environment safety, and helping with activities of daily living for elderly care. As the research matures into deployed technologies, the ability to predict an individual goal raises significant ethical considerations, primarily on how to make decisions based on the output of goal recognition approaches. While such decisions are outside the scope of the goal recognition process itself [Etzioni and Etzioni, 2017], practitioners must be especially mindful of two key limitations in goal recognition: low confidence predictions and low fidelity models.

Finally, the challenge remains for researchers to compare approaches in a principled way, to the effect that current resources could be improved in two ways. First, most approaches use variations of the original problem description and dataset developed by Ram´ırez and Geffner [2009], all of them derived from problems in the International Planning Competition (IPC). While IPC domains constitute challenging settings for planning implementations, these domains are not necessarily realistic or representative of goal recognition problems. Second, and unlike planning algorithms, many of the approaches surveyed lack an openly accessible reference implementation amenable to objective comparison. Thus, developing a unified benchmark in a common format using representative goal recognition problems, and making all efforts openly available constitute key targets for future efforts. Having said that, we believe that this survey will be able to guide new research directions in Goal and Plan Recognition.

Acknowledgments

Felipe Meneguzzi acknowledges support from CNPq with projects 407058/2018-4 (Universal) and 302773/2019-3 (PQ Fellowship). Ramon Fraga Pereira acknowledges support from the ERC Advanced Grant WhiteMech (No. 834228) and the EU ICT-48 2020 project TAILOR (No. 952215). We acknowledge the valuable input provided by the anonymous IJCAI reviewers, which greatly improved this survey.