Quantum walks on graphs have been proven to be a useful tool in quantum algorithm construction for various problems. In this thesis we introduce a new type of continuous-time quantum walk on graphs called the quantum snake walk, the basis states of which are fixed-length paths (snakes) in the underlying graph. We first consider the quantum snake walk on the line. The analysis of the eigenvalues and the eigenvectors of the Hamiltonian governing the walk reveals that most states initially localized in a segment on the line always remain in that same segment. However, there are exponentially small (in the length of the snake) fraction of states which move on the line as wave packets with momentum inversely proportional to the length of the snake. Next we show how an algorithm based on the quantum snake walk might be able to solve an extended version of the glued trees problem which asks to find a path connecting both roots of the glued trees graph. No efficient quantum algorithm solving this problem is known yet. For that reason we consider a specific extension of the glued trees graph and analyze how the quantum snake walk behaves on it. In particular we show that the quantum snake walk on the infinite binary tree, restricted to certain superpositions, in many aspects is very similar to the quantum snake walk on the line. We also argue why the quantum snake walk, initialized in certain superpositions on one side of the glued trees graph, after certain amount of time is likely to be found on the other side of the graph. This seems to be crucial if we want our algorithm to work.

No description available.

There is an abundance of pathfinding solutions, but are any of those solutions suitable for usage in a real time strategy (RTS) game designed for mobile systems with limited processing and storage capabilities (such as the Nintendo DS, PSP, cellular phones, etc.)? The RTS domain puts great requirements on the pathfinding mechanics used in the game; in the form of de- mands on responsiveness and path optimality. Furthermore, the Nintendo DS, and its portable, distant relatives, bring hard con- straints on the processing- and memory resources available to said mechanics. This master thesis aims to find a pathfinding solution well suited to function within the above mentioned, narrow domain. From a broad selection of candidate solutions, a few promising subjects are treated to an investigative empirical study; with the goal of finding the best “fitting” solution, considering the domain. The empirical study shows that the triangle-based TRA* solution and the hierarchical-abstraction influenced Minimal Memory so- lution are both very promising candidates. Depending on how one exactly defines the domain, either one of the solutions could be considered the ‘best’ choice. Since the overall performance of TRA* showed a slight advantage, this solution was further inves- tigated by running an implementation on one of the intended domain platforms; the Nintendo DS. This paper is structured to serve as a guide, of sorts, to some very interesting, and diverse, pathfinding solutions. In the spirit of this effort, all of the more important aspects of these solu- tions, and the pathfinding domain as a whole, are thoroughly explained.

Context: Pathfinding is an important phase when it comes to AI. The AI needs to know how to get from one point to another when there are obstacles ahead. For that reason, different pathfinding algorithms have been created. Objective: In this paper a new pathfinding algorithm, THPA*, is described, and it will also be compared to the more common algorithms, A*, and HPA* which THPA* is based on. Methods: These algorithms are then tested on an extensive array of maps with different paths and the results consisting of the execution times will be compared against each other. Results: The result of those tests conclude that THPA* performs better in terms of execution time in the average case; however it does suffer from low quality paths. Conclusions: This paper concludes that THPA* is a promising algorithm albeit in need of more refinement to make up for the negative points.

Context. Producing NavMeshes for pathfinding in computer games is a time-consuming process. Recast and Detour is a pair of stateof-the-art libraries that allows automation of NavMesh generation. It builds on a technique called Scene Voxelization, where triangle geometry is converted to voxels in heightfields. The algorithm is expensive in terms of execution time. A fast voxelization algorithm could be useful in real-time applications where geometry is dynamic. In recent years, voxelization implementations on the GPU have been shown to outperform CPU implementations in certain configurations. Objectives. The objective of this thesis is to find a GPU-based alternative to Recast’s voxelization algorithm, and determine when the GPU-based solution is faster than the reference. Methods. This thesis proposes a GPU-based alternative to Recast’s voxelization algorithm, designed to be an interchangeable step in Recast’s pipeline, in a real-time application where geometry is dynamic. Experiments were conducted to show how accurately the algorithm generates heightfields, how fast the execution time is in certain con- figurations, and how the algorithm scales with different sets of input data. Results. The proposed algorithm, when run on an AMD Radeon RX 480 GPU, was shown to be both accurate and fast in certain configurations. At low voxelfield resolutions, it outperformed the reference algorithm on typical Recast reference models. The biggest performance gain was shown when the input contained large numbers of small triangles. The algorithm performs poorly when the input data has triangles that are big in relation to the size of the voxels, and an optional optimization was presented to address this issue. Another optimization was presented that further increases performance gain when many instances of the same mesh are voxelized. Conclusions. The objectives of the thesis were met. A fast, GPUbased algorithm for voxelization in Recast was presented, and conclusions about when it can outperform the reference algorithm were drawn. Possibilities for even greater performance gains were identified for future research.

Context. There have been a lot of progress made in the field of pathfinding. One of the most used algorithms is A*, which over the years has had a lot of variations. There have been a number of papers written about the variations of A* and in what way they specifically improve A*. However, few papers have been written comparing A* with several different variations of A*. Objectives. The objectives of this thesis is to find how Dijkstra's algorithm, IDA*, Theta* and HPA* compare against A* based on the variables computation time, number of opened nodes, path length as well as number of path nodes. Methods. To find the answers to the question in Objectives, an experiment was set up where all the algorithms were implemented and tested over a number of maps with varying attributes. Results. The experimental data is compiled in a table showing the result of the tested algorithms for computation time, number of opened nodes, path length and number of path nodes over a number of different maps as well as the average performance over all maps. Conclusions. A* is shown to perform well overall, with Dijkstra's algorithm trailing shortly behind in computation time and expanded nodes. Theta* finds the best path, with overall good computation time marred by a few spikes on large, open maps. HPA* performs poorly overall when fully computed, but has by far the best computation time and node expansion when partially pre-computed. IDA* finds the same paths as A* and Dijkstra's algorithm but has a notably worse computation time than the other algorithms and should generally be avoided on octile grid maps.

Neural Networks have been applied in numeral broad categories of work. Such as classification, data processing, robotics, systemcontrol e.t.c. This thesis compares using traditional methods of the routing process in chip circuit design to using a Neural Network trained with evolution. Constructing and evaluating a chip design is a complicated thing, where a lot of variables have to be accounted for and therefore a simplified evaluation and design process is used in order to train the network and compare the results. This was done by constructing simple test cases and running the algorithms BFS, A*Star and the neural network and comparing the paths each algorithm found using a fitness function. The results were that BFS and A*Star both performed better on complex circuits, but the neural network was able to create better paths on very small and niche circuits. The conclusion of the study is that the neural network approach is not able to compete with the standard industry methods of the routing process, but we do not exclude the possibility that with a better designed Fitness function, this could be possible. / Neurala Nätverk används i flertal breda kategorier av arbete. Såsom klassificering, databehandling, robotik, systemkontroll e.t.c. Denna avhandling jämför traditionella metoder för routingprocessen i chip-kretsdesign med att använda ett neuralt nätverk utbildat med evolution. Att konstruera och utvärdera en chipdesign är en komplicerad sak, där många variabler måste tas hänsyn till och därför används en förenklad utvärderings- och designprocess för att träna nätverket och jämföra resultaten. Detta gjordes genom att konstruera enkla testfall och köra algoritmerna BFS, A * Star och det neurala nätverket och jämföra de sökvägar som varje algoritm fann med hjälp av en så kallad Fitness-funktion. Resultaten var att BFS och A * Star både fungerade bättre på komplexa kretsar, men det neurala nätverket kunde skapa bättre vägar på mycket små och nischade kretsar. Slutsatsen av studien är att det neurala nätverkssättet inte kan konkurrera med routingprocessens standardindustrimetoder, men vi utesluter inte möjligheten att med en bättre utformad Fitness-funktion skulle detta vara möjligt.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2017-02-13T13:05:50Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação-Mestrado-Adônis_Tavares-digital.pdf: 1967837 bytes, checksum: 2d0c23ab20f389f08ae9964b086b5f9f (MD5) / Made available in DSpace on 2017-02-13T13:05:50Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação-Mestrado-Adônis_Tavares-digital.pdf: 1967837 bytes, checksum: 2d0c23ab20f389f08ae9964b086b5f9f (MD5) Previous issue date: 2013-08-30 / Nos últimos anos, as unidades de processamento gráfico (GPU) têm apresentado um avanço significativo dos recursos computacionais disponíveis para o uso de aplicações não-gráficas. A capacidade de resolução de problemas envolvendo computação paralela, onde o mesmo programa é executado em diversos elementos de dados diferentes ao mesmo tempo, bem como o desenvolvimento de novas arquiteturas que suportem esse novo paradigma, como CUDA (Computed Unified Device Architecture), tem servido de motivação para a utilização da GPU em aplicações de propósito geral, especialmente em jogos. Em contrapartida, a performance das CPUs, mesmo com a presença de múltiplos núcleos (multi-core), tem diminuído, limitando o avanço tecnológico de diversas técnicas desenvolvidas na área de jogos e favorecendo a transição e o desenvolvimento das mesmas para a GPU. Alguns algoritmos de Inteligência Artificial que podem ser decompostos e demonstram certo nível de paralelismo, como o pathfinding, utilizado na navegação de agentes durante o jogo, têm sido desenvolvidos em GPU e demonstrado um desempenho melhor quando comparado à CPU. De modo semelhante, este trabalho tem como proposta a investigação e o desenvolvimento de possíveis otimizações ao algoritmo de pathfinding em GPU, por meio de CUDA, com ênfase em sua utilização na área de jogos, escalando a quantidade de agentes e nós de um mapa, possibilitando um comparativo com seu desempenho apresentado na CPU. / In recent years, graphics processing units (GPUs) have shown a significant advance of computational resources available for the use of non-graphical applications. The ability to solve problems involving parallel computing as well as the development of new architectures that supports this new paradigm, such as CUDA, has encouraged the use of GPU for general purpose applications, especially in games. Some parallel tasks which were CPU based are being ported over to the GPU due to their superior performance. One of these tasks is the pathfinding of an agent over a game map, which has already achieved a better performance on GPU, but is still limited. This work describes some optimizations to a GPU pathfinding implementation, addressing a larger work set (agents and nodes) with good performance compared to a CPU implementation.

This thesis explores the combination of influence maps and potential fields in two novel pathfinding algorithms, IM+PF and IM/PF, that allows AI agents to intelligently navigate an environment. The novel algorithms are compared to two established pathfinding algorithms, A* and A*+PF, in the real-time strategy (RTS) game StarCraft 2. The main focus of the thesis is to evaluate the pathfinding capabilities and real-time performance of the novel algorithms in comparison to the established pathfinding algorithms. Based on the results of the evaluation, general use cases of the novel algorithms are presented, as well as an assessment if the novel algorithms can be used in modern games. The novel algorithms’ pathfinding capabilities, as well as performance scalability, are compared to established pathfinding algorithms to evaluate the viability of the novel solutions. Several experiments are created, using StarCraft 2’s base game as a benchmarking tool, where various aspects of the algorithms are tested. The creation of influence maps and potential fields in real-time are highly parallelizable, and are therefore done in a GPGPU solution, to accurately assess all algorithms’ real-time performance in a game environment. The experiments yield mixed results, showing better pathfinding and scalability performance by the novel algorithms in certain situations. Since the algorithms utilizing potential fields enable agents to inherently avoid and engage units in the environment, they have an advantage in experiments where such qualities are assessed. Similarly, influence maps enable agents to traverse the map more efficiently than simple A*, giving agents inherent advantages. In certain use cases, where multiple agents require pathfinding to the same destination, creating a single influence map is more beneficial than generating separate A* paths for each agent. The main benefits of generating the influence map, compared to A*-based solutions, being the lower total compute time, more precise pathfinding and the possibility of pre-calculating the map. / Denna rapport utforskar kombinationen av influence maps och potential fields med två nya pathfinding algoritmer, IM+PF och IM/PF, som möjliggör intelligent navigation av AI agenter. De nya algoritmerna jämförs med två existerande pathfindingalgoritmer, A* och A*+PF, i realtidsstrategispelet StarCraft 2. Rapportens fokus är att utvärdera de nya algoritmernas pathfindingförmåga samt realtidsprestanda i förhållande till de två existerande algoritmerna, i sex olika experiment. Baserat på resultaten av experimenten presenteras generella användningsområden för algoritmerna tillsammans med en bedömning om algoritmerna kan användas i moderna spel. De fyra pathfindingalgoritmerna implementeras för att jämföra pathfindingförmåga och realtidsprestanda, för att dra slutsatser angående de nya algoritmernas livsduglighet. Med användningen av StarCraft 2 som ett benchmarkingvertyg skapas sex experiment där olika aspekter av algoritmerna testas. Genereringen av influence maps och potential fields i realtid är ett arbete som kan parallelliseras, och därför implementeras en GPGPU-lösning för att få en meningsfull representation av realtidsprestandan av algoritmerna i en spelmiljö. Experimenten visar att de nya algoritmerna presterar bättre i både pathfindingförmåga och skalbarhet under vissa förhållanden. Algoritmerna som använder potential fields har en stor fördel gentemot simpel A*, då agenterna kan naturligt undvika eller konfrontera enheter i miljön, vilket ger de algoritmerna stora fördelar i experiment där sådana förmågor utvärderas. Influence maps ger likväl egna fördelar gentemot A*, då agenter som utnyttjar influence maps kan traversera världen mer effektivt. Under förhållanden då flera AI agenter ska traversera en värld till samma mål kan det vara förmånligt att skapa en influence map, jämfört med att generera individuella A*-vägar till varje agent. De huvudsakliga fördelarna för de influence map-baserade algoritmerna är att de kräver lägre total beräkningstid och ger en merexakt pathfinding, samt möjligheten att förberäkna influence map-texturen.

The neural cell adhesion molecule L1 is a member of the immunoglobulin superfamily and it mediates many adhesive interactions during brain development. Mutations in the L1 gene are associated with a spectrum of X-linked neurological disorders known as CRASH or L1 syndrome. The objective of this thesis was to use the zebrafish model to investigate the molecular mechanisms of L1 functions and the pathological effects of its mutations. Zebrafish has two L1 homologs, L1.1 and L1.2. Inhibition of L1.1 expression by antisense morpholino oligonucleotides resulted in phenotypes that showed resemblances to L1 patients. However, knockdown of L1.2 expression did not result in notable neural defects. Furthermore, analysis of the expression pattern of L1.1 has led to the discovery of a novel soluble L1.1 isoform, L1.1s. L1.1s is an alternatively spliced form of L1.1, consisting of the first four Ig-like domains and thus a soluble secreted protein. L1.1 morphants exhibited disorganized brain structures with many having an enlarged fourth/hindbrain ventricle. Further characterization revealed aberrations in ventricular polarity, cell patterning and proliferation and helped differentiate the functions of L1.1 and L1.1s. While L1.1 plays a pivotal role in axonal outgrowth and guidance, L1.1s is crucial to brain ventricle formation. Significantly, L1.1s mRNA rescued many anomalies in the morphant brain, but not the trunk phenotypes. Receptor analysis confirmed that L1.1 undergoes heterophilic interactions with neuropilin-1a (Nrp1a). Peptide inhibition studies demonstrated further the involvement of L1.1s in neuroepithelial cell migration during ventricle formation. In the spinal cord, spinal primary motoneurons expressed exclusively the full-length L1.1, and abnormalities in axonal projections of morphants could be rescued only by L1.1 mRNA. Further studies showed that a novel interaction between the Ig3 domain of L1.1 and Unplugged, the zebrafish muscle specific kinase (MuSK), is crucial to motor axonal growth. Together, these results demonstrate that the different parts of L1.1 contribute to the diverse functions of L1.1 in neural development.