String Shuffling over a Gap between Parsing and Plan Recognition

We propose a new probabilistic plan recognition algorithm YR based onan extension of Tomita's Generalized LR (GLR) parser for grammarsenriched with the shuffle operator. YR significantly outperformsprevious approaches based on top down parsers, shows more consistentrun times among similar libraries, and degrades more gracefully asplan library complexity increases. YR also lifts the restrictions onleft-recursion imposed by approaches based on top-down parsingalgorithms. We further propose that context-free shuffle grammars,more than traditional context-free grammars, should be seen as theappropriate analogue of HTN plan libraries in the correspondence ofplan recognition and parsing.