The use of artificial potential fields is beneficial in most two dimensional environments but they are bound by limitations. Introduction of the third dimension eradicates some of the limitations and brings about a set of new problems. If the emergent problems are solved then the new approach can give way to smarter helicopters and consequently a new game-play experience or possibly safer flight. This thesis aims to solve the emergent problems and proposes a new solution for guidance of autonomous helicopter agents in 3D games based on artificial potential fields. This new approach is compared to the most used alternative the A* pathfinding algorithm. Our experiments reveal that potential fields is a formidable alternative for navigation of helicopters. It can perform many times faster than the A* alternative and has lower rate of collision. / Neoaxis PFA

The use of potential field based navigation schemes in robotics has been limited by inherent local minima issues. Local minima traps, small passages, unstable motion, and targets positioned near objects all pose major concerns when using potential fields for local vehicle control. This work proposes a new algorithm, "Re-Active Vector Equilibrium" (RAVE) that mitigates many of these issues. The vehicle representation model is expanded to use multiple points subject to potential calculation and the addition of two forces, a velocity dependent "risk force" (F_rsk) and a velocity and direction dependent "tangential force" (F_tan). The vehicle representation model is also expanded from a single reactive point to a series of points that define the vehicle body, providing better and simpler vehicle control. This has the effect of simplifying the required calculations at the cost of increasing the calculation count. The risk force, F_rsk, allows for dynamic adaptation to the immediate environment by acting in opposition to the net obstacle force, and is inversely proportional to the vehicle speed. The tangential force, F_tan, encourages better wall-following behaviour and provides a biasing mechanism to resolve obstacle aligned with target local minima issues.

In eighties, the idea of using potential fields was first introduced in the field of the robotics. The purpose of using potential fields was to achieve the natural movement in robotics. Many researchers proceeded this idea to enhance their research. The idea of using potential fields was also introduced in real time strategy games for the better movement of objects. In this thesis we worked on the idea of using asymmetric potential fields in the game environment. The purpose of our study was to analyze the affect of asymmetric potential fields on unit’s formation and their movement in game environment. In this study performance of asymmetric potential fields was also compared with symmetric potential fields. By literature review the potential field and its usage in RTS games were studied. The methodology to implement the potential fields in RTS game was also identified in literature review. In experimental part the asymmetric potential fields implemented by using the methodology proposed by Hagelbäck and Johansson. By following that methodology asymmetric potential field was applied on StarCraft bot by using the BWAPI. Experiment was also designed to test the asymmetric potential field bot. Asymmetric potential field bot was tested on the two maps of StarCraft: Brood War game. On these two maps, bot implemented with asymmetric potential field and the bot implemented with symmetric potential field competed with four bots. Three bots were selected from StarCraft competition and one was built-in bot of this game. The results of these competition shows that asymmetric potential field bot has better performance than symmetric potential field bot. The results of experiments show that the performance of bot implemented with asymmetric potential fields was better than symmetric potential field on single unit type and two unit types. This study shows that with the help of asymmetric potential fields interesting unit formation can be formed in real time strategy games, which can give better result than symmetric potential fields.

Real-Time Strategy (RTS) is a sub-genre of strategy games which is running in real-time, typically in a war setting. The player uses workers to gather resources, which in turn are used for creating new buildings, training combat units, build upgrades and do research. The game is won when all buildings of the opponent(s) have been destroyed. The numerous tasks that need to be handled in real-time can be very demanding for a player. Computer players (bots) for RTS games face the same challenges, and also have to navigate units in highly dynamic game worlds and deal with other low-level tasks such as attacking enemy units within fire range. This thesis is a compilation grouped into three parts. The first part deals with navigation in dynamic game worlds which can be a complex and resource demanding task. Typically it is solved by using pathfinding algorithms. We investigate an alternative approach based on Artificial Potential Fields and show how an APF based navigation system can be used without any need of pathfinding algorithms. In RTS games players usually have a limited visibility of the game world, known as Fog of War. Bots on the other hand often have complete visibility to aid the AI in making better decisions. We show that a Multi-Agent PF based bot with limited visibility can match and even surpass bots with complete visibility in some RTS scenarios. We also show how the bot can be extended and used in a full RTS scenario with base building and unit construction. In the next section we propose a flexible and expandable RTS game architecture that can be modified at several levels of abstraction to test different techniques and ideas. The proposed architecture is implemented in the famous RTS game StarCraft, and we show how the high-level architecture goals of flexibility and expandability can be achieved. In the last section we present two studies related to gameplay experience in RTS games. In games players usually have to select a static difficulty level when playing against computer oppo- nents. In the first study we use a bot that during runtime can adapt the difficulty level depending on the skills of the opponent, and study how it affects the perceived enjoyment and variation in playing against the bot. To create bots that are interesting and challenging for human players a goal is often to create bots that play more human-like. In the second study we asked participants to watch replays of recorded RTS games between bots and human players. The participants were asked to guess and motivate if a player was controlled by a human or a bot. This information was then used to identify human-like and bot-like characteristics for RTS game players.

Potential Fields is an obstacle avoidance and general path-finding technique that has only quite recently started to be used in AI for video games. It has previously mainly been used in robotics for robot navigation. Although quite unexplored, Potential Fields have so far worked well in video games. Previous research has mainly focused on RTS (Real-Time Strategy) games. This research explores the use of Potential Fields in another genre called arena games (which is a quite unexplored genre as well). In the implementation, multiple Potential Fields have been used together, where each field had a different task. Also, weights were used on the different Potential Fields to give them different importance depending on some factors that are dynamic through the game, hence the use of the word weighted. The main focus of the user studies conducted was the impact the weights had on the computer controlled unit's general behaviour. The user studies conducted showed that it was hard to determine who was a computer controlled character and who was human controlled, therefore telling that multiple Potential Fields worked well for movement. The test participants became better at determining this the second match they played, no matter the properties of the match. However, the user studies did not show that the weights made a remarkable difference; there was no significant improvement on the situation adaptation and team cooperation, but no deterioration either. The concept of using weights needs to be explored further.

Real-Time Strategy (RTS) is a sub-genre of strategy games which is running in real-time, typically in a war setting. The player use workers to gather resources, which in turn is used for creating new buildings, training combat units and build upgrades and research. The game is won when all buildings of the opponents have been destroyed. The numerous tasks that need to be handled in real-time can be very demanding for a player. Computer players (bots) for RTS games face the same challenges, and also have to navigate units in highly dynamic game worlds and deal with other low-level tasks such as attacking enemy units within fire range. This thesis is a compilation of nine papers. The first four papers deal with navigation in dynamic game worlds, which can be very complex and resource demanding. Typically it is solved by using pathfinding algorithms. We investigate an alternative approach based on Artificial Potential Fields and show how a PF based navigation system can be used without any need of pathfinding algorithms. In RTS games players usually have a limited visibility of the game world, known as Fog of War. Bots on the other hand often have complete visibility to aid the AI in making better decisions. In a paper we show that a Multi-Agent PF based bot with limited visibility can match and even surpass bots with complete visibility in some RTS scenarios. In the sixth paper we show how the bot can be extended and used in a full RTS scenario with base building and unit construction. This is followed by a paper where we propose a flexible and expandable RTS game architecture that can be modified at several levels of abstraction to test different techniques and ideas. The proposed architecture is implemented in the famous RTS game StarCraft, and we show how the high-level architecture goals of flexibility and expandability can be achieved. The last two papers present two studies related to gameplay experience in RTS games. In games players usually have to select a static difficulty level when playing against computer opponents. In the first study we use a bot that during runtime can adapt the difficulty level depending on the skills of the opponent, and study how it affects the perceived enjoyment and variation in playing against the bot. To create bots that are interesting and challenging for human players a goal is often to create bots that play more human-like. In the second study we asked participants to watch replays of recorded RTS games between bots and human players. The participants were asked to guess and motivate if a player was controlled by a human or a bot. This information was then used to identify human-like and bot-like characteristics for RTS game players.

Este trabalho aborda o problema de planejamento de caminhos em robótica móvel autônoma utilizando campos potenciais. Dentre as várias técnicas de campos potenciais para controlar robôs, encontram-se as técnica de Campos Potenciais de Khatib1 (CP), Campo Potencial Harmônico (CPH), Campo Potencial Orientado (CPO) e Campo Potencial Localmente Orientado (CPLO). As técnicas CPH, CPO e CPLO são chamadas de técnicas baseadas em Problema de Valor de Contorno (PVC), pois são obtidas a partir de soluções de Equações Diferenciais Parciais (EDP) Elípticas em uma determinada condição de contorno, é obtido um sistema planejador de caminhos. Tais técnicas necessitam de uma etapa de solução de sistemas lineares, na qual se utiliza métodos iterativos, decorrentes da aplicação do método de diferenças finitas como solucionador das EDP. No presente trabalho, as técnicas de Campos Potenciais baseados em PVC foram estudadas e implementadas (usando processamento sequencial e paralelo), de modo a obter resultados de forma mais rápida e confiável. Foram utilizadas arquiteturas paralelas do tipo manycore. Finalmente, são feitas análises comparativas entre os vários métodos implementados. Todos os métodos estão prontos para serem incorporados tanto no simulador quanto nos times de robôs em desenvolvimento pelo grupo Warthog Robotics / This works details the task o path planning in autonomous mobile robots using potential fields techniques. Among potential fields techniques to control robots, there are Khatibs Potential Field2 (KPF), Harmonic Potential Field (HPF), Oriented Potential Field (OPF) and Locally Oriented Potential Field (LOPF). The HPF, OPF and LOPF techniques are called Boundary Value Problem (BVP) based, bacause they are obtained from numerical solutions of Elliptic Partial Differential Equations (PDE) in a well-defined boundary condition. These techniques go through a step of solving linear systems, in which is used iterative methods, that came from numerical solution of PDE. In this work, potential fields BVP based was studied and coded (using sequential and parallel architectures), to obtain results more quickly and reliably. And, finally, a comparative analyses of the various methods implemented are made. All methods are ready to be incorporated in the intelligent systens that are being developed by Warthog Robotics

A Suíte Figueira Branca é um complexo máfico-ultramáfico no Terreno Jauru, sudoeste do Cráton Amazônico. Novos dados litológicos, geoquímicos, de raios gama e de campos potenciais, integrados com dados geológicos, isotópicos e paleomagnéticos, foram utilizados para caracterizar of pulso magmático Mesoproterozóico da suíte vinculado a um ambiente distensivo. A Suíte Figueira Branca foi formada pela intrusão na crosta de um magma juvenil em 1425 Ma, mesma idade dos estágios tardios da orogenia Santa Helena. Em três artigos, esta suíte foi estudada em escalas desde microscópicas a continentais. Primeiramente, a Suíte Figueira Branca foi analisada através de lâminas para determinar a influência da utilização de vínculos errados ou inadequados na modelagem de dados de campos magnéticos e gravimétricos. Em seguida, a extensão do magmatismo pertencente à suite foi delimitado, via campos potenciais e gamaespectrometria, a quatro corpos ao norte da cidade de Indiavaí, MT - Brasil. A modelagem dos dados de campos gravimétrico e magnético indicaram que as fontes dos sinais geofísicos se encontram em horizontes rasos ou aflorantes. Estas intrusões apresentam um alinhamento noroeste por mais de 8 Km, com magnetização remanente significativa consistentes direções publicadas em estudos paleomagnéticos. O crescente enriquecimento de Elementos de Terras-Raras leves em corpos gabróicos da suíte foi interpretado como evidência de fracionamento progressivo do magma. A instrusão, a mineralogia e a assinatura geoquímica indicaram um ambiente de extesão de retro-arco durante os estágios finais da orogenia Santa Helena. A terceira parte deste trabalho consistiu na avaliação de reconstruções através de dados de campo magnético do supercontinente paleo- a mesoproterozóico Nuna. O mapa global de anomalia magnética, EMAG2, permitiu observar continuidades de lineamentos e regimes magnéticos em domínios de idades similares em diferentes crátons (Amazônico, Báltico, Oeste Africano, do Norte da China). Estas propriedades magnéticas indicaram a teoria que melhor se adequava aos dados de campo magnético, e sugeriram o ambiente regional onde o Terreno Jauru se encontrava na época da intrusão da Suíte Figueira Branca. / The Figueira Branca Suite is a layered mafic-ultramafic complex in the Jauru Terrane, southwest Amazon Craton. New lithological, geochemical, gamma-ray and potential field data, integrated with geological, isotope and paleomagnetic data are used to characterize this pulse of Mesoproterozoic extension-related magmatism. The Figueira Branca Suite formed through juvenile magma emplacement into the crust at 1425 Ma, coeval with the later stages of the Santa Helena Orogen. In three papers, this suite was studied from microscopic to continental scales. First, the Figueira Branca suite was analysed through thin sections to determine the influence of inaccurate constraints in magnetic and gravity field modelling. Then, the extent of magmatism within the suite was delimited to four bodies to the north of Indiavaí city, MT - Brazil, with potential fields and gamma-ray data. Modelling gravity and magnetic field data indicated that the anomalous sources are close to the surface or outcropping. These intrusions trend northwest over 8 km, with significant remanent magnetization that is consistent with published direction obtained through paleomagnetic data. The increasing enrichment of LREE in the gabbroic bodies of the suite was interpreted as evidence of progressive fractionation of the magma. The emplacement, mineralogy and geochemical signature point towards a backarc extension tectonic framework in the later stages of the Santa Helena Orogen. The third part of the work consisted on evaluating reconstructions of the Paleo-Mesoproterozoic supercontinent Nuna with magnetic field data. The global magnetic anomaly map, EMAG2, allowed to observe continuity of magnetic lineaments and regimes in domains of similar ages in different cratons (Amazon, Baltica, West Africa and North China). These magnetic features indicated the theory which the magnetic field best supported, and suggested the regional environment where the Jauru Terrane was inserted by the time of the intrusion of the Figueira Branca Suite.

A Suíte Figueira Branca é um complexo máfico-ultramáfico no Terreno Jauru, sudoeste do Cráton Amazônico. Novos dados litológicos, geoquímicos, de raios gama e de campos potenciais, integrados com dados geológicos, isotópicos e paleomagnéticos, foram utilizados para caracterizar of pulso magmático Mesoproterozóico da suíte vinculado a um ambiente distensivo. A Suíte Figueira Branca foi formada pela intrusão na crosta de um magma juvenil em 1425 Ma, mesma idade dos estágios tardios da orogenia Santa Helena. Em três artigos, esta suíte foi estudada em escalas desde microscópicas a continentais. Primeiramente, a Suíte Figueira Branca foi analisada através de lâminas para determinar a influência da utilização de vínculos errados ou inadequados na modelagem de dados de campos magnéticos e gravimétricos. Em seguida, a extensão do magmatismo pertencente à suite foi delimitado, via campos potenciais e gamaespectrometria, a quatro corpos ao norte da cidade de Indiavaí, MT - Brasil. A modelagem dos dados de campos gravimétrico e magnético indicaram que as fontes dos sinais geofísicos se encontram em horizontes rasos ou aflorantes. Estas intrusões apresentam um alinhamento noroeste por mais de 8 Km, com magnetização remanente significativa consistentes direções publicadas em estudos paleomagnéticos. O crescente enriquecimento de Elementos de Terras-Raras leves em corpos gabróicos da suíte foi interpretado como evidência de fracionamento progressivo do magma. A instrusão, a mineralogia e a assinatura geoquímica indicaram um ambiente de extesão de retro-arco durante os estágios finais da orogenia Santa Helena. A terceira parte deste trabalho consistiu na avaliação de reconstruções através de dados de campo magnético do supercontinente paleo- a mesoproterozóico Nuna. O mapa global de anomalia magnética, EMAG2, permitiu observar continuidades de lineamentos e regimes magnéticos em domínios de idades similares em diferentes crátons (Amazônico, Báltico, Oeste Africano, do Norte da China). Estas propriedades magnéticas indicaram a teoria que melhor se adequava aos dados de campo magnético, e sugeriram o ambiente regional onde o Terreno Jauru se encontrava na época da intrusão da Suíte Figueira Branca. / The Figueira Branca Suite is a layered mafic-ultramafic complex in the Jauru Terrane, southwest Amazon Craton. New lithological, geochemical, gamma-ray and potential field data, integrated with geological, isotope and paleomagnetic data are used to characterize this pulse of Mesoproterozoic extension-related magmatism. The Figueira Branca Suite formed through juvenile magma emplacement into the crust at 1425 Ma, coeval with the later stages of the Santa Helena Orogen. In three papers, this suite was studied from microscopic to continental scales. First, the Figueira Branca suite was analysed through thin sections to determine the influence of inaccurate constraints in magnetic and gravity field modelling. Then, the extent of magmatism within the suite was delimited to four bodies to the north of Indiavaí city, MT - Brazil, with potential fields and gamma-ray data. Modelling gravity and magnetic field data indicated that the anomalous sources are close to the surface or outcropping. These intrusions trend northwest over 8 km, with significant remanent magnetization that is consistent with published direction obtained through paleomagnetic data. The increasing enrichment of LREE in the gabbroic bodies of the suite was interpreted as evidence of progressive fractionation of the magma. The emplacement, mineralogy and geochemical signature point towards a backarc extension tectonic framework in the later stages of the Santa Helena Orogen. The third part of the work consisted on evaluating reconstructions of the Paleo-Mesoproterozoic supercontinent Nuna with magnetic field data. The global magnetic anomaly map, EMAG2, allowed to observe continuity of magnetic lineaments and regimes in domains of similar ages in different cratons (Amazon, Baltica, West Africa and North China). These magnetic features indicated the theory which the magnetic field best supported, and suggested the regional environment where the Jauru Terrane was inserted by the time of the intrusion of the Figueira Branca Suite.

In this thesis we present a hybrid control methodology using Artificial Potential Fields (APF) integrated with a modified Simulated Annealing (SA) optimization algorithm for motion planning of a multi-link robots team. The principle of this work is based on the locomotion of a snake where subsequent links follow the trace of the head. The proposed algorithm uses the APF method which provides simple, efficient and effective path planning and the modified SA is applied in order for the robots to recover from a local minima. Modifications to the SA algorithm improve the performance of the algorithm and reduce convergence time. Validation on a three-link snake robot shows that the derived control laws from the motion planning algorithm that combine APF and SA can successfully navigate the robot to reach its destination, while avoiding collisions with multiple obstacles and other robots in its path as well as recover from local minima. To improve the performance of the algorithm, the gradient descent method is replaced by Newton’s method which helps in reducing the zigzagging phenomenon in gradient descent method while the robot moves in the vicinity of an obstacle. / UOIT