Stochastic Tree Search for Highly Coordinated Planning
2016-08
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Stochastic Tree Search for Highly Coordinated Planning
Authors
Published Date
2016-08
Publisher
Type
Thesis or Dissertation
Abstract
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.
Description
University of Minnesota Ph.D. dissertation. August 2016. Major: Computer Science. Advisors: Stephen Guy, Maria Gini. 1 computer file (PDF); xi, 108 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Kartal, Bilal. (2016). Stochastic Tree Search for Highly Coordinated Planning. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/183362.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.