In goal recognition problems, the goal is to identify the goal of an observed agent as quickly as possible before they reach their goal. This problem can be applied to a number of applications ranging from software personal assistants and robots that anticipate the needs of humans; intelligent tutoring systems that recognize sources of confusion or misunderstanding in students through their interactions with the system; and security applications that recognize terrorists plans.

In goal recognition design problems, the objective is to identify the best ways to modify the underlying environment of the agents in such a way that they are forced to reveal their goals as early as possible. This problem is typically applicable in the same goal recognition applications as long as the underlying environment can be modified. For example, in intelligent tutoring systems, it is possible to modify the sequence or type of questions asked so that students’ misunderstanding can be identified sooner. Similarly, in security applications, it may be possible to block some paths so that an attacker’s plan can be recognized earlier. To learn more, please see our tutorial on goal recognition design, which we gave at ICAPS 2019. Slides available here.

Our current research is on both the algorithmic back-end, where the goal is to enrich the models so as to better capture more realistic problem characteristics and develop efficient algorithms to solve them, as well as the user interface front-end, where the goal is to develop visualization interfaces that allow our methods to be adapted to specific applications and evaluated with human users.

Goal Recognition Design (GRD) problems identify the minimum number of environmental modifications aiming to force an interacting agent to reveal its goal as early as possible. Researchers proposed several extensions to the original model, some of them handling stochastic agent action outcomes. While this generalization is useful, it assumes optimal acting agents, which limits its applicability. This paper presents the Suboptimal Stochastic GRD model, where we consider boundedly rational agents that, due to limited resources, might follow a suboptimal policy. Inspired by theories on human behavior asserting that humans are (close to) optimal when making perceptual decisions, we assume the chosen policy has at most u suboptimal actions. Our contribution includes (i) Extending the stochastic goal recognition design framework by supporting suboptimal agents in cases where an observer has either full or partial observability; (ii) Presenting methods to evaluate the ambiguity of the model under these assumptions; and (iii) Evaluating our approach on a range of benchmark applications.

ECAI

Accounting for Observer’s Partial Observability in Stochastic Goal Recognition Design

Christabel Wayllace, Sarah Keren, Avigdor Gal, and
3 more authors

In European Conference on Artificial Intelligence, 2020

Motivated by security applications, where agent intentions are unknown, actions may have stochastic outcomes, and an observer may have an obfuscated view due to low sensor resolution, we introduce partially-observable states and unobservable actions into a stochastic goal recognition design framework. The proposed model is accompanied by a method for calculating the expected maximal number of steps before the goal of an agent is revealed and a new sensor refinement modification that can be applied to enhance goal recognition. A preliminary empirical evaluation on a range of benchmark applications shows the effectiveness of our approach.

IJCAI

New Metrics and Algorithms for Stochastic Goal Recognition Design Problems

Christabel Wayllace, Ping Hou, and William Yeoh

In International Joint Conference on Artificial Intelligence, 2017

Goal Recognition Design (GRD) problems involve identifying the best ways to modify the underlying environment that agents operate in, typically by making a subset of feasible actions infeasible, in such a way that agents are forced to reveal their goals as early as possible. The Stochastic GRD (S-GRD) model is an important extension that introduced stochasticity to the outcome of agent actions. Unfortunately, the worst-case distinctiveness (wcd) metric proposed for S-GRDs has a formal definition that is inconsistent with its intuitive definition, which is the maximal number of actions an agent can take, in the expectation, before its goal is revealed. In this paper, we make the following contributions: (1) We propose a new wcd metric, called all-goals wcd (wcdag), that remedies this inconsistency; (2) We introduce a new metric, called expected-case distinctiveness (ecd), that weighs the possible goals based on their likelihood of being the true goal; (3) We provide theoretical results comparing these different metrics as well as the complexity of computing them optimally; and (4) We describe new efficient algorithms to compute the wcdag and ecd values.

GameSec

Game-Theoretic Goal Recognition Models with Applications to Security Domains

Samuel Ang, Hau Chan, Albert Xin Jiang, and
1 more author

In International Conference on Decision and Game Theory for Security, 2017

Motivated by the goal recognition (GR) and goal recognition design (GRD) problems in the artificial intelligence (AI) planning domain, we introduce and study two natural variants of the GR and GRD problems with strategic agents, respectively. More specifically, we consider game-theoretic (GT) scenarios where a malicious adversary aims to damage some target in an (physical or virtual) environment monitored by a defender. The adversary must take a sequence of actions in order to attack the intended target. In the GTGR and GTGRD settings, the defender attempts to identify the adversary?s intended target while observing the adversary?s available actions so that he/she can strengthens the target?s defense against the attack. In addition, in the GTGRD setting, the defender can alter the environment (e.g., adding roadblocks) in order to better distinguish the goal/target of the adversary.
We propose to model GTGR and GTGRD settings as zero-sum stochastic games with incomplete information about the adversary?s intended target. The games are played on graphs where vertices represents states and edges are adversary?s actions. For the GTGR setting, we show that if the defender is restricted to playing only stationary strategies, the problem of computing optimal strategies (for both defender and adversary) can be formulated and represented compactly as a linear program. For the GTGRD setting, where the defender can choose K edges to block at the start of the game, we formulate the problem of computing optimal strategies as a mixed integer program, and present a heuristic algorithm based on LP duality and greedy methods. Experiments show that our heuristic algorithm achieves good performance (i.e., close to defender?s optimal value) with better scalability compared to the mixed-integer programming approach.
In contrast with our research, existing work, especially on GRD problems, has focused almost exclusively on decision-theoretic paradigms, where the adversary chooses its actions without taking into account the fact that they may be observed by the defender. As such an assumption is unrealistic in GT scenarios, our proposed models and algorithms fill a significant gap in the literature.

IJCAI

Goal Recognition Design with Stochastic Agent Action Outcomes

Christabel Wayllace, Ping Hou, William Yeoh, and
1 more author

In International Joint Conference on Artificial Intelligence, 2016

Goal Recognition Design (GRD) problems involve identifying the best ways to modify the underlying environment that the agents operate in, typically by making a subset of feasible actions infeasible, in such a way that agents are forced to reveal their goals as early as possible. Thus far, existing work assumes that the outcomes of the actions of the agents are deterministic, which might be unrealistic in real-world problems. For example, wheel slippage in robots cause the outcomes of their movements to be stochastic. In this paper, we generalize the GRD problem to Stochastic GRD (S-GRD) problems, which handle stochastic action outcomes. We also generalize the worst-case distinctiveness (wcd) measure, which measures the goodness of a solution, to take stochasticity into account. Finally, we introduce Markov decision process (MDP) based algorithms to compute the wcd and minimize it by making up to k actions infeasible.