Extensions of Monte Carlo Tree Search into Continuous Action Spaces
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2022-06-13
Department
Major/Subject
Computer Science
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
40 + 1
Series
Abstract
This thesis explored Monte Carlo Tree Search (MCTS) algorithm and its extensions to continuous action spaces. MCTS is a relevant search algorithm used in cutting edge AI design in discrete domains. However, its extensions to continuous action spaces have not been comprehensibly listed and categorized. Furthermore empirical comparison of their performance has been incomplete. This thesis consisted of a literary survey and an empirical comparison of MCTS extensions. The aim was to find out how the different methods work, where they can be applied and how they compare to each other. In addition, the performance of the extensions was compared against each other and other continuous non-MCTS algorithms. The survey found twelve prominent MCTS extensions of varying complexity and performance. These extensions could be categorized into four general approaches: Manual/Informed discretization, Unpruning, Action optimization and Policy optimization. Three of these extension methods were benchmarked in the empirical study: Discrete Upper Confidence Bounds applied to Trees, Progressive Widening and Value-Gradient Upper Confidence Trees. In addition, two baseline algorithms called Random Branching Depth and Covariance Matrix Adaptation Evolution Strategy (CMA-ES) were used to further evaluate the performance of MCTS methods. The results of the performance study suggest that Progressive Widening is the best general purpose MCTS extension when using offline planning in continuous control settings. The results also seem to suggest that MCTS extensions could perform better than CMA-ES when action dimensionality and/or planning horizon depth increases. Further research could be conducted by including more extensions in the performance study. In addition online planning and time limited open loop planning performance also provides an interesting research direction when considering usage in real-time problems.Tämä maisterintyö tutki Monte Carlo Tree Search (MCTS) hakualgoritmiä ja sen laajentamista jatkuviin toiminta-avaruuksiin. MCTS on suosittu hakualgoritmi, jolla on tekoälytutkimuksessa saavutettu osa parhaista tuloksista diskreeteissä toiminta-avaruuksissa, kuten lautapeleissä. MCTS on onnistuneesti laajennettu toimimaan myös jatkuvissa toiminta-avaruuksissa, mutta näitä laajennusmetodeja ei ole tyhjentävästi listattu tai kategorisoitu. Lisäksi empiirinen tutkimus metodien toimintakyvystä on puutteellista. Tämä maisterityö koostuu kirjallisuuskatsauksesta sekä empiirisestä tutkimuksesta. Työn tarkoituksena on löytää miten metodit toimivat, missä niitä voi soveltaa ja miten ne vertautuvat toisiinsa. Tämän lisäksi laajennusmetodien toimintakykyä verrataan toisiinsa sekä myös muihin algoritmeihin, joita käytetään jatkuvissa toiminta-avaruuksissa. Kirjallisuuskatsauksessa löydettiin kaksitoista laajennusmenetelmää, jotka voitiin kategorisoida neljään yleiseen lähestymistapaan: manuaalinen/tietoon perustuva diskretisointi, toiminta-avaruuden kasvatus, toimioptimointi sekä toimintaperiaateoptimointi. Empiiriseen tutkimukseen valittiin kolme menetelmää: Discrete Upper Confidence Bounds applied to Trees, Progressive Widening ja Value-Gradient Upper Confidence Trees. Lisäksi tutkimuksessa käytettiin kahta vertailualgoritmia, jotka eivät perustu MCTS algoritmiin: Covariance Matrix Adaptation Evolution Strategy (CMA-ES) sekä Random Branching Depth. Tutkimuksen tulokset viittaavat siihen, että Progressive Widening on paras MCTS laajennusmenetelmä yleiseen käyttöön jatkuvissa toiminta-avaruuksissa. Tulokset myös vihjaavat, että MCTS menetelmät saattavat toimia paremmin kuin CMA-ES, kun toiminta-avaruuden ja/tai suunnitteluhorisontin pituus kasvaa. Tulevaisuudessa olisi kiinnostavaa nähdä laajempaa tutkimusta eri menetelmien välillä. Esimerkiksi toimintakyky aikarajoitteisessa jatkuvassa toiminta-avaruudessa on tärkeää, kun halutaan toimia tosiaikaisten ongelmien parissa.Description
Supervisor
Hämäläinen, PerttuThesis advisor
Acharya, AdityaKeywords
Monte Carlo tree search, MCTS, continuous action spaces, continuous control, benchmark