Computational Complexity of Optimization Problems in Planning

Automated planning is known to be computationally hard in the general
case. Propositional planning is PSPACE-complete and first-order planning is undecidable. One method for analyzing the computational complexity of planning is to study restricted subsets of planning instances, with the aim of differentiating instances with varying complexity. We use this methodology for studying the computational complexity of planning.

Finding new tractable (i.e. polynomial-time solvable)
problems has been a particularly important goal for researchers in the area. The reason behind this is not only to differentiate between easy and hard planning instances, but also to use polynomial-time solvable instances in order to construct better heuristic functions and improve planners.

We identify a new class of tractable cost-optimal planning instances by
restricting the causal graph. We also study the computational complexity of oversubscription planning (such as the net-benefit problem) under various restrictions and revealstrong connections with classical planning. Inspired by this, we present a method for compiling oversubscription planning problems into the ordinary plan existence problem. We further study the parameterized complexity of cost-optimal and net-benefit
planning under the same restrictions and show that the choice of numeric
domain for the action costs has a great impact on the parameterized complexity.

We finally consider the parameterized complexity of certain problems related to partial-order planning. In some applications, less restricted plans than total-order plans are needed. Therefore, a partial-order plan is being used instead. When dealing with partial-order plans, one important question is how to achieve optimal partial order plans, i.e.
having the highest degree of freedom according to some notion of flexibility. We study several optimization problems for partial-order plans, such as finding a minimum deordering or reordering, and finding the minimum parallel execution length.
Read more

Prize for best Bachelor and Master theses

The prize for the best master and final year project thesis during 2016 was awarded in cooperation with the Computer Society (East). The winner at Bachelor level is Tim Hultman and at Master level August Ernstsson.
Read more

Enhancing public sector capability to make use of design

There are many initiatives taken across the world to encourage the use of a design approach to development and innovation within public sector. In relation to this trend there is a need to improve the understanding of how public sector organizations develop ability to exploit design; how they develop design capability. This is the focus of Lisa Malmberg's thesis, which through an exploratory study has observed two initiatives aiming to introduce design and develop design capability within healthcare and social service organizations.

One main contribution of this work is an understanding of the design capability concept based on a structured review of the use of the design capability concept in the literature. The concept has previously been used in relation to different aspects of designs in organizations.

Another important contribution is the development of an understanding for how design capability is developed based on interpretations founded in the organizational learning perspective of absorptive capacity. The study has identified how different antecedents to development of design capability have influenced this development in the two cases. The findings have identified aspects that both support and impede the development of design capability which are important to acknowledge and address when aiming to develop design capability within a public sector organization.

In both cases, the set up of the knowledge transferring efforts focus mainly on developing awareness of design. Similar patterns are seen in other prior and parallel initiatives. The findings however suggest that it is also important to ensure that the organization have access to design competence and that structures like routines, processes and culture support and enable the use of design practice, in order to make design a natural part of the continuous development work.
Read more

Analysing adaptive performance to improve safety in complex systems

To cope with variations, disturbances, and unexpected events in safety-critical work, such as cockpit operations and crisis management, people are required to continuously adapt to the changing environment, sometimes in novel and innovative ways. In her thesis, Amy Rankin examines what enables and disables successful adaptations, and how contextual factors shape performance. Examples include a crisis command team dealing with the loss of key personnel, a crew coping with unreliable system feedback in the cockpit, and a nursing team managing an overload of patients.

Two main contributions of the thesis is the analysis of cases of people coping with variations and disturbances, and the development of conceptual models to report findings, structure cases, and make sense of sharp-end adaptations in complex work settings. The findings emphasise that adaptive performance outside procedures and textbook scenarios at the sharp end is a critical ability to cope with variation and unexpected events. However, the results also show that adaptations may come at the cost of new vulnerabilities and system brittleness. Analysing adaptive performance in everyday events informs safety management by making visible limitations and possibilities of system design, organisational structures, procedures, and training.
Read more

Energy-Efficiency in many-core stream processing

From Social media to scientific research, from mobile multimedia to Internet of things, there is an overwhelming need to process more data faster, while targetting energy sobriety. In his thesis, Nicolas Melot explores the Crown Scheduling technique and designs the Drake programming framework in order to build energy-efficient stream programs for many-core processors.
Read more