Complexity in Decision-making with Applications to Large-scale and Human-in-the-loop Systems
Tid: Ti 2024-12-10 kl 09.00
Plats: Kollegiesalen, Brinellvägen 8, Stockholm
Videolänk: https://kth-se.zoom.us/j/63934653631
Språk: Engelska
Ämnesområde: Elektro- och systemteknik
Respondent: Elis Stefansson , Reglerteknik
Opponent: Professor Majid Zamani, University of Colorado, Boulder, CO, USA
Handledare: Professor Karl H. Johansson, Reglerteknik; Professor Henrik Sandberg, Reglerteknik
QC 20241118
Abstract
Autonoma system är viktiga komponenter i utvecklingen av det moderna samhället genom intelligenta transporter, energi och byggnader. Komplexiteten i beslut och mänskliga interaktioner i dessa system växer enormt. Därför utvecklar vi i denna avhandling styrenheter som ger låg beräkningskomplexitet och tar hänsyn till mänsklig interaktion.
I den första delen av avhandlingen formaliserar vi komplexitet i beslutsfattande, föreslår kontrollalgoritmer med låg komplexitet och beräkningseffektiva designmetoder. Mer exakt presenterar vi först ett planeringsobjektiv för styrsystem som modelleras som finita tillståndsmaskiner, vilket ger en explicit avvägning mellan en styrlags prestanda och dess Kolmogorov-komplexitet. Detta mål är svårt att optimera eftersom dynamisk programmering visar sig vara ogenomförbar. Trots detta föreslår vi två heuristiska algoritmer för att beräkna styrlagar med låg komplexitet, vilka empiriskt ger goda resultat. Vi undersöker sedan planering av kortaste vägen i stora system som modelleras som hierarkiska finita tillståndsmaskiner. Vi presenterar en planeringsalgoritm med låg tidskomplexitet som skalar väl med systemstorleken. Beräkningstiden minskas genom att man i förväg beräknar optimala utgångskostnader för varje maskin och sedan använder dem för att ta bort irrelevanta delar av hierarkin. Vi presenterar också en algoritm för kortaste vägen för grafer, som först hittar en hierarkisk dekomposition och sedan använder den för att snabbt beräkna kortaste vägen. I värsta fall har algoritmen nästan samma tidskomplexitet som Dijkstras algoritm, men är betydligt snabbare om det finns en hierarkisk struktur i grafen. Slutligen visar vi hur man effektivt kan beräkna styrlagar baserade på Hamilton-Jacobi-Bellman-ekvationen med hjälp av tensor dekompositioner.
I den andra delen av avhandlingen behandlar vi human-in-the-loop-system och förutser mänskligt beslutsfattande i sådana system. Vi börjar med att förutse interaktionen mellan en robot och en människa i ett styrsystem, med fokus på en autonom lastbilskonvoj som interagerar med en människostyrd bil. Förutsägelsemodellen är ett hierarkiskt dynamiskt spel med en högupplöst taktisk horisont, som förutsäger omedelbara interaktioner, och en lågupplöst strategisk horisont med, som uppskattar långsiktigt beteende. Modellen ger naturliga och säkra interaktioner i simuleringar. Slutligen söker vi modeller som förklarar mänskligt beslutsfattande i ett scenario med omkörning av en förare. Vi föreslår och analyserar numeriskt riskagnostiska och riskmedvetna beslutsmodeller, som bedömer om en omkörning är önskvärd, och jämför dessa modeller på en experimentell testbädd med mänskliga förare.