In this article, we work towards the goal of developing agents that can learn to act in complex worlds. We develop a probabilistic, relational planning rule representation that compactly models noisy, nondeterministic action effects, and show how such rules can be effectively learned. Through experiments in simple planning domains and a 3D simulated blocks world with realistic physics, we demonstrate that this learning algorithm allows agents to effectively model world dynamics.

Many combinatorial optimization problems such as the bin packing and multiple knapsack problems involve assigning a set of discrete objects to multiple containers. These problems can be used to model task and resource allocation problems in multi-agent systems and distributed systms, and can also be found as subproblems of scheduling problems. We propose bin completion, a branch-and-bound strategy for one-dimensional, multicontainer packing problems. Bin completion combines a bin-oriented search space with a powerful dominance criterion that enables us to prune much of the space. The performance of the basic bin completion framework can be enhanced by using a number of extensions, including nogood-based pruning techniques that allow further exploitation of the dominance criterion. Bin completion is applied to four problems: multiple knapsack, bin covering, min-cost covering, and bin packing. We show that our bin completion algorithms yield new, state-of-the-art results for the multiple knapsack, bin covering, and min-cost covering problems, outperforming previous algorithms by several orders of magnitude with respect to runtime on some classes of hard, random problem instances. For the bin packing problem, we demonstrate significant improvements compared to most previous results, but show that bin completion is not competitive with current state-of-the-art cutting-stock based approaches.

Agency, being one's ability to perform an action and have some influence over the world, is fundamental to interactive entertainment. Although much of the games industry is concerned with providing more agency to its players, what seems to matter more is how much agency each player will actually perceive. In this paper, we present a computational model of this phenomena, based on the notion that the amount of agency that one perceives depends on how much they desire the outcomes that result from their decisions. Using a structure for high-agency stories that we designed specifically for this intent, we present the results of a 141-participant user study that tests our model's ability to select subsequent events in an original interactive story. Using a newly validated survey instrument for measuring both agency and fun, we found with a high degree of confidence that event sequences selected by our model result in players perceiving more agency than players who experience event sequences that our model does not recommend.

Gameplay in real-time strategy games seems somehow to be confined to a de facto standard where economical micro-management is equally important as combat strategy, if not more important. To enable stronger combat-oriented gameplay without sacrificing other key aspects of the genre, we propose an automated system for scheduling unit training, which we believe may allow the exploration of new paradigms of play. To be accepted by the player, such a system must, among other things, be efficient and reliable, which is a non-trivial task considering the highly dynamic nature of the environment in this genre of games. To overcome such a challenge, we propose a system inspired in the swarm intelligence demonstrated by social insects, namely wasps, and describe its limitations and benefits, based on the evaluation of an implementation of the approach as a modification of the game Warcraft III The Frozen Throne (Blizzard Entertainment, 2003).

Authoring interactive stories where the player is afforded a wide range of social interactions results in a very large space of possible social and story situations. The amount of effort required to individually author for each of these circumstances can quickly become intractable. The social AI system Comme il Faut (CiF) aims to reduce the burden on the author by providing a playable model of social interaction where the author provides reusable and recombinable representations of social norms and social interactions. Motivated through examples from an in-development video game, Prom Week, this paper provides a detailed description of the structures with which CiF represents social knowledge and how this knowledge is employed to simulate social interactions between characters.

Online multiplayer gaming has emerged as a popular form of entertainment. the course of a multiplayer game, playerinteractions may result in interesting emer- gent narratives that go unnoticed. Afterthought is a system that monitors player activity, recognizes instances of story elements in gameplay and renders cinematic highlights of the story-oriented game play, allowing players to view these emergent narratives after completing their gameplay session. This paper describes Afterthought’s implementation as well as an empirical human-subjects evaluation of the effectiveness of the cinematics that it creates.

The task of keyhole (unobtrusive) plan recognition is central to adaptive game AI. “Tech trees” or “build trees” are the core of real-time strategy (RTS) game strategic (long term) planning. This paper presents a generic and simple Bayesian model for RTS build tree prediction from noisy observations, which parameters are learned from replays (game logs). This unsupervised machine learning approach involves minimal work for the game developers as it leverage players’ data (com- mon in RTS). We applied it to StarCraft1 and showed that it yields high quality and robust predictions, that can feed an adaptive AI.

In recent years, real-time strategy (RTS) games have gained interest in the AI research community for their multitude of challenging subproblems — such as collaborative pathfinding, effective resource allocation and unit targeting, to name a few. In this paper we consider the build order problem in RTS games in which we need to find concurrent action sequences that, constrained by unit dependencies and resource availability, create a certain number of units and structures in the shortest possible time span. We present abstractions and heuristics that speed up the search for approximative solutions considerably in the game of StarCraft, and show the efficacy of our method by comparing its real-time performance with that of professional StarCraft players.

Conflict is an essential element of interesting stories. In previous work, we proposed a formal model of narrative conflict. We also described 7 dimensions which can be used to distinguish one conflict from another: participants, subject, duration, balance, directness, intensity, and resolution. This paper presents the results of an experiment designed to measure how well our metrics for balance, directness, intensity, and resolution predict the responses of human readers when asked to measure these same values in a set of four stories. We conclude that our metrics are able to rank stories similarly to human readers.

Since early days of Artificial Intelligence (AI), one of the We present a computational approach for creating new goals has been to procedurally simulate the human ability types of magical and science fiction objects by of storytelling. Many story generation systems (Meehan extrapolating and combining existing object types. The 1981; Lebowitz 1985; Turner 1992; Pérez y Pérez and approach described here augments the creativity of planbased Sharples 2001; Cavazza, Charles, and Mead 2002; Riedl story generators such as that by Riedl and Young and Young 2010; Gervás et al. 2005) begin with a (2006). We empower a traditional story planner with the predefined world configuration. Such configurations ability to plan with analogies. We incrementally modify include unchangeable facts about the fictional world such behaviors of known objects based on a consistent set of as what objects exist, how they relate to each other and analogies with backward chaining and combine behaviors what events can happen. With the initial world of multiple objects to create a new behavior. The process configuration, story generators build stories, the execution results in a new gadget that can cause desired changes in of which transform and evolve the world. As most story the fictional world that are impossible or improbable to generators accept the initial world as a given rather than achieve by other means.