Hide menu

AIICS Publications: Student Theses

Hide abstracts BibTeX entries
[40] Simon Keisala. 2017.
Designing an Artificial Neural Network for state evaluation in Arimaa: Using a Convolutional Neural Network.
Student Thesis. 31 pages. ISRN: LIU-IDA/LITH-EX-G--17/024--SE.

Agents being able to play board games such as Tic Tac Toe, Chess, Go and Arimaa has been, and still is, a major difficulty in Artificial Intelligence. For the mentioned board games, there is a certain amount of legal moves a player can do in a specific board state. Tic Tac Toe have in average around 4-5 legal moves, with a total amount of 255168 possible games. Both Chess, Go and Arimaa have an increased amount of possible legal moves to do, and an almost infinite amount of possible games, making it impossible to have complete knowledge of the outcome.This thesis work have created various Neural Networks, with the purpose of evaluating the likelihood of winning a game given a certain board state. An improved evaluation function would compensate for the inability of doing a deeper tree search in Arimaa, and the anticipation is to compete on equal skills against another well-performing agent (meijin) having one less search depth.The results shows great potential. From a mere one hundred games against meijin, the network manages to separate good from bad positions, and after another one hundred games able to beat meijin with equal search depth.It seems promising that by improving the training and by testing different sizes for the neural network that a neural network could win even with one less search depth. The huge branching factor of Arimaa makes such an improvement of the evaluation beneficial, even if the evaluation would be 10 000 times more slow.

[39] Niclas Jonsson. 2017.
Implementation and testing of an FPT-algorithm for computing the h+ heuristic.
Student Thesis. 39 pages. ISRN: LIU-IDA/LITH-EX-G–17/077–SE.

We have implemented and benchmarked an FPT-algorithm, that has two input parameters, k and w besides the input problem instance, which is a planing instance, in this thesis. The algorithm has an exponential running time as a function of these two parameters. The implemented algorithm computes the heuristic value h^+(s) of a state s that belongs to a state space, which originates from a strips instance. The purpose of the project was to test if the algorithm can be used to compute the heuristic function h^+, i.e. the delete-relaxation heuristic, in practice. The delete-relaxation heuristic value for some state is the length of the optimal solution from the state to a goal in the delete-relaxed-instance, which is the original instance without all its negative effects. Planning instances was benchmarked with the search algorithm A^* to test the algorithms practical value. The heuristic function blind was benchmarked together with A^* with the same instances so that we could compare the quality of the benchmark result for the implemented algorithm. The conclusion of the project was that the implemented algorithm is too slow to be used in practise.

[38] Henrik Phung. 2017.
Software developers? performance awareness.
Student Thesis. 49 pages. ISRN: LIU-IDA/LITH-EX-A--17/016--SE.

Automated tests and non-functional requirements are two widely used terms in the software development sector. Both are essential for software development teams but rarely mentioned together. Today, most software development teams are utilizing the development practice continuous integration. A method where software is built in iterations and in each iteration small chunks of code are merged into the main repository. Continuous integration requires automated tests to verify that each chunk of code is compatible with the main chunk. Automated test is essential for continuous integration to detect anomalies in each chunk of code. Customer satisfaction is a result of how well the delivered product performs in terms of non-functional requirements. Although the term “non-functional requirement” has not been formally defined and the existing definitions are diverse. In this thesis, we define the non-functional requirement, response time with help from a user-centered evaluation of responsiveness study. We create a test suite that can be ran on an automated build with focus on user-action-response. Based on the test result and a conducted survey, we evaluate how aware developers are when it comes to causes to performance issues.

[37] Full text  Daniel Artchounin. 2017.
Tuning of machine learning algorithms for automatic bug assignment.
Student Thesis. 135 pages. ISRN: LIU-IDA/LITH-EX-A--17/022--SE.

In software development projects, bug triage consists mainly of assigning bug reports to software developers or teams (depending on the project). The partial or total automation of this task would have a positive economic impact on many software projects. This thesis introduces a systematic four-step method to find some of the best configurations of several machine learning algorithms intending to solve the automatic bug assignment problem. These four steps are respectively used to select a combination of pre-processing techniques, a bug report representation, a potential feature selection technique and to tune several classifiers. The aforementioned method has been applied on three software projects: 66 066 bug reports of a proprietary project, 24 450 bug reports of Eclipse JDT and 30 358 bug reports of Mozilla Firefox. 619 configurations have been applied and compared on each of these three projects. In production, using the approach introduced in this work on the bug reports of the proprietary project would have increased the accuracy by up to 16.64 percentage points.

[36] Fredrik Präntare. 2017.
Simultaneous coalition formation and task assignment in a real-time strategy game.
Student Thesis. 65 pages. ISRN: LIU-IDA/LITH-EX-A--17/032--SE.

In this thesis we present an algorithm that is designed to improve the collaborative capabilities of agents that operate in real-time multi-agent systems. Furthermore, we study the coalition formation and task assignment problems in the context of real-time strategy games. More specifically, we design and present a novel anytime algorithm for multi-agent cooperation that efficiently solves the simultaneous coalition formation and assignment problem, in which disjoint coalitions are formed and assigned to independent tasks simultaneously. This problem, that we denote the problem of collaboration formation, is a combinatorial optimization problem that has many real-world applications, including assigning disjoint groups of workers to regions or tasks, and forming cross-functional teams aimed at solving specific problems.The algorithm's performance is evaluated using randomized artificial problems sets of varying complexity and distribution, and also using Europa Universalis 4 – a commercial strategy game in which agents need to cooperate in order to effectively achieve their goals. The agents in such games are expected to decide on actions in real-time, and it is a difficult task to coordinate them. Our algorithm, however, solves the coordination problem in a structured manner.The results from the artificial problem sets demonstrates that our algorithm efficiently solves the problem of collaboration formation, and does so by automatically discarding suboptimal parts of the search space. For instance, in the easiest artificial problem sets with 12 agents and 8 tasks, our algorithm managed to find optimal solutions after only evaluating approximately 0.000003% of the possible solutions. In the hardest of the problem sets with 12 agents and 8 tasks, our algorithm managed to find a 80% efficient solution after only evaluating approximately 0.000006% of the possible solutions.

[35] Full text  Tova Linder and Ola Jigin. 2017.
Organ Detection and Localization in Radiological Image Volumes.
Student Thesis. 88 pages. ISRN: LIU-IDA/LITH-EX-A--17/024--SE.

Using Convolutional Neural Networks for classification of images and for localization and detection of objects in images is becoming increasingly popular. Within radiology a huge amount of image data is produced and meta data containing information of what the images depict is currently added manually by a radiologist. To aid in streamlining physician’s workflow this study has investigated the possibility to use Convolutional Neural Networks (CNNs) that are pre-trained on natural images to automatically detect the presence and location of multiple organs and body-parts in medical CT images. The results show promise for multiclass classification with an average precision 89.41% and average recall 86.40%. This also confirms that a CNN that is pre-trained on natural images can be succesfully transferred to solve a different task. It was also found that adding additional data to the dataset does not necessarily result in increased precision and recall or decreased error rate. It is rather the type of data and used preprocessing techniques that matter.

[34] Full text  Elena Moral López. 2017.
Muting pattern strategy for positioning in cellular networks.
Student Thesis. 65 pages. ISRN: LIU-IDA/LITH-EX-A--17/018--SE.

Location Based Services (LBS) calculate the position of the user for different purposes like advertising and navigation. Most importantly, these services are also used to help emergency services by calculating the position of the person that places the emergency phone call. This has introduced a number of requirements on the accuracy of the measurements of the position. Observed Time Difference of Arrival (OTDOA) is the method used to estimate the position of the user due to its high accuracy. Nevertheless, this method relies on the correct reception of so called positioning signals, and therefore the calculations can suffer from errors due to interference between the signals. To lower the probability of interference, muting patterns can be used. These methods can selectively mute certain signals to increase the signal to interference and noise ratio (SINR) of others and therefore the number of signals detected. In this thesis, a simulation environment for the comparison of the different muting patterns has been developed. The already existing muting patterns have been simulated and compared in terms of number of detected nodes and SINR values achieved. A new muting pattern has been proposed and compared to the others. The results obtained have been presented and an initial conclusion on which of the muting patterns offers the best performance has been drawn.

[33] Petra Öhlin. 2017.
Prioritizing Tests with Spotify?s Test & Build Data using History-based, Modification-based & Machine Learning Approaches.
Student Thesis. 43 pages. ISRN: LIU-IDA/LITH-EX-A--2017/021--SE.

This thesis intends to determine the extent to which machine learning can be used to solve the regression test prioritization (RTP) problem. RTP is used to order tests with respect to probability of failure. This will optimize for a fast failure, which is desirable if a test suite takes a long time to run or uses a significant amount of computational resources. A common machine learning task is to predict probabilities; this makes RTP an interesting application of machine learning. A supervised learning method is investigated to train a model to predict probabilities of failure, given a test case and a code change. The features investigated are chosen based on previous research of history- based and modification-based RTP. The main motivation for looking at these research areas is that they resemble the data provided by Spotify. The result of the report shows that it is possible to improve how tests run with RTP using machine learning. Nevertheless, a much simpler history- based approach is the best performing approach. It is looking at the history of test results, the more failures recorded for the test case over time, the higher priority it gets. Less is sometimes more.

[32] Full text  Joakim Gylling. 2017.
Transition-Based Dependency Parsing with Neural Networks.
Student Thesis. 10 pages. ISRN: LIU-IDA/LITH-EX-G--17/011--SE.

Dependency parsing is important in contemporary speech and language processing systems. Current dependency parsers typically use the multi-class perceptron machine learning component, which classifies based on millions of sparse indicator features, making developing and maintaining these systems expensive and error-prone. This thesis aims to explore whether replacing the multi-class perceptron component with an artificial neural network component can alleviate this problem without hurting performance, in terms of accuracy and efficiency. A simple transition-based dependency parser using the artificial neural network (ANN) as the classifier is written in Python3 and the same program with the classifier replaced by a multi-class perceptron component is used as a baseline. The results show that the ANN dependency parser provides slightly better unlabeled attachment score with only the most basic atomic features, eliminating the need for complex feature engineering. However, it is about three times slower and the training time required for the ANN is significantly longer.

[31] Full text  Maximilian Bragazzi Ihrén and Henrik Ingbrant Björs. 2017.
Visualizing atmospheric data on a mobile platform.
Student Thesis. 10 pages. ISRN: LIU-IDA/LITH-EX-G--17/010--SE.

Weather data is important for almost everyone today. Thedaily weather report, home thermometers, and a lot of otherthings affect our every day life. In order to develop betterand more efficient equipment, tools and algorithms, thepeople working with this data need to be able to access it inan easily accessible and easy to read format. In thisresearch, methods of visualizing data on mobile platformsare evaluated based on what researchers in the field wants,since their respective fields might want to use very specificvisualizations. The implementability of these visualizationsare then evaluated, based on the implementations madethroughout this paper. The results show that the researchersknow what they want, and that what they want isimplementable on mobile platforms given some limitationscaused by performance.

[30] Full text  Fredrik Jonsén and Alexander Stolpe. 2017.
The feasibility and practicality of a generic social media library.
Student Thesis. ISRN: LIU-IDA/LITH-EX-G--17/009--SE.

[29] Full text  Marcus Johansson. 2016.
Online Whole-Body Control using Hierarchical Quadratic Programming: Implementation and Evaluation of the HiQP Control Framework.
Student Thesis. 76 pages. ISRN: LIU-IDA/LITH-EX-A--16/056--SE.

The application of local optimal control is a promising paradigm for manipulative robot motion generation.In practice this involves instantaneous formulations of convex optimization problems depending on the current joint configuration of the robot and the environment.To be effective, however, constraints have to be carefully constructed as this kind of motion generation approach has a trade-off of completeness.Local optimal solvers, which are greedy in a temporal sense, have proven to be significantly more effective computationally than classical grid-based or sampling-based planning approaches.In this thesis we investigate how a local optimal control approach, namely the task function approach, can be implemented to grant high usability, extendibility and effectivity.This has resulted in the HiQP control framework, which is compatible with ROS, written in C++.The framework supports geometric primitives to aid in task customization by the user.It is also modular as to what communication system it is being used with, and to what optimization library it uses for finding optimal controls.We have evaluated the software quality of the framework according to common quantitative methods found in the literature.We have also evaluated an approach to perform tasks using minimal jerk motion generation with promising results.The framework also provides simple translation and rotation tasks based on six rudimentary geometric primitives.Also, task definitions for specific joint position setting, and velocity limitations were implemented.

[28] Full text  Tomas Melin. 2016.
Implementation and Evaluation of a Continuous Code Inspection Platform.
Student Thesis. 100 pages. ISRN: LIU-IDA/LITH-EX-A--16/047—SE.

Establishing and preserving a high level of software quality is a not a trivial task, although the benefits of succeeding with this task has been proven profitable and advantageous. An approach to mitigate the decreasing quality of a project is to track metrics and certain properties of the project, in order to view the progression of the project’s properties. This approach may be carried out by introducing continuous code inspection with the application of static code analysis. However, as the initial common opinion is that these type of tools produce a too high number of false positives, there is a need to investigate what the actual case is. This is the origin for the investigation and case study performed in this paper. The case study is performed at Ida Infront AB in Linköping, Sweden and involves interviews with developers to determine the performance of the continuous inspection platform SonarQube, in addition to examine the general opinion among developers at the company. The author executes the implementation and configuration of a continuous inspection environment to analyze a partition of the company’s product and determine what rules that are appropriate to apply in the company’s context. The results from the investigation indicate the high quality and accuracy of the tool, in addition to the advantageous functionality of continuously monitoring the code to observe trends and the progression of metrics such as cyclomatic complexity and duplicated code, with the goal of preventing the constant increase of complex and duplicated code. Combining this with features such as false positive suppression, instant analysis feedback in pull requests and the possibility to break the build given specified conditions, suggests that the implemented environment is a way to mitigate software quality difficulties.

[27] Full text  Martin Estgren. 2016.
Lightweight User Agents.
Student Thesis. 36 pages. ISRN: LIU-IDA/LITH-EX-G--16/036--SE.

The unit for information security and IT architecture at The Swedish Defence Research Agency (FOI) conducts work with a cyber range called CRATE (Cyber Range and Training Environment). Currently, simulation of user activity involves scripts inside the simulated network. This solution is not ideal because of the traces it leaves in the system and the general lack of standardised GUI API between different operating systems. FOI are interested in testing the use of artificial user agent located outside the virtual environment using computer vision and the virtualisation API to execute actions and extract information from the system.This paper focuses on analysing the reliability of template matching, a computer vision algorithm used to localise objects in images using already identified images of said object as templates. The analysis will evaluate both the reliability of localising objects and the algorithms ability to correctly identify if an object is present in the virtual environment.Analysis of template matching is performed by first creating a prototype of the agent's sensory system and then simulate scenarios which the agent might encounter. By simulating the environment, testing parameters can be manipulated and monitored in a reliable way. The parameters manipulated involves both the amount and type of image noise in the template and screenshot, the agent’s discrimination threshold for what constitutes a positive match, and information about the template such as template generality.This paper presents the performance and reliability of the agent in regards to what type of image noise affects the result, the amount of correctly identified objects given different discrimination thresholds, and computational time of template matching when different image filters are applied. Furthermore the best cases for each study are presented as comparison for the other results.In the end of the thesis we present how for screenshots with objects very similar to the templates used by the agent, template matching can result in a high degree of accuracy in both object localization and object identification and that a small reduction of similarity between template and screenshot to reduce the agent's ability to reliably identifying specific objects in the environment.

[26] Full text  Rasmus Holm. 2016.
Cluster Analysis of Discussions on Internet Forums.
Student Thesis. 62 pages. ISRN: LIU-IDA/LITH-EX-G--16/037—SE.

The growth of textual content on internet forums over the last decade have been immense which have resulted in users struggling to find relevant information in a convenient and quick way.The activity of finding information from large data collections is known as information retrieval and many tools and techniques have been developed to tackle common problems. Cluster analysis is a technique for grouping similar objects into smaller groups (clusters) such that the objects within a cluster are more similar than objects between clusters.We have investigated the clustering algorithms, Graclus and Non-Exhaustive Overlapping <em>k</em>-means (NEO-<em>k</em>-means), on textual data taken from Reddit, a social network service. One of the difficulties with the aforementioned algorithms is that both have an input parameter controlling how many clusters to find. We have used a greedy modularity maximization algorithm in order to estimate the number of clusters that exist in discussion threads.We have shown that it is possible to find subtopics within discussions and that in terms of execution time, Graclus has a clear advantage over NEO-<em>k</em>-means.

[25] Full text  Erik Hansson. 2016.
Search guidance with composite actions: Increasing the understandability of the domain model.
Student Thesis. 98 pages. ISRN: LIU-IDA/LITH-EX--16/043--SE.

This report presents an extension to the domain definition language for Threaded Forward-chaining Partial Order Planner (TFPOP) that can be used to increase the understandability of domain models. The extension consists of composite actions which is a method for expressing abstract actions as procedures of primitive actions. TFPOP can then uses these abstract actions when searching for a plan. An experiment, with students as participants, was used to show that using composite action can increase the understandability for non-expert users. Moreover, it was also proved the planner can utilize the composite action to significantly decrease the search time. Furthermore, indications was found that using composite actions is equally fast in terms of search time as using existing equivalent methods to decrease the search time.

[24] Full text  Anna Boyer de la Giroday. 2016.
Automatic fine tuning of cavity filters.
Student Thesis. 49 pages. ISRN: LIU-IDA/LITH-EX-A--16/036--SE.

Cavity filters are a necessary component in base stations used for telecommunication. Without these filters it would not be possible for base stations to send and receive signals at the same time. Today these cavity filters require fine tuning by humans before they can be deployed. This thesis have designed and implemented a neural network that can tune cavity filters. Different types of design parameters have been evaluated, such as neural network architecture, data presentation and data preprocessing. While the results was not comparable to human fine tuning, it was shown that there was a relationship between error and number of weights in the neural network. The thesis also presents some rules of thumb for future designs of neural network used for filter tuning.

[23] Full text  Stefan Bränd. 2015.
Using Rigid Landmarks to Infer Inter-Temporal Spatial Relations in Spatio-Temporal Reasoning.
Student Thesis. 32 pages. ISRN: LIU-IDA/LITH-EX-G--15/074--SE.

Spatio-temporal reasoning is the area of automated reasoning about space and time and is important in the field of robotics. It is desirable for an autonomous robot to have the ability to reason about both time and space. ST0 is a logic that allows for such reasoning by, among other things, defining a formalism used to describe the relationship between spatial regions and a calculus that allows for deducing further information regarding such spatial relations. An extension of ST0 is ST1 that can be used to describe the relationship between spatial entities across time-points (inter-temporal relations) while ST0 is constrained to doing so within a single time-point. This allows for a better ability of expressing how spatial entities change over time. A major obstacle in using ST1 in practise however, is the fact that any observations made regarding spatial relations between regions is constrained to the time-point in which the observation was made, so we are unable to observe inter-temporal relations. Further complicating things is the fact that deducing such inter-temporal relations is not possible without a frame of reference. This thesis examines one method of overcoming these problems by considering the concept of rigid regions which are assumed to always be unchanging and using them as the frame of reference, or as landmarks. The effectiveness of this method is studied by conducting experiments where a comparison is made between various landmark ratios with respect to the total number of regions under consideration. Results show that when a high degree of intra-temporal relations are fully or partially known, increasing the number of landmark regions will reduce the percentage of inter-temporal relations to be completely unknown. Despite this, very few inter-temporal relations can be fully determined even with a high ratio of landmark regions.

[22] Full text  Valberg Joakim. 2015.
Document Separation in Digital Mailrooms.
Student Thesis. 47 pages. ISRN: LIU-IDA/LITH-EX-A-15/056-SE.

The growing mail volumes for businesses worldwide is one reason why theyare increasingly turning to digital mailrooms. A digital mailroom automaticallymanages the incoming mails, and a vital technology to its success isdocument classication. A problem with digital mailrooms and the documentclassication is separating the input stream of pages into documents.This thesis investigates existing classication theory and applies it to createan algorithm which solves the document separation problem. This algorithmis evaluated and compared against an existing algorithmic solution, over adataset containing real invoices.

[21] Full text  Erik Sommarström. 2015.
I am the Greatest Driver in the World!: -Does self-awareness of driving ability affect traffic safety behaviour?.
Student Thesis. 43 pages. ISRN: LIU-IDA/KOGVET-A--15/008—SE.

This simulator study aims to investigate if there is a relationship between self-awareness of driving ability and traffic safety behaviour. Self-awareness in this study is accurate self-evaluation of one’s abilities. By letting 97 participants (55-75 years old) drive the simulator and answering the Driver Skill Inventory (DSI; Warner et al., 2013) as well as the Multidimensional locus of control (T-loc; Özkan &amp; Lajunen, 2005). A measure of self-awareness was computed using the residuals from regression line. Furthermore, this measure could show if a participant over-estimated or under-estimated their ability. Four self-awareness measures were made. The self-awareness measures were compared to traffic safety behaviour. Three different traffic safety measures were computed using specific events in the simulator scenario. The self-awareness measures were grouped into three groups; under-estimators, good self-awareness and over-estimators. These groups were then compared to each other with respect to traffic safety. A multivariate ANOVA was made to test for differences between the self-awareness groups but no significant main difference was found. The results showed no difference in traffic safety behaviour given the different levels of self-awareness. Furthermore, this could be a result of the old age of the sample group as self-awareness may only be relevant in a learning context. The conclusion of the study is that the analysis shows that there is no difference between over-estimators and under-estimators of driving ability, at least not in experienced older drivers.

[20] Tina Danielsson. 2015.
Portering frćn Google Apps REST API till Microsoft Office 365 REST API.
Student Thesis. 10 pages. ISRN: LiTH-IDA/ERASMUS-G--15/003--SE.

Stress pÄ arbetsplatsen relaterat till mÄnga inkommande och utgÄende kommunikationskanaler Àr ett reellt problem. Applikationer som samlar alla kanaler i samma verktyg kan hjÀlpa till pÄ det hÀr omrÄdet. För att förenkla vid utveckling av en sÄdan applikation kan ett modulÀrt system skapas, dÀr varje modul ser liknande ut och enkelt kan kopplas in i en huvudapplikation. Den hÀr studien undersöker de problem som kan uppstÄ nÀr flera tjÀnster ska integreras, mer specifikt genom att titta pÄ hur en befintlig modul för e-post via Google Apps kan porteras för att stödja e-post via Microsoft Office 365. Arbetet har skett enligt metoder för testdriven portering och varje steg i porteringen har dokumenterats noggrant. Ett antal problemomrÄden har identifierats och möjliga lösningar föreslÄs. UtfrÄn de problem som uppstÄtt dras slutsatsen att de Àr av en sÄdan karaktÀr att de inte utgör nÄgot hinder för en portering.

[19] Full text  Jonas Hietala. 2015.
A Comparison of Katz-eig and Link-analysis for Implicit Feedback Recommender Systems.
Student Thesis. 85 pages. ISRN: LIU-IDA/LITH-EX-A--15/026--SE.

Link: http://www.jonashietala.se/masters_thesi...

Recommendations are becoming more and more important in a world where there is an abundance of possible choices and e-commerce and content providers are featuring recommendations prominently. Recommendations based on explicit feedback, where user is giving feedback for example with ratings, has been a popular research subject. Implicit feedback recommender systems which passively collects information about the users is an area growing in interest. It makes it possible to generate recommendations based purely from a user's interactions history without requiring any explicit input from the users, which is commercially useful for a wide area of businesses. This thesis builds a recommender system based on implicit feedback using the recommendation algorithms katz-eig and link-analysis and analyzes and implements strategies for learning optimized parameters for different datasets. The resulting system forms the foundation for Comordo Technologies' commercial recommender system.

[18] Full text  Patrik Bergström. 2015.
Automated Setup of Display Protocols.
Student Thesis. 44 pages. ISRN: LIU-IDA/LITH-EX-A--15/014--SE.

Link: http://urn.kb.se/resolve?urn=urn:nbn:se:...

Radiologists' workload has been steadily increasing for decades. As digital technology matures it improves the workflow for radiology departments and decreases the time necessary to examine patients. Computer systems are widely used in health care and are for example used to view radiology images. To simplify this, display protocols based on examination data are used to automatically create a layout and hang images for the user. To cover a wide variety of examinations hundreds of protocols must be created, which is a time-consuming task and the system can still fail to hang series if strict requirements on the protocols are not met. To remove the need for this manual step we propose to use machine learning based on past manually corrected presentations. The classifiers are trained on the metadata in the examination and how the radiologist preferred to hang the series. The chosen approach was to create classifiers for different layout rules and then use these predictions in an algorithm for assigning series types to individual image slots according to categories based on metadata, similar to how display protocol works. The resulting presentations shows that the system is able to learn, but must increase its prediction accuracy if it is to be used commercially. Analyses of the different parts show that increased accuracy in early steps should improve overall success.

[17] Full text  Karl Nygren. 2015.
Trust Logics and Their Horn Fragments: Formalizing Socio-Cognitive Aspects of Trust.
Student Thesis. 93 pages. ISRN: LiTH-MAT-EX--2015/01--SE.

This thesis investigates logical formalizations of Castelfranchi and Falcone's (C&amp;F) theory of trust [9, 10, 11, 12]. The C&amp;F theory of trust defines trust as an essentially mental notion, making the theory particularly well suited for formalizations in multi-modal logics of beliefs, goals, intentions, actions, and time.Three different multi-modal logical formalisms intended for multi-agent systems are compared and evaluated along two lines of inquiry. First, I propose formal definitions of key concepts of the C&amp;F theory of trust and prove some important properties of these definitions. The proven properties are then compared to the informal characterisation of the C&amp;F theory. Second, the logics are used to formalize a case study involving an Internet forum, and their performances in the case study constitute grounds for a comparison. The comparison indicates that an accurate modelling of time, and the interaction of time and goals in particular, is integral for formal reasoning about trust.Finally, I propose a Horn fragment of the logic of Herzig, Lorini, Hubner, and Vercouter [25]. The Horn fragment is shown to be too restrictive to accurately express the considered case study.

[16] Full text  Mattias Tiger. 2014.
Unsupervised Spatio-Temporal Activity Learning and Recognition in a Stream Processing Framework.
Student Thesis. 103 pages. ISRN: LIU-IDA/LITH-EX-A--14/059--SE.

Learning to recognize and predict common activities, performed by objects and observed by sensors, is an important and challenging problem related both to artificial intelligence and robotics.In this thesis, the general problem of dynamic adaptive situation awareness is considered and we argue for the need for an on-line bottom-up approach.A candidate for a bottom layer is proposed, which we consider to be capable of future extensions that can bring us closer towards the goal.We present a novel approach to adaptive activity learning, where a mapping between raw data and primitive activity concepts are learned and continuously improved on-line and unsupervised. The approach takes streams of observations of objects as input and learns a probabilistic representation of both the observed spatio-temporal activities and their causal relations. The dynamics of the activities are modeled using sparse Gaussian processes and their causal relations using probabilistic graphs.The learned model supports both estimating the most likely activity and predicting the most likely future (and past) activities. Methods and ideas from a wide range of previous work are combined to provide a uniform and efficient way to handle a variety of common problems related to learning, classifying and predicting activities.The framework is evaluated both by learning activities in a simulated traffic monitoring application and by learning the flight patterns of an internally developed autonomous quadcopter system. The conclusion is that our framework is capable of learning the observed activities in real-time with good accuracy.We see this work as a step towards unsupervised learning of activities for robotic systems to adapt to new circumstances autonomously and to learn new activities on the fly that can be detected and predicted immediately.

[15] Full text  Per Jonsson. 2014.
Design och implementation av webbenkäter: kvalitet, svarsfrekvens och underhćll.
Student Thesis. 10 pages. ISRN: LIU-IDA/LITH-EX-G--14/049--SE.

En webbapplikation för analys och administration av webbenkÀter har designats och implementerats. Dess syfte Àr att maximera svarskvalitet och svarsfrekvens samt att vara underhÄllbar. Uppdragsgivaren Ericsson Linköping har utfÀrdat kravspecifikationen för applikationen. HÀnsyn har tagits till aspekterna webbenkÀtdesign och under-hÄllbarhet av mjukvara. UnderhÄllbarhetsmodeller för mjukvara med tillhörande metriker, samt designmodeller och rekommendationer för webbenkÀter har studerats. Arbetets bidrag till dessa omrÄden Àr en praktisk modell som tillÀmpar rÄdande forskning, i form av en webbapplikation. Applikationen har testats mot modeller och rekommendationer för underhÄllbarhet och enkÀtdesign. Applikationen uppvisar hög grad av analyserbarhet, förÀndringsbarhet och testbarhet, men inte stabilitet. Effekten av enkÀtdesignen har inte utvÀrderats. Modellen för underhÄllbarhet kan klarlÀgga orsak och verkan i mjukvarusystem och bidra till utveckling av programvara med hög kvalitet.

[14] Full text  Anders Wikström. 2014.
Resource allocation of drones flown in a simulated environment.
Student Thesis. 24 pages. ISRN: LIU-IDA/LITH-EX-G--14/003—SE.

In this report we compare three different assignment algorithms in how they can be used to assign a set of drones to get to a set of goal locations in an as resource efficient way as possible. An experiment is set up to compare how these algorithms perform in a somewhat realistic simulated environment. The Robot Operating system (ROS) is used to create the experimental environment. We found that by introducing a threshold for the Hungarian algorithm we could reduce the total time it takes to complete the problem while only sightly increasing total distance traversed by the drones.

[13] Jakob Pogulis. 2013.
Testramverk för distribuerade system.
Student Thesis. 46 pages. ISRN: LIU-IDA/LITH-EX-G--13/010--SE.

When developing software that is meant to be distributed over several different computers and several different networks while still working together against a common goal there is a challenge in testing how updates within a single component will affect the system as a whole. Even if the performance of that specific component increases that is no guarantee for the increased performance of the entire system. Traditional methods of testing software becomes both hard and tedious when several different machines has to be involved for a single test and all of those machines has to be synchronized as well.This thesis has resulted in an exemplary application suite for testing distributed software. The thesis describes the method used for implementation as well as a description of the actual application suite that was developed. During the development several important factors and improvements for such a system was identified, which are described at the end of the thesis even though some of them never made it into the actual implementation. The implemented application suite could be used as a base when developing a more complete system in order to distribute tests and applications that has to run in a synchronized manner with the ability to report the results of each individual component.

[12] Full text  Christopher Bergdahl. 2013.
Modeling Air Combat with Influence Diagrams.
Student Thesis. 64 pages. ISRN: LIU-IDA/LITH-EX-A--13/031--SE.

Air combat is a complex situation, training for it and analysis of possible tactics are time consuming and expensive. In order to circumvent those problems, mathematical models of air combat can be used. This thesis presents air combat as a one-on-one influence diagram game where the influence diagram allows the dynamics of the aircraft, the preferences of the pilots and the uncertainty of decision making in a structural and transparent way to be taken into account. To obtain the players’ game optimal control sequence with respect to their preferences, the influence diagram has to be solved. This is done by truncating the diagram with a moving horizon technique and determining and implementing the optimal controls for a dynamic game which only lasts a few time steps.The result is a working air combat model, where a player estimates the probability that it resides in any of four possible states. The pilot’s preferences are modeled by utility functions, one for each possible state. In each time step, the players are maximizing the cumulative sum of the utilities for each state which each possible action gives. These are weighted with the corresponding probabilities. The model is demonstrated and evaluated in a few interesting aspects. The presented model offers a way of analyzing air combat tactics and maneuvering as well as a way of making autonomous decisions in for example air combat simulators.

[11] Full text  Johan Fredborg. 2013.
Spam filter for SMS-traffic.
Student Thesis. 82 pages. ISRN: LIU-IDA/LITH-EX-A--13/021-SE.

Communication through text messaging, SMS (Short Message Service), is nowadays a huge industry with billions of active users. Because of the huge userbase it has attracted many companies trying to market themselves through unsolicited messages in this medium in the same way as was previously done through email. This is such a common phenomenon that SMS spam has now become a plague in many countries.This report evaluates several established machine learning algorithms to see how well they can be applied to the problem of filtering unsolicited SMS messages. Each filter is mainly evaluated by analyzing the accuracy of the filters on stored message data. The report also discusses and compares requirements for hardware versus performance measured by how many messages that can be evaluated in a fixed amount of time.The results from the evaluation shows that a decision tree filter is the best choice of the filters evaluated. It has the highest accuracy as well as a high enough process rate of messages to be applicable. The decision tree filter which was found to be the most suitable for the task in this environment has been implemented. The accuracy in this new implementation is shown to be as high as the implementation used for the evaluation of this filter.Though the decision tree filter is shown to be the best choice of the filters evaluated it turned out the accuracy is not high enough to meet the specified requirements. It however shows promising results for further testing in this area by using improved methods on the best performing algorithms.

[10] Full text  Jonatan Olofsson. 2012.
Towards Autonomous Landing of a Quadrotorusing Monocular SLAM Techniques.
Student Thesis. 102 pages. ISRN: LIU-IDA/LITH-EX-A--12/026--SE.

Use of Unmanned Aerial Vehicles have seen enormous growth in recent years due to the advances in related scientific and technological fields. This fact combined with decreasing costs of using UAVs enables their use in new application areas. Many of these areas are suitable for miniature scale UAVs - Micro Air Vehicles(MAV) - which have the added advantage of portability and ease of deployment. One of the main functionalities necessary for successful MAV deployment in real-world applications is autonomous landing. Landing puts particularly high requirements on positioning accuracy, especially in indoor confined environments where the common global positioning technology is unavailable. For that reason using an additional sensor, such as a camera, is beneficial. In this thesis, a set of technologies for achieving autonomous landing is developed and evaluated. In particular, state estimation based on monocular vision SLAM techniques is fused with data from onboard sensors. This is then used as the basis for nonlinear adaptive control as well trajectory generation for a simple landing procedure. These components are connected using a new proposed framework for robotic development. The proposed system has been fully implemented and tested in a simulated environment and validated using recorded data. Basic autonomous landing was performed in simulation and the result suggests that the proposed system is a viable solution for achieving a fully autonomous landing of a quadrotor.

[9] Full text  Anders Hongslo. 2012.
Stream Processing in the Robot Operating System framework.
Student Thesis. 79 pages. ISRN: LIU-IDA/LITH-EX-A--12/030--SE.

Streams of information rather than static databases are becoming increasingly important with the rapid changes involved in a number of fields such as finance, social media and robotics. DyKnow is a stream-based knowledge processing middleware which has been used in autonomous Unmanned Aerial Vehicle (UAV) research. ROS (Robot Operating System) is an open-source robotics framework providing hardware abstraction, device drivers, communication infrastructure, tools, libraries as well as other functionalities.This thesis describes a design and a realization of stream processing in ROS based on the stream-based knowledge processing middleware DyKnow. It describes how relevant information in ROS can be selected, labeled, merged and synchronized to provide streams of states. There are a lot of applications for such stream processing such as execution monitoring or evaluating metric temporal logic formulas through progression over state sequences containing the features of the formulas. Overviews are given of DyKnow and ROS before comparing the two and describing the design. The stream processing capabilities implemented in ROS are demonstrated through performance evaluations which show that such stream processing is fast and efficient. The resulting realization in ROS is also readily extensible to provide further stream processing functionality.

[8] Full text  Viet Ha Nguyen. 2012.
Design Space Exploration of the Quality of Service for Stream Reasoning Applications.
Student Thesis. 35 pages. ISRN: LIU-IDA/LITH-EX-A--12/027--SE.

An Unmanned Aerial Vehicle (UAV) is often an aircraft with no crew that can fly independently by a preprogrammed plan, or by remote control. Several UAV applications, like autonomously surveillance and traffic monitoring, are real-time applications. Hence tasks in these applications must complete within specied deadlines.Real Time Calculus (RTC) is a formal framework for reasoning about realtime systems and in particular streaming applications. RTC has its mathematical roots in Network Calculus. It supports timing analysis, estimating loads and predicting memory requirements.In this thesis, a formal analysis of real-time stream reasoning for UAV applications is conducted. The performance analysis is based on RTC using an abstract performance model of the streaming reasoning on board a UAV. In this study, we consider two dierent scheduling methods, first-in-first-out (FIFO) and fixed priority (FP). In the FIFO scheduling model the priorities of the tasks are assigned and processed based on the order of their arrival, while in the FP scheduling model the priorities of the tasks are preassigned. The Quality of Service (QoS) of these applications is calculated and analyzed in a proposed design space exploration framework.QoS can be defined dierently depending on what field we are studying and in this thesis we are interested in studying the delays of the real-time stream reasoning applications when (i) we fix jitters and number of instances and vary the periods, (ii) we fix the periods and number of instances and vary the jitters, and (iii) we fix the periods, jitters and vary the number of instances.

[7] Full text  Daniel Lazarovski. 2012.
Extending the Stream Reasoning in DyKnow with Spatial Reasoning in RCC-8.
Student Thesis. 74 pages. ISRN: LIU-IDA/LITH-EX-A--12/008--SE.

Autonomous systems require a lot of information about the environment in which they operate in order to perform different high-level tasks. The information is made available through various sources, such as remote and on-board sensors, databases, GIS, the Internet, etc. The sensory input especially is incrementally available to the systems and can be represented as streams. High-level tasks often require some sort of reasoning over the input data, however raw streaming input is often not suitable for the higher level representations needed for reasoning. DyKnow is a stream processing framework that provides functionalities to represent knowledge needed for reasoning from streaming inputs. DyKnow has been used within a platform for task planning and execution monitoring for UAVs. The execution monitoring is performed using formula progression with monitor rules specified as temporal logic formulas. In this thesis we present an analysis for providing spatio-temporal functionalities to the formula progressor and we extend the formula progression with spatial reasoning in RCC-8. The result implementation is capable of evaluating spatio-temporal logic formulas using progression over streaming data. In addition, a ROS implementation of the formula progressor is presented as a part of a spatio-temporal stream reasoning architecture in ROS.

[6] Full text  Zlatan Dragisic. 2011.
Semantic Matching for Stream Reasoning.
Student Thesis. 110 pages. ISRN: LIU-IDA/LITH-EX-A--11/041--SE.

Autonomous system needs to do a great deal of reasoning during execution in order to provide timely reactions to changes in their environment. Data needed for this reasoning process is often provided through a number of sensors. One approach for this kind of reasoning is evaluation of temporal logical formulas through progression. To evaluate these formulas it is necessary to provide relevant data for each symbol in a formula. Mapping relevant data to symbols in a formula could be done manually, however as systems become more complex it is harder for a designer to explicitly state and maintain thismapping. Therefore, automatic support for mapping data from sensors to symbols would make system more flexible and easier to maintain.DyKnow is a knowledge processing middleware which provides the support for processing data on different levels of abstractions. The output from the processing components in DyKnow is in the form of streams of information. In the case of DyKnow, reasoning over incrementally available data is done by progressing metric temporal logical formulas. A logical formula contains a number of symbols whose values over time must be collected and synchronized in order to determine the truth value of the formula. Mapping symbols in formula to relevant streams is done manually in DyKnow. The purpose of this matching is for each variable to find one or more streams whose content matches the intended meaning of the variable.This thesis analyses and provides a solution to the process of semantic matching. The analysis is mostly focused on how the existing semantic technologies such as ontologies can be used in this process. The thesis also analyses how this process can be used for matching symbols in a formula to content of streams on distributed and heterogeneous platforms. Finally, the thesis presents an implementation in the Robot Operating System (ROS). The implementation is tested in two case studies which cover a scenario where there is only a single platform in a system and a scenario where there are multiple distributed heterogeneous platforms in a system.The conclusions are that the semantic matching represents an important step towards fully automatized semantic-based stream reasoning. Our solution also shows that semantic technologies are suitable for establishing machine-readable domain models. The use of these technologies made the semantic matching domain and platform independent as all domain and platform specific knowledge is specified in ontologies. Moreover, semantic technologies provide support for integration of data from heterogeneous sources which makes it possible for platforms to use streams from distributed sources.

[5] Full text  Marjan Alirezaie. 2011.
Semantic Analysis Of Multi Meaning Words Using Machine Learning And Knowledge Representation.
Student Thesis. 74 pages. ISRN: LiU/IDA-EX-A- -11/011- -SE.

The present thesis addresses machine learning in a domain of naturallanguage phrases that are names of universities. It describes two approaches to this problem and a software implementation that has made it possible to evaluate them and to compare them.In general terms, the system's task is to learn to 'understand' the significance of the various components of a university name, such as the city or region where the university is located, the scienti c disciplines that are studied there, or the name of a famous person which may be part of the university name. A concrete test for whether the system has acquired this understanding is when it is able to compose a plausible university name given some components that should occur in the name.In order to achieve this capability, our system learns the structure of available names of some universities in a given data set, i.e. it acquires a grammar for the microlanguage of university names. One of the challenges is that the system may encounter ambiguities due to multi meaning words. This problem is addressed using a small ontology that is created during the training phase.Both domain knowledge and grammatical knowledge is represented using decision trees, which is an ecient method for concept learning. Besides for inductive inference, their role is to partition the data set into a hierarchical structure which is used for resolving ambiguities.The present report also de nes some modi cations in the de nitions of parameters, for example a parameter for entropy, which enable the system to deal with cognitive uncertainties. Our method for automatic syntax acquisition, ADIOS, is an unsupervised learning method. This method is described and discussed here, including a report on the outcome of the tests using our data set.The software that has been implemented and used in this project has been implemented in C.

[4] Full text  Fredrik Ćslin. 2010.
Evaluation of Hierarchical Temporal Memory in algorithmic trading.
Student Thesis. 32 pages. ISRN: LIU-IDA/LITH-EX-G--10/005--SE.

This thesis looks into how one could use Hierarchal Temporal Memory (HTM) networks to generate models that could be used as trading algorithms. The thesis begins with a brief introduction to algorithmic trading and commonly used concepts when developing trading algorithms. The thesis then proceeds to explain what an HTM is and how it works. To explore whether an HTM could be used to generate models that could be used as trading algorithms, the thesis conducts a series of experiments. The goal of the experiments is to iteratively optimize the settings for an HTM and try to generate a model that when used as a trading algorithm would have more profitable trades than losing trades. The setup of the experiments is to train an HTM to predict if it is a good time to buy some shares in a security and hold them for a fixed time before selling them again. A fair amount of the models generated during the experiments was profitable on data the model have never seen before, therefore the author concludes that it is possible to train an HTM so it can be used as a profitable trading algorithm.

[3] Mikael Nilsson. 2009.
Spanneröar och spannervägar.
Student Thesis. 126 pages. ISRN: -.

In this Master Thesis the possibility to efficiently divide a graph into spanner islands is examined. Spanner islands are islands of the graph that fulfill the spanner condition, that the distance between two nodes via the edges in the graph cannot be too far, regulated by the stretch constant, compared to the Euclidian distance between them. In the resulting division the least number of nodes connecting to other islands is sought-after. Different heuristics are evaluated with the conclusion that for dense graphs a heuristic using MAX-FLOW to divide problematic nodes gives the best result whereas for sparse graphs a heuristic using the single-link clustering method performs best. The problem of finding a spanner path, a path fulfilling the spanner condition, between two nodes is also investigated. The problem is proven to be NP-complete for a graph of size n if the spanner constant is greater than n^(1+1/k)*k^0.5 for some integer k. An algorithm with complexity O(2^(0.822n)) is given. A special type of graph where all the nodes are located on integer locations along the real line is investigated. An algorithm to solve this problem is presented with a complexity of O(2^((c*log n)^2))), where c is a constant depending only on the spanner constant. For instance, the complexity O(2^((5.32*log n)^2))) can be reached for stretch 1.5.

[2] Full text  Tommy Persson. 2009.
Evaluating the use of DyKnow in multi-UAV traffic monitoring applications.
Student Thesis. 75 pages. ISRN: LIU-IDA/LITH-EX-A--09/019--SE.

This Master’s thesis describes an evaluation of the stream-based knowledge pro-cessing middleware framework DyKnow in multi-UAV traffic monitoring applica-tions performed at Saab Aerosystems. The purpose of DyKnow is “to providegeneric and well-structured software support for the processes involved in gen-erating state, object, and event abstractions about the environments of complexsystems.\" It does this by providing the concepts of streams, sources, computa-tional units (CUs), entity frames and chronicles.This evaluation is divided into three parts: A general quality evaluation ofDyKnow using the ISO 9126-1 quality model, a discussion of a series of questionsregarding the specific use and functionality of DyKnow and last, a performanceevaluation. To perform parts of this evaluation, a test application implementinga traffic monitoring scenario was developed using DyKnow and the Java AgentDEvelopment Framework (JADE).The quality evaluation shows that while DyKnow suffers on the usability side,the suitability, accuracy and interoperability were all given high marks.The results of the performance evaluation high-lights the factors that affect thememory and CPU requirements of DyKnow. It is shown that the most significantfactor in the demand placed on the CPU is the number of CUs and streams. Italso shows that DyKnow may suffer dataloss and severe slowdown if the CPU istoo heavily utilized. However, a reasonably sized DyKnow application, such as thescenario implemented in this report, should run without problems on systems atleast half as fast as the one used in the tests.

[1] Jonas Kvarnström. 1996.
A New Tractable Planner for the SAS+ Formalism.
Student Thesis. In series: LiTH-IDA-Ex #9625. 283 pages. ISRN: LiTH-IDA-Ex-9625.

Computer science

Page responsible: Patrick Doherty
Last updated: 2014-04-30