No description available.

Identifying a globally optimal solution for an intractable discrete optimization problem is often cost prohibitive. Therefore, solutions that are within a predetermined threshold are often acceptable in practice. This dissertation introduces the concept of B-acceptable solutions where B is a predetermined threshold for the objective function value. It is difficult to assess a priori the effectiveness of local search algorithms, which makes the process of choosing parameters to improve their performance difficult. This dissertation introduces the B-acceptable solution probability in terms of B-acceptable solutions as a finite-time performance measure for local search algorithms. The B-acceptable solution probability reflects how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. The B-acceptable solution probability is also used to obtain necessary asymptotic convergence (with probability one) conditions. Upper and lower bounds for the B-acceptable solution probability are presented. These expressions assume particularly simple forms when applied to specific local search strategies such as Monte Carlo search and threshold accepting. Moreover, these expressions provide guidelines on how to manage the execution of local search algorithm runs. Computational experiments are reported to estimate the probability of reaching a B-acceptable solution for a fixed number of iterations. Logistic regression is applied as a tool to estimate the probability of reaching a B-acceptable solution for values of B close to the objective function value of a globally optimal solution as well as to estimate this objective function value. Computational experiments are reported with logistic regression for pure local search, simulated annealing and threshold accepting applied to instances of the TSP with known optimal solutions. / Ph. D.

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.

Many cities suffer from problems with high traffic flows in the city centers which leads to a desire to get more people to choose public transport over cars. For many car drivers, the main reason to take the car is the convenience and time efficiency; the price is often of less importance. The public transport providers should, therefore, strive to improve their Level of Service (LOS). A general process that can be used by public transport providers or other stakeholders to evaluate the LOS in a public transport system based on Automated Vehicle Location (AVL) data is developed and presented in this thesis.The process values the quality and suitability of the AVL data, propose which KPIs to use and how to use the results to find possible improvements. Four different types of erroneous data were discovered: outliers in position, outliers in speed, outliers in travel time and general errors. KPIs are developed in three main areas: on-time performance, travel time distribution and speed, where each KPI is divided into several sub-areas.

Background. Neural Networks have mainly been used in behavior and gameplayrelated areas in games, but they have not yet been used specifically for intersection testing. This thesis explores the possibility to use deep neural networks for intersection testing of two 3D meshes. Objectives. The main goal of the thesis is to train a Deep Neural Network that can be used to replace traditional intersection test algorithms by having similar accuracy and a faster execution time. Methods. The research methods used in this thesis are implementation and experimentation. The deep neural network is trained using TensorFlow. Two different mesh generation techniques are implemented, one generating heightmaps and one generating planets. The two mesh types are combined to test all combinations of generated meshes. Attempts to make the network as general as possible are done through importance sampling to expose the network to tricky situations. A test application is developed where the intersection testing can be performed and compared to the Separating Axis Theorem (SAT). Heatmaps are also created to see how accurate the network is. Results. The results show that the network is accurate at classifying intersection between meshes similar to the ones it trained on. However, the network lacks generality and has bad accuracy if new meshes are introduced. The measured execution times show that the trained Deep Neural Network is 15.6 times as fast as a singlethreaded implementation of the SAT and 2.3 times as fast as the multi-threaded SAT. Conclusions. The trained network can be used as an early exit intersection test before using more expensive algorithms. The faster intersection testing can be useful in game physics by allowing faster classification of which meshes need to be tested for collisions. However, the main outcome is the shown potential for future work in the area including training a more general network, allowing variable mesh sizes, and providing information for solving collision responses. / Bakgrund. Neurala Nätverk har främst använts för beteende- och spelmekanikrelaterade områden inom spel, men de har ännu inte använts för genomskärningstester. Det här examensarbetet utförskar möjligheten att använda djupinlärning för att utföra genomskärningstester mellan två tredimensionella spelobjekt. Syfte. Huvudmålet med det här examensarbetet är att träna ett djupinlärt neuralt nätverk som kan ersätta traditionella genomskärningstestalgoritmer genom likvärdig precision och snabbare exekveringstid. Metod. Forskningsmetoderna som användes under examensarbetet är implementation och experimentation. Det djupinlärda neurala nätverket tränas med TensorFlow. Två olika spelobjektsgenereringsmetoder implementeras, där den ena genererar heightmaps och den andra genererar planeter. De två objekttyperna kombineras så att alla kombinationer av spelobjekt kan testas. För att göra nätverket så generellt som möjligt används importance sampling som utsätter nätverket för svåra situationer. Ett testprogram utvecklas där genomskärningstester kan utföras och jämföras mot Separating Axis Theorem (SAT). Grafer av typen heatmaps skapas också för att visa hur hög precision nätverket har. Resultat. Resultaten visar att nätverket har hög precision vid klassificering av spelobjekt liknande de som den tidigare har tränat på. Nätverket har sämre precision när nya spelobjekt introduceras. De uppmätta exekveringstiderna visar att det neurala nätverket är 15.6 gånger så snabbt som singeltrådade implementationen av SAT och 2.3 gånger så snabbt som den flertrådade SAT-implementationen. Slutsatser. Det tränade nätverket kan användas som ett tidig avbrott innan en dyrare algoritm används. Den snabbare genomskärningstestningen kan vara användbar i spelfysik eftersom den tillåter snabbare klassificering av vilka spelobjekt som behöver testas för kollision. Det huvudsakliga utfallet är den visade potentialen för vidare forskning inom området vilket inkluderar träning av ett mer generellt nätverk, möjlighet att variera spelobjektens storlek samt ge information för att kunna lösa kollisioner.

Transportation and installation of offshore wind turbines (Tower, Nacelle and Rotor) is a complete process conducted over several phases, usually in sequence. There are several factors that can turn this process into a challenge. These factors can either be due to offshore site conditions or the technical limitations of the installation vessels. Each project has its own characteristic parameters and requires a unique optimum solution. This paper identifies the dynamics of the installation process and analyzes the effects of each phase on the progression of events.The challenges in wind turbine installations due to offshore environment were investigated, the effects of each were explained and their significances were stressed. Special installation vessels were examined and their technical specifications were analyzed in terms of working conditions, dimensions, service performances, and crane capacities as well as projecting future design trends. Several offshore wind farm projects were analyzed; their installation methods were specified, and compared to each other to determine advantages and disadvantages of different pre-assembly concepts. The durations of the sub-phases of the process were defined in terms of different variables such as site conditions and individual vessel performance. These definitions were used for making time estimations, and conducting further analyses regarding the effects of different site specific parameters on the overall project duration.In conclusion, this study considered the main operation parameters in an offshore wind turbine installation context: the benefits and drawbacks of different pre-assembly methods were researched and evaluated resulting in new knowledge and a productive contribution for optimizing “the offshore turbine transportation and installation process”, based on actual time usage.

An Over-Actuated (OA) vehicle is a system that presents more control variables than degrees of freedom. Therefore, more than one configuration of the control input can drive the system to a desired state in the state space, and this redundancy can be exploited to fulfill other tasks or solve further problems. In particular, nowadays, challenges concerning electric vehicles regarding their autonomy and solutions to reduce energy consumption are becoming more and more attractive. OA vehicles, on this problem, offer the possibility of using the redundancy to choose the control input, among possible ones, so as to minimize energy consumption. In this regard, the research objective is to investigate different techniques to control in real-time an over-actuated autonomous driving vehicle to guarantee trajectory following and stability with the aim of minimizing energy consumption. The research project focuses on a vehicle able to drive and steer the four wheels (4WD, 4WS) independently. This work extends the contribution of previous theoretical energy-based research developed and provides a control algorithm that must work in real-time on a prototype vehicle (RCV-E) developed at the Integrated Transport Research Lab (ITRL) within KTH with the over-actuation investigated. To this end, the control algorithm has to balance the complexity of a multi-input system, the optimal allocation objectives, and the agility to run in real-time on the MicroAutoBox II - dSPACE system mounted on the vehicle. The solution proposed is a two-level controller which handles separately high and low-rate dynamics with an adequate level of complexity. The upper level is responsible for trajectory following and energy minimization. The allocation problem is solved in two steps. A Linear Time-Varying Model Predictive Controller (LTV-MPC) solves the trajectory-following problem and allocates the forces at the wheels considering the wheel energy losses due to longitudinal and lateral sliding. The second step re-allocates the longitudinal forces between the front and rear axles by considering each side of the vehicle independently to minimize energy loss in the motors. The lower level is responsible for transforming the forces at the wheels into torques and steering angles; it runs at a faster rate than the upper level to account for the high-frequency dynamics of the wheels. Last, the overall control strategy is tested in simulation concerning the trajectory-following and energy minimization performance. The real-time performance are assessed on MircoAutoBox II, the control interface used on the RCV-E. / Ett fordon med olika grad av över-aktuering är ett system som har fler kontrollvariabler än frihetsgrader. Därför kan mer än en konfiguration av styrinmatningen driva systemet till ett önskat tillstånd i tillståndsrummet, och denna redundans kan utnyttjas för att utföra andra uppgifter eller lösa andra problem. I synnerhet blir det i dag allt mer attraktivt med utmaningar som rör elfordon när det gäller deras självklörande drift och lösningar för att minska energiförbrukningen. Överaktuerat fordon ger möjlighet att använda redundansen för att välja en av de möjliga styrinmatningarna för att minimera energiförbrukningen. Forskningsmålet är att undersöka olika tekniker för att i realtid styra ett självkörande fordon som är överaktuerat för att garantera banföljning och stabilitet i syfte att minimera energiförbrukningen. Forskningsprojektet är inriktat på ett fordon som kan köra och styra de fyra hjulen (4WD, 4WS) självständigt. Detta arbete utökar bidraget från den tidigare teoretisk energi-baserade forskning som utvecklats genom att tillhandahålla en regleralgoritm som måste fungera i realtid på ett prototypfordon (RCV-E) som utvecklats vid ITRL inom KTH med den undersökta överaktueringen. I detta syfte måste regleralgoritmen balansera komplexiteten hos ett system med flera ingångar, målen för optimal tilldelning och smidigheten samt att fungera i realtid på MicroAutoBox II - dSPACE-systemet som är monterat på fordonet. Den föreslagna lösningen är en tvåstegsstyrning som hanterar dynamiken med hög och låg hastighet separat med en lämplig komplexitetsnivå. Den övre nivån ansvarar för banföljning och energiminimering. Tilldelningsproblemet löses i två steg. En LTV-MPC löser banföljningsproblemet och fördelar krafterna på hjulen med hänsyn till energiförlusterna på hjulen på grund av longitudinell och lateral glidning. I det andra steget omfördelas de längsgående krafterna mellan fram- och bakaxlarna genom att varje fordonssida beaktas oberoende av varandra för att minimera energiförlusterna i motorerna. Den lägre nivån ansvarar för att omvandla krafterna vid hjulen till vridmoment och styrvinklar; den körs i snabbare takt än den övre nivån för att ta hänsyn till hjulens högfrekventa dynamik. Slutligen testas den övergripande reglerstrategin i simulering med avseende på banföljning och energiminimering, och därefter på MircoAutoBox II monterad på RCV-E för att bedöma realtidsprestanda. / Un veicolo sovra-attuato è un sistema che presenta più variabili di controllo che gradi di libertà. Pertanto, più di una configurazione dell’ingresso di controllo può portare il sistema a uno stato desiderato nello spazio degli stati e questa ridondanza può essere sfruttata per svolgere altri compiti o risolvere ulteriori problemi. In particolare, al giorno d’oggi le sfide relative ai veicoli elettrici per quanto riguarda la loro autonomia e le soluzioni per ridurre il consumo energetico stanno diventando sempre più interessanti. I veicoli sovra-attuati, riguardo a questo problema, offrono la possibilità di utilizzare la ridondanza per scegliere l’ingresso di controllo, tra quelli possibili, che minimizza i consumi energetici. A questo proposito, l’obiettivo della ricerca è studiare diverse tecniche per controllare, in tempo reale, un veicolo a guida autonoma sovra-attuato per garantire l’inseguimento della traiettoria e la stabilità con l’obiettivo di minimizzare il consumo energetico. Questo studio si concentra su un veicolo in grado di guidare e sterzare le quattro ruote (4WD, 4WS) in modo indipendente, ed estende il contributo delle precedenti ricerche teoriche fornendo un algoritmo di controllo che deve funzionare in tempo reale su un prototipo di veicolo (RCV-E) sviluppato presso l’ITRL all’interno del KTH, che presenta la sovra-attuazione studiata. A tal fine, l’algoritmo di controllo deve bilanciare la complessità di un sistema a più ingressi, gli obiettivi di allocazione dell’azione di controllo ottimale e l’agilità di funzionamento in tempo reale sul sistema MicroAutoBox II - dSPACE montato sul veicolo. La soluzione proposta è un controllore a due livelli che gestisce separatamente le dinamiche ad alta e bassa frequenza. Il livello superiore è responsabile dell’inseguimento della traiettoria e della minimizzazione dell’energia. Il problema di allocazione viene risolto in due fasi. Un LTV-MPC risolve il problema dell’inseguimento della traiettoria e assegna le forze alle ruote tenendo conto delle perdite di energia agli pneumatici dovute al loro scorrimento longitudinale e laterale. Il secondo passo rialloca le forze longitudinali tra l’asse anteriore e quello posteriore considerando ciascun lato del veicolo in modo indipendente per minimizzare le perdite di energia nei motori. Il livello inferiore è responsabile della trasformazione delle forze alle ruote in coppia e angolo di sterzo; funziona a una più alta frequenza rispetto al livello superiore per tenere conto delle dinamiche veloci delle ruote. Infine, la strategia di controllo viene testata in simulazione per quanto riguarda le prestazioni di inseguimento della traiettoria e di minimizzazione dell’energia, e successivamente su MircoAutoBox II montato sull’RCV-E per valutare le prestazioni in tempo reale.