PRIMAL-algoritmin käyttäytyminen yhteisriippuvuustilanteita sisältävissä karttatopologioissa

Abstract

Työssä tutkitaan G. Sartorettin PRIMAL-algoritmin (”Pathfinding via Reinforcement and Imitation Learning”) toimintaa eri karttatopologioissa, joissa on yhteisriippuvuustilanteita. Erityisesti tutkitaan karttatopologioita, jotka sisältävät pullonkauloja. Algoritmi käyttää kahta koneoppimistekniikkaa, vahvistus- ja mallioppimista, etsimään agenteille nopeimmat reitit maaleihinsa. Agentteja on monta, ja niiden pitää toimia keskenään niin, että ne eivät törmää toisiinsa tai estä toisiaan pääsemästä maaleihinsa. Törmäys tapahtuu, jos kaksi agenttia menee samaan ruutuun samalla hetkellä. Agenttien nopeus päästä maaleihinsa määritellään polkukustannusten summana. Se tarkoittaa agenttien tekemiä liikettä yhteensä, jotta ne pääsevät maaleihinsa. Hypoteesina tutkimuksessa oli, että algoritmi ei suoriudu hyvin polkukustannusten näkökulmasta, kun se kohtaa yhteisriippuvuustilanteita kuten pullonkauloja karttatopologioissa. Yhteisriippuvuustilanteen opettaminen algoritmille on paljon vaikeampaa kuin toisen agentin väistäminen. Agentille ei ole siis opetettu tämän tyylisiä tilanteita, ja tämän takia sen suorituskyky on heikko näissä karttatopologioissa. Jos meillä on karttatopologia, jossa on pullonkaula, agentit väistelevät epäitsekkäästi muita agentteja. Tällä agentit aiheuttavat sen, että kukaan ei mene pullonkaulasta läpi. Algoritmi on opettanut myös agentit mieluummin tutkimaan ympäristöään kuin pysymään paikallaan, ja näin syntyy monta turhaa liikettä ennen kuin nämä yhteisriippuvuustilanteet selviävät. PRIMAL:n kouluttamat agentit pitävät uusien reittien etsinnästä, mutta jos niitä ei ole, polkukustannusten summa voi nousta turhaan. Kokeissa yksinkertaisella kartalla testattiin, kuinka monella liikkeellä kolme agenttia menee pullonkaulan läpi, eli mikä on niiden polkukustannusten summa. Mallilla polkukustannusten summaksi tuli keskiarvoltaan 54.4 liikettä, mutta jos agentit olisivat menneet suorinta reittiä, polkukustannusten summa olisi ollut 34 liikettä. Työssä testattiin valmista PRIMAL-algoritmia ja todettiin, että tutkimus tukee hypoteesia ja algoritmin polkukustannukset nousevat suuriksi näissä tilanteissa. Agentit tekevät turhia liikkeitä ja estävät toisia agentteja pääsemästä maaleihinsa.

This study examines the performance of G. Sartoretti's PRIMAL algorithm ("Pathfinding via Reinforcement and Imitation Learning") in various map topologies which have interdependency scenarios. Special attention is given to map topologies that contain bottlenecks. The algorithm uses two machine learning techniques, reinforcement learning and imitation learning, to find the fastest routes for agents to reach their goals. There are multiple agents, and they must operate in coordination without colliding with each other or blocking one another from reaching their goals. A collision occurs if two agents enter the same cell at the same time. The speed at which agents reach their goals is defined by the total path cost, meaning the total number of movements all agents make to reach their destinations. The hypothesis of the study was that the algorithm performs poorly in terms of path cost when it encounters interdependency scenarios such as bottlenecks in map topologies. Teaching an algorithm to handle interdependent situations is much more challenging than simply teaching it to avoid other agents. The algorithm has not been trained on these types of scenarios, which results in poor performance in such topologies. In a map topology with a bottleneck, agents behave unselfishly by avoiding others, which ironically leads to none of them passing through the bottleneck. The algorithm has also taught the agents to prefer exploring their environment overstaying in place, resulting in many unnecessary actions before the interdependency situation is resolved. Agents trained with PRIMAL enjoy finding new paths, but when no new paths exist, the total path cost can increase unnecessarily. In experiments conducted on a simple map, the number of movements required for three agents to pass through a bottleneck to their total path cost was measured. The model produced an average total path cost of 54,4 moves, whereas if the agents had taken the most direct route, the total path cost would have been 34 moves. The study tested the existing PRIMAL algorithm and found that the results support the hypothesis. The algorithm incurs high path costs in these scenarios. The agents make unnecessary moves and prevent other agents from reaching their goals.