aalto1 untyped-item.component.html
Procedural generation of route network layouts for multi-agent navigation simulation
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Electrical Engineering |
Bachelor'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
Department
Major/Subject
Mcode
Language
en
Pages
33
Series
Abstract
As logistics automation increases, smart warehouses require more extensive and efficient navigation algorithms. Reinforcement Learning (RL) can be utilized in learning-based navigation methods. As these navigation methods learn, they tend to achieve the best performance only in their specific training environment. Consequently, a significant challenge in RL is overfitting to static training environments. This thesis develops a procedural route network generator and investigates its suitability for training navigation models.
This thesis uses constructive research method by developing procedural generator. The generation process consists of dynamic node dropout, adding spatial noise to nodes, forming bottlenecks and adding directionality to the edges. The algorithm mathematically ensures strong connectivity of the graphs. This guarantees the navigability of the environment and prevents unsolvable situations in simulations. The algorithm takes into account real-world traffic constraints, such as unidirectional routes and narrow crossing points. These constraints force the agents to learn dynamic routing and collision avoidance, especially in high-traffic bottlenecks.
The variation created by the generator is quantitively evaluated. The results indicate that the generator is capable of producing significant structural variation even with standardized input parameters. A high coefficient of variation is observed in the metrics describing navigation difficulty. This proves that the generator creates different navigation challenges in each generation cycle. Furthermore, the thesis compares navigation models trained on static and procedurally generated route networks. The comparison found that procedural content generation improves the performance of the agents in new testing environments. The variation provided by the generated networks forces agents to learn generalizable navigation policies. Thus, procedural generation offers an effective and scalable solution for creating training and evaluation environments.
Logistiikan automaation lisääntyessä älykkäissä varastoissa tarvitaan entistä laajempia ja tehokkaampia navigointialgoritmeja. Vahvistusoppimista (RL, Reinforcement Learning) pystytään hyödyntämään oppimiseen perustuvissa navigaatiometodeissa. Näiden navigointimenetelmien oppiessa ne pyrkivät saavuttamaan parhaan suorituskyvyn vain tietyssä omassa koulutusympäristössään. Näin ollen vahvistusoppimisen merkittävänä haasteena on algoritmien ylioppiminen staattisiin koulutusympäristöihin. Tässä kandidaatintyössä kehitetään proseduraalinen generaattori reittiverkostojen luomiseksi ja tutkitaan sen soveltuvuutta navigointimallien koulutuksessa.
Työssä sovelletaan konstruktiivista tutkimusmenetelmää kehittämällä proseduraalinen generaattori. Generointiprosessi koostuu dynaamisesta solmujen poistamisesta, paikkakohinan lisäämisestä soluihin, pullonkaulojen muodostamisesta sekä reittien suuntauksesta. Algoritmi varmistaa matemaattisesti graafien vahvan yhtenäisyyden. Tämä takaa ympäristöjen navigoitavuuden ja estää ratkaisemattomien tilanteiden syntymisen simulaatiossa. Menetelmässä huomioidaan reaalimaailman liikenteen rajoitteet, kuten yksisuuntaiset kulkuväylät ja kapeat ylityskohdat. Nämä rajoitteet pakottavat agentit oppimaan dynaamista reitinvalintaa sekä törmäyksenestoa etenkin korkean liikenteen pullonkauloissa.
Generaattorin luomaa vaihtelua arvioidaan kvantitatiivisesti. Tulokset osoittavat, että generaattori kykenee tuottamaan merkittävää rakenteellista vaihtelua myös vakioiduilla syöteparametreilla. Erityisesti verkon navigointivaikeutta kuvaavissa ominaisuuksissa havaittu korkea variaatiokerroin todistaa generaattorin luovan uudenlaisia navigointihaasteita jokaisella generointisyklillä. Lisäksi työssä verrataan staattisilla sekä proseduraalisesti luoduilla reittiverkostoilla koulutettuja navigointimalleja. Vertailussa todettiin proseduraalisen sisällöntuoton parantavan agenttien suorituskykyä uusissa testiympäristöissä. Generoitujen verkkojen tarjoama vaihtelu pakottaa agentit oppimaan yleistettäviä navigointipolitiikkoja. Täten, proseduraalinen generointi tarjoaa tehokkaan ja skaalautuvan ratkaisun koulutus- ja arviointiympäristöjen luomiseen.