This paper focuses on the problem of scaling Combinatory Categorial Grammar (CCG)-based plan recognition to large CCG representations in the context of Real-Time Strategy (RTS) games. Specifically, we present a technique to scale plan recognition to large domain representations using Monte-Carlo Tree Search (MCTS). CCG-based planning and plan recognition (like other domain-configurable planning frameworks) require domain definitions to be either manually authored or learned from data. Prior work has demonstrated successful learning of these CCG domain definitions from data, but these representations can be very large for complex application domains. We propose a MCTS-based approach to search for explanations and predict the goal of a given sequence of observed actions. We evaluate our approach on the RTS game AI testbed microRTS. Our experimental results show our method scales better to these large, learned CCGs than previous CCG-based approaches.

This paper defines a learning algorithm for plan grammars used for plan recognition. The algorithm learns Combinatory Categorial Grammars (CCGs) that capture the structure of plans from a set of successful plan execution traces paired with the goal of the actions. This work is motivated by past work on CCG learning algorithms for natural language processing, and is evaluated on five well know planning domains.

This paper extends existing plan recognition research to handle plans containing loops. We supply an encoding of plans with loops for recognition, based on techniques used to parse lexicalized grammars, and demonstrate its effectiveness empirically. To do this, the paper first shows how encoding plan libraries as context free grammars permits the application of standard rewriting techniques to remove left recursion and ε-productions, thereby enabling polynomial time parsing. However, these techniques alone fail to provide efficient algorithms for plan recognition. We show how the loop-handling methods from formal grammars can be extended to the more general plan recognition problem and provide a method for encoding loops in an existing plan recognition system that scales linearly in the number of loop iterations.

Based on an ongoing attempt to integrate Natural Language instructions with human figure animation, we demonstrate that agents' understanding and use of instructions can complement what they can derive from the environment in which they act. We focus on two attitudes that contribute to agents' behavior—their intentions and their expectations—and shown how Natural Language instructions contribute to such attitudes in ways that complement the environment. We also show that instructions can require more than one context of interpretation and thus that agents' understanding of instructions can evolve as their activity progresses. A significant consequence is that Natural Language understanding in the context of behavior cannot simply be treated as “front end” processing, but rather must be integrated more deeply into the processes that guide an agent's behavior and respond to its perceptions.