10 december 2018

På vilket sätt ska vissa enheter samarbeta för att lösa en uppgift på bästa sätt? Fredrik Präntare har fått årets Lilla Polhemspris för sitt examensarbete som svarar på just den frågan, och ger en lösning på ett långvarigt optimeringsproblem.

Fredrik Präntare
Fredrik Präntare. Foto: Susanna Lönnqvist.
Frågeställningen är allmängiltig: hur ska ett team eller arbetslag bildas och samarbeta för att på effektivast möjliga sätt lösa ett problem? Optimeringsproblemet är välkänt speciellt inom forskningsområdet för artificiell intelligens, AI. Fredrik Präntare, doktorand vid Institutionen för datavetenskap, har utvecklat en algoritm som visar vem som ska jobba med vem, för att lösa flera givna uppgifter. 

– Algoritmen är utvecklad för så kallade multiagentsystem, ett system som utgörs av olika agenter eller enheter. Agenterna kan vara människor eller robotar, och det ingår inga antaganden om agenterna arbetar med eller mot varandra, eller om det är blandande grupper av människor och robotar, beskriver Fredrik Präntare.

Det algoritmen gör är en koordinering av enheterna och en optimering av resursanvändningen, för att effektivast lösa en uppgift. En uppgift kan till exempel vara att ta hand om patienter på ett sjukhus. Läkarna och sjuksköterskorna är agenterna som kan utföra olika arbetsuppgifter, och problemet som ska lösas är hur arbetslagen ska sättas ihop för att patienterna ska få bäst och effektivast vård. 

I sitt examensarbete, under utbildningen till civilingenjör i datateknik, har Fredrik Präntare applicerat algoritmen på strategispel. I spelet ska personen som spelar styra runt sina arméer på en karta med syftet att utmanövrera fienden. Den nyutvecklade algoritmen ställdes mot spelets nuvarande optimeringslösningar, och Fredrik Präntare lät också en artificiell intelligens spela spelet och koordinera sina arméer med hjälp av algoritmen i realtid. 

– I realtidsstrategispel tas beslut hela tiden, du kan inte vänta med att ta ett beslut i ett spel som pågår eller i en process som är igång. Det för med sig att algoritmen också går att applicera på verkliga problem och inte bara fungerar i en teoretisk miljö, säger Fredrik Präntare. 

Testar algoritmen på de svåraste problemen

Ett annat sätt att ta reda på hur bra en algoritm är, är att testa den mot syntetiska testdata. För liknande problem som optimeringsproblemet inom AI finns teoretiska problem som är väldigt komplexa och har flera olika lösningar. 
 
– Om du på ditt sjukhus har en läkare som är specialist på cancer, då vet du att du antagligen ska placera den läkaren i arbetslaget som ska ta hand om cancerpatienter. Det är en förenkling av problemet. Idén med syntetiska testdata är att de inte ska innehålla några sådana förenklingar, så att problemet blir så svårt som möjligt för algoritmen att lösa, säger Fredrik Präntare. 

I jämförelse med flera andra algoritmer är Fredrik Präntares algoritm i dag den mest effektiva för att lösa optimeringsproblemet. Nästa steg i utvecklingen är att använda maskininlärning för att kunna ta fram lösningar på problem som är för komplexa för dagens algoritmer. Ett problem med tio uppgifter och 1000 agenter ger tio upphöjt i tusen möjliga lösningar, vilket ingen algoritm i dag kan lösa inom rimlig tid.

– Vi vill också fortsätta titta på hur algoritmen kan tillämpas på verkliga frågeställningar; en specialistsjuksköterska kan till exempel vara en del av två arbetslag samtidigt genom att jobba i ett och handleda ett annat. Att lägga till sådana beskrivningar i problemen som ska lösas skulle utöka användningsområdet för algoritmen och vara intressant att titta närmare på, säger Fredrik Präntare. 


Lilla Polhemspriset

Lilla Polhemspriset delas årligen ut av Sveriges Ingenjörer till bästa examensarbete på civilingenjörsnivå utfört på svenskt universitet eller svensk teknisk högskola. Prisceremonin Polhemsfesten ordnades 19 november. Christopher Polhem (1661-1751) var en svensk uppfinnare och tidig ingenjör.

Examensarbetet

Läs Fredrik Präntares prisvinnande examensarbete:

Publikationer

2021

Fredrik Präntare, Herman Appelgren, Fredrik Heintz (2021) Anytime Heuristic and Monte Carlo Methods for Large-Scale Simultaneous Coalition Structure Generation and Assignment THIRTY-FIFTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THIRTY-THIRD CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE AND THE ELEVENTH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, s. 11317-11324 Vidare till DOI
Fredrik Präntare, Fredrik Heintz (2021) Hybrid Dynamic Programming for Simultaneous Coalition Structure Generation and Assignment PRIMA 2020: Principles and Practice of Multi-Agent Systems: 23rd International Conference, Nagoya, Japan, November 18–20, 2020, Proceedings, s. 19-33 Vidare till DOI

2020

Fredrik Präntare, Mattias Tiger, David Bergström, Herman Appelgren, Fredrik Heintz (2020) Towards Utilitarian Combinatorial Assignment with Deep Neural Networks and Heuristic Algorithms
Veronika Domova, Erik Gärtner, Fredrik Präntare, Martin Pallin, Johan Källström, Nikita Korzhitskii (2020) Improving Usability of Search and Rescue Decision Support Systems: WARA-PS Case Study In proceedings of the 2020 25th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), s. 1251-1254 Vidare till DOI
Fredrik Präntare, Fredrik Heintz (2020) An anytime algorithm for optimal simultaneous coalition structure generation and assignment Autonomous Agents and Multi-Agent Systems, Vol. 34, Artikel 29 Vidare till DOI

2018

Fredrik Präntare, Fredrik Heintz (2018) An Anytime Algorithm for Simultaneous Coalition Structure Generation and Assignment PRIMA 2018: Principles and Practice of Multi-Agent Systems: 21st International Conference, Tokyo, Japan, October 29-November 2, 2018, Proceedings, s. 158-174 Vidare till DOI

2017

Fredrik Präntare, Ingemar Ragnemalm, Fredrik Heintz (2017) An Algorithm for Simultaneous Coalition Structure Generation and Task Assignment PRIMA 2017: Principles and Practice of Multi-Agent Systems 20th International Conference, Nice, France, October 30 – November 3, 2017, Proceedings, s. 514-522 Vidare till DOI

Kontakt

Senaste nytt från LiU

Person (Jie Zhou) pekar på en datorskärm.

Ny värld av 2D-material öppnas

Material som är extremt tunna får ovanliga egenskaper som gör dem lämpliga för bland annat energilagring, katalys och vattenrening. Nu har forskare vid LiU utvecklat en metod där hundratals nya 2D-material kan skapas.

Lakrits i skål och lakritsrot bredvid.

Liten mängd lakrits höjer blodtrycket

Det är känt att större mängder lakrits orsakar högt blodtryck. Nu visar en studie av forskare vid LiU att även små mängder lakrits höjer blodtrycket. De individer som reagerar kraftfullast visar också tecken på belastning av hjärtat.

Han lotsar sina studenter till toppjobb

Det går bra för LiU-studenter i SM i företagsvärdering. År efter år går segern till Linköpings universitet. Vinst i tävlingen är en genväg till toppjobb i storbanker och revisionsbolag. Vad är egentligen hemligheten bakom framgångarna?