MVEX01-19-31 Multi-agent pathfinding med reinforcement learning och Markov decision processes

​Reinforcement learning är ett område inom maskininlärning där en ”agent” iterativt förbättrar sina försök att utföra en uppgift med hjälp av ett belöningssystem. Markov decision processes används ofta när omgivningen representeras av ett antal olika ”tillstånd” och agenten ska optimera en serie beslut enbart med information om sitt nuvarande tillstånd.

Det finns många praktiska tillämpningar där ett antal agenter rör sig mot olika mål i samma omgivning, t ex robotar i en lagerlokal eller självkörande bilar i trafik. I multi-agent pathfinding (MAPF) är omgivningen ofta representerad av ett 2D rutnät, en s.k. gridworld, där agenterna rör sig från ruta till ruta och ska ta sig mot sina givna mål så optimalt som möjligt utan att kollidera eller fastna i trafikstockningar. Dessa problem kan varieras i det oändliga med olika typer av belöningssystem, olika målfunktioner, olika grad av medvetenhet hos agenterna, osv.

Tidigare har algoritmer för att lösa sådana MAPF-problem främst använt sig av centraliserad planering, där systemet behandlas som en enda mångdimensionell agent. Detta innebär dock att beräkningskomplexiteten växer exponentiellt med antal agenter, vilket begränsar både hur många agenter man kan tillåta och hur snabbt systemet kan anpassa sig till förändrade förutsättningar. I det här projektet ska vi implementera och analysera några olika typer av gridworld problem där agenterna styrs helt decentraliserat, i första hand med hjälp av Markov decision processes, men även med hjälp av neurala nätverk om det är möjligt. Vi jämför olika modeller utifrån hur väl de presterar samt deras komplexitet.

Projektkod MVEX01-19-31
Gruppstorlek 3-6 studenter
Målgrupp GU- och Chalmersstudenter. För GU-studenter räknas projektet som ett projekt i Matematisk statistik(MSG900/MSG910).
Projektspecifika förkunskapskrav Grundkurs i programmering krävs. En kurs i datastrukturer och stokastiska processer rekommenderas. 
Se respektive kursplan för allmänna förkunskapskrav. Utöver de allmänna förkunskapskraven i MVEX01 ska Chalmersstudenter ha avklarat kurser i en- och flervariabelanalys, linjär algebra och matematisk statistik.
Handledare Marina Axelson-Fisk
Examinator Maria Roginskaya, Ulla Dinger
Institution Matematiska vetenskaper

Publicerad: må 05 nov 2018.