We consider the configuration formation problem in modular robotic systems where a set of singleton modules that are spatially distributed in an environment are required to assume appropriate positions so that they can configure into a new, user-specified target configuration, while simultaneously maximizing the amount of information collected while navigating from their initial to final positions. Each module has a limited energy budget to expend while moving from its initial to goal location. To solve this problem, we propose a budget-limited, heuristic search-based algorithm that finds a path that maximizes the entropy of the expected information along the path. We have analytically proved that our proposed approach converges within finite time. Experimental results show that our planning approach has lower run-time than an auction-based allocation algorithm for selecting modules' spots.

The increasing availability of large text corpora holds the promise of acquiring an unprecedented amount of knowledge from this text. However, current techniques are either specialized to particular domains or do not scale to large corpora. This dissertation develops a new technique for learning open-domain knowledge from unstructured web-scale text corpora. A first application aims to capture common sense facts: given a candidate statement about the world and a large corpus of known facts, is the statement likely to be true? We appeal to a probabilistic relaxation of natural logic -- a logic which uses the syntax of natural language as its logical formalism -- to define a search problem from the query statement to its appropriate support in the knowledge base over valid (or approximately valid) logical inference steps.

State of the art methods for generating non-player character (NPC) tactical behaviors typically depend on hard-coding actions or minimizing a given objective function. In many games however, it is hard to foresee how the NPC should behave to appear intelligent or to accommodate human player preferences for NPC tactics. In this paper we consider an alternative approach, by training NPC tactical behavior via demonstrations. We propose a heuristic search-based planning method based on previously-developed Experience Graphs, which facilitates the use of behavior demonstration data to plan goal-oriented NPC behavior. Our method provides a principled solution to the problem which tolerates some amount of differences in between the training demonstration and the actual problem and yet still grants guarantees on the quality of the solution output.

We construct a large scale of causal knowledge in term of Fabula elements by extracting causal links from existing common sense ontology ConceptNet5. We design a Constrained Monte Carlo Tree Search (cMCTS) algorithm that allows users to specify positive and negative concepts to appear in the generated stories. cMCTS can find a believable causal story plot. We show the merits by experiments and discuss the remedy strategies in cMCTS that may generate incoherent causal plots.

Real-time heuristic search is suitable for time-sensitive pathfinding and planning tasks when an AI-controlled non-playable character must interleave its planning and plan execution. Since its inception in the early 90s, numerous real-time heuristic search algorithms have been proposed. Many of the algorithms also have control parameters leaving a practitioner with a bewildering array of choices. Recent work treated the task of algorithm and parameter selection as a search problem in itself. Such automatically found algorithms outperformed previously known manually designed algorithms on the standard video-game pathfinding benchmarks. In this paper we follow up by selecting an algorithm and parameters automatically per map. Our sampling-based approach is efficient on the standard video-game pathfinding benchmarks. We also apply the approach to per-problem algorithm selection and while it is effective there as well, it is not practical. We offer suggestions on making it so.

The ability to distract opponents is a key mechanic in many stealth games.  Existing search-based approaches to stealth analysis, however, focus entirely on solving the non-detection problem, for which they rely on static, ahead-of-time models of guard movements that do not depend on player interaction.  In this work we extend and optimize an approach based on heuristic search of stealth games to model variation in guard paths as dynamically triggered by player actions.  Our design is expressive, accommodating different distraction designs, including remote activation and time delays.  Using a Unity3D implementation, we show our enhanced search can solve distraction puzzles found in real games, as well as more complex, multiple-distraction level designs.  Our work shows how heuristic search can be applied to dynamically determined contexts, and significantly extends the ability to model and solve stealth games.

Portfolio Online Evolution is a novel method for playing real-time strategy games through evolutionary search in the space of assignments of scripts to individual game units. This method builds on and recombines two recently devised methods for playing multi-action games: (1) Portfolio Greedy Search, which searches in the space of heuristics assigned to units rather than in the space of actions, and (2) Online Evolution, which uses evolution rather than tree search to effectively play games where multiple actions per turn lead to enormous branching factors. The combination of both ideas lead to the use of evolution to search the space of which script/heuristic is assigned to which unit. In this paper, we introduce the ideas of Portfolio Online Evolution and apply it to StarCraft micro, or individual battles. It is shown to outperform all other tested methods in battles of moderate to large size.

Applying game-tree search techniques to RTS games poses a significant challenge, given the large branching factors involved. This paper studies an approach to incorporate knowledge learned offline from game replays to guide the search process. Specifically, we propose to learn Naive Bayesian models predicting the probability of action execution in different game states, and use them to inform the search process of Monte Carlo Tree Search. We evaluate the effect of incorporating these models into several Multiarmed Bandit policies for MCTS in the context of StarCraft, showing a significant improvement in gameplay performance.

In this paper we introduce a computational model based on the concept of symmetry to generate visually pleasing maps of platform games. We cast the problem of generating symmetrical maps as an optimization task and propose a heuristic search algorithm to solve it. A user study using a platform game shows the advantage of our method over other approaches in terms of visual aesthetics and enjoyment. Another user study shows that our method is able to generate maps as visually pleasing as maps created by professional designers.

In this work, we propose a Monte Carlo Tree Search (MCTS) based approach to procedurally generate Sokoban puzzles. Our method generates puzzles through simulated game play, guaranteeing solvability in all generated puzzles. We perform a user study to infer features that are efficient to compute and are highly correlated with expected puzzle difficulty. We combine several of these features into a data-driven evaluation function for MCTS puzzle creation. The resulting algorithm is efficient and can be run in an anytime manner, capable of quickly generating a variety of challenging puzzles. We perform a second user study to validate the predictive capability of our approach, showing a high correlation between increasing puzzle scores and perceived difficulty.