Low-level motion planning techniques must be combined with high-level task planning formalisms in order to generate realistic plans that can be carried out by humans and robots. Previous attempts to integrate these two planning formalisms mostly used either Classical Planning or HTN Planning. Recently, we developed Hierarchical Goal Networks (HGNs), a new hierarchical planning formalism that combines the advantages of HTN and Classical planning, while mitigating some of the disadvantages of each individual formalism. In this paper, we describe our ongoing research on designing a planning formalism and algorithm that exploits the unique features of HGNs to better integrate task and motion planning. We also describe how the proposed planning framework can be instantiated to solve assembly planning problems involving human-robot teams.

In order for robots to interact with humans in the world around them, it is important that they are not just aware of the presence of people, but also able to understand what those people are doing. In particular, interaction involves multiple agents which requires some form of coordination, and this cannot be achieved by acting blindly. The field of plan recognition (PR) studies methods for identifying an observed agent's task or goal given her action sequence. This is often regarded as the inverse of planning which, given a set of goal conditions, aims to derive a sequence of actions that will achieve the goals when performed from a given initial state. Ram ırez and Geffner (2009; 2010) proposed a simple transformation of PR problems into classical planning problems for which off-the-shelf software is available for quick and efficient implementations. However, there is a reliance on the observed agent's optimality which makes this PR technique most useful as a post-processing step when some of the final actions are observed.

A central problem in designing and implementing interactive systems---action selection---is also a core research topic in automated planning. While numerous toolkits are available for building end-to-end interactive systems, the tight coupling of representation, reasoning, and technical frameworks found in these toolkits often makes it difficult to compare or change the underlying domain models. In contrast, the automated planning community provides general-purpose representation languages and multiple planning engines that support these languages. We describe our recent work on automated planning for task-based social interaction, using a robot that must interact with multiple humans in a bartending domain.

Proactive Decision Support (PDS) aims at improving the decision making experience of human decision makers by enhancing both the quality of the decisions and the ease of making them. In this paper, we ask the question what role automated decision-making technologies can play in the deliberative process of the human decision maker.Specifically, we focus on expert humans in the loop who now share a detailed, if not complete, model of the domain with the assistant, but may still be unable to compute plans due to cognitive overload. To this end, we propose a PDS framework RADAR based on research in the automated planning community that aids the human decision maker in constructing plans. We will situate our discussion on principles of interface design laid out in the literature on the degrees of automation and its effect on the collaborative decision-making process. Also, at the heart of our design is the principle of naturalistic decision making which has been shown to be a necessary requirement of such systems, thus focusing more on providing suggestions rather than enforcing decisions and executing actions. We will demonstrate the different properties of such a system through examples in a fire-fighting domain, where human commanders are involved in building response strategies to mitigate a fire outbreak.The paper is written to serve both as a position paper by motivating requirements of an effective proactive decision support system, and also an emerging application of these ideas in the context of the role of an automated planner in human decision making, in a platform that can prove to be a valuable test bed for research on the same.

Inherent human limitations in teaming environments coupled with complex planning problems spur the integration of intelligent decision support (IDS) systems for human-agent planning. However, prior research in human-agent planning has been limited to dyadic interaction between a single human and a single planning agent. In this paper, we highlight an emerging research area of IDS for human team planning, i.e. environments where the agent works with a team of human planners to enhance the quality of their plans and the ease of making them. We review prior works in human-agent planning and identify research challenges for an agent participating in human team planning.

Path planning is a critical part of modern computer games; rare is the game where nothing moves and path planning is unneeded. A* is the workhorse for most path planning applications. Block A* is a state-of-the-art algorithm that is always faster than A* in experiments using game maps. Unlike other methods that improve upon A*'s performance, Block A* is never worse than A* nor require any knowledge of the map. In our experiments, Block A* is ideal for games with randomly generated maps, large maps, or games with a highly dynamic multi-agent environment. Furthermore, in the domain of grid-based any-angle path planning, we show that Block A* is an order of magnitude faster than the previous best any-angle path planning algorithm, Theta*. We empirically show our results using maps from Dragon Age: Origins and Starcraft. Finally, we introduce populated game maps'' as a new test bed that is a better approximation of real game conditions than the standard test beds of this field. The main contributions of this paper is a more rigorous set of experiments for Block A*, and introducing a new test bed (populated game maps) that is a more accurate representation of actual game conditions than the standard test beds.

In this paper we focus on proactive behavior for non-player characters (NPCs) in the first-person shooter (FPS) genre of video games based on goal-oriented planning. Some recent approaches for applying real-time planning in commercial video games show that the existing hardware is starting to follow up on the computing resources needed for such techniques to work well. Nonetheless, it is not clear under which conditions real-time efficiency can be guaranteed. In this paper we give a precise specification of SimpleFPS, a STRIPS planning domain expressed in PDDL that captures some basic planning tasks that may be useful in a first person shooter video game. This is intended to work as a first step towards quantifying the performance of different planning techniques that may be used in real-time to guide the behavior of NPCs. We present a simple tool we developed for generating random planning problem instances in PDDL with user defined properties, and show some preliminary results based on SimpleFPS instances that vary in the size of the domain and two well-known planners from the planning community.

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.

Planning-based techniques are a very powerful tool for automated story generation. However, as the number of possible actions increases, traditional planning techniques suffer from a combinatorial explosion due to large branching factors. In this work, we apply Monte Carlo Tree Search (MCTS) techniques to generate stories in domains with large numbers of possible actions (100). Our approach employs a Bayesian story evaluation method to guide the planning towards believable stories that reach a user defined goal. We generate stories in a novel domain with different type of story goals. Our approach shows an order of magnitude improvement in performance over traditional search techniques.

Game tree search in games with large branching factors is a notoriously hard problem. In this paper, we address this problem with a new sampling strategy for Monte Carlo Tree Search (MCTS) algorithms, called "Naive Sampling", based on a variant of the Multi-armed Bandit problem called the "Combinatorial Multi-armed Bandit" (CMAB) problem. We present a new MCTS algorithm based on Naive Sampling called NaiveMCTS, and evaluate it in the context of real-time strategy (RTS) games. Our results show that as the branching factor grows, NaiveMCTS performs significantly better than other algorithms.