Online Probabilistic Goal Recognition over Nominal Models

Ramon Fraga Pereira, Mor Vered, Felipe Meneguzzi, Miquel RamírezIJCAI 2019 · DOI

TL;DR

This paper tackles the challenge of inferring an agent's goal when its underlying behavior model is unknown and must be learned from data. They propose a framework that uses deep neural networks to learn these "nominal" models and adapt existing goal recognition algorithms to work with them, showing promising results in complex navigation tasks.

What Problem Does This Paper Address?

Goal recognition is the task of figuring out what an agent wants to achieve, given observations of its actions and a model of how the world works. Traditionally, this relies on meticulously crafted "domain models" that describe the environment's dynamics and constraints. However, in real-world scenarios, these models are often incomplete, inaccurate, or simply unknown. This paper addresses the critical gap of performing goal recognition when the agent's behavior model isn't given but must be learned from observed data. This is crucial for building more robust AI systems that can understand and interact with agents whose internal workings are opaque.

Methods

The core of this work lies in two main contributions:

  • Learning Nominal Models: Instead of relying on expert-defined models, the authors use Deep Neural Networks (DNNs) to learn the system's dynamics (transition function) from observed state transitions. This approach, inspired by recent work in hybrid planning, allows them to create "nominal models" that approximate the true system behavior without explicit symbolic descriptions.
  • Adapting Goal Recognition Algorithms: They adapt two existing goal recognition algorithms to work with these learned nominal models:
  • Mirroring (ηMIRRORING): This approach, originally designed for continuous domains, is adapted to use the DNN-learned models. It involves comparing "ideal plans" (optimal plans for a given goal) with "observation-matching plans" (plans that follow the observed trajectory).
  • Cost Differences (Δ(O, G)): This method, inspired by probabilistic goal recognition, uses potential fields to modify cost functions based on observations. The authors adapt this to work with the learned dynamics, essentially performing a "but-for" test of causality between potential goals and observed behavior.

Datasets

The authors created synthetic datasets for three benchmark domains based on the constrained Linear-Quadratic Regulator (LQR) problem. These domains involve discrete-time linear dynamical systems with quadratic cost functions and box constraints on control inputs.

  • 1D Navigation: States represent position and velocity in one dimension.
  • 2D Navigation: States represent position and velocities in two dimensions for multiple vehicles.

They generated datasets by encoding these problems in the RDDL domain description language and using a planner (TF-PLAN) to generate trajectories. Observations were sampled from these trajectories, with varying percentages of the trajectory (5% and 10%) used to simulate missing intermediate states.

Key Insights and Ideas

  • Learning Dynamics is Feasible: The paper demonstrates that DNNs can learn surprisingly accurate models of system dynamics from data, even for complex domains. This opens the door to applying model-based AI techniques in situations where models are not readily available.
  • Nominal Models Degrade Performance (but not catastrophically): While the goal recognition algorithms perform best with "actual" (ground truth) models, they still achieve reasonable performance with the learned "nominal" models. This highlights the trade-off between model accuracy and the ability to perform goal recognition in data-driven settings.
  • "But-for" Test Adaptation: The core idea of adapting "but-for" tests (causality checks) to work with learned, opaque models is a significant conceptual contribution. This allows for reasoning about what would have happened if a different goal were pursued, even without direct access to the underlying dynamics.
  • Cost-Based Approach Sensitivity: The cost-difference approach (Δ(O, G)) proved to be sensitive to the planner's convergence to local minima, impacting its performance. This suggests that the choice of optimization algorithm for generating trajectories is critical.

Key Results

  • ηMIRRORING Dominates: The adapted Mirroring algorithm (ηMIRRORING) consistently outperformed the cost-difference approach (Δ(O, G)) across various settings (online, offline, first observation) and model types (actual vs. nominal).
  • High-Quality Nominal Models: The learned nominal models, as judged by their loss functions, were of "very high quality," with Mean Squared Errors (MSE) in the range of 10⁻⁵ to 10⁻⁴.
  • Performance Degradation: When using nominal models instead of actual models, performance (measured by True Positive Rate - TPR) generally decreased, but the algorithms still managed to infer correct hidden goals.
  • Computational Cost: The adapted algorithms require a number of planner calls linear in the number of goals and observations, with ηMIRRORING being more efficient than the original mirroring algorithm.

Limitations and Future Work

  • Sensitivity of Cost-Based Method: The authors acknowledge the sensitivity of the cost-based goal recognition method to planner convergence issues. They suggest exploring alternative optimization algorithms like Differential Dynamic Programming (DDP) for future work.
  • Handling Increased Variance: The paper notes that the algorithms' performance with increasing variance in the system's random disturbances (w) needs further investigation.
  • Improving Nominal Model Learning: A key future direction is to modify the loss function for training nominal models to better account for accumulated errors along trajectories, rather than just immediate prediction errors.
  • Broader Applicability: The authors aim to expand the applicability of model-based goal recognition by replacing hand-engineered models with data-driven ones, fostering synergies between planning, control, optimization, and machine learning.

Summary updated

BibTeX
@inproceedings{pereira2019online,
  author = {Ramon Fraga Pereira and Mor Vered and Felipe Meneguzzi and Miquel Ramírez},
  title = {{Online Probabilistic Goal Recognition over Nominal Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/770},
}
Figure