Original title: Monte Carlo Techniques in Planning
Translated title: Monte Carlo Techniques in Planning
Authors: Trunda, Otakar ; Barták, Roman (advisor) ; Toropila, Daniel (referee)
Document type: Master’s theses
Year: 2013
Language: eng
Abstract: [eng] [cze]
The Monte Carlo Tree Search (MCTS) algorithm has recently proved to be able to solve difficult problems in the field of optimization as well as game-playing. It has been able to address several problems that no conventional techniques have been able to solve efficiently. In this thesis we investigate possible ways to use MCTS in the field of planning and scheduling. We analyze the problem theoretically trying to identify possible difficulties when using MCTS in this field. We propose the solutions to these problems based on a modification of the algorithm and preprocessing the planning domain. We present the techniques we have developed for these tasks and we combine them into an applicable algorithm. We specialize the method for a specific kind of planning problems - the transportation problems. We compare our planner with other planning system. Algoritmus Monte Carlo Tree Search (MCTS) v nedávné době prokázal, že dokáže úspěšně řešit těžké problémy v oblasti optimalizace i v oblasti hraní her. Pomocí tohoto algoritmu byly vyřešeny i některé problémy, které dlouho vzdorovaly konvenčním technikám. V této práci zkoumáme možnosti aplikace MCTS v oblasti plánování a rozvrhování. Problém zkoumáme z teoretického pohledu a snažíme se identifikovat případné potíže při použití MCTS v této oblasti. Navrhujeme řešení těchto problémů pomocí úpravy algoritmu a pomocí předzpracování plánovací domény. Představujeme techniky které jsme pro tyto účely vyvinuli a integrujeme je do funkčního celku. Výsledný algoritmus specializujeme na konkrétní typ plánovacích problémů - plánování přepravy. Vzniklý plánovač experimentálně porovnáváme se současnými plánovacími systémy.
Keywords: HTN-learning; Monte Carlo Tree Search; planning; transportation domain; logistické domény; Monte Carlo Tree Search; plánování; učení HTN

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/55318

Permalink: http://www.nusl.cz/ntk/nusl-324610


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses