We propose a formal design framework to automatically synthesize coordination and control schemes for cooperative multi-agent systems by combining a top-down mission planning with a bottom-up motion planning. The multi-agent system is assigned a global mission, specified as regular languages over all the agents' capabilities, whereas basic motion controllers for each agent shall be designed with respect to given environment description. On one hand, a mission planning layer sits on the top of the proposed framework, decomposing the global mission into local tasks that are in consistency with each agent's individual capabilities, and compositionally verifying the joint effort of the agents via an assume guarantee paradigm. On the other hand, corresponding to these local missions, motion plans associated with each agent are synthesized by composing basic motion primitives, which are verified safe by differential dynamic logic (dL), through a Satisfiability Modulo Theories (SMT) solver that searches feasible solutions in face of constraints due to local task requirements and the environment description. It is shown that the proposed framework can handle changing environments as the motion primitives are reactive in nature, making the motion planning adaptive to local environmental changes. Furthermore, on-line mission reconfiguration can be triggered by the motion planning layer once no feasible solutions can be found through the SMT solver. The effectiveness of the overall design framework is demonstrated by an automated warehouse case study.

Much research has been done to apply auctions, markets, and negotiation mechanisms to solve the multiagent task allocation problem. However, there has been very little work on human-agent group task allocation. We believe that the notion of bounty hunting has good properties for human-agent group interaction in dynamic task allocation problems. We use previous experimental results comparing bounty hunting with auction-like methods to argue why it would be particularly adept at handling scenarios with unreliable collaborators and unexpectedly hard tasks: scenarios we believe highlight difficulties involved in working with humans collaborators.

The creation of effective autonomous agents (bots) for combat scenarios has long been a goal of the gaming industry. However, a secondary consideration is whether the autonomous bots behave like human players; this is especially important for simulation/training applications which aim to instruct participants in real-world tasks. Bots often compensate for a lack of combat acumen with advantages such as accurate targeting, predefined navigational networks, and perfect world knowledge, which makes them challenging but often predictable opponents. In this paper, we examine the problem of teaching a bot to play like a human in first-person shooter game combat scenarios. Our bot learns attack, exploration and targeting policies from data collected from expert human player demonstrations in Unreal Tournament.

We address the challenges of evaluating the fidelity of AI agents that are attempting to produce human-like behaviors in games. To create a believable and engaging game play experience, designers must ensure that their non-player characters (NPCs) behave in a human-like manner. Today, with the wide popularity of massively-multi-player online games, this goal may seem less important. However, if we can reliably produce human-like NPCs, this can open up an entirely new genre of game play. In this paper, we focus on emulating human behaviors in strategic game settings, and focus on a Social Ultimatum Game as the testbed for developing and evaluating a set of metrics for comparing various autonomous agents to human behavior collected from live experiments.

Interactive narrative environments offer significant potential for creating engaging narrative experiences that are tailored to individual users. Increasingly, applications in education, training, and entertainment are leveraging narrative to create rich interactive experiences in virtual storyworlds. A key challenge posed by these environments is devising accurate models of director agents' strategies that determine the most appropriate director action to perform for crafting customized story experiences. A promising approach is developing an empirically informed model of director agents' decision-making strategies. In this paper, we propose a framework for learning models of director agent decision-making strategies by observing human-human interactions in an interactive narrative-centered learning environment. The results are encouraging and suggest that creating empirically driven models of director agent decision-making is a promising approach to interactive narrative.

We describe a heuristic search technique for multi-agent pursuit-evasion games in partially observable Euclidean space where a team of trackers attempt to minimize their uncertainty about an evasive target. Agents' movement and observation capabilities are restricted by polygonal obstacles, while each agent's knowledge of the other agents is limited to direct observation or periodic updates from team members. Our polynomial-time algorithm is able to generate strategies for games in continuous two-dimensional Euclidean space, an improvement over past algorithms that were only applicable to simple gridworld domains. We demonstrate that our algorithm is tolerant of interruptions in communication between agents, continuing to generate good strategies despite long periods of time where agents are unable to communicate directly. Experiments also show that our technique generates effective strategies quickly, with decision times of less than a second for reasonably sized domains with six or more agents.

This paper looks at the challenges and solutions for intelligent mobile agents existing in virtual environments. Representing and using a map of these very large-scale, dynamic environments is a key challenge in providing an autonomous agent for large, online worlds. We look at a method for improving the generation of probabilistic roadmaps by observing and using the movements of other avatars in an environment. We also look at methods for segmenting and scaling the map in very large environments. Finally we extend this to look at generating and updating maps in dynamic environments.

The problem of optimal planning under uncertainty in collaborative multi-agent domains is known to be deeply intractable but still demands a solution. This thesis will explore principled approximation methods that yield tractable approaches to planning for AI assistants, which allow them to understand the intentions of humans and help them achieve their goals. AI assistants are ubiquitous in video games, mak- ing them attractive domains for applying these planning techniques. However, games are also challenging domains, typically having very large state spaces and long planning horizons. The approaches in this thesis will leverage recent advances in Monte-Carlo search, approximation of stochastic dynamics by deterministic dynamics, and hierarchical action representation, to handle domains that are too complex for existing state of the art planners. These planning techniques will be demonstrated across a range of video game domains.

This paper proposes a method for the development of AI for autonomous agents in game worlds modeled by fixed regular grids. This approach uses context behaviors driven by distance maps to support multiple agents in a dynamic environment. This paper introduces the notion of hierarchical distance maps which allow for higher-level goals to be easily specified by designers. We also discuss potential applications of our approach in the design and development of agents and behaviors in the block world genre.

This article describes a technical approach to movement-based interactions between a human interactor and an intelligent agent based on the theatrical Viewpoints movement framework.