Unmanned aerial vehicles are becoming more popular in today’s society, which results in the rise of laws intended to maintain safety. To abide by these, while allowing the technology to expand, functioning path-planning algorithms are required.This also includes having methods for detecting and managing obstacles. This project aims to improve an existing path-planning algorithm that is based on A* and implemented in Python.The solution consisted of using functions for finding polytopeintersection,as well as optimizing the collision avoidance and the search algorithm. In addition to that, realistic constraints were implemented on the generated trajectory in order to reflect real-life limitations. The results demonstrated that the paths were always feasible, with respect to input and position constraints. The program’s computation time was also reduced up to 89% of the original run-time. There is, however, still room for improvement since the original code generated a shorter path for the three scenarios it was created for. On the other hand,the improved algorithm could handle a new scenario, which the original code failed to do. / Obemannade flygfarkoster blir alltmer vanliga i dagens samhälle, vilket resulterar i uppkomsten av nya lagar ämnade åt att upprätthålla säkerhet. För att förhålla sig till dessa, samtidigt som teknologin tillåts expandera, krävs fungerande vägplaneringsalgoritmer. Där ingår det även att ha metoder för att upptäcka och hantera hinder. Detta projekt syftar till att förbättra en befintlig vägplaneringsalgoritm som är baserad på A* och implenterad i Python. Lösningsmetoden bestod av att använda inbyggda Python-funktioner ämnade åt att finna skärningar mellan polytoper, samt optimera kollisionshantering och sökalgoritmen. Dessutom infördes realistiska krav på den framställda vägen i syfte om att reflektera verlighetens begränsningar. Resultatet visade att vägarna alltid var genomförbara, med avseende på inmatningsoch positionsrelaterade villkor. Programmets beräkningstid hade även reducerats upptill 89% av den ursprungliga körtiden. Det finns dock utrymme för förbättringar då den ursprungliga koden generar en kortare väg för de tre scenarion den tillverkades för. Däremot kinde den förbättrade algoritmen hantera ett nytt scenario, en ursprungliga koden misslyckades med. / Kandidatexjobb i elektroteknik 2022, KTH, Stockholm

This project proposes an adaptation of the dRRT* algorithm, a samplingbased multi-robot planner, for real-time industrial automation scenarios. The main objectives include optimizing computationally expensive sections of the algorithm, solving partially specified multi-robot problems, and evaluating the performance of the resulting method in various industry-like scenarios. The proposed algorithm, called Fast-dRRT*, aims to achieve highquality collision-free paths within strict time constraints. To accomplish this, the project introduces modifications to the dRRT* algorithm, such as the utilization of pre-computed swept volumes for efficient collision detection. The performance of four multi-robot planners, namely dRRT, ao-dRRT, dRRT*, and Fast-dRRT*, is evaluated through experiments on toy scenarios and industrial use cases. The results show that the proposed Fast-dRRT* algorithm outperforms the other planners in terms of finding solutions within the given time limits. It demonstrates improved efficiency, speed, and resilience to increased search spaces and the number of robots. The algorithm’s performance is further evaluated in real-world scenarios, including automotive assembly lines and warehouse automation, where it consistently outperforms dRRT* in terms of search speed and total planning time. Additionally, the algorithm successfully handles partially specified multi-robot problems, optimizing the overall movements’ cost. The study concludes that Fast-dRRT* is a promising option for real-time planning in industrial automation, offering reduced computation time and feasible solutions to complex multi-robot motion planning problems. / Detta projekt föreslår en anpassning av dRRT*-algoritmen, en samplingsbaserad multirobotplanerare, för realtidsscenarier inom industriell automation.. De huvudsakliga målen inkluderar optimering av beräkningskrävande delar av algoritmen, lösning av delvis specificerade multirobotproblem och utvärdering av den resulterande metodens prestanda i olika industriliknande scenarier. Den föreslagna algoritmen, kallad Fast-dRRT*, syftar till att uppnå högkvalitativa kollisionsfria banor inom strikta tidsbegränsningar. För att uppnå detta introducerar projektet modifieringar av dRRT*-algoritmen, såsom användning av förberäknade svepta volymer för effektiv kollisionsdetektering. Prestandan hos fyra multirobotplanerare, nämligen dRRT, ao-dRRT, dRRT* och Fast-dRRT*, utvärderas genom experiment på leksaksscenarier och industriella användningsfall. Resultaten visar att den föreslagna Fast-dRRT*- algoritmen överträffar de andra planerarna när det gäller att hitta lösningar inom de givna tidsgränserna. Den visar förbättrad effektivitet, hastighet och motståndskraft mot ökade sökutrymmen och antalet robotar. Algoritmens prestanda utvärderas vidare i verkliga scenarier, inklusive monteringslinjer för bilar och lagerautomation, där den konsekvent överträffar dRRT* när det gäller sökhastighet och total planeringstid. Dessutom hanterar algoritmen framgångsrikt delvis specificerade multirobotproblem och optimerar den totala rörelsekostnaden. Studien drar slutsatsen att Fast-dRRT* är ett lovande alternativ för realtidsplanering inom industriell automation, eftersom den erbjuder kortare beräkningstid och genomförbara lösningar på komplexa problem med rörelseplanering för multirobotar.

Tyre wear is a significant problem on today's road vehicles, particularly for heavy trucks. As the tyre wears, microplastics is released in the air causing long term health issues and environmental pollution. With the introduction of automated vehicles there is a big potential to improve tyre wear of heavy trucks. In this direction, this thesis investigates the fundamentals of motion planning for minimising the lateral tyre wear in cornering for automated articulated vehicles. The trade-off between journey time and tyre wear is analysed. For the simulations, firstly an articulated vehicle model is used from the literature and validated with IPG/TruckMaker. Secondly, a sensitivity analysis is conducted on the articulated vehicle on a couple of parameters. The front cornering stiffness, hitch point, trailer mass and trailer centre of gravity position where the parameters influence on tyre wear is analysed. The results showed that moving the hitch point forward decreases the total tyre wear, increasing mass of the trailer increases tyre wear while the front cornering stiffness and centre of gravity position of the trailer did low to no difference to the total tyre wear. Then, an optimal control problem was configured to investigate the motion planning of an articulated vehicle. Then, the motion planning system is configured to find an optimal feasible trajectory with respect to dynamic and path constraints for the articulated vehicle to minimise lateral wear at a predefined path for fixed journey times. Four case different configurations of the problem are investigated to study the influence of driving style, lateral manoeuvrability allowance, vehicle acceleration capabilities and of the number of steering axles on the tractor. The results showed that motion planning can be used for minimising lateral tyre wear. The case study with largest impact on tyre wear was driving style, where the tyre wear showed significant difference between slow driving and aggressive driving. The second case study showed that wider lateral allowance led to less tyre wear and increasing the acceleration capabilities also decreases lateral tyre wear. The additional steering axle on the truck decreased tyre wear at higher velocities but for lower velocities the difference was negligible. / Däckslitage är ett signifikant problem både ur ett miljöperspektiv och ur ett ekonomiskt perspektiv. Väldigt lite fokus läggs på utsläpp från däck när olika utsläppskällor diskuteras. När transportsamhället rör sig mot automation finns det stora möjligheter att utnyttja automatiserade fordon för att minska däckslitage. Det här examensarbetet undersöker möjligheterna att minimera däckslitage genom ruttplanering för automatiserade lastbilar med en artikulationspunkt. Ett optimeringsproblem formuleras och definieras med två målfunktioner för att undersöka hur det laterala däckslitaget i kurvor kan minimeras utan att förlänga restiden. Ruttplaneringens uppgift är att finna den mest optimala rutten med hänsyn till den fördefinierade vägen, fordonets dynamiska begränsningar och vägens begränsningar. Fyra delstudier genomförs, där körstil, vägbredd, maximal tillåten acceleration och påverkan av en ytterligare styrande axel undersökes. För att genomföra simuleringarna implementeras en bilmodell från litteraturen. Bilmodellen jämförs sedan med ett program för att validera dess noggrannhet och robusthet. Sedan görs en känslighetsanalys med hänsyn till däckslitage på några fordonsparametrar, nämligen artikuleringspunkten, framaxelns kurvstyvhet, placering av släpets tyngdpunkt och släpets vikt. Resultatet påvisade att ruttplanering är en bra metod för att minimera däckslitage, resultatet visade att körstil var en viktig faktor till däckslitage, där aggressiv körstil resulterade i mer slitage. Sedan visades det att vägbredd också hade en stor påverkan, där bredare vägar gav upphov till mindre slitage, och smalare vägar gav upphov till mer slitage. Vid högre tillåtna acclerationsnivåer blev däckslitaget lägre men högre vid lägre accelerationsgränser. När två styrbara axlar styrbara används så påvisades mindre däckslitage mot samma restid som när en axel är styrbar. Sist så visade känslighetsanalysen en stor skillnad på totalt däckslitage i relation till placering av artikuleringspunkten. Högre släpvikt gav också mer slitage medan placering av släpets tyngdpunkt och framaxelns kurvstyvhet gav upphov till låg ändring i totalt däckslitage.

Autonomous vehicles promise to play an important role aiming at increased efficiency and safety in road transportation. Although we have seen several examples of autonomous vehicles out on the road over the past years, how to ensure the safety of autonomous vehicle in the uncertain and dynamic environment is still a challenging problem. This thesis studies this problem by developing a risk-aware decision making framework. The system that integrates the dynamics of an autonomous vehicle and the uncertain environment is modelled as a Partially Observable Markov Decision Process (POMDP). A risk measure is proposed based on the Responsibility-Sensitive Safety (RSS) distance, which quantifying the minimum distance to other vehicles for ensuring safety. This risk measure is incorporated into the reward function of POMDP for achieving a risk-aware decision making. The proposed risk-aware POMDP framework is evaluated in two case studies. In a single-lane car following scenario, it is shown that the ego vehicle is able to successfully avoid a collision in an emergency event where a vehicle in front of it makes a full stop. In the merge scenario, the ego vehicle successfully enters the main road from a ramp with a satisfactory distance to other vehicles. As a conclusion, the risk-aware POMDP framework is able to realize a trade-off between safety and usability by keeping a reasonable distance and adapting to other vehicles behaviours. / Autonoma fordon förutspås spela en stor roll i framtiden med målen att förbättra effektivitet och säkerhet för vägtransporter. Men även om vi sett flera exempel av autonoma fordon ute på vägarna de senaste åren är frågan om hur säkerhet ska kunna garanteras ett utmanande problem. Det här examensarbetet har studerat denna fråga genom att utveckla ett ramverk för riskmedvetet beslutsfattande. Det autonoma fordonets dynamik och den oförutsägbara omgivningen modelleras med en partiellt observerbar Markov-beslutsprocess (POMDP från engelskans “Partially Observable Markov Decision Process”). Ett riskmått föreslås baserat på ett säkerhetsavstånd förkortat RSS (från engelskans “Responsibility-Sensitive Safety”) som kvantifierar det minsta avståndet till andra fordon för garanterad säkerhet. Riskmåttet integreras i POMDP-modellens belöningsfunktion för att åstadkomma riskmedvetna beteenden. Den föreslagna riskmedvetna POMDP-modellen utvärderas i två fallstudier. I ett scenario där det egna fordonet följer ett annat fordon på en enfilig väg visar vi att det egna fordonet kan undvika en kollision då det framförvarande fordonet bromsar till stillastående. I ett scenario där det egna fordonet ansluter till en huvudled från en ramp visar vi att detta görs med ett tillfredställande avstånd till andra fordon. Slutsatsen är att den riskmedvetna POMDP-modellen lyckas realisera en avvägning mellan säkerhet och användbarhet genom att hålla ett rimligt säkerhetsavstånd och anpassa sig till andra fordons beteenden.

Cette étude a porté sur l’analyse de l’énantiosélectivité de la lipase de Burkholderia cepacia (BCL) pour les acides 2-substitués, synthons chiraux d’intérêt pharmaceutique, avec pour objectif d’examiner le rôle de l’accès au site actif enfoui de BCL sur l’énantiosélectivité et de développer une procédure d’ingénierie permettant de créer des mutants d’énantiosélectivité améliorée. Pour traiter le problème, une nouvelle approche de calcul, basée sur des algorithmes de planification de mouvements issus de la robotique a été développée. Elle permet l’exploration conformationnelle des espaces multi-dimensionnels contraints et a été appliquée au calcul des trajectoires de plusieurs racémiques dans le site actif de BCL et à l’identification de résidus pouvant potentiellement gêner le déplacement du substrat le long du site actif. Les résultats obtenus in silico ont révélé une corrélation qualitative avec les valeurs d’énantiosélectivité et ont permis de proposer des cibles de mutagénèse. Sur cette base, l’ingénierie du site actif de BCL a été entreprise pour moduler sélectivement l’accès des énantiomères R et S à la triade catalytique. Un système d’expression hétérologue de BCL chez E. coli compatible avec une expression en microplaque, a été développé. Une librairie de 57 (3x19) mono-mutants sur les positions : Leu17, Val266 et Leu287 a été construite par iPCR puis criblée en utilisant une procédure à moyen débit pour identifier les variants actifs pour l’hydrolyse du pNPB. L’énantiosélectivité de ces mutants a ensuite été évaluée pour l’hydrolyse du racémique (R,S)-2 bromophényl acétate de 2-chloro-éthyle, par utilisation d’une nouvelle procédure de criblage en deep-wells. Ce crible a permis de mettre en évidence plusieurs mutants dont les plus prometteurs ont été caractérisés. Ainsi les mutants Leu17Ser et Leu17Met présentent une augmentation de l’énantiosélectivité d’un facteur 10 accompagnée d’une augmentation de leur activité d’un facteur 4 à 5. Le mutant Val266Gly présente, quant à lui, une inversion de l’énantiosélectivité pour le substrat d’intérêt. L’étude des trajectoires par les techniques de planification combinée à une représentation sous la forme de carte de voxels a été réalisée en parallèle. Pour les mutants sélectionnés, une bonne corrélation a été observée entre les résultats obtenus in silico et expérimentalement. De plus, cela a permis de proposer de nouvelles combinaisons de mutations ayant conduit à l’identification de deux double-mutants Leu17Met/Val266Met et Leu17Ser/Leu287Ile d’énantiosélectivité supérieure à 150 pour le substrat modèle, révélant ainsi l’intérêt de l’approche semi-rationnelle proposée / This work has been focused on the understanding of the Burkholderia cepacia lipase (BCL) enantioselectivity towards 2-substituted acids which are chiral building blocks of pharmaceutical interest. The main objective of this work was the investigation of the potential role of substrate accessibility toward the buried active site of BCL on enantioselectivity and the development of an engineering procedure for the design of enantioselective mutants. To study further this hypothesis, a novel computational approach, based on motion-planning algorithms, originally used in robotics, was developed. It allows the conformational exploration of constrained high-dimensional spaces and was applied to the computation of trajectories for a set of racemates within the catalytic site. This methodology also enables the identification of residues potentially hindering substrates displacement along the active site. Results obtained in silico were correlated qualitatively with experimental values of enantioselectivity. On the basis of these results, engineering of the narrow active site of BCL has been undertaken to modulate selectively the access of R and S enantiomers to the catalytic triade. An heterologous expression system of BCL in E. coli compatible with production at microplate scale was developed. A library of 57 (3x19) variants targeted at positions Leu17, Val266 and Leu287 was built by iPCR and subsequently screened using a medium-throughput procedure to identify active variants against pNPB hydrolysis. Next, the enantioselectivity of these mutants was evaluated towards a given racemate, the (R,S)-2-chloro ethyl 2-bromophenylacetate, using a novel screening procedure developed in deep wells. Such screening enabled the identification of several variants amongst which the most promising were characterized. Mutants Leu17Ser and Leu17Met showed a remarkable 10-fold increase of their enantioselectivity and a 4- and 5-fold improvement of their specific activity. Compared to the wild-type enzyme, mutant Val266Gly displayed a reversed enantioselectivity for the substrate of interest. Investigation of the trajectories using motion-planning techniques combined to a voxel map representation was carried out. For selected variants, a fair correlation was observed between in silico and experimental results. Moreover, this enabled us to suggest novel combinations of mutations that led to the identification of two double-mutants Leu17Met/Val266Met and Leu17Ser/Leu287Ile showing an enantioselectivity value higher than 150 for the racemic substrate, revealing thus the effiency of the semi-rational strategy

Cette thèse se concentre sur les robots aériens autonomes qui interagissent avec l’environnement et en particulier sur la conception de nouvelles méthodes de commande et de planification de mouvement pour tels systèmes. De nos jours, les véhicules aériens autonomes sont de plus en plus utilisés dans des nombreux domaines d’application, mais ils viennent utilisés surtout comme des simples capteurs. Au vu de ça, les défis majeurs dans le domaine de l’interaction physique aérienne, est aujourd’hui d’aller au-delà de cette application limitée, et d’exploiter entièrement les capacités des robots aériens afin d’interagir avec l’environnement. Dans le but de réaliser cet objectif, cette thèse considère l’analyse d’une classe spécifique de systèmes aériens interagissant avec l’environnement : les véhicules aériens attachés avec des câbles ou des bars. Ce travail se concentre sur l’analyse formelle et minutieuse de véhicules aériens attachés, en allant du contrôle et l’évaluation d’état à la planification du mouvement. Nous avons examiné notamment la platitude différentielle du système, trouvant deux sorties plate possibles qui révèlent des nouvelles capacités de tel système pour l’interaction physiques. En plus, poussé par l’intérêt pour l’interaction physique aérienne d’A à Z, nous avons abordés des problèmes supplémentaires liés à la conception, au contrôle et à la planification du mouvement pour des manipulateurs aériens. / This thesis focuses on the study of autonomous aerial robots interacting with the surrounding environment, and in particular on the design of new control and motion planning methods for such systems. Nowadays, autonomous aerial vehicles are extensively employed in many fields of application but mostly as autonomously moving sensors. On the other hand, in the recent field of aerial physical interaction, the goal is to go beyond sensing-only applications and fully exploit the aerial robots capabilities in order to interact with the environment. With the aim of achieving this goal, this thesis considers the analysis of a particular class of aerial robots interacting with the environment: tethered aerial vehicles. This work focuses on the thorough formal analysis of tethered aerial vehicles ranging from control and state estimation to motion planning. In particular, the differential flatness property of the system is investigated, finding two possible flat outputs that reveal new capabilities of such system for the physical interaction. The theoretical results were finally employed to solve the challenging problem of landing and takeoff on/from a sloped surface. In addition, moved by the interest on aerial physical interaction from A to Z, we addressed supplementary problems related to the design, control and motion planning for aerial manipulators.

Existem aplicações na área da robótica móvel em que, além da navegação autônoma do robô, é necessário que um usuário humano interaja no controle de navegação do robô. Neste caso, considerado como controle semi-autônomo, o usuário humano têm a possibilidade de alterar localmente a trajetória autônoma previamente planejada para o robô. Entretanto, o sistema de controle inteligente do robô, por meio de um módulo independente do usuário, continuamente evita colisões, mesmo que para isso os comandos do usuário precisem ser modificados. Esta abordagem cria um ambiente seguro para navegação que pode ser usado em cadeiras de rodas robotizadas e veículos robóticos tripulados onde a segurança do ser humano deve ser garantida. Um sistema de controle que possua estas características deve ser baseado numa arquitetura para robôs móveis adequada. Esta arquitetura deve integrar a entrada de comandos de um ser humano com a camada de controle autônomo do sistema que evita colisões com obstáculos estáticos e dinâmicos, e que conduz o robô em direção ao seu objetivo de navegação. Neste trabalho é proposta uma arquitetura de controle híbrida (deliberativa/reativa) para um robô móvel com interação humana. Esta arquitetura, desenvolvida principalmente para tarefas de navegação, permite que o robô seja operado em diferentes níveis de autonomia, possibilitando que um usuário humano compartilhe o controle do robô de forma segura enquanto o sistema de controle evita colisões. Nesta arquitetura, o plano de movimento do robô é representado por uma função de navegação. É proposto um método para combinar um comportamento deliberativo que executa o plano de movimento, com comportamentos reativos definidos no contexto de navegação, e com entradas contínuas de controle provenientes do usuário. O sistema de controle inteligente definido por meio da arquitetura foi implementado em uma cadeira de rodas robotizada. São apresentados alguns dos resultados obtidos por meio de experimentos realizados com o sistema de controle implementado operando em diferentes modos de autonomia. / There are some applications in mobile robotics that require human user interaction besides the autonomous navigation control of the robot. For these applications, in a semi-autonomous control mode, the human user can locally modify the autonomous pre-planned robot trajectory by sending continuous commands to the robot. In this case, independently from the user\'s commands, the intelligent control system must continuously avoid collisions, modifying the user\'s commands if necessary. This approach creates a safety navigation system that can be used in robotic wheelchairs and manned robotic vehicles where the human safety must be guaranteed. A control system with those characteristics should be based on a suitable mobile robot architecture. This architecture must integrate the human user\'s commands with the autonomous control layer of the system which is responsible for avoiding static and dynamic obstacles and for driving the robot to its navigation goal. In this work we propose a hybrid (deliberative/reactive) mobile robot architecture with human interaction. This architecture was developed mainly for navigation tasks and allows the robot to be operated on different levels of autonomy. The user can share the robot control with the system while the system ensures the user and robot\'s safety. In this architecture, a navigation function is used for representing the robot\'s navigation plan. We propose a method for combining the deliberative behavior responsible for executing the navigation plan, with the reactive behaviors defined to be used while navigating, and with the continuous human user\'s inputs. The intelligent control system defined by the proposed architecture was implemented in a robotic wheelchair, and we present some experimental results of the chair operating on different autonomy modes.

Cette thèse se situe dans la planification et le suivi de mouvement d’un humanoïde mobile à deux bras. Premièrement, MDH est utilisé pour la modélisation cinématique. Afin de surmonter les insuffisances de la méthode d’Euler-Lagrange qui nécessitent des calculs d’énergie et ses dérivées partielles, la méthode de Kane est utilisée. En plus, la stabilité physique est analysée et un contrôleur est conçu. Deuxièmement, un algorithme avancée MaxiMin NSGA-II est proposée pour concevoir l’orientation et la position optimales de la plate-forme mobile (PB) et la configuration optimale du manipulateur supérieur (MS) étant donnée uniquement la pose initiale et les positions et orientations souhaitées des EEs. Un algorithme à connexion directe combinant BiRRT et la gradient-descente est conçu pour réaliser la transition de la pose initiale à la pose optimale, et une méthode d'optimisation géométrique est conçue pour optimiser et cohérer le chemin. En outre, les motions en avant sont obtenues en attribuant des orientations pour MB indiquant ainsi l'intention du robot. Afin de résoudre le problème d'échec de l’algorithme hors ligne, un algorithme en ligne est proposé en estimant les motions des obstacles dynamiques. De plus, afin d'optimiser les via-poses, un algorithme basé sur les via-points des EEs et MOGA est proposé en optimisant quatre fonctions objectives. Enfin, le problème de suivi de motion est étudié étant donné les motions des EEs dans l'espace de tâche. Au lieu de contrôler la motion absolue, deux motions relatives sont introduites pour réaliser la coordination et la coopération entre MB et MS. De plus, une technique mWLN est proposée pour éviter les limites des joints. / This thesis focuses on the motion planning and tracking of a dual-arm mobile humanoid. First, MDH is used for kinematic modeling. The co-simulation via Simulink-Adams on prototype is realized to validate the effectiveness of RBFNN controller. In order to overcome the shortcomings of Euler-Lagrange’s formulations that require calculating energy and energy derivatives, Kane’s method is used. In addition, physical stability is analyzed based on Kane’s method and a controller is designed using back-stepping technique. Secondly, an improved MaxiMin NSGA-II is proposed to design the mobile base’s (MB) optimal position-orientation and the upper manipulator’s (UM) optimal configuration given only the initial pose and end-effectors’ (EEs) desired positions-orientations. A direct connect algorithm combining BiRRT and gradient-descent is designed to plan the transition from initial pose to optimal pose, and a geometric optimization method is designed to optimize and cohere the path. In addition, forward motions are obtained by assigning orientations for MB thus indicating robot’s intention. In order to solve the failure problem of offline algorithm, an online algorithm is proposed while estimating dynamic obstacles’ motions. In addition, in order to optimize via-poses, an algorithm based on EEs’ via-points and MOGA is proposed by optimizing four via-pose-based objective functions. Finally, the motion tracking problem is studied given EEs’ motions in the task space. Instead of controlling the absolute motion, two relative motions are introduced to realize the coordination and cooperation between MB and UM. In addition, an modulated WLN technique is proposed to avoid joints’ limits.

Existem aplicações na área da robótica móvel em que, além da navegação autônoma do robô, é necessário que um usuário humano interaja no controle de navegação do robô. Neste caso, considerado como controle semi-autônomo, o usuário humano têm a possibilidade de alterar localmente a trajetória autônoma previamente planejada para o robô. Entretanto, o sistema de controle inteligente do robô, por meio de um módulo independente do usuário, continuamente evita colisões, mesmo que para isso os comandos do usuário precisem ser modificados. Esta abordagem cria um ambiente seguro para navegação que pode ser usado em cadeiras de rodas robotizadas e veículos robóticos tripulados onde a segurança do ser humano deve ser garantida. Um sistema de controle que possua estas características deve ser baseado numa arquitetura para robôs móveis adequada. Esta arquitetura deve integrar a entrada de comandos de um ser humano com a camada de controle autônomo do sistema que evita colisões com obstáculos estáticos e dinâmicos, e que conduz o robô em direção ao seu objetivo de navegação. Neste trabalho é proposta uma arquitetura de controle híbrida (deliberativa/reativa) para um robô móvel com interação humana. Esta arquitetura, desenvolvida principalmente para tarefas de navegação, permite que o robô seja operado em diferentes níveis de autonomia, possibilitando que um usuário humano compartilhe o controle do robô de forma segura enquanto o sistema de controle evita colisões. Nesta arquitetura, o plano de movimento do robô é representado por uma função de navegação. É proposto um método para combinar um comportamento deliberativo que executa o plano de movimento, com comportamentos reativos definidos no contexto de navegação, e com entradas contínuas de controle provenientes do usuário. O sistema de controle inteligente definido por meio da arquitetura foi implementado em uma cadeira de rodas robotizada. São apresentados alguns dos resultados obtidos por meio de experimentos realizados com o sistema de controle implementado operando em diferentes modos de autonomia. / There are some applications in mobile robotics that require human user interaction besides the autonomous navigation control of the robot. For these applications, in a semi-autonomous control mode, the human user can locally modify the autonomous pre-planned robot trajectory by sending continuous commands to the robot. In this case, independently from the user\'s commands, the intelligent control system must continuously avoid collisions, modifying the user\'s commands if necessary. This approach creates a safety navigation system that can be used in robotic wheelchairs and manned robotic vehicles where the human safety must be guaranteed. A control system with those characteristics should be based on a suitable mobile robot architecture. This architecture must integrate the human user\'s commands with the autonomous control layer of the system which is responsible for avoiding static and dynamic obstacles and for driving the robot to its navigation goal. In this work we propose a hybrid (deliberative/reactive) mobile robot architecture with human interaction. This architecture was developed mainly for navigation tasks and allows the robot to be operated on different levels of autonomy. The user can share the robot control with the system while the system ensures the user and robot\'s safety. In this architecture, a navigation function is used for representing the robot\'s navigation plan. We propose a method for combining the deliberative behavior responsible for executing the navigation plan, with the reactive behaviors defined to be used while navigating, and with the continuous human user\'s inputs. The intelligent control system defined by the proposed architecture was implemented in a robotic wheelchair, and we present some experimental results of the chair operating on different autonomy modes.

Στην παρούσα διατριβή παρουσιάζονται παράλληλοι αλγόριθμοι και εφαρμογές σε πολυπύρηνες μονάδες επεξεργασίας γραφικών. Πιο συγκεκριμένα, εξετάζονται οι μέθοδοι σχεδίασης ενός παράλληλου αλγορίθμου για την επίλυση τόσο απλών και κοινών προβλημάτων, όπως η ταξινόμηση, όσο και υπολογιστικά απαιτητικών προβλημάτων, έτσι ώστε να εκμεταλλευτούμε πλήρως την τεράστια υπολογιστική δύναμη που προσφέρουν οι σύγχρονες μονάδες επεξεργασίας γραφικών. Πρώτο πρόβλημα που εξετάστηκε είναι η ταξινόμηση, η οποία είναι ένα από τα πιο συνηθισμένα προβλήματα στην επιστήμη των υπολογιστών. Υπάρχει σαν εσωτερικό πρόβλημα σε πολλές εφαρμογές, επομένως πετυχαίνοντας πιο γρήγορη ταξινόμηση πετυχαίνουμε πιο καλή απόδοση γενικότερα. Στο Κεφάλαιο 3 περιγράφονται όλα τα βήματα σχεδιασμού για την εκτέλεση ενός αλγορίθμου ταξινόμησης για ακεραίους, της count sort, σε μια μονάδα επεξεργασίας γραφικών. Σημαντική επίδραση στην απόδοση είχε η αποφυγή του συγχρονισμού των νημάτων στο τελευταίο βήμα του αλγορίθμου. Στη συνέχεια παρουσιάζονται εφαρμογές παράλληλων αλγορίθμων σε υπολογιστικά απαιτητικά προβλήματα. Στο Κεφάλαιο 4, εξετάζεται το πρόβλημα χρονοπρογραμματισμού εξετάσεων Πανεπιστημίων, το οποίο είναι ένα πρόβλημα συνδυαστικής βελτιστοποίησης. Για την επίλυσή του χρησιμοποιείται ένας υβριδικός εξελικτικός αλγόριθμος, ο οποίος εκτελείται εξ' ολοκλήρου στην μονάδα επεξεργασίας γραφικών. Η τεράστια υπολογιστική δύναμη της GPU και ο παράλληλος προγραμματισμός δίνουν τη δυνατότητα χρήσης μεγάλων πληθυσμών έτσι ώστε να εξερευνήσουμε καλύτερα τον χώρο λύσεων και να πάρουμε καλύτερα ποιοτικά αποτελέσματα. Στο επόμενο κεφάλαιο γίνεται επίλυση του προβλήματος σχεδιασμού κίνησης για υποθαλάσσια οχήματα με βραχίονα. Εξετάζεται το πρόβλημα τόσο του ολικού σχεδιασμού όσο και του τοπικού. Στην πρώτη περίπτωση είναι σημαντική η καλή λύση και η ακρίβεια και ο παράλληλος αλγόριθμος που χρησιμοποιείται για την αναπαράσταση του περιβάλλοντος εργασίας σε μια Bump-επιφάνεια βοηθάει προς αυτή την κατεύθυνση. Στη δεύτερη περίπτωση, το πρόβλημα είναι πρόβλημα πραγματικού χρόνου και μας ενδιαφέρει η ταχύτητα εύρεσης της επόμενης θέσης του οχήματος. Ο παράλληλος προγραμματισμός και η GPU βοηθούν σημαντικά σε αυτό. Τελευταία εφαρμογή που εξετάστηκε είναι η μελέτη ενός συστήματος ημιφθοριωμένων αλκανίων με την μοριακή προσομοίωση Monte Carlo. Η παραλληλοποίηση ενός μέρους, του πιο χρονοβόρου, του αλγορίθμου έδωσε τη δυνατότητα εξέτασης ενός πολύ μεγαλύτερου συστήματος σε αποδεκτό χρόνο. Σε γενικές γραμμές, γίνεται φανερό ότι ο παράλληλος προγραμματισμός και οι σύγχρονες πολυπύρηνες αρχιτεκτονικές, όπως οι μονάδες επεξεργασίας γραφικών, δίνουν νέες δυνατότητες στην αντιμετώπιση καθημερινών προβλημάτων, προβλημάτων πραγματικού χρόνου και προβλημάτων συνδυαστικής βελτιστοποίησης. / In this thesis, parallel algorithms and applications in manycore graphics processing units are presented. More specifically, we examine methods of designing a parallel algorithm for solving both simple and common problems such as sorting, and computationally demanding problems, so as to fully exploit the enormous computing power of modern graphics processing units (GPUs). First problem considered is sorting, which is one of the most common problems in computer science. It exists as an internal problem in many applications. Therefore, sorting faster, results in better performance in general. Chapter 3 describes all design options for the implementation of a sorting algorithm for integers, count sort, on a graphics processing unit. The elimination of thread synchronization in the last step of the algorithm had a significant effect on the performance. Chapter 4 addresses the examination timetabling problem for Universities, which is a combinatorial optimization problem. A hybrid evolutionary algorithm, which runs entirely on GPU, was used to solve the problem. The tremendous computing power of GPU and parallel programming enable the use of large populations in order to explore better the solution space and get better quality results. In the next chapter, the problem of motion planning for underwater vehicle manipulator systems is examined. In the gross motion planning problem, it is important to achieve a good solution with high accuracy. The parallel algorithm used for the representation of the working environment in a Bump-surface is a step towards this direction. In the local motion planning problem, which is a real-time problem, the time needed to find the next configuration of the vehicle is crucial. Parallel programming and the GPU greatly assist in this online problem. Last application considered is the atomistic Monte Carlo simulation of semifluorinated alkanes. The parallelization of part of the algorithm, the most time-consuming, enabled the study of a much larger system in an acceptable execution time. In general, it becomes obvious that parallel programming and new novel manycore architectures, such as graphics processing units, give new capabilities for solving everyday problems, real time and combinatorial optimization problems.