Random Search Algorithms for Optimal Control

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.advisorHämäläinen, Perttu, Prof., Aalto University, Department of Media, Finland
dc.contributor.advisorKyrki, Ville, Prof., Aalto University, Department of Electrical Engineering and Automation, Finland
dc.contributor.authorRajamäki, Joose
dc.contributor.departmentTietotekniikan laitosfi
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.labAalto Game Research Groupen
dc.contributor.schoolPerustieteiden korkeakoulufi
dc.contributor.schoolSchool of Scienceen
dc.contributor.supervisorHämäläinen, Perttu, Prof., Aalto University, Department of Media, Finland
dc.date.accessioned2018-09-05T09:03:22Z
dc.date.available2018-09-05T09:03:22Z
dc.date.defence2018-10-09
dc.date.issued2018
dc.description.abstractOptimal control is an important tool in many application areas, it is for example a central tool in robotics. Many widely used methods such as differential dynamic programming (DDP) are based on differentiating the dynamics of the controlled systems and the objective function. The assumption that one would have access to a differentiable model of the entire system does not hold for many systems of interest. For example, collisions break this assumption. In this case one has to resort to random search (Monte Carlo) algorithms. This thesis presents random search algorithms that fall into two categories. The first category is locally optimal sampling based trajectory optimization methods. The second one is real-time capable Monte Carlo tree search (MCTS) methods augmented with supervised machine learning. This thesis presents sampled differential dynamic programming (SaDDP), which is a random search trajectory optimization method, derived from the differential dynamic programming algorithm. SaDDP is derived by relating the quantities of the Taylor-expansion in DDP to the statistics of a multivariate normal distribution. This allows the statistics to be recomputed from sampled data instead of utilizing differentiation to obtain them. The thesis also presents ways to regularize the SaDDP algorithm efficiently.  The real-time capable MCTS methods presented in this thesis enable the real-time control of complicated systems, such as physics-based 3D characters. The methods perform a receding horizon lookahead search and use the data produced by the lookahead search to teach machine learning models how to better search for the actions in the future. The demonstrated combination of receding horizon search and supervised learning is fast to converge and yields robust learning.  The MCTS in this thesis combines information from multiple sources. This thesis presents how to combine the information from various sources in such a way that the search adapts to the information sources agreeing or disagreeing. In addition to new search algorithms, this thesis presents a combination of MCTS and a neural network generative model. This combination enables the neural network to learn that it can perform different actions in a single state.en
dc.description.abstractOptimisäätö on tärkeä väline useilla sovellusalueilla, se on esimerkiksi keskeinen työkalu robotiikassa. Monet laajasti käytössä olevat menetelmät kuten differentiaalinen dynaaminen optimointi (DDP) perustuvat ohjatun järjestelmän dynamiikan ja kohdefunktion differentiointiin. Oletus järjestelmän mallin differentioituvuudesta ei päde monille järjestelmille, joita halutaan säätää. Esimerkiksi törmäykset rikkovat kyseisen olettaman. Tässä tapauksessa on otettava käyttöön satunnaishaku- eli Monte Carlo algoritmit. Tässä väitöskirjassa esitetyt satunnaishakualgoritmit jakautuvat kahteen kategoriaan. Toinen näistä on lokaalisti optimaaliset satunnaishakuun perustuvat liikerataoptimointimenetelmät. Toinen kategorioista on reaaliaikaiseen ohjaukseen kykenevät Monte Carlo puuhakumenetelmät (MCTS), joita on täydennetty koneoppimismenetelmillä, joita koulutetaan valvotulla oppimisella.  Tämä väitöskirja esittää näytteistetyn differentiaalisen dynaamisen optimoinnin (SaDDP), joka on differentiaalisesta dynaamisesta optimoinnista johdettu satunnaishakuun perustuva liikerataoptimointimenetelmä. SaDDP on johdettu rinnastamalla DDP:ssä käytetyn Taylor-kehitelmän suureet moniulotteisen normaalijakauman tunnuslukuihin. Nämä tunnusluvut voidaan laskea uudelleen näytteistä sen sijaan, että käytettäisiin differentiointia niiden laskemiseen. Tämä väitöskirja esittää myös tapoja SaDDP:n tehokkaaseen regularisoimiseen.  Tässä väitöskirjassa esitetyt reaaliaikaiseen säätöön kykenevät MCTS-menetelmät mahdollistavat monimutkaisten järjestelmien, kuten 3D-hahmojen, ohjaamisen. Menetelmät suorittavat loitontuvan horisontin haun ja käyttävät haun tuottamaa dataa koneoppimismallien opettamiseen. Nämä koneoppimismallit vuorostaan avustavat tulevia hakuja. Kyseinen loitontuvan horisontin haku yhdistettynä valvottuun koneoppimiseen konvergoi nopeasti ja saa algoritmin oppimaan vakaasti.  Tämän väitöskirjan MCTS-menetelmät yhdistävät informaatiota useista lähteistä. Tässä väitöskirjassa esitetään, miten näiden lähteiden sisältämä informaatio voidaan yhdistää siten, että menetelmä sopeutuu tilanteisiin, jossa informaatio on yhtenevää taikka ristiriitaista. Näiden uudenlaisten hakualgoritmien lisäksi tässä väitöskirjassa esitetään MCTS-haku, jota avustaa generatiivinen neuroverkko. Tämä yhdistelmä mahdollistaa sen, että neuroverkko voi oppia suorittamaan useita vaihtoehtoisia toimintoja kussakin tilassa.fi
dc.format.extent104 + app. 58
dc.format.mimetypeapplication/pdfen
dc.identifier.isbn978-952-60-8156-4 (electronic)
dc.identifier.isbn978-952-60-8155-7 (printed)
dc.identifier.issn1799-4942 (electronic)
dc.identifier.issn1799-4934 (printed)
dc.identifier.issn1799-4934 (ISSN-L)
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/33837
dc.identifier.urnURN:ISBN:978-952-60-8156-4
dc.language.isoenen
dc.opnTassa, Yuval, Dr., Google, United Kingdom
dc.publisherAalto Universityen
dc.publisherAalto-yliopistofi
dc.relation.haspart[Publication 1]: Joose Rajamäki, Kourosh Naderi, Ville Kyrki, Perttu Hämäläinen. Sampled Differential Dynamic Programming. In IEEE/RSJ International Conference on Intelligent Robots and Systems, Daejeon, South Korea, October 2016. DOI: 10.1109/IROS.2016.7759229
dc.relation.haspart[Publication 2]: Joose Rajamäki, Perttu Hämäläinen. Regularizing Sampled Differential Dynamic Programming. In American Control Conference, Milwaukee, USA, June 2018. DOI: 10.23919/ACC.2018.8430799
dc.relation.haspart[Publication 3]: Joose Rajamäki, Perttu Hämäläinen. Augmenting Sampling Based Controllers with Machine Learning. In ACM SIGGRAPH / Eurographics Symposium on Computer Animation, Los Angeles, USA, July 2017. DOI: 10.1145/3099564.3099579
dc.relation.haspart[Publication 4]: Joose Rajamäki, Perttu Hämäläinen. Continuous Control Monte Carlo Tree Search Informed by Multiple Experts. IEEE Transactions on Visualization and Computer Graphics, July 2018. DOI: 10.1109/TVCG.2018.2849386
dc.relation.haspart[Errata file]: Errata of P3
dc.relation.ispartofseriesAalto University publication series DOCTORAL DISSERTATIONSen
dc.relation.ispartofseries164/2018
dc.revvan de Panne, Michiel, Prof., University of British Columbia, Canada
dc.revMansard, Nicolas, Dr., Laboratoire d'analyse et d'architecture des systèmes, France
dc.subject.keywordMonte Carloen
dc.subject.keywordMonte Carlo tree searchen
dc.subject.keyworddifferential dynamic programmingen
dc.subject.keywordMonte Carlo -puuhakufi
dc.subject.keyworddifferentiaalinen dynaaminen optimointifi
dc.subject.otherAutomationen
dc.subject.otherComputer scienceen
dc.titleRandom Search Algorithms for Optimal Controlen
dc.titleSatunnaishakualgoritmeja optimaaliseen säätöönfi
dc.typeG5 Artikkeliväitöskirjafi
dc.type.dcmitypetexten
dc.type.ontasotDoctoral dissertation (article-based)en
dc.type.ontasotVäitöskirja (artikkeli)fi
local.aalto.acrisexportstatuschecked
local.aalto.archiveyes
local.aalto.formfolder2018_09_04_klo_16_43
Files
Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
isbn9789526081564.pdf
Size:
2.59 MB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
Errata_rajamaki_joose_DD_164_2018 publication_P3.pdf
Size:
98.62 KB
Format:
Adobe Portable Document Format
Description:
Errata Joose Rajamäki DD-164/2018 publication P3