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.
â 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.
â 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.
