Efficiency of a Scenario Editor for Connectivity Between Virtual Military Combat Systems
Tobias Mellberg, Liam Vilhelmsson
Grundnivå (16hp)
kl 13:15, Alan Turing (In English)
[Abstract]Today people spend a lot of time trying to complete different software-related tasks. Poorly designed software can waste both time and resources needed to complete a task. It is therefore important to have efficient ways to complete these tasks. The Swedish Defence Research Agency, also known as FOI has developed software to calculate whether simulated units in the terrain have radio contact or not. In the current approach the employees manually writes scenario files which contains information about the contact, however, these scenario files quickly become very large and difficult to work with. A possible solution to this issue is creating a scenario editor where the user can use an interface to create information about the contact between the units. This thesis suggests a Military Combat System Scenario Editor (MCSSE) which is compared to the current approach. The comparison is made by first performing a number of tasks with both applications. The applications thereafter evaluated using a metric called Minimal Actions Performed (MAP) which is defined for this comparison. The thesis also suggests appropriate tasks for evaluating the applications using an iterative method consisting of meetings with an expert with specified questions. By using the MAP metric, the application can be evaluated and the results show that the MCSSE is on average 62.93% more efficient than the current approach. |
Solving Temporal CSPs via Enumeration and SAT Compilation
Leif Eriksson
Avancerad (30hp)
kl 10:15, Alan Turing (In English)
[Abstract]The constraint satisfaction problem (CSP) is a powerful framework used in theoretical computer science for formulating a multitude of problems. The CSP over a constraint language \Gamma (CSP(\Gamma)) is the decision problem of verifying whether a set of constraints based on the relations in \Gamma admits a satisfying assignment or not. Temporal CSPs are a special subclass of CSPs frequently encountered in AI. Here, the relations are first-order definable in the structure (Q;<), i.e the rationals with the usual order. These problems have previously often been solved by either enumeration or SAT compilation. We study a restriction of temporal CSPs where the constraint language is limited to logical disjunctions of <-, =-, \neq- and \leq-relations, and were each constraint contains at most k such basic relations (CSP({<,=,\neq,\leq\}^(\lor k))).
Every temporal CSP with a finite constraint language \Gamma is polynomial-time reducible to CSP({<,=,\neq,\leq\}^{\lor k}) where k is only dependent on \Gamma. As this reduction does not increase the number of variables, the time complexity of CSP(\Gamma) is never worse than that of CSP({<,=,\neq,\leq\}^(\lor k)). This makes the complexity of CSP({<,=,\neq,\leq\}^(\lor k)) interesting to study.
We develop algorithms combining enumeration and SAT compilation to solve CSP({<,=,\neq,\leq\}^(\lor k)), and study the asymptotic behaviour of these algorithms for different classes. Our results shows that all finite constraint languages \Gamma first order definable over (Q;<) are solvable in O*(((1/(e*ln(2)))-\epsilon_k)n)^n) time for some \epsilon_k>0 dependent on \Gamma. This is strictly better than O*((n/(e*ln(2))^n), i.e. O*((0.5307n)^n), achieved by enumeration algorithms. Some examples of upper bounds on time complexity achieved in the thesis are CSP({<}^(\lor 2)) in O*((0.1839n)^n) time, CSP({<,=,\leq}^(\lor 2)) in O*((0.2654n)^n) time, CSP({<,=,\neq}^(\lor 3)) in O*((0.4725n)^n) time and CSP({<,=,\neq,\leq}^(\lor 3)) in O*((0.5067n)^n) time. For CSP({<}^(\lor 2)) this should be compared to the bound O*((0.3679n)^n), from previously known enumeration algorithms. |
Investigating the Strength in Character-Based Word Models
Simon Keisala
Avancerad (30hp)
kl 13:15, Alan Turing (In English)
[Abstract]Using AI to automatically describe images is a challenging task.
The aim of this study has been to compare the use of character-based language models
with one of the current state-of-the-art token-based language model, im2txt, to generate
image captions, with focus on morphological correctness.
Some previous work has shown that character-based language models are able to outperform token-based
language models in morphologically rich languages,
other show that simple multi-layered LSTM-blocks are able to learn to replicate the syntax of its
training data, thus showing that character-based language models can be used for generating captions.
An alternative model based on TensorFlow im2txt has been created, where an additional LSTM-Block
is added. The new model was trained on character-sized tokens instead of word-sized tokens.
Both the original model and alternated model used the MSCOCO 2014 image and annotation sets
for training and testing. These sets are the ones originally used during the 2015 image
captioning competition.
The results suggest that a character-based language model has the potential of outperforming
current token-based language models, although due to time and computing power
constraints this study fail to make a clear conclusion. The training was limited to phase 1,
where the image recognition network was not trained, and reduced to 10\% of the recommended
training epochs (100k epochs instead of 1m).
The trained token-based language model was also using a larger vocabulary than the trained character-based language model.
A problem using the original subsampling of tokens is discussed, where using the original method on character-sized tokens would
remove characters (including special characters) instead of full words.
To solve this issue, a two-phase approach is suggested, where training data first is separated
into word-sized tokens where subsampling is performed. The remaining tokens are then separated
into character-sized tokens.
Future work suggest implementing the modified subsampling and fine-tuning the hyperparameters
of the character-based language model to gain a clearer conclusion of the performance. |
General-purpose maintenance planning using deep reinforcement learning and Monte Carlo tree search
Viktor Holmgren
Avancerad (30hp)
kl 13:15, Alan Turing (In English)
[Abstract]Maintenance planning and execution is increasingly important for the modern industrial sector. Maintenance costs can amount to a major part of industrial spending.However, it is not as simple as just reducing maintenance budgets. A balance must be struck between risking unplanned downtime and the costs of maintenance efforts, in order to keep the profit margins needed to compete in the global markets of today. One approach to improve the effectiveness of industries is to apply intelligent maintenance planners. In this thesis, a general-purpose maintenance planner based on Monte-Carlo tree search and deep reinforcement learning is presented. This planner was evaluated and compared against two different periodic planners as well as the oracle lower bound on four different maintenance scenarios. These four scenarios are all based on servicing wind turbines. All scenarios include imperfect maintenance actions, as well as uncertainty in terms of the outcomes of maintenance actions. Furthermore, the four scenarios include both single and multi-component variants. The evaluation showed that the proposed method is outperforming both periodic planners in three of the four scenarios, with the forth being inconclusive. These results indicate that the maintenance planner introduced in this paper is a viable method, at least for these types of maintenance problems. However,further research is needed on this topic of maintenance planning under uncertainty. More specifically, the viability of the proposed method on a more diverse set of maintenance problems is needed to draw any clear general conclusions. Finally, possible improvements to the training process that are discussed in this thesis should be investigated. |
Swedish web site
