Este trabalho está inserido no campo da Geomática e se concentra, mais especificamente, no estudo de métodos para exploração e seleção de rotas em espaços geográficos sem delimitação prévia de vias trafegáveis. As atividades que poderiam se beneficiar de estudos desse tipo estão inseridas em áreas da engenharia, logística e robótica. Buscou-se, com as pesquisas realizadas nesse trabalho, elaborar um modelo computacional capaz de consultar as informações de um terreno, explorar uma grande quantidade de rotas viáveis e selecionar aquelas rotas que oferecessem as melhores condições de trajetória entre dois pontos de um mapa. Foi construído um sistema a partir do modelo computacional proposto para validar sua eficiência e aplicabilidade em diferentes casos de estudo. Para que esse sistema fosse construído, foram combinados conceitos de sistemas baseados em agentes, lógica nebulosa e planejamento de rotas em robótica. As informações de um terreno foram organizadas, consumidas e apresentadas pelo sistema criado, utilizando mapas digitais. Todas as funcionalidades do sistema foram construídas por meio de software livre. Como resultado, esse trabalho de pesquisa disponibiliza um sistema eficiente para o estudo, o planejamento ou a simulação de rotas sobre mapas digitais, a partir de um módulo de inferência nebuloso aplicado à classificação de rotas e um módulo de exploração de rotas baseado em agentes autônomos. A perspectiva para futuras aplicações utilizando o modelo computacional apresentado nesse trabalho é bastante abrangente. Acredita-se que, a partir dos resultados alcançados, esse sistema possa ajudar a reduzir custos e automatizar equipamentos em diversas atividades humanas. / This research is placed in the field of Geomatics and focuses more specifically on the study of methods for exploration and route selection in geographic areas without prior definition of trafficable roads. Activities that could benefit from such studies are embedded in areas of engineering, logistics and robotics. This study aimed to develop a computational model able to select information from a terrain, explore a lot of viable routes and select those routes that offer the best possible path between two points on a map. It was built a system from the proposed computational model to validate its effectiveness and applicability in different case studies. For this system to be built concepts of agent-based systems, fuzzy logic and route planning in robotics were combined. The information about land were organized, presented and consumed by the system created using digital maps. All features of the system were built using open source. As a result, this research provides an efficient system for the study, planning or route simulation on digital maps, using a fuzzy inference module applied to the classification of routes and a module to operate routes based on autonomous agents. The perspective for future applications using the computational model presented in this study is quite comprehensive. It is believed that from the results, this system can help reduce costs and automate equipment in various human activities.

In underwater tracking and surveillance, the active towed array sonar presents a way of discovering and tracking adversarial submerged targets that try to stay hidden. The configuration consist of listening and emitting hydrophones towed behind a ship. Moreover, it has inherent limitations, and the characteristics of sound in the ocean are complex. By varying the pulse form emitted and the trajectory of the ship the measurement accuracy may be improved. This type of optimization constitutes a sensor management problem. In this thesis, a model of the tracking scenario has been constructed derived from Cramér-Rao bound analyses. A model predictive control approach together with information measures have been used to optimize a filter's estimated state of the target. For the simulations, the MATLAB environment has been used. Different combinations of decision horizons, information measures and variations of the Kalman filter have been studied. It has been found that the accuracy of the Extended Kalman filter is too low to give consistent results given the studied information measures. However, the Unscented Kalman filter is sufficient for this purpose.

Taxis équipés de capteurs GPS sont un dispositif sensoriel important pour examiner les mouvements et les activités des gens. Dans cette thèse, nous cherchons à découvrir les facettes cachées en ce qui concerne les dynamiques sociales et communautaires codés dans les données de taxi GPS pour mieux comprendre comment se comporte la population urbaine et la dynamique résultant de la ville. Comme certains « aspects cachés» sont en ce qui concerne l'aspect similaire de la dynamique sociale et de la communauté, nous avons encore définissons formellement trois catégories pour l'étude, et les explorer à combler les écarts importants entre la première circuler des données GPS et des applications innovantes et des services urbains intelligents. Plus précisément, 1. Pour permettre aux applications d'alertes de fraude de taxi en temps réel, nous vous proposons algorithme iBoat qui est capable de détecter des trajectoires anormales "à la volée " et déterminer quelles parties de la trajectoire sont responsables de sa "anomalousness", en les comparant historiquement trajectoires ayant la même origine et de destination. 2. Pour introduire des services de transport respectueux de l'environnement aux citoyens rentable et, nous vous proposons B -Planner qui est une approche en deux phases, à planifier des itinéraires de bus de nuit bi- directionnelles de levier grands taxis données GPS. 3. Afin d'offrir un système de planification voyage d'itinéraire personnalisé, interactif, et le trafic-courant pour les utilisateurs, nous proposons système Tripplanner qui contient à la fois hors ligne et des procédures en ligne, en s'appuyant sur une combinaison de géolocalisation réseau social et des ensembles de données de taxi GPS. Enfin, certaines directions de recherche prometteuses pour les travaux futurs sont signalées, qui tentent essentiellement de fusionner les données de taxi GPS avec d'autres ensembles de données pour fournir des services urbains plus intelligents et personnalisés / Taxis equipped with GPS sensors are an important sensory device for examining people’s movements and activities. They are not constrained to a pre-defined schedule/route. Big taxi GPS data recording the spatio-temporal traces left by taxis provides rich and detailed glimpse into the motivations, behaviours, and resulting dynamics of a city’s mobile population through the road network. In this dissertation, we aim to uncover the “hidden facets” regarding social and community dynamics encoded in the taxi GPS data to better understand how urban population behaves and the resulting dynamics in the city. As some “hidden facets” are with regard to similar aspect of social and community dynamics, we further formally define three categories for study (i.e. social dynamics, traffic dynamics, and operational dynamics), and explore them to fill the wide gaps between the raw taxi GPS data and innovative applications and smart urban services. Specifically, 1. To enable applications of real-time taxi fraud alerts, we propose iBOAT algorithm which is capable of detecting anomalous trajectories “on-the-fly” and identifying which parts of the trajectory are responsible for its anomalousness, by comparing them against historically trajectories having the same origin and destination. 2. To introduce cost-effective and environment-friendly transport services to citizens, we propose B-Planner which is a two-phase approach, to plan bi-directional night bus routes leveraging big taxi GPS data. 3. To offer a personalized, interactive, and traffic-aware trip route planning system to users, we propose TripPlanner system which contains both offline and online procedures, leveraging a combination of Location-based Social Network (i.e. LBSN) and taxi GPS data sets. Finally, some promising research directions for future work are pointed out, which mainly attempt to fuse taxi GPS data with other data sets to provide smarter and personalized urban services for citizens

Metrogaining is an urban outdoor navigational sport that uses a street map to which scored control points have been added. The objective is to collect maximum score points within a set time by visiting a subset of the scored control points. There is currently no metrogaining scoring standard, only guidelines on how to allocate scores. Accordingly, scoring approaches were explored to create new score sets by using scoring algorithms based on a simple relationship between the score of, and the number of visits to a control point. A spread model, which was developed to evaluate the score sets, generated a range of routes by solving a range of orienteering problems, which belongs to the class of NP-hard combinatorial optimisation problems. From these generated routes, the control point visit frequencies of each control point were determined. Using the visit frequencies, test statistics were subsequently adapted to test the goodness of scoring for each score set. The ndings indicate that the score-visits relationship is not a simple one, as the number of visits to a control point is not only dependent on its score, but also on the scores of the surrounding control points. As a result, the scoring algorithms explored were unable to cope with the complex scoring process uncovered. / Decision Sciences / M. Sc. (Operations Research)

In this work we present algorithms that are capable of calculating paths to destination for electric vehicles. These paths can be based on the simple metrics such as the distance, time or the paths can be based on more advanced metric such as the minimum energy demanding metric. This metric is parameterizable by the physical construction of the electrical vehicle. We also propose a new algorithm that computes energy optimal paths that are more acceptable by the driver, because it also takes into consideration the time metric while computing the path.

Given a grid of cells, each having a value indicating its cost per unit area, a variant of the least-cost path problem is to find a corridor of a specified width connecting two termini such that its cost-weighted area is minimized. A computationally efficient method exists for finding such corridors, but as is the case with conventional raster-based least-cost paths, their incremental orientations are limited to a fixed number of (typically eight orthogonal and diagonal) directions, and therefore, regardless of the grid resolution, they tend to deviate from those conceivable on the Euclidean plane. Additionally, these methods are limited to problems found on two-dimensional grids and ignore the ever-increasing availability and necessity of three-dimensional raster based geographic data. This thesis attempts to address the problems highlighted above by designing and testing least-cost corridor algorithms. First a method is proposed for solving the two-dimensional raster-based least-cost corridor problem with reduced distortion by adapting a distortion reduction technique originally designed for least-cost paths and applying it to an efficient but distortionprone least-cost corridor algorithm. The proposed method for distortion reduction is, in theory, guaranteed to generate no less accurate solutions than the existing one in polynomial time and, in practice, expected to generate more accurate solutions, as demonstrated experimentally using synthetic and real-world data. A corridor is then modeled on a threedimensional grid of cost-weighted cubic cells or voxels as a sequence of sets of voxels, called ‘neighborhoods,’ that are arranged in a 26-hedoral form, design a heuristic method to find a sequence of such neighborhoods that sweeps the minimum cost-weighted volume, and test its performance with computer-generated random data. Results show that the method finds a low-cost, if not least-cost, corridor with a specified width in a threedimensional cost grid and has a reasonable efficiency as its complexity is O(n2) where n is the number of voxels in the input cost grid and is independent of corridor width. A major drawback is that the corridor found may self-intersect, which is often not only an undesirable quality but makes the estimation of its cost-weighted volume inaccurate. / Med tanke på ett rutnät av celler, som vart och ett har ett värde som indikerar dess kostnad per areaenhet, är en variant av det billigaste banproblemet att hitta en korridor med en specificerad bredd som förbinder två terminaler så att dess kostnadsviktade område minimeras. Det finns en beräkningseffektiv metod för att hitta sådana korridorer, men som är fallet med konventionella rasterbaserade lägsta kostnadsspår är deras inkrementella orienteringar begränsade till ett fast antal (vanligtvis åtta ortogonala och diagonala) riktningar, och därför, oavsett nätupplösning tenderar de att avvika från de tänkbara på det euklidiska planet. Dessutom är dessa metoder begränsade till problem som finns i tvådimensionella nät och ignorerar den ständigt ökande tillgängligheten och nödvändigheten av tredimensionell rasterbaserad geografisk data. Denna avhandling försöker ta itu med problemen som belyses ovan genom att utforma och testa korridoralgoritmer till lägsta kostnad. Först föreslås en metod för att lösa det tvådimensionella rasterbaserade problemet med billigaste korridorer med minskad förvrängning genom att anpassa en distorsionsminskningsteknik som ursprungligen utformades för billigaste vägar och tillämpa den på en effektiv men distorsionsbenägen billigaste korridoralgoritm. Den föreslagna metoden för distorsionsminskning är i teorin garanterad att generera inte mindre exakta lösningar än den befintliga i polynomtid och i praktiken förväntas generera mer exakta lösningar, vilket demonstreras experimentellt med syntetiska och verkliga data. En korridor modelleras sedan på ett tredimensionellt rutnät av kostnadsvägda kubikceller eller voxels som en sekvens av uppsättningar av voxels, kallade "stadsdelar", som är ordnade i en 26-hedoral form, designar en heuristisk metod för att hitta en sekvens av sådana stadsdelar som sveper den lägsta kostnadsviktade volymen och testar dess prestanda med datorgenererade slumpmässiga data. Resultaten visar att metoden hittar en låg kostnad, om inte minst kostnad, korridor med en specificerad bredd i ett tredimensionellt kostnadsnät och har en rimlig effektivitet eftersom dess komplexitet är O (n2) där n är antalet voxlar i ingångskostnadsnätet och är oberoende av korridorbredd En stor nackdel är att korridoren som hittas kan korsa sig själv, vilket ofta inte bara är en oönskad kvalitet utan gör uppskattningen av dess kostnadsviktade volym felaktig. / <p>QC 20210309</p>

This thesis explores and compares traditional and reinforcement learning (RL) methods of performing 2D flight path planning in 3D space. A wide overview of natural, classic, and learning approaches to planning s done in conjunction with a review of some general recurring problems and tradeoffs that appear within planning. This general background then serves as a basis for motivating different possible solutions for this specific problem. These solutions are implemented, together with a testbed inform of a parallelizable simulation environment. This environment makes use of random world generation and physics combined with an aerodynamical model. An A* planner, a local RL planner, and a global RL planner are developed and compared against each other in terms of performance, speed, and general behavior. An autopilot model is also trained and used both to measure flight feasibility and to constrain the planners to followable paths. All planners were partially successful, with the global planner exhibiting the highest overall performance. The RL planners were also found to be more reliable in terms of both speed and followability because of their ability to leave difficult decisions to the autopilot. From this it is concluded that machine learning in general, and reinforcement learning in particular, is a promising future avenue for solving the problem of flight route planning in dangerous environments.