Göm menyn

Nyheter 2017

Beräkningskomplexitet av optimeringsproblem i planering

Huvudtemat i denna avhandling är studiet av beräkningskomplexitet för automatisk planering. På en hög nivå kan man betrakta planeringsproblemet så här; man utgår från en värld eller ett system, som ett obemannat fordon eller en autonom robot, och antar att det finns vissa handlingar som ändrar tillståndet i systemet. Man antar dessutom att det finns ett initial- och ett måltillstånd. Planering är problemet att hitta en sekvens av handlingar som tranformerar initialtillståndet till måltillståndet. En sådan sekvens av handlingar kallas en plan. En planerare är ett datorprogram som löser planeringsproblem, och planerare baseras ofta på sökning genom tillstånden i systemet. Vanligtvis vill man optimera sökningen och hitta en plan som är optimal med avseende på något kriterium. Vad man vill optimera beror på tillämpningen men det är ofta att hitta en kortaste eller billigaste plan.

En viktig fråga när man studerar automatisk planering är hur snabbt man kan hitta lösningar. Ett sätt att analysera denna fråga är att studera beräkningskomplexiteten för olika planeringsproblem. Komplexitetsteori är den gren av datavetenskapen som försöker klassificera hur svåra olika beräkningsproblem är, det vill säga analysera hur mycket resurser (såsom tid och minne) som behövs. Man likställer ofta effektivt lösbara problem med
de som kan lösas i polynomisk tid: ett problem kan lösas i polynomisk tid om det finns en algoritm vars tidsåtgång begränsas av ett polynom i indatas storlek. Det grundläggande planeringsproblemet är exempelvis känt att vara PSPACE-fullständigt. PSPACE är den komplexitetsklass som innehåller alla de beräkningsproblem som kan lösas genom att använda polynomiskt mycket minne och de PSPACE-fullständiga problemen utgör de svåraste problemen i PSPACE.
Man tror att det inte finns några PSPACE-fullständiga problem som kan lösas i polynomisk tid-detta är ett viktigt olöst problem inom teoretisk datalogi-och man förväntar sig därför inte att det generella planeringsproblemet kan lösas i polynomisk tid.

En metod för att analysera beräkningskomplexitet av planering är att studera begränsade delmängder av planeringsinstanser i syfte att särskilja fall med varierande komplexitet. Vi använder denna metod genomgående i denna avhandling. Så kallad "oversubscription planning" är en typ av planering där man mäter hur nära ett givet måltillstånd man kan komma. Vi studerar beräkningskomplexiteten för denna typ av planering under olika restriktioner och avslöjar starka kopplingar med vanlig planering. Kostnadsoptimal planering är planering där varje handling har en kostnad och målet är att hitta en plan med minimal kostnad. Dessa handlingskostnader kan hämtas från olika numeriska domäner såsom de positiva heltalen eller de rationella talen.
Vi studerar effekter av valet av numeriska domäner och noterar intressanta komplexitetsmässiga skillnader. För kostnadsoptimal planering identifierar vi dessutom en ny klass av instanser som kan lösas i polynomisk tid.
Slutligen studerar vi komplexiteten för olika problem inom så kallad partialordningsplanering där man tillåter planer som inte nödvändigtvis är sekvenser av handlingar.
Läs mer

Bästa exjobb utfört under 2016

För 18:e gången i rad delades priset ut för bästa exjobb inom IT-området sponsrat av Dataföreningen (Östra). Pristagare på kandidatnivå blev Tim Hultman och i kategorin Master blev August Ernstsson.
Läs mer

Utveckling av offentlig sektors förmåga att nyttja design

Runt om i världen har flera initiativ tagits för att uppmuntra användningen av design för att driva utveckling och innovation inom offentlig sektor. Denna trend medför ett behov att öka förståelsen för hur förmågan att nyttja design utvecklas inom organisationer i den offentliga sektorn. Genom en explorativ studie där två initiativ med syfte att introducera design och utveckla designförmåga inom vård- och omsorgsorganisationer har observerats, har Lisa Malmbergs avhandling syftat till att utveckla denna förståelse.

Konceptet designförmåga har tidigare använts i relation till flera olika aspekter av hur en organisation till exempel uppfattar eller använder design. Ett av arbetets huvudsakliga bidrag är en samlad förståelse för vad designförmåga innebär baserar på en strukturerad litteraturgenomgång.

Ett annat viktigt bidrag är utvecklingen av en förståelse för hur designförmåga utvecklas i de studerade organisationerna. Denna förståelse grundas i tolkningar av det organisatoriska lärandet utifrån ett absorptive capacity perspektiv. Studien har identifierat hur utvecklingen av designförmåga påverkats av olika faktorer som både kan stötta och hindra utvecklingen av designförmåga. Dessa faktorer är viktiga att beakta och adressera i satsningar som syftar till att utveckla designförmågan inom den offentliga sektorn.

I båda studerade fallen har upplägg för kunskapsöverföringen fokuserat på utveckling av medvetenhet om design och vad design innebär. Liknande mönster kring fokus finns i tidigare och parallella initiativ. Forskningens resultat tyder dock på att det också är viktigt att organisationen har tillgång till resurser i form av designkompetens och att strukturer inom organisationen så som, rutiner, processer eller kultur möjliggör och stöttar användningen av ett designdrivet arbetssätt för att design ska bli en naturlig del i ett kontinuerligt utvecklingsarbete.
Läs mer

Förbättra säkerheten genom ökad anpassningsförmåga

Komplexiteten i dagens säkerhetskritiska verksamheter, t.ex. flyg, sjukvård, kärnkraft och krisberedskap, gör det omöjligt att förutse och förbereda sig för alla potentiella händelser. För att hantera störningar och bibehålla kontroll vid oväntade händelser krävs att de operatörer som arbetar i systemet klarar av att anpassa sitt arbete i en komplex, föränderlig och dynamisk miljö. Det kan vara en krisorganisation som måste hantera att nyckelpersoner inte når fram till ett drabbat område, en pilot som ska fatta snabba beslut när flygsystemen ger otillförlitliga data eller en skeppsbesättning som manövrerar i en trång hamn just som dimman håller på att lägga sig.

I sin avhandling har Amy Rankin studerat vardagssituationer och större händelser som kräver anpassning som ligger utanför vad som förväntas och således kräver ett visst mått av improvisation. I studierna ingår beskrivningar och analyser av verkliga situationer i flera olika domäner där människor hanterar oförutsedda händelser och störningar. Resultaten visar att operatörens förmåga att anpassa sig till det som ligger utanför vad som beskrivs i organisationens rutiner och föreskrifter är viktig för den dagliga verksamheten. Resultaten visar också att anpassningarna skapar nya sårbarheter i systemet, både på kort och lång sikt.

I avhandlingen har flera modeller tagits fram för att vägleda forskare och praktiker i arbetet med att beskriva och analysera anpassningsförmåga och dess påverkan på systemet. Ökad förståelse för de processer som gör att anpassningar fungerar (eller inte) leder till kunskap om vad som möjliggör (eller hindrar) framgångsrik hantering av oväntade händelser, vilka delar av systemet som bör stödjas och stärkas för att öka säkerheten, samt ger en mer nyanserad bild av vilka sårbarheter som finns och hur framtida olyckor kan förebyggas.
Läs mer

Energieffektiv flerkärnig behandling av strömmande data

Sociala medier, forskning, mobilt multimedia, sakernas internet - alla har de ett starkt behov av att snabbare behandla allt större datamängder samtidigt som det krävs sparsam energianvändning. I sin doktorsavhandling undersöker Nicolas Melot "Crown Scheduling"-tekniken och programmeringsramverket Drake för att bygga energieffektiva strömmande program för flerkärnade processorer.
Läs mer


Sidansvarig: Webmaster