國立虎尾科技大學 |

Stochastic Tree Search for Highly Coordinated Planning.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Stochastic Tree Search for Highly Coordinated Planning./
Author:	Kartal, Bilal.
Description:	1 online resource (125 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 78-04(E), Section: B.
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9781369354805

Stochastic Tree Search for Highly Coordinated Planning.
Kartal, Bilal.

Stochastic Tree Search for Highly Coordinated Planning. - 1 online resource (125 pages)

Source: Dissertation Abstracts International, Volume: 78-04(E), Section: B.

Thesis (Ph.D.)--University of Minnesota, 2016.

Includes bibliographical references

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.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9781369354805Subjects--Topical Terms:

573171
Computer science.
Index Terms--Genre/Form:

554714
Electronic books.

Stochastic Tree Search for Highly Coordinated Planning.
LDR:03510ntm a2200349K 4500 001 913663
005 20180622095235.5
006 m o u
007 cr mn||||a|a||
008 190606s2016 xx obm 000 0 eng d
020 $a 9781369354805
035 $a (MiAaPQ)AAI10192715
035 $a (MiAaPQ)umn:17460
035 $a AAI10192715
040 $a MiAaPQ $b eng $c MiAaPQ
100 1 $a Kartal, Bilal. $3 1186594
245 1 0 $a Stochastic Tree Search for Highly Coordinated Planning.
264 0 $c 2016
300 $a 1 online resource (125 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 78-04(E), Section: B.
500 $a Advisers: Stephen J. Guy; Maria Gini.
502 $a Thesis (Ph.D.)--University of Minnesota, 2016.
504 $a Includes bibliographical references
520 $a 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.
520 $a 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.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
650 4 $a Artificial intelligence. $3 559380
650 4 $a Robotics. $3 561941
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0800
690 $a 0771
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of Minnesota. $b Computer Science. $3 1180176
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10192715 $z click for full text (PQDT)