Introduction
Goal recognition is a fundamental capability in artificial intelligence, enabling systems to infer an agent's hidden intent by observing a sequence of actions. Whether a robot is assisting a human in a kitchen or a software agent is predicting a user's workflow, the ability to anticipate goals is crucial for proactive collaboration. Traditionally, goal recognition algorithms have relied on the "closed-world assumption," which posits that the observer possesses a complete and perfectly accurate model of the domain—including every possible action, precondition, and effect.
In real-world applications, however, this assumption rarely holds. Domain models are frequently "leaky" or incomplete due to action ambiguity (uncertainty about how a task is performed) or noisy sensors (failure to detect state changes). When an observer's model is missing critical information, standard recognition techniques often fail because they cannot find a valid logical path from the observations to the hypothesized goal. This paper, originally presented at AAAI-18, addresses this gap by proposing a landmark-based heuristic designed specifically for incomplete domain models.
Methodology
The authors introduce a framework that explicitly accounts for uncertainty by categorizing domain elements into "known" and "possible" preconditions and effects. To navigate this uncertainty, the approach utilizes three primary technical components:
1. Optimistic Relaxed Planning Graph (ORPG)
Standard planning often uses a Relaxed Planning Graph (RPG), which simplifies the problem by ignoring the negative side effects of actions. The authors extend this into an Optimistic Relaxed Planning Graph (ORPG). This structure assumes that all "possible" preconditions are met and all "possible" effects occur. By adopting this optimistic stance, the system can identify potential paths to a goal that would otherwise appear unreachable in a "broken" or incomplete model.
2. Landmark Extraction and Classification
Landmarks are facts or states that must be achieved at some point for a goal to be reached. In an incomplete model, landmarks are categorized into three types:
- Definite Landmarks: Facts that are strictly required based on known domain effects.
- Possible Landmarks: Facts that may be necessary depending on whether "possible" effects are actually required in the real world.
- Overlooked Landmarks: These are landmarks not identified during initial analysis but discovered dynamically as observations arrive. If a goal becomes unsolvable when a specific fact is removed during the observation sequence, that fact is identified as a hidden requirement.
3. The Landmark Heuristic ($h_{GR}$)
Rather than relying on computationally expensive probabilistic equations or plan compilations, the authors propose a ratio-based heuristic, $h_{GR}$. This heuristic calculates progress toward a goal by comparing the number of achieved landmarks (definite, possible, and overlooked) against the total number of landmarks required for that specific goal. This allows for a "lighter" and faster inference process.
Experimental Design
To evaluate the robustness of the $h_{GR}$ heuristic, the researchers developed a new benchmark by modifying 15 standard AI planning domains. They systematically introduced "model blindness" by stripping information and adding "possible" annotations, creating scenarios ranging from 20% to 80% incompleteness. This rigorous testing aimed to determine how well the system could maintain accuracy as the observer's knowledge of the world diminished.
Key Insights and Results
- Robustness to Ignorance: The heuristic maintained high accuracy even when the domain model was missing up to 80% of its information. The "optimistic" approach ensures that the system doesn't prematurely rule out valid goal hypotheses.
- Computational Efficiency: By utilizing graph-based landmark extraction instead of exhaustive plan generation or complex compilation methods, the algorithm is significantly faster than state-of-the-art probabilistic alternatives. This makes it more suitable for real-time applications.
- The Value of Dynamic Discovery: The inclusion of "overlooked" landmarks—those discovered on the fly—was found to be a critical factor in boosting the system's ability to distinguish between competing goal hypotheses in highly incomplete models.
Limitations and Future Directions
While the proposed framework effectively handles an incomplete observer model, it currently assumes that the agent being observed is acting rationally according to a complete model. It does not yet account for agents who might be making mistakes or acting irrationally.
Future research directions suggested by the authors include refining the heuristic to weight "definite" landmarks more heavily than "possible" ones and extending the technique to handle models that are not just incomplete, but actively incorrect (containing false information). Additionally, integrating this approach with probabilistic sensor data remains a key challenge for deployment in physical robotic environments.
Summary updated