A Probabilistic Framework for Hierarchical Goal Recognition

This paper introduces the first planning-based probabilistic framework for hierarchical goal recognition by integrating Hierarchical Task Networks (HTNs) with a three-stage generative model to infer goal hypotheses under uncertainty.

The Gist

Imagine you are sitting in a coffee shop, watching a stranger. They pick up a napkin, grab a sugar packet, stir their coffee, and then suddenly reach for a blueberry muffin.

Your brain immediately starts playing a game of "What’s their goal?" You don't just see a series of random movements; you see a story. You think, "They are having a breakfast snack," or "They are preparing for a long study session."

You do this because humans are natural experts at Hierarchical Goal Recognition. We don't just track tiny finger movements; we group them into "chapters" (like "making coffee") and "scenes" (like "stirring").

The Problem: The "All-or-Nothing" Robot

Until now, most AI systems that try to do this were a bit too rigid—like a very strict librarian.

If you told a traditional AI, "The person is making coffee," and then the person accidentally dropped a spoon (an "exogenous action" or a random mistake), the AI would panic. It would say, "Error! Dropping a spoon is not in the 'Making Coffee' manual! Therefore, they are NOT making coffee!" It was an all-or-nothing system. It couldn't handle the "messiness" of real life, like noise, mistakes, or random interruptions.

The Solution: The "Detective with a Gut Feeling"

The researchers in this paper have created a new framework that turns the AI from a strict librarian into a skilled detective.

Instead of saying "Yes" or "No" to a goal, this new AI uses probability. It says, "I am 80% sure they are making breakfast, but there's a 20% chance they are just cleaning up."

Here is how the "Detective AI" works, using a three-step process:

1. The Blueprint (Decomposition): The AI looks at a big goal (like "Making a Sandwich") and knows it's made of smaller steps (getting bread, spreading jam, etc.). It understands the "family tree" of actions.
2. The Rehearsal (Linearization): The AI imagines all the different ways someone could actually perform those steps. It knows there isn't just one way to make a sandwich; you could grab the bread first or the jam first.
3. The Comparison (Likelihood): This is the secret sauce. The AI compares what it sees happening in real life to the "rehearsals" it imagined.

Why is this better? (The "Surprise" Factor)

The paper introduces a brilliant way to handle "surprises."

Imagine two suspects:

• Suspect A is a professional chef. To explain why they are holding a knife, you have to assume they are performing a very complex, rare ritual.
• Suspect B is a person making a sandwich. To explain the knife, you just assume they are cutting bread.

The old AI might pick Suspect A because the "ritual" is technically possible. But the new Probabilistic AI says, "Wait, Suspect B is much less surprising. It's much more likely that a normal person is just making a sandwich." It prefers the explanation that requires the least amount of "weirdness" to make sense.

The "Messy Reality" Test

The researchers also made the AI "forgiving." If the person in the coffee shop does something totally random—like checking their phone—the AI doesn't throw away its entire theory. It simply says, "That phone check was a random interruption, but the rest of the actions still look a lot like someone making breakfast."

Summary

In short, this paper moves AI away from being a rigid rule-follower and toward being a nuanced observer. It allows machines to understand human intentions in a world that is messy, unpredictable, and full of "extra" movements that don't always fit the plan.

Technical Summary

Technical Summary: A Probabilistic Framework for Hierarchical Goal Recognition

1. Problem Statement

Goal recognition is the task of inferring an agent's underlying intentions based on observed behaviors. While humans naturally exploit the hierarchical structure of activities (e.g., seeing "chopping onions" as part of "making soup"), existing computational approaches face two major limitations:

• Lack of Probabilistic Integration: Most hierarchical recognizers (specifically those using Hierarchical Task Networks, or HTNs) are deterministic. They perform a binary feasibility check (accept/reject) rather than providing a probability distribution over multiple competing hypotheses. This prevents the system from ranking goals or expressing uncertainty.
• Fragility to Noise (Exogenous Actions): Deterministic HTN recognizers require every observed action to be strictly licensed by the task decomposition. If an agent performs a single "irrelevant" or "noisy" action (an exogenous action), the recognizer may reject the correct goal entirely.

2. Methodology

The authors propose the first planning-based probabilistic framework for hierarchical goal recognition over HTNs. The core of the approach is casting goal recognition as a Bayesian inference problem.

A. The Three-Stage Generative Model
To estimate the likelihood $P(\hat{o} | N_g, s_0)$—the probability of seeing observations $\hat{o}$ given a goal hypothesis $N_g$—the authors define a three-stage process:

1. Network Decomposition: The high-level goal is decomposed into a primitive task network using a Boltzmann (softmax) distribution, which biases the model toward "cheaper" or more efficient decompositions.
2. Executable Linearization: The primitive tasks are converted into a sequence of actions (a plan) by sampling from available actions that satisfy both precedence constraints and state preconditions.
3. Observation Model: The observed trace is compared against the generated plan. This stage accounts for the "progress" of the agent (how many steps have been executed) and uses dynamic programming to handle partial observability (where observations are a subsequence of the plan).

B. Practical Inference via Approximation
Since calculating the exact marginal likelihood is computationally intractable, the authors approximate it using a ratio of two representative executions obtained from an off-the-shelf HTN planner:

• Numerator: The most probable execution that is consistent with the observations (found using an "observation-enforcing" compilation).
• Denominator: The most probable unconstrained execution (the "base" plan for that goal).
  This ratio effectively measures how much "surprise" or "cost" is incurred by forcing the agent to match the observations.

C. Handling Exogenous Actions
The framework incorporates task insertion semantics, allowing the model to account for actions that are not part of the goal's hierarchy. This allows the posterior probability of a correct goal to remain non-zero even if the agent performs noisy or irrelevant actions.

3. Key Contributions

• First Probabilistic HTN Framework: Integrates hierarchical task structures with Bayesian inference.
• Likelihood Approximation Algorithm: Provides a way to use standard, non-probabilistic HTN planners to perform complex probabilistic reasoning.
• Top-K Hypothesis Selection: A practical strategy to handle large goal sets and planner incompleteness by focusing on the most promising candidates.
• Robustness to Noise: A theoretical and practical framework for handling exogenous actions through task insertion.

4. Experimental Results

The framework was evaluated on the Kitchen and Monroe domains, comparing it against the current state-of-the-art deterministic HTN recognizer.

• Improved Accuracy: The probabilistic model significantly outperformed the baseline in top-3 and top-5 accuracy, particularly in the early stages of observation (when uncertainty is highest).
• Robustness to Partial Observations: Even when 20% of the actions were missing, the probabilistic approach maintained a higher degree of recognition accuracy.
• Handling Noise: Sanity checks demonstrated that while the baseline failed or produced "hallucinated" goals when exogenous actions were injected, the proposed framework correctly maintained the ground-truth goal as a high-probability hypothesis.
• Computational Trade-off: There is a moderate increase in runtime (e.g., from ~5s to ~24s in the Kitchen domain), which the authors argue is a justified cost for the significant gains in reliability.

5. Significance

This work moves goal recognition from a "brittle" feasibility problem toward a "robust" reasoning problem. By grounding probabilistic inference in hierarchical planning, it provides a foundation for more practical AI applications—such as human-robot collaboration—where agents must reason about human intentions amidst noisy, incomplete, and sub-optimal behavior.