# Goal Recognition via Linear Programming

arXiv: https://arxiv.org/abs/2404.07934 · HTML: https://mlsanity.com/paper/2404.07934/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 60 references that are in the map.
- First posted on arXiv 11 Apr 2024.

## Builds on (most cited first, 11 of 11)

- [Online Bayesian Goal Inference for Boundedly-Rational Planning Agents](https://mlsanity.com/paper/2006.07532/) (2020)
- [Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary](https://mlsanity.com/paper/1705.00154/) (2017)
- [Landmark-Based Approaches for Goal Recognition as Planning](https://mlsanity.com/paper/1904.11739/) (2019)
- [Interpretable Sequence Classification via Discrete Optimization](https://mlsanity.com/paper/2010.02819/) (2020)
- [Heuristic Online Goal Recognition in Continuous Domains](https://mlsanity.com/paper/1709.09839/) (2017)
- [Goal Recognition as Reinforcement Learning](https://mlsanity.com/paper/2202.06356/) (2022)
- [Goal Recognition as a Deep Learning Task: the GRNet Approach](https://mlsanity.com/paper/2210.02377/) (2022)
- [An LP-Based Approach for Goal Recognition as Planning](https://mlsanity.com/paper/1905.04210/) (2019)
- [A New Model of Plan Recognition](https://mlsanity.com/paper/1301.6700/) (2013)
- [Temporally Extended Goal Recognition in Fully Observable Non-Deterministic Domain Models](https://mlsanity.com/paper/2306.08680/) (2023)
- [Probabilistic State-Dependent Grammars for Plan Recognition](https://mlsanity.com/paper/1301.3888/) (2013)

## Abstract (arXiv)

Goal Recognition is the task by which an observer aims to discern the goals that correspond to plans that comply with the perceived behavior of subject agents given as a sequence of observations. Research on Goal Recognition as Planning encompasses reasoning about the model of a planning task, the observations, and the goals using planning techniques, resulting in very efficient recognition approaches. In this article, we design novel recognition approaches that rely on the Operator-Counting framework, proposing new constraints, and analyze their constraints' properties both theoretically and empirically. The Operator-Counting framework is a technique that efficiently computes heuristic estimates of cost-to-goal using Integer/Linear Programming (IP/LP). In the realm of theory, we prove that the new constraints provide lower bounds on the cost of plans that comply with observations. We also provide an extensive empirical evaluation to assess how the new constraints improve the quality of the solution, and we found that they are especially informed in deciding which goals are unlikely to be part of the solution. Our novel recognition approaches have two pivotal advantages: first, they employ new IP/LP constraints for efficiently recognizing goals; second, we show how the new IP/LP constraints can improve the recognition of goals under both partial and noisy observability.