Goal Recognition (GR) is a research problem that studies ways to infer the goal of an intelligent agent based on its observed behavior and knowledge of the environment. A common assumption of GR is that the underlying environment is stationary. However, in many real-world scenarios, it is necessary to recognize agents' goals over extended periods. Therefore, it is reasonable to assume that the environment will change throughout a series of goal recognition tasks. This paper introduces the problem of continuous GR over a changing environment. The solution to this problem is a GR system capable of recognizing agents' goals over an extended period where the environment in which the agents operate changes. To support the evaluation of candidate solutions to this new GR problem, in this paper, we present the Goal Recognition Amidst Changing Environments (GRACE) tool for generating instances of the new problem. Specifically, the tool can be configured to generate GR problems that account for diferent environmental changes and drifts. GRACE can generate a series of modified environments over discrete time steps and the data induced by agents operating in the environment while completing diferent goals.
Goal recognition (GR) techniques aim to develop a GR system capable of detecting the
goal/intention of an agent embedded in an environment based on the observed behavior of the agent.
The existing GR techniques, such as the plan library-based approaches [
The research on the problem of continuous GR is impeded by the lack of benchmarks for evaluating candidate solutions. Thus, in this paper, we present the Goal Recognition Amidst Changing Environments (GRACE) tool for generating changes in environments where agents work towards various goals. As seed environments, that is, those environments over which changes are applied, we use the static domains widely used in classical GR.1
We identify a change in an environment based on two aspects. Firstly, we characterize a
change in the environment in which agents fulfill goals based on changes in the components
that define the corresponding GR problem. For example, such components can be the initial and
goal states of the agents and actions the agents can perform in the environment. Secondly, by
interpreting an environment as a signal, and, consequently, a change in the original environment
as a change in the original signal, we characterize changes in the environment based on the
diferent types of concept drift [
Concretely, this paper makes the following two contributions: • It motivates and defines the problem of continuous GR over a changing environment; and • It presents a tool, called GRACE, that can imitate changes in the environment in which agents strive to achieve goals and, thus, can serve as a simulator for GR systems for solving problems of continuous GR over a changing environment.
In the next section, we define the problem of continuous GR over a changing environment and discuss diferent types of changes in the environment our tool aims to support. Section 3 presents the tool. Section 4 examines related work before conclusions are given in Section 5.
This section starts with an example that motivates the problem of continuous GR over a changing environment (Section 2.1). Then, we define this problem (Section 2.2) and discuss diferent types of changes (Section 2.3) and drifts (Section 2.4) that may happen in an environment over time and, thus, must be accounted for when solving the continuous version of the GR problem.
Figure 1 presents a synthetic example of an environment change from environment to environment , both given as 11 × 11 grids. In environment , there are four keys (objects) located in two rooms and four locked cells (see the cells with the gray background). The locked cells can be unlocked using the corresponding keys; for example, locked cell 1 can be unlocked using Key1 . A robot (an agent) starts from the initial cell at cell (0, 0) and can move to any adjacent cell if there is no wall between those two cells; walls are shown as solid black lines in the figure. Once the robot reaches a cell with a key, it can pick up the key in that cell. It can subsequently carry the key. If the robot that carries a key reaches the corresponding locked cell, it can unlock it. In the environment, there are two goal states, 1 and 2, surrounded by walls or locked cells. Once a cell is unlocked, the robot can pass it to reach a goal state.
1https://github.com/pucrs-automated-planning/goal-plan-recognition-dataset
Key1
Key2 Room 1 Room 2
Key3 Key4 0 I
Key3
Key4 Room 1
2 Room 2
Key1 Key2
In environment , Key1 and Key2 are located in Room 1, while Key3 and Key4 are located in Room 2. Later, environment changes to environment , in which Key1 and Key2 from Room 1 are swapped with Key3 and Key4 from Room 2.
We simulated a sequence of 20 GR problems. Each problem is composed of historical behaviors of agents in the environment and observations for which a goal must be recognized. These behaviors are the only available information about the environments where the agents operate; complete descriptions of the environment are not available. The first ten problems in the sequence were obtained based on the behaviors of agents in environment . Then, the environment undergoes a sudden change, and the subsequent ten problems are based on the behaviors of agents in environment . This sequence of 20 GR problems is publicly available.2
We tackled the GR problems in the sequence using the GR system grounded in process mining
techniques [
2A sequence of 20 GR problems: https://github.com/zihangs/GRACE/tree/main/motivating_example.
The state-of-the-art GR approaches focus on solving a GR problem in a stationary environment. This version of the GR problem usually takes three inputs: (1) a sequence of actions, also called an observation, denoted by , that has been executed by an autonomous agent and observed by the GR system; (2) knowledge about the domain, or environment, in which the agent operates, denoted by ; and (3) a set of possible goals that an agent may pursue in the environment, namely goal candidates, denoted by . A solution to the problem often takes the shape of a probability distribution over the goals, that is, ( ∈ ). Therefore, an approach for solving the classical GR problem defines a belief function : × × → ( ∈ ) that maps observations, knowledge about the environment, and goal candidates onto probability distributions over the goals. The concrete distribution then expresses a belief of the observer, the GR system, about the true goal being pursued by the agent.
Domain knowledge is diferent for diferent GR approaches. For example, for a plan
librarybased GR approaches [
It is reasonable to assume that only partial information about the environment is available to a GR system. As and contribute to the explanation of the environment, we accept them as all and only knowledge about the environment available to a GR system, denoted by , and rewrite the belief function for the -th GR problem in the series as : × → ( ∈ ), ∈ [1 .. ]. In the setting of the continuous GR problem, any two environments and , 1 ≤ , ≤ , may be diferent, i.e., ̸= . A naïve solution to a problem of continuous GR in a changing environment can be achieved by solving each GR problem in the series independently, for example, by applying some state-of-the-art GR system. However, a GR system that operates over an extended period and solves a series of GR problems can benefit from at least two factors. Firstly, when solving the next GR problem in the series, a GR system can reuse all the experiences and results obtained from solving all the preceding GR problems. Secondly, a GR system with access to historical trends and experiences can project them into the future and then use these forecasts to tune its subsequent goal recognition practices.
In this work, we rely on the first-order representation of environments [
One can augment objects, for instance, by removing them, which requires a subsequent removal of the ground predicates defined over the removed objects. Note that such removal of predicates can augment the initial state and/or some goal states.
Once a new environment is obtained, it can be changed again. By applying changes iteratively, one can generate a series of modified environments. Note that a modified environment can be constructed by applying any subset of the above four changes simultaneously.
Environment changes can progress diferently over time. For example, one can experience
abrupt changes that get into efect over a short period or observe small changes accumulating
over time. Diferent patterns of changes in the environment can be classified according to five
types of concept drifts [
1. Sudden drift, see Figure 2a, concerns the situation when the original environment (env0 ) changes to the new environment (env1 ) over a short period. After the change is implemented, the original environment is never observed again. In the figure, ten environments are shown(1, . . . , 10), where environments 1, . . . , 5 are equal to env0 while environments 5, . . . , 10 are equal to env1 . 2. Gradual drift, see Figure 2b, concerns the situation where observations of the original environment (env0 ) alternate with increasingly frequent observations of the new environment (env1 ) until env0 is no longer observed. The series of environments in the figure consists of sixteen environments (1, . . . , 16). Environments 1, . . . , 4 are equal to env0 , environments 12, . . . , 16 are equal to env1 , and the gradual drift from env0 to env1 happens from 4 to 12. 3. Incremental drift concerns the situation when the environment “moves” from env0 to env1 through a number of subsequent intermediate environments. Figure 2c shows a series of environments 1, . . . , 12 that make up an incremental drift. Environments 1 to 4 are equal to env0 , then environment env0 moves to env1 through four intermediate environments 5, 6, 7, and 8; not that environments 8 to 12 are all equal to env1 . 4. Reoccurring drift, see Figure 2d, concerns the situation when two distinct environments env0 and env1 repeatedly alternate, where each environment is observed for some period. 1 t n e m n o ir v n E 0 0.8 (a) Sudden (b) Gradual 1 2 3 4 5 6 7 8 9 10 11 12
Time (c) Incremental 1 2 3 4 5 6 7 8 9 10111213141516
Time (d) Reoccurring 1 2 3 4 5 6 7 8 9 10
Time (e) Outlier
This section presents GRACE, a tool for generating input to a GR system that aims to solve a continuous GR problem. GRACE is implemented in Python and is publicly available.3 Section 3.1 and Section 3.2 present the architecture and the interface of GRACE, respectively.
The architecture of GRACE is shown in Figure 3. It consists of three components: Environment
Modifier, Planner, and Drift Generator. As input, GRACE takes a description of a GR problem in
Planning Domain Definition Language (PDDL) [
An environment specification (PDDL)
A series of GR problems
Environments (original & modified)
Sets of plans for environments Environment Modifier
Planner
Drift Generator
The simulator for continuous GR over changing environments (GRACE) the initial state, objects, goal candidates, and action schemes available in the environment. The output is a series of GR problems, each comprising a PDDL description of the environment of the problem and an observation of an agent’s behavior in the environment. The environments of the GR problems in the generated series are modified according to the requested types of changes and drifts, as described in Section 2.3 and Section 2.4, respectively.
The Environment Modifier component of GRACE transforms the description of an input environment according to the requested types of environmental changes described in Section 2.3, producing a set of modified environments. The number of modified environments depends on the requested type of concept drift discussed in Section 2.4. For example, incremental drift entails the intermediate stages of the environmental change, resulting in multiple modified environments generated by GRACE. Conversely, the other drift types are defined over two environments and, thus, GRACE generates one modified environment for them. Next, the Planner component takes the environments (original and modified) and generates multiple sets of plans induced by agents that operate in them. Finally, the Drift Generator component constructs the requested drift by selecting and arranging the environments and the generated plans on the timeline; the latter are used as observations of how agents achieve their goals in the environments. GRACE returns all the generated artifacts to support the evaluation of various GR systems with diferent assumptions and, thus, data requirements.
Table 1 gives an overview of the parameters for configuring each component of GRACE. Mandatory parameters must be configured for every call to GRACE, while optional parameters can be omitted. Optional parameters can be mutually exclusive, that is, never specified together, and associated, that is, specific to some selected option. The Input parameter is mandatory for all three components. Next, we discuss the parameters of each component.
GRACE implements all four methods for automatically changing environments discussed in
Section 2.3. These methods can be invoked using options -InitRW, -ObjectRM, -ActionRM,
and -GoalRW of Environment Modifier. Option -InitRW is used to modify the initial state
by executing a number of possible random actions and accepting the resulting state as the
new initial state in the modified environment. The number of random actions is specified
using the associated parameter “Steps of random walk from start”. The -ObjectRM option
is used to modify the environment by randomly deleting objects from the initial state. The
associated parameter “Delete count” specifies the number of objects to be deleted. When an
object is deleted from the environment, all predicates in the initial state containing the value
of that object are deleted as well. The -ActionRM option is used to modify the environment
by randomly deleting ground actions. The associated parameter “Delete count” specifies the
number of ground actions to be deleted from the environment. Finally, the -GoalRW option is
introduced to support modifications that augment the states that define the goal candidates.
To implement this change, we apply the backward search method [
An example call to Environment Modifier ( env_modifier.py) is shown below.
python env_modifier.py original_env -ObjectRM 5 1
We use original_env as input, which is a directory that stores files specifying the domain model of the original environment.4 The call uses option -ObjectRM to remove five objects from the environment (see parameter 5) and requests to construct one modified environment (see parameter 1). The instructions on how to use Environment Modifier are available in the documentation of GRACE.5
The original environment is a ten-by-ten grid. In this environment, the solid black lines between cells are walls that agents cannot pass. The cells in gray are locked, where the shape number in the locked cells indicates the number of the key that the agent can use to unlock this cell. For example, the cell with shape 21 can be unlocked with Key21 . The initial state where an agent starts is cell (0, 0), and there are ten goal states the agent might aim to achieve; see 1 to 10 in the figure. Figure 4b shows the modified environment produced after executing the command. In the modified environment, the five cells in black are deleted permanently, which 4The files that specify the environment in Figure 4a can be accessed via https://github.com/zihangs/GRACE/tree/main/env_modifier/data_examples/original_env.
5https://github.com/zihangs/GRACE/tree/main/env_modifier
Key12 13 8 Key10 G8
Key17 16 Key16 18 6 5
4 G8
Key17 16 Key16
17 2 Key19
Key7 Key4 Key9 Key18 K1e9y5
18
6
8
means the agent can never access or pass these cells. Note that other objects, for instance, keys,
can be removed as well.
3.2.2. Planner
The Planner component of GRACE has two options: the Top-K planner [
An example call to Planner (planner.py) is proposed below.
python planner.py all_envs -Topk 50 20
The all_envs input describes the original and the modified environments shown in Figure 4. We use the Top-K planner, see option -Topk, to generate 50 plans for each goal in the environments with the time limit set to 20 seconds (per goal); see the last two parameters in the call. For more details on using the Planner component, please refer to the documentation.6
A call to Planner returns two sets of plans, one containing the plans generated in the original environment and the other with plans in the modified environment. Since both environments have ten goal candidates, refer to the figure, the generated plans, for each of the two environments, are grouped into ten subsets, each containing the plans for the corresponding goal.
6https://github.com/zihangs/GRACE/tree/main/planner
The Drift Generator component takes a plan pool generated by the Planner component as input, selects plans from the plan pool, and queues the selected plans to simulate one of the concept drifts discussed in Section 2.4. One can simulate a sudden drift by selecting option -Sudden. This option requires the associated parameter “Cases per env”, which specifies the number of observations to use from each environment in the resulting drift. Specifically, after observations from the original environment, observations from the modified environment follow. To simulate a gradual drift, option -Gradual should be used. Parameter “Stable period” specifies the requested number of observations during each stable period for which the environment does not change, while parameter “Changing period” specifies the requested number of observations during the changing period. Option -Incremental is used to simulate an incremental drift. This option also uses the “Stable period” to specify the periods of no changes for the original and the resulting environments, while parameter “Intermediate stages” specifies the number of intermediate transient environments to generate between the two stable environments. Option -Reoccurring simulates a reoccurring drift. Two associated parameters are “Stable period”, which, as above, specifies the period of stability for each environment, and “ Occurrence count”, which defines the number of times the change between the environments happens. Finally, option -Outlier simulates an outlier drift, where parameter “Cases” specifies the total number of observed plans during the entire period and parameter Probability specifies the probability for an outlier to occur at each timestamp. For all the discussed options, each of the observations included in the simulated period aims to reach one random candidate goal.
An example call to Drift Generator (drift_generator.py) is proposed below.
python drift_generator.py plan_pool -Gradual 50 50
Input plan_pool contains sets of plans generated by the Planner component. In this call, Drift Generator is requested to generate a gradual drift, see option -Gradual, while the associated parameters “Stable period” and “Changing period” are both set to 50. The execution of the command resulted in a series of observations shown in Figure 5. Note that there are ten goal candidates in each environment, and each plan achieves one of the goal candidates indicated by diferent colors in the figure; for example, in Figure 5b, the observed plan of GR problem 51 is to achieve goal 7 in environment 0. For more details on the use of the component, see the documentation.7
The problem of continuous GR over a changing environment is an extension of the classical
GR problem in which the environment is accepted to be stationary. Similar to the problem
of concept drift detection in process mining [
Case ID 0 20 40 60 100 120 140 160 (a) A gradual drift over 150 observations with the change occurring between time steps 51 and 100. 50 55 60 65 70 (b) A time window from step 51 to step 100 showing the gradual change period.
The GRACE tool presented in this paper works with environments captured in Planning
Domain Definition Language (PDDL) [
This paper introduces the problem of continuous goal recognition (GR) over a changing environment, which requests a GR system to continuously tackle GR problems over a period during which the underlying environment may change. We define this new problem as an extension of the classical GR problem for stationary environments. To generate the experimental data that can be used to test solutions to the new problem, we present a tool, called GRACE, which can automatically modify an environment given as a planning domain, to obtain a series of GR problems defined over the environments modified according to a wide range of types of changes. The paper explains the architecture and interface of GRACE. Hence, the results reported in this paper enable future work on developing and evaluating GR techniques for solving GR problems in changing environments.