Bakalářská práce

Navigace bludištěm pomocí prohledávání stromu metodou Monte Carlo

Maze Navigation via Monte Carlo Tree Search

Ján Petrák
Anotace

Táto práca používa Monte Carlo Tree Search (MCTS) v abstraktnej doméne navigácie robota v bludisku podobnom mriežke (podobnému ako v "Hallway" benchmarku), sťaženej tým, že pohyb robota podlieha pravdepodobnostným chybám. Prvá časť práce poskytuje prehľad algoritmu MCTS. Druhá časť analyzuje efekty zmien MCTS parametrov a na základe týchto efektov navrhuje ich vhodné nastavenie. Posledná časť práce predstavuje a vyhodnocuje niekoľko doménovo závislých MCTS heuristík.

Abstract

The thesis uses Monte Carlo Tree Search (MCTS) in the abstract domain of robot navigation in a grid-like maze (similar to the one in the Hallway benchmark), hardened by the robot's movement being subject to probabilistic errors. The first part of the thesis gives an overview of the MCTS algorithm. The second part analyses the effects of changing MCTS parameters, and proposes a suitable parameter setup …více

Klíčová slova
maze navigation Monte Carlo Tree Search Markov Decision Process heuristics AI
Zadání práce
The aim of the thesis is to investigate the effect of parameter selection and additional domain-dependent heuristics on the performance of the Monte Carlo tree search method (MCTS) in the abstract domain of robot navigation in a grid-like maze.

More specifically, the work on the thesis should consist of:
1. Implementing suitable representations of the grid-maze domain in the AI-toolbox framework and experimental evaluation of these representations.
2. Evaluating methods for selection of the exploration parameter in MCTS and their effect on the performance in the grid-maze domain.
3. Design, implementation, and evaluation of at least two domain-dependent MCTS heuristics for the grid-maze domain.
4. Presentation of the aforementioned experimental results, as well as their discussion in the written part of the thesis. The thesis will also contain an overview of the MCTS method.
Administrativní informace
Práce zkontrolována:
28. 5. 2019 12:51, doc. RNDr. Petr Novotný, Ph.D., učo 172743
Plný text práce
476,3 KB / soubor PDF
Přílohy (1)
Jazyk práce
angličtina angličtina
Termín obhajoby
28. 6. 2019
Práce byla úspěšně obhájena

Vedoucí

doc. RNDr. Petr Novotný, Ph.D., učo 172743
KTP FI MU

Oponent

doc. RNDr. Tomáš Brázdil, Ph.D., MBA, učo 4074
KSUZD FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Aplikovaná informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.