Kartal, Bilal2016-12-192016-12-192016-08http://hdl.handle.net/11299/183362University of Minnesota Ph.D. dissertation. August 2016. Major: Computer Science. Advisors: Stephen Guy, Maria Gini. 1 computer file (PDF); xi, 108 pages.Coordination plays a key role in efficiently solving multi-agent problems such as exploration of unknown environments, search and rescue, and surveillance. Planning in a highly coordinated fashion causes traditional search algorithms to perform poorly as it creates combinatorial search spaces that renders exploration versus exploitation dilemma challenging as well. Recently, there has been great improvement in stochastic planning in large search spaces with sampling based algorithms. One particular algorithm is Monte Carlo Tree Search (MCTS) which is an anytime stochastic planning algorithm. MCTS employs the well-established multi-armed bandit theory to solve optimization problems by asymmetrically sampling actions where it foresees the existence of an optimal solution. In this thesis, we propose new algorithms and heuristics in order to address several challenges arising due to highly coordinated planning in physical and abstract domains. Our algorithms improve scalability for search in large domains, provides data-driven evaluation functions to guide the search algorithm better, and enables finite search algorithms to produce infinite length solutions. In the first part of this thesis, we study two multi-robot planning problems that require high degree of coordination, patrolling and task allocation. The main challenge for these domains is the large search space. For patrolling, we propose a novel search technique, the Monte Carlo Tree Search with Useful Cycles, which can generate optimal cyclic patrol policies with theoretical convergence guarantees. For task allocation, we develop a parallelized MCTS based planner where branch and bound paradigm is integrated to the search algorithm for admissible pruning. In the second part of this thesis, we study two coordinated abstract planning problems within the field of procedural content generation, goal-driven computer narrative generation and Sokoban puzzle level creation. In these problems, virtual agents coordinate their actions to procedurally create stories and puzzles which have numerous application areas ranging from video games to education. We formulate both story generation and Sokoban puzzle generation as optimization problems and propose data-driven heuristic evaluation metrics for efficient coordinated solutions using MCTS.enCoordinationMonte Carlo Tree SearchPlanningRoboticsSearchThesis or Dissertation