In Real-Time Strategy (RTS) video games, players (controlled by humans or computers) build structures and recruit armies, fight for space and resources in order to control strategic points, destroy the opposing force and ultimately win the game. Players need to predict where and how the opponents will strike in order to best defend themselves. Conversely, assessing how the opponents will defend themselves is crucial to mounting a successful attack while exploiting the vulnerabilities in the opponent's defence strategy. In this context, to be truly adaptable, computer-controlled players need to recognize their opponents' behaviour, their goals, and their plans to achieve those goals. In this paper we analyze the algorithmic challenges behind behaviour recognition in RTS games and discuss a generic RTS behaviour recognition system that we are developing to address those challenges. The application domain is that of RTS games, but many of the key points we discuss also apply to other video game genres such as multiplayer first person shooter (FPS) games.

Previous work on the YAPPR plan recognition system provided algorithms for translating conventional HTN plan libraries into lexicalized grammars and treated the problem of plan recognition as one of parsing. To produce these grammars required a fixed bound for any loops within the grammar and a presented a problem for optional actions within HTN plans. In this work we show that well known transformations from formal language theory can be used to rewrite the plan grammars to remove these limitations on the plan libraries.

We present a formal approach for combining programming by demonstration (PbD) with programming by instruction (PbI) — a largely unsolved problem. Our solution is based on the integration of two successful formalisms: version space algebras and the logic programming language Golog. Version space algebras have been successfully applied to programming by demonstration. Intuitively, a version space describes a set of candidate procedures and a learner filters this space as necessary to be consistent with all given demonstrations of the target procedure. Golog, on the other hand, is a logical programming language defined in the situation calculus that allows for the specification of non-deterministic programs. While Golog was originally proposed as a means for integrating programming and automated planning, we show that it serves equally well as a formal framework for integrating PbD and PbI. Our approach is the result of two key insights: (a) Golog programs can be used to define version spaces, and (b) with only a minor augmentation, the existing Golog semantics readily provides the update-function for such version spaces, given demonstrations. Moreover, as we will show, two or more programs can be symbolically synchronized, resulting in the intersection of two, possibly infinite, version spaces. The framework thus allows for a rather flexible integration of PbD and PbI, and in addition establishes a new connection between two active research areas, enabling cross-fertilization.

A metareasoning problem involves three parts: 1) a set of concrete problem domains; 2) reasoners to reason about the problems; and, 3) metareasoners to reason about the reasoners. We believe that the metareasoning community would benefit from agreeing on the first two problems. To support this kind of collaboration, we offer an open source 3D simulator containing everyday, commonsense problems that take place in kitchens. This paper presents several arguments for using a simulator to solve commonsense problems. The paper concludes by describing future work in simulator-based unified generative benchmarks for AI.

Many approaches were explored in recent years to introduce principles of metacognition and meta-learning into cognitive architectures, yet none of them resulted in a scalable human-like learner. This work presents an approach intended to fill the gap between human self-regulated learners and artificial learners by introducing a new spin of the familiar core cognitive architecture paradigm, taking it to a meta-level. The resultant architecture enables in artifacts exclusively human higher cognitive and learning abilities: specifically, deliberative new knowledge construction. Model predictions agree with results of a pilot study with human subjects.

It is still unclear what metacognition is. Two main theories about metacognition are reviewed, each of which claims to provide a better explanation of the phenomenon, while discrediting the other theory as inappropriate. My claim is that in order to do justice to the complex phenomenon of metacognition, we must distinguish two levels of this capacity. It can be shown that each of these theories has been trying to explain only one of the two levels and that, consequently, the conflict between them can be dissolved. Finally, I characterize each level and explain some of their interactions.

It is crucial for social systems to adapt to the dynamics of open environments. This adaptation process becomes especially challenging in the context of multiagent systems. In this paper, we argue that multiagent meta-level control is an effective way to determine when this adaptation process should be done and how much effort should be invested in adaptation as opposed to continuing with the current action plan. We develop a reinforcement learning based mechanism for multiagent meta-level control that facilitates the metalevel control component of each agent to learn policies in a decentralized fashion that (a) it can efficiently support agent interactions with other agents and (b) reorganize the underlying network when needed. We evaluate this mechanism in the context of a multiagent tornado tracking application called NetRads. Empirical results show that adaptive multiagent meta-level control significantly improves the performance of the tornado tracking network for a variety of weather scenarios.

One of the challenges of multiagent decision making is that the behavior needed to maximize utility can depend on what other agents choose to do: sometimes there is no "right" answer in the absence of knowledge of how opponents will act. The Nash equilibrium is a sensible choice of behavior because it represents a mutual best response. But, even when there is a unique equilibrium, other players are under no obligation to take part in it. This observation has been forcefully illustrated in the behavioral economics community where repeated experiments have shown individuals playing Nash equilibria and performing badly as a result. In this paper, we show how to apply a tool from behavioral economics called the Cognitive Hierarchy (CH) to the design of agents in general sum games. We attack the recently introduced ``Lemonade Game'' and show how the results of an open competition are well explained by CH. We believe this game, and perhaps many other similar games, boils down to predicting how deeply other agents in the game will be reasoning. An agent that does not reason enough risks being exploited by its opponents, while an agent that reasons too much may not be able to interact productively with its opponents. We demonstrate these ideas by presenting empirical results using agents from the competition and idealizations arising from a CH analysis.

In this paper we apply a Monte-Carlo Tree Search implementation that is boosted with domain knowledge to the game of poker. More specifically, we integrate an opponent model in the Monte-Carlo Tree Search algorithm to produce a strong poker playing program. Opponent models allow the search algorithm to focus on relevant parts of the game-tree. We use an opponent modelling approach that starts from a (learned) prior, i.e., general expectations about opponent behavior, and then learns a relational regression tree-function that adapts these priors to specific opponents. Our modelling approach can generate detailed game features or relations on-the-fly. Additionally, using a prior we can already make reasonable predictions even when limited experience is available for a particular player. We show that Monte-Carlo Tree Search with integrated opponent models performs well against state-of-the-art poker programs.

Distributed Partially Observable Markov Decision Processes (DEC-POMDPs) are a popular planning framework for multiagent teamwork to compute (near-)optimal plans. However, these methods assume a complete and correct world model, which is often violated in real-world domains. We provide a new algorithm for DEC-POMDPs that is more robust to model uncertainty, with a focus on domains with sparse agent interactions. Our STC algorithm relies on the following key ideas: (1) reduce planning-time computation by shifting some of the burden to execution-time reasoning, (2) exploit sparse interactions between agents, and (3) maintain an approximate model of agents’ beliefs. We empirically show that STC is often substantially faster to existing DEC-POMDP methods without sacrificing reward performance.