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.