This thesis details the implementation of a navigation mesh within the interior space planning software CET Designer. The motivation for this is to investigate whether a navigation mesh is a suitable alternative to its current path finding solution which is based on a waypoint graph. An empirical analysis between the navigation mesh and the waypoint graph was also conducted. A navigation mesh is successfully implemented and an alternative triangulation method is also tested. The alternative method which is referred to as "narrowest first-ear clipping" seems to create a navigation mesh that produces slightly shorter paths than a navigation mesh that utilizes an arbitrary triangulation method. It is argued that the navigation mesh alleviates much work from the user since it requires less user input. The mesh is also able to generate paths between any two given points within it. This makes it much more dynamic than the waypoint graph. The conducted analysis shows that the navigation mesh seems to generate paths that are generally shorter than the waypoint graph. The path generation time for the navigation mesh is on average slower than the waypoint graph. We failed to provide an environment where the navigation mesh was faster on average than the waypoint graph. However, the time difference between the navigation mesh and the waypoint graph seemed to reduce as the test environment size increased.

Unmanned vehicles are increasingly being used for mobile sensing missions. These missions can range from target acquisition to chemical and biological sensing. The reason why these vehicles are increasingly being used is because they can carry many different types of sensors and can function as a cheap platform for carrying these sensors. The sensing that will be explained in this thesis is target acquisition. Target acquisition is the act of locating the exact position of an "area of interest." Currently this task can be completed with different types of complex range sensors. This thesis presents a type of target acquisition scheme for unmanned vehicles that will use a combination of cheap, simple vision sensors and robot inertial navigation data in order to accurately measure the location of a target in real world coordinates. This thesis will first develop an accurate waypoint driving algorithm that will either use dead reckoning or GPS/ compass sensors. We will then develop a robust target extraction algorithm that will be able to pick out a target in an image. After this is completed we will develop an algorithm that will be used to find the distance to the target from the robot. This algorithm will be based on a type of active vision system. Finally we will integrate all of these algorithms together in order to develop a target extraction technique that will be able to accurately find the distance to the target. With the distance we can then find the real world location of the target. / Master of Science

Då artificiella intelligenta agenter försöker navigera i en virtuell värld med statiska hinder så behöver dess väg beräknas. För denna beräkning används ett lager som beskriver hur och vart agenten kan röra sig i världen kallat för sökrymd. Detta kan göras på flera olika sätt vilket ger skillnad i prestanda och minnesåtgång samt indirekta fördelar genom sättet sökrymden är uppbyggd på. Genom att jämföra dessa skillnader i olika miljöer så kan resultatet påvisa vilka egenskaper sökrymdstyperna ger i de olika miljöerna. Rapporten visar att n-sidat polygonbaserat navigationsnät ger mycket bra egenskaper i de olika mätningarna och ger även flera fördelar på grund av dess utformning som gör att det kan anpassa sig bra till olika miljöer.

<p>Då artificiella intelligenta agenter försöker navigera i en virtuell värld med statiska hinder så behöver dess väg beräknas. För denna beräkning används ett lager som beskriver hur och vart agenten kan röra sig i världen kallat för sökrymd. Detta kan göras på flera olika sätt vilket ger skillnad i prestanda och minnesåtgång samt indirekta fördelar genom sättet sökrymden är uppbyggd på. Genom att jämföra dessa skillnader i olika miljöer så kan resultatet påvisa vilka egenskaper sökrymdstyperna ger i de olika miljöerna.</p><p>Rapporten visar att n-sidat polygonbaserat navigationsnät ger mycket bra egenskaper i de olika mätningarna och ger även flera fördelar på grund av dess utformning som gör att det kan anpassa sig bra till olika miljöer.</p>

Video game characters must almost always be able to travel from point A to point B and this task can be solved in various ways. There exist grid maps, waypoints, mesh navigation and hierarchical techniques to solve this problem. On randomly generated terrain we make use of automatically generated waypoints to solve pathfinding queries. The waypoints are connected by edges to create a waypoint graph and the graph can be used in real time pathfinding for a single agent in a static environment. This is done by finding the vertices of the blocked triangles from the terrain and place a waypoint on each. We make use of the GPU to create the waypoint graph. The waypoints are connected by utilizing a serialized GPU quad tree to find the relevant blocked geometry to do a line-triangle intersection test. If a line between two waypoints do not intersect any blocked geometry the connection is valid and stored. We found out that it is possible to generate a waypoint graph during the startup of the game with acceptable time results, make use of such a graph for real time pathfinding and that players perceive the paths generated by the algorithm as realistic and responsive. Our conclusion is that our solution is well suited for a deterministic environment with agents of the same size.

Nowadays, with the development of electronic and communication technologies, more and more low-cost vehicles such as small, light-weight aircraft are widely applied in all kinds of fields. Ground Station is an essential part of low cost vehicles for the operator to control and monitor the vehicles. In this thesis, Ground Station Display and Flight Management System for Low-Cost Vehicles have been developed.The major objective of this project is to design an intuitive and easy operative Human Machine Interface for displaying and monitoring the flight data and traffic information on ground. Meanwhile, a Graphic User Interface for the Flight Management System has been developed for realizing the waypoints input and flight plan for the vehicles. To fulfill this task, a low-cost hardware and software architecture is presented. Moreover, some COTS tools such as VAPS and MATLAB are applied for the software development because of their Object-Oriented and Rapid Prototype design methods. At the end of project, simulation has been done for the display HMI to test the behaviours of objects and the impacts of display. The trajectory simulation of flight management control panel is also implemented to test the waypoints creation, trajectory generation and smoothing.

Aerial surveillance missions require a geographical region known as the area of interest to be inspected. The route that the aerial reconnaissance vehicle will follow is known as the flight route. Flight route planning operation has to be done before the actual mission is executed. A flight route may consist of hundreds of pre-defined geographical positions called waypoints. The optimal flight route planning manages to find a tour passing through all of the waypoints by covering the minimum possible distance. Due to the combinatorial nature of the problem it is impractical to devise a solution using brute force approaches. This study presents a strategy to find a cost effective and near-optimal solution to the flight route planning problem. The proposed approach is implemented on GPU using CUDA.

I nästan alla moderna datorspel så återfinns datorstyrda karaktärer, vilka behöver kunna navigera i spelvärlden. Dessa karaktärer kan vara olika typer av fiender i ett förstapersonskjutarspel, eller motståndare och medhjälpare i ett sportspel (exempelvis fotboll- eller rallyspel) med mera. Det finns många tekniker för att realisera vägplanering och det kan vara stora skillnader, både prestandamässiga och funktionella, mellan dem. Detta arbete jämför två olika sökrymdsrepresentationer för vägplanering, nämligen vägpunktsgrafer och navigationsnät, där sökrymderna automatgenererats. Jämförelsen görs med ett experiment och avser såväl prestanda (tids- och minneskostnad) som funktionalitet (optimal väg och antal svängar). Experimentmiljön stödjer godtyckliga vägar och ger detaljerad statistik för en noggrann jämförelse av vägplaneringsteknikerna. Arbetet visar på att navigationsnätet presterar bäst vad gäller funktionalitet. Vad gäller prestanda så presterar navigationsnätet generellt sett bäst, men vägpunktsgrafen kan ge bättre prestanda om nodavståndet hålls relativt högt. Det finns också många möjligheter att vidareutveckla arbetet, exempelvis förfina vägarna och kombinera vägplaneringsteknikerna med robotik.

The work contains presentation of the Geocaching game, mainly from the view of an information system. It contains study of existing applications with their advantages and disadvantages. There is a specification of new application, that should solve major disadvantages of existing products in second part of the work. Design of such application, that meets the requirements, follows. The application is implemented, which is described in following chapters, with the aim to target specific problems that were solved during the implementation. There is summary and future plans cotained in the closing chapter.

<p>I många nätverk antas det att någon form av fix infrastruktur existerar och att nätverkets olika noder kan använda denna för att kommunicera med varandra. I ett ad hoc-nätverk antar man att det inte finns någon fix infrastruktur och att noderna måste använda varandra för att kunna kommunicera. Ett exempel på ett ad hoc-nätverk kan vara bärbara datorer sammankopplade med infraröda länkar under ett möte. När ad hoc-nätverket är mobilt innebär det att noderna rör sig.</p><p>I detta arbete har de tre protokollen Epidemic, GeoMean och GeoMove tillsammans med de två rörelsemodellerna Waypoint och den utökade slumpmässiga vandringen implementerats i en nyskriven simulator för denna typ av nätverk.</p><p>De två Geo-protokollen är nyutvecklade och syftar till att använda geografisk information för att underlätta kommunikationen i denna kategori av nätverk tillsammans med den nya utvidgade slumpmässiga vandringsmodellen.</p> / <p>In many networks, some kind of fix infrastructure is assumed to exist and the nodes of the network can use this infrastructure to communicate with each other. In an ad hoc network one assumes that there don't exist any kind of fix infrastructure and that the nodes must use each other to be able to communicate. One example of an ad hoc network could be laptops connected together with infrared links during a meeting. When an ad hoc network is mobile it implies that the nodes are moving.</p><p>In this work, the three protocols Epidemic, GeoMean and GeoMove together with the two mobility models Waypoint and Extended Random Walk, have been implemented in a newly written simulator for this kind of network.</p><p>The two Geo-protocols are newly developed and aim to use geographical information to aid communication in this category of networks together with the new Extended Random Walk model.</p>