# Heuristics for Planning, Plan Recognition and Parsing

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2016.

## Built on by (most cited first, 3 of 3)

- [Generalized Planning as Heuristic Search](https://mlsanity.com/paper/2103.14434/) (2021)
- [Generalized Planning as Heuristic Search: A new planning search-space that leverages pointers over objects](https://mlsanity.com/paper/2301.11087/) (2023)
- [HBTP: Heuristic Behavior Tree Planning with Large Language Model Reasoning](https://mlsanity.com/paper/2406.00965/) (2024)

## Abstract (arXiv)

In a recent paper, we have shown that Plan Recognition over STRIPS can be formulated and solved using Classical Planning heuristics and algorithms. In this work, we show that this formulation subsumes the standard formulation of Plan Recognition over libraries through a compilation of libraries into STRIPS theories. The libraries correspond to AND/OR graphs that may be cyclic and where children of AND nodes may be partially ordered. These libraries include Context-Free Grammars as a special case, where the Plan Recognition problem becomes a parsing with missing tokens problem. Plan Recognition over the standard libraries become Planning problems that can be easily solved by any modern planner, while recognition over more complex libraries, including Context-Free Grammars (CFGs), illustrate limitations of current Planning heuristics and suggest improvements that may be relevant in other Planning problems too.