New Wilkes Stipendium awarded

The winner of the 2017 Wilkes Stipendium, a prize that is given to a female student in one of our computer science and engineering related programs every year, is Anna Montelius who studies in the second year of the Software Technology degree program. She will be given the opportunity to travel to a scientific conference with a staff member during 2018.
Read more

Detecting Unsolvable Planning Instances

Automated planning is a branch of artificial intelligence which deals with the construction of plans. In his PhD thesis, Simon Ståhlberg studies unsolvable planning instances, i.e. when there is no plan. Historically, this topic has been neglected by the planning community, and up to recently the International Planning Competition only evaluated planners on solvable planning instances. For many applications we can know, for instance by design, that there is a solution, but this cannot be a general assumption. One example is penetration testing in computer security, where a system is considered safe if there is no plan for intrusion. Other examples are resource bounded planning instances that have insufficient resources to achieve the goal.

The main theme of the thesis is to use variable projection to prove unsolvability of planning instances. Two planners are implemented and evaluated: the first checks variable projections with the goal of finding an unsolvable projection, and the second builds a pattern collection to provide dead-end detection. In addition to comparing these planners to existing planners, a large computer cluster is also utilised to statistically assess whether they can be optimised further. On the benchmarks of planning instances that was used, it turns out that further improvement is likely to come from supplementary techniques rather than further optimisation. With the help of isomorphic variables the thesis identifies a computationally tractable class of planning instances that meet certain restrictions. There are several special cases of this class that are of practical interest, and this result encompass them.
Read more

Content Ontology Design Patterns

Ontologies are formal knowledge models that describe concepts and relationships and enable data integration, information search, and reasoning. Ontology Design Patterns (ODPs) are reusable solutions intended to simplify ontology development and support the use of semantic technologies by ontology engineers. ODPs document and package good modelling practices for reuse, ideally enabling inexperienced ontologists to construct high-quality ontologies. Although ODPs are already used for development, there are still remaining challenges that have not been addressed in the literature. These research gaps include a lack of knowledge about (1) which ODP features are important for ontology engineering, (2) less experienced developers' preferences and barriers for employing ODP tooling, and (3) the suitability of the eXtreme Design (XD) ODP usage methodology in non-academic contexts.

Karl Hammar's PhD thesis aims to close these gaps by combining quantitative and qualitative methods, primarily based on five ontology engineering projects involving inexperienced ontologists. A series of ontology engineering workshops and surveys provided data about developer preferences regarding ODP features, ODP usage methodology, and ODP tooling needs. Other data sources are ontologies and ODPs published on the web, which have been studied in detail. To evaluate tooling improvements, experimental approaches provide data from comparison of new tools and techniques against established alternatives.

The analysis of the gathered data resulted in a set of measurable quality indicators that cover aspects of ODP documentation, formal representation or axiomatisation, and usage by ontologists. These indicators highlight quality trade-offs: for instance, between ODP Learnability and Reusability, or between Functional Suitability and Performance Efficiency. Furthermore, the results demonstrate a need for ODP tools that support three novel property specialisation strategies, and highlight the preference of inexperienced developers for template-based ODP instantiation?neither of which are supported in prior tooling. The studies also resulted in improvements to ODP search engines based on ODP-specific attributes. Finally, the analysis shows that XD should include guidance for the developer roles and responsibilities in ontology engineering projects, suggestions on how to reuse existing ontology resources, and approaches for adapting XD to project-specific contexts.
Read more

Completion of Ontologies and Ontology Networks

Imagine we are interested in finding out how many Academy Awards nominations and wins each actor in a movie has ever had. Trying to find this information on the Internet would probably require visiting multiple websites, taken that none of the existing websites provide this information directly. For example, we would first need to visit the website containing the list of names of all actors in the movie. Next, we would have to visit another website that might have a list of Academy Award nominations over the years. Finally, we would then be able to combine the information and count the number of nominations per actor.

If this information is available on the Web, why cannot this query be automated? Because of the current design of the Web, the information is not directly usable by automated agents. The machine-readable content of a website usually only contains the information needed to properly represent the website in an Internet browser. One way to deal with this is to also include machine-readable information which describes the content of the website. In this way automated agents can understand the information a website contains. Further, they can then relate and combine it with information on other websites encoded in the similar manner and answer the query autonomously. This is one of the goals of the Semantic Web, which is supposed to be an extension of the current Web so that the knowledge and information is readable and understandable by the machines. One of the technologies used to achieve this is ontologies. Ontologies provide means for specifying the vocabulary used to describe information on the Web. They enable defining terms and relations between them, which an automated agent can then use to interpret the content of the website. However, ontologies are often not complete which can lead to incomplete results. In the cases where it is necessary to combine information from multiple websites, such as in our example, it maybe the case that ontologies use different terms to define the same concept. For example, one website might use the term actor while the other might use the term artist to describe movie actors. This heterogeneity makes it difficult to combine information from multiple sources. Therefore, it is necessary to identify the relationships between terms of the ontologies used by different websites. The set of these relationships is called an alignment.

The focus of Zlatan Dragisic's PhD thesis is on completing ontologies and ontologies networks, i.e. ontologies connected with alignments. High quality completion of ontologies and alignments requires the user's involvement as deciding if a certain relation holds in an ontology or between ontologies requires knowledge of the domain the ontologies are describing.
Read more

Gated Bayesian Networks

A graphical model is a description of how different phenomena are related to one another. The word graphical is used to stress that this description is done using a graph, where the phenomena are depicted using nodes and relationships are drawn as arrows. A graphical model might for instance describe how different lifestyle choices relate to each other, such as physical activity, alcohol consumption, nutritional intake and smoking. The graphical component describes assumptions that are made in order to allow for efficient representation and computation of certain quantities.

The real world is however not constant. Over time it may be required to switch focus to other phenomena, or the relationships among the phenomena already studied may change. If we are using a model that does not take such changes into consideration we may end up with an underperforming model. In his thesis, Marcus Bendtsen introduces a new graphical model which has the capacity to take such changes into consideration. The new graphical model, which is called gated Bayesian networks, is an extension of the popular graphical model Bayesian networks. The new model combines multiple Bayesian networks and can choose among them in order to maintain good performance.

The thesis introduces algorithms that allow for learning of gated Bayesian networks from data. The algorithms vary depending on the goal of the learning as well as the preconditions in terms of data and knowledge that is available before the learning starts. For instance, it is shown how models can be learnt that automatically buy and sell shares on a stock market in such a way that risks towards the invested capital are severely reduced. The algorithms are also applied to identify changes that occur over time, specifically when it comes to changes in volatility of financial markets and professional athletes performance.
Read more

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