This report covers an investigation of the methods and algorithms required to plan and perform semi-autonomous photo missions on Apple iPad devices using data exported from Google Earth. Flight time was to be minimized, taking wind velocity and aircraft performance into account. Google Earth was used both to define what photos to take, and to define the allowable mission area for the aircraft. A benchmark mission was created containing 30 photo operations in a 250 by 500 m area containing several no-fly-areas. The report demonstrates that photos taken in Google Earth can be reproduced in reality with good visual resemblance. High quality paths between all possible photo operation pairs in the benchmark mission could be found in seconds using the Theta* algorithm in a 3D grid representation with six-edge connectivity (Up, Down, North, South, East, West). Smoothing the path in a post-processing step was shown to further increase the quality of the path at a very low computational cost. An optimal route between the operations in the benchmark mission, using the paths found by Theta*, could be found in less than half a minute using a Branch-and-Bound algorithm. It was however also found that prematurely terminating the algorithm after five seconds yielded a route that was close enough to optimal not to warrant running the algorithm to completion.

This thesis serves as an introduction to anyone that has an interest in artificial intelligence games and has experience in programming or anyone who knows nothing of computer games but wants to learn about it. The first part will present a brief introduction to AI, then it will give an introduction to games and game programming for someone that has little knowledge about games. This part includes game programming terminology, different game genres and a little history of games. Then there is an introduction of a couple of common techniques used in game AI. The main contribution of this dissertation is in the second part where three techniques that never were properly implemented before 3D games took over the market are introduced and it is explained how they would be done if they were to live up to today’s standards and demands. These are: line of sight, image recognition and pathfinding. These three techniques are used in today’s 3D games so if a 2D game were to be released today the demands on the AI would be much higher then they were ten years ago when 2D games stagnated. The last part is an evaluation of the three discussed topics.

Detta examensarbete undersöker navigering för grupper av autonoma agenter i dataspelsmiljöer. Genom att kombinera olika styrbeteenden och beräkningsmodeller utvärderar arbetet vilken av dessa tekniker som är mest effektiv med avseende på tid och vägval i trånga spelmiljöer. En experimentmiljö har utvecklats som implementerar fyra stycken tekniker och utvärderar dessa i tre olika miljöer med 10 respektive 50 agenter som navigerar genom miljön. Som grund använder samtliga tekniker ett vägföljningsbeteende och ett flockbeteende. Det som skiljer teknikerna åt är vilken beräkningsmodell som används samt att två av teknikerna använder ett väggundvikelsebeteende. Resultatet visar att alla tekniker är användbara men att den mer avancerade beräkningsmodellen ger ett bättre resultat överlag. Väggundvikelsebeteendet bidrar också till ett bättre resultat och gör alltså nytta i de miljöer som använts. Ett problem med styrbeteenden är dock balanseringen av vikterna som används i teknikerna och det kan krävas mycket finjustering innan man får ett bra beteende.

The fast-developing industry of electric vehicles is growing, and so is the driver community, which puts pressure on the electric charging grid. The purpose of this thesis is to simplify for the drivers of electric cars to charge their cars during trips. The research questions investigated are” How do the technologies and algorithms behind navigation APIs differ from each other?” and “What information is provided by the charging station APIs and how do they collect data about new stations?”. Information for the thesis was collected by reading and analyzing both documentation and previous work, as well as by conducting experiments. The study was limited to purely electric vehicles. We created an application to conduct experiments on the API combination Mapbox and Open Charge Map, we call it ChargeX. We compare, TomTom, Tesla, Plugshare, Google Maps and ChargeX. The most common shortest-path algorithms are Dijkstra’s, A* and Bidirectional A*. They provide reasonable solutions to the shortest path problem. The algorithms can be improved by considering traffic flow, travel time and distance between origin and destination and apply it as weights on the edges. What has the largest impact on the final route is the choice of charging stations. The algorithm for picking charging stations can be optimized in several ways for example by considering real time availability information of the charging stations, prioritize highways, calculate the temperature and altitude impact on the battery or prioritize faster chargers such as superchargers for Tesla.

Slay the Spire is a complex deck-building and roguelike game with many possibilities of improving players ability to win. An important part of Slay the Spire is choosing a path that makes the players character as successful as possible. In this study we show that machine learning can help players pick better paths by creating an Artificial Neural Network (ANN) that predicts the most successful path of all available paths, we also discuss what makes a path successful. This study performed two experiments, one user study and one simulation experiment, with the intention of evaluating the created ANN and analysing what makes paths successful. Through the user study this paper shows that the ANN was effective at predicting paths, outperforming all other human players who played normally in all three cases. This study concludes that machine learning can be used effectively to help make pathing decisions in Slay the Spire. Furthermore the study proves the importance of the room types ’Elite’ and ’Campfires’ through the simulation experiment, user study and analysis of data from previous playthroughs.

L’objectif de cette thèse est de proposer un modèle comportemental de l’être humain pour la simulation d’évacuation de bâtiment en cas d’incendie et de l’intégrer dans un outil de simulation d’évacuation de bâtiment. Le modèle proposé représente une approche individu-centré du comportement et répond aux axiomes de la Rationalité Limitée énoncés par Herbert Simon grâce à une conception hiérarchique des moyens cognitifs des agents simulés. L’implémentation du modèle du comportement présente la particularité d’être intégralement réalisée en GPU (via OpenGL 2.0). Ainsi la fréquence du moteur de comportement est très proche de celle du simulateur et permet une adaptation quasi temps réel des comportements des agents à un changement de perception de leur environnement. Le logiciel d’évacuation développé permet :– l’importation de scénario d’incendie de bâtiment simulé grâce au logiciel FDS,– la configuration des archétypes de comportement des agents évacuant, notamment :– la description des hypothèses sur le monde (connaissance individuelle),– la configuration des comportements des agents (moyens cognitifs individuels).– le positionnement des agents dans le bâtiment,– la simulation de l’évacuation,– l’enregistrement et le play-back d’un scénario d’évacuation.Les contraintes (feu, fumée, obstacles, autres agents) captées par un agent sont interprétées par ce dernier en fonction de son archétype de comportement afin de déterminer si sa stratégie d’évacuation doit être remise en cause. / The main objective of this thesis is to propose a behavioral model of the human being in presence of several constraints and to integrate it into a simulation tool for building egress. The proposed model represents an individual-based approach of behavior modelisation and implement axioms of the bounded rationality set by Herbert Simon providing two key features :– individual prioritization and parametisation of cognitivemeans,– individual perception and knowledgemanagement.The proposed software has the particularity to run entirely on GPU via OpenGL 2.0. Thus the frequency of the behavior engine is very near to that of the simulator and allow adaptation of near real-time behavior of agents in a changing perception of their environment.

[pt] Bases de conhecimento são ferramentas poderosas que fornecem suporte a um amplo espectro de aplicações como, por exemplo, busca exploratória, ranqueamento e recomendação. Bases de conhecimento podem ser vistas como grafos, onde os nós representam entidades e as arestas seus relacionamentos. Atualmente, motores de busca usam bases de conhecimento para melhorar suas recomendações. No entanto, motores de busca são orientados a uma única entidade e enfrentam dificuldades ao tentar explicar porque e como duas entidades estão relacionadas, um problema conhecido como relacionamento entre entidades. Esta tese explora o uso de bases de conhecimento em formato RDF para endereçar o problema de relacionamento entre entidades, em duas direções. Em uma direção, a tese define o conceito de perfis de conectividade para pares de entidades, que são explicações concisas sobre como as entidades se relacionam. A tese introduz uma estratégia para gerar um perfil de conectividade entre um par de entidades, que combina anotações semânticas e métricas de similaridade para resumir um conjunto de caminhos entre as duas entidades. Em seguida, introduz a ferramenta DBpedia profiler, que implementa a estratégia proposta, e cuja efetividade foi medida através de experimentos com usuários. Em outra direção, considerando os desafios para explorar grandes bases de conhecimento online, a tese apresenta uma estratégia genérica de busca baseada na heurística backward, a qual prioriza alguns caminhos sobre outros. A estratégia combina medidas de similaridade e de ranqueamento, criando diferentes alternativas. Por último, a tese avalia e compara as diferentes alternativas em dois domínios, música e filmes, adotando como ground truth rankings especializados de caminhos especialmente desenvolvidos para os experimentos. / [en] Knowledge bases are a powerful tool for supporting a large spectrum of applications such as exploratory search, ranking, and recommendation. Knowledge bases can be viewed as graphs whose nodes represent entities and whose edges represent relationships. Currently, search engines take advantage of knowledge bases to improve their recommendations. However, search engines are single entity-centric and face difficulties when trying to explain why and how two entities are related, a problem known as entity relatedness. This thesis explores the use of knowledge bases in RDF format to address the entity relatedness problem, in two directions. In one direction, it defines the concept of connectivity profiles for entity pairs, which are concise explanations about how the entities are related. The thesis introduces a strategy to generate a connectivity profile for an entity pair that combines semantic annotations and similarity metrics to summarize a set of relationship paths between the given entity pair. The thesis then describes the DBpedia profiler tool, which implements the strategy for DBpedia, and whose effectiveness was evaluated through user experiments. In another direction, motivated by the challenges of exploring large online knowledge bases, the thesis introduces a generic search strategy, based on the backward search heuristic, to prioritize certain paths over others. The strategy combines similarity and ranking measures to create different alternatives. Finally, the thesis evaluates and compares the different alternatives in two domains, music and movies, based on specialized path rankings taken as ground truth.

This thesis covers an implementation of an artificial intelligence (AI) system for cooperation between multiple AI-agents. It was done as a part of a master thesis in Media Technology and a master thesis in Computer Engineering at Linköping University, campus Norrköping. The aim of the project was to explore modern techniques in AI and also develop a platform where this AI is implemented for the upcoming educational purposes. The idea is that students can use the system as a base to extend, learn and implement their own AI algorithms. Based on a literature study in AI systems the decision was made to base APAC on the GOAP system, a scalable planning architecture designed for real-time control of autonomous character behavior in games. The result of the thesis is a virtual world, made in Unity3D and C#, where the system is being used by virtual agents to build a city.

La synthèse de la parole par corpus (sélection d'unités) est le sujet principal de cette thèse. Tout d'abord, une analyse approfondie et un diagnostic de l'algorithme de sélection d'unités (algorithme de recherche dans le treillis d'unités) sont présentés. L'importance de l'optimalité de la solution est discutée et une nouvelle mise en œuvre de la sélection basée sur un algorithme A* est présenté. Trois améliorations de la fonction de coût sont également présentées. La première est une nouvelle façon – dans le coût cible – de minimiser les différences spectrales en sélectionnant des séquences d'unités minimisant un coût moyen au lieu d'unités minimisant chacune un coût cible de manière absolue. Ce coût est testé pour une distance sur la durée phonémique mais peut être appliqué à d'autres distances. Notre deuxième proposition est une fonction de coût cible visant à améliorer l'intonation en se basant sur des coefficients extraits à travers une version généralisée du modèle de Fujisaki. Les paramètres de ces fonctions sont utilisés au sein d'un coût cible. Enfin, notre troisième contribution concerne un système de pénalités visant à améliorer le coût de concaténation. Il pénalise les unités en fonction de classes reposant sur une hiérarchie du degré de risque qu'un artefact de concaténation se produise lors de la concaténation sur un phone de cette classe. Ce système est différent des autres dans la littérature en cela qu'il est tempéré par une fonction floue capable d'adoucir le système de pénalités pour les unités présentant des coûts de concaténation parmi les plus bas de leur distribution. / This PhD thesis focuses on the automatic speech synthesis field, and more specifically on unit selection. A deep analysis and a diagnosis of the unit selection algorithm (lattice search algorithm) is provided. The importance of the solution optimality is discussed and a new unit selection implementation based on a A* algorithm is presented. Three cost function enhancements are also presented. The first one is a new way – in the target cost – to minimize important spectral differences by selecting sequences of candidate units that minimize a mean cost instead of an absolute one. This cost is tested on a phonemic duration distance but can be applied to others. Our second proposition is a target sub-cost addressing intonation that is based on coefficients extracted through a generalized version of Fujisaki's command-response model. This model features gamma functions modeling F0 called atoms. Finally, our third contribution concerns a penalty system that aims at enhancing the concatenation cost. It penalizes units in function of classes defining the risk a concatenation artifact occurs when concatenating on a phone of this class. This system is different to others in the literature in that it is tempered by a fuzzy function that allows to soften penalties for units presenting low concatenation costs.

Thesis deals with automatic guided mobile robot focused on obstacle avoidance during ride on planned route. There are summaries of usually used obstacle detecting sensors and algorithms used for path finding. Based on this, own solution is designed. It uses waypoints changes to pass obstacle. MATLAB simulation is created for tests of new designed method. This method is implemented to real robot for real world testing. Reached goals and upgrade possibilities are summarized in bottom of thesis.