A aplicação de técnicas baseadas em amostragem em algoritmos que envolvem o planejamento de trajetórias de robôs tem se tornado cada vez mais difundida. Deste grupo, um dos algoritmos mais utilizados é chamado Rapidly-exploring Random Tree (RRT), que se baseia na amostragem incremental para calcular de forma eficiente os planos de trajetória do robô evitando colisões com obstáculos. Vários esforços tem sido realizados a fim de reduzir o custo computacional do algoritmo RRT, visando aplicações que necessitem de respostas mais rápidas do algoritmo, como, por exemplo, em ambientes dinâmicos. Um dos dilemas relacionados ao RRT está na etapa de geração de primitivas de movimento. Se várias primitivas são geradas, permitindo o robô executar vários movimentos básicos diferentes, um grande custo computacional é gasto. Por outro lado, quando poucas primitivas são geradas e, consequentemente, poucos movimentos básicos são permitidos, o robô pode não ser capaz de encontrar uma solução para o problema, mesmo que esta exista. Motivados por este problema, um método de geração de primitivas de movimento foi proposto. Tal método é comparado com os métodos tradicional e aleatório de geração de primitivas, considerando não apenas o custo computacional de cada um, mas também a qualidade da solução obtida. O método proposto é aplicado ao algoritmo RRT, que depois é aplicado em um caso de estudo em um ambiente dinâmico. No estudo de caso, o algoritmo RRT otimizado é avaliado em termos de seus custos computacionais durante planejamentos e replanejamento de trajetória. As simulações são realizadas em dois simuladores: um desenvolvido em linguagem Python e outro em Matlab. / The application of sample-based techniques in path-planning algorithms has become year-by-year more widespread. In this group, one of the most widely used algorithms is the Rapidly-exploring Random Tree (RRT), which is based on an incremental sampling of configurations to efficiently compute the robot\'s path while avoiding obstacles. Many efforts have been made to reduce RRT computational costs, targeting, in particular, applications in which quick responses are required, e.g., in dynamic environments. One of the dilemmas posed by the RRT arises from its motion primitives generation. If many primitives are generated to enable the robot to perform a broad range of basic movements, a signicant computational cost is required. On the other hand, when only a few primitives are generated, thus, enabling a limited number of basic movements, the robot may be unable to find a solution to the problem, even if one exists. To address this quandary, an optimized method for primitive generation is proposed. This method is compared with the traditional and random primitive generation methods, considering not only computational cost, but also the quality of local and global solutions that may be attained. The optimized method is applied to the RRT algorithm, which is then used in a case study in dynamic environments. In the study, the modied RRT is evaluated in terms of the computational costs of its planning and replanning. The simulations were developed to access the effectiveness and efficiency of the proposed algorithm.

Cette thèse s’inscrit dans le développement et la conception de fonctions d’aide à la conduite pour les véhicules autonomes de niveau 3 et plus en milieu urbain ou péri urbain. Du fait d’un environnement plus complexe et de trajectoires possibles plus nombreuses et sinueuses, les algorithmes des véhicules autonomes développés pour l’autoroute ne sont pas adaptés pour le milieu urbain. L’objectif de la thèse est de mettre à disposition des méthodes et des réalisations pour permettre au véhicule autonome d’évoluer en milieu urbain. Cette thèse se focalise sur la proposition de solutions pour améliorer le guidage latéral des véhicules autonomes en milieu urbain à travers l’étude de la planification de trajectoire en situation complexe, l’analyse du comportement des usagers et l’amélioration du suivi de ces trajectoires complexes à faibles vitesses. Les solutions proposées doivent fonctionner en temps réel dans les calculateurs des prototypes pour pouvoir ensuite être appliquées sur route ouverte. L’apport de cette thèse est donc autant théorique que pratique.Après une synthèse des fonctions d’aide à la conduite présentes à bord des véhicules et une présentation des moyens d’essais mis à disposition pour la validation des algorithmes proposés, une analyse complète de la dynamique latérale est effectuée dans les domaines temporel et fréquentiel. Cette analyse permet alors la mise en place d’observateurs de la dynamique latérale pour estimer des signaux nécessaires aux fonctions de guidage latéral et dont les grandeurs ne sont pas toujours mesurables, fortement dégradées ou bruitées. La régulation latérale du véhicule autonome se base sur les conclusions apportées par l’analyse de cette dynamique pour proposer une solution de type multirégulateur capable de générer une consigne en angle volant pour suivre une trajectoire latérale quelle que soit la vitesse. La solution est validée tant en simulation que sur prototype pour plusieurs vitesses sur des trajectoires de changement de voie. La suite de la thèse s’intéresse à la génération d’une trajectoire en milieu urbain tenant compte non seulement de l’infrastructure complexe (intersection/rond-point) mais également des comportements des véhicules autour. C’est pourquoi, une analyse des véhicules de l’environnement est menée afin de déterminer leur comportement et leur trajectoire. Cette analyse est essentielle pour la méthode de génération de trajectoire développée dans cette thèse. Cette méthode, basée sur l’algorithme A* et enrichie pour respecter les contraintes géométriques et dynamiques du véhicule, se focalise d’abord dans un environnement statique complexe de type parking ou rond-point. Des points de passage sont intégrés à la méthode afin de générer des trajectoires conformes au code de la route et d’améliorer le temps de calcul. La méthode est ensuite adaptée pour un environnement dynamique où le véhicule est alors capable, sur une route à double sens de circulation, de dépasser un véhicule avec un véhicule arrivant en sens inverse. / This thesis is about the design of driving assistance systems for level 3 urban automated driving. Because of a more complex of the environment and a larger set of possible trajectories, the algorithms of highway automated driving are not adapted to urban environment. This thesis objective is to provide methods and algorithms to enable the vehicle to perform automated driving in urban scenarios, focusing on the vehicle lateral guidance and on the path planning. The proposed solutions operate in real-time on board of the automated vehicle prototypes. The contribution of this thesis is as theoretical as practical.After a synthesis of the driving assistance systems available on current cars and a presentation of the prototypes used for the validation of the algorithms developed in the thesis, a complete analysis of the vehicle lateral dynamics is carried out in time and frequency domains. This analysis enables the design of observers of the lateral dynamics in order not only to estimate signals required for the lateral guidance functions but also to increase reliability of available measurements. Based on the conclusions from the analysis of lateral dynamic, a multi-controller solution has been proposed. It enables the computation of a steering wheel input to follow a trajectory at any longitudinal speed. The solution is validated in simulation and on real road traffic for lane change scenarios. Another contribution consist in an analysis on the other vehicles of the environment is conducted in order to identify their behaviors and which maneuver there are performing. This analysis is essential for the path planning function developed in the thesis. This method, based on the A* algorithm and extended to respect geometric and dynamic constraints, firstly focuses on static environment such as a parking lot. Waypoints are added to the method in order to compute trajectories compatible with traffic regulation and improve the computation time. The method is then adapted for dynamic environment where, in the end, the vehicle is able to perform overtaking manoeuvers in a complex environment.

This thesis addresses the path planning problem for Autonomous Underwater Vehicles (AUVs) using homotopy classes to provide topological information on how paths avoid obstacles. Looking for a path within a homotopy class constrains the search into a specific area of the search space, speeding up the computation of the path. Given a workspace with obstacles, the method starts by generating the homotopy classes. Those which probably contain lower cost solutions are determined by means of a lower bound criterion before computing a path. Finally, a path planner uses the topological information of homotopy classes to generate a few good solutions very quickly. Three path planners from different approaches have been proposed to generate paths for the homotopy classes obtained. The path planning is performed on Occupancy Grid Maps (OGMs) improved with probabilistic scan matching techniques. The results obtained with synthetic s scenarios and with real datasets show the feasibility of our method. / Aquesta tesi aborda el problema de la planificació de camins per a Vehicles Submarins Autònoms (AUVs) mitjançant la utilització de classes d'homotopia per a proporcionar informació topològica de com els camins eviten els obstacles. Calcular un camí dins d'una classe d'homotopia permet limitar l'espai de cerca accelerant-ne el càlcul de la solució. Donat un workspace amb obstacles, el mètode primer genera les classes homotòpiques. Aquelles classes que probablement contenen les solucions de menor cost s'identifiquen per mitjà d'una heurística sense haver-ne de calcular el camí al workspace. Finalment, un planificador de camins utilitza la informació topològica de les classes d'homotopia per generar solucions segons les classes seleccionades molt ràpidament. El mètode de planificació de camins s’aplica sobre Mapes d’Occupació de Graella (OGMs) millorats amb tècniques de scan matching probabilístic. Els tests i resultats obtinguts tan en escenaris sintètics com en datasets reals mostren la viabilitat del nostre mètode.

This dissertation presents a basic information-driven sensor management problem, referred to as treasure hunt, that is relevant to mobile-sensor applications such as mine hunting, monitoring, and surveillance. The objective is to classify/infer one or multiple fixed targets or treasures located in an obstacle-populated workspace by planning the path and a sequence of measurements of a robotic sensor installed on a mobile platform associated with the treasures distributed in the sensor workspace. The workspace is represented by a connectivity graph, where each node represents a possible sensor deployment, and the arcs represent possible sensor movements. A methodology is developed for planning the sensing strategy of a robotic sensor deployed. The sensing strategy includes the robotic sensor's path, because it determines which targets are measurable given a bounded field of view. Existing path planning techniques are not directly applicable to robots whose primary objective is to gather sensor measurements. Thus, in this dissertation, a novel approximate cell-decomposition approach is developed in which obstacles, targets, the sensor's platform and field of view are represented as closed and bounded subsets of an Euclidean workspace. The approach constructs a connectivity graph with observation cells that is pruned and transformed into a decision tree, from which an optimal sensing strategy can be computed. It is shown that an additive incremental-entropy function can be used to efficiently compute the expected information value of the measurement sequence over time. The methodology is applied to a robotic landmine classification problem and the board game of CLUE$^{\circledR}$. In the landmine detection application, the optimal strategy of a robotic ground-penetrating radar is computed based on prior remote measurements and environmental information. Extensive numerical experiments show that this methodology outperforms shortest-path, complete-coverage, random, and grid search strategies, and is applicable to non-overpass capable platforms that must avoid targets as well as obstacles. The board game of CLUE$^{\circledR}$ is shown to be an excellent benchmark example of treasure hunt problem. The test results show that a player implementing the strategies developed in this dissertation outperforms players implementing Bayesian networks only, Q-learning, or constraint satisfaction, as well as human players. / Dissertation

The recent technological advances in the field of autonomous vehicles have resulted in a growing impetus for researchers to improve the current framework of mission planning and execution within both the military and civilian contexts. Many recent efforts towards this direction emphasize the importance of replacing the so-called monolithic paradigm, where a mission is planned, monitored, and controlled by a unique global decision maker, with a network centric paradigm, where the same mission related tasks are performed by networks of interacting decision makers (autonomous vehicles). The interest in applications involving teams of autonomous vehicles is expected to significantly grow in the near future as new paradigms for their use are constantly being proposed for a diverse spectrum of real world applications. One promising approach to extend available techniques for addressing problems involving a single autonomous vehicle to those involving teams of autonomous vehicles is to use the concept of Voronoi diagram as a means for reducing the complexity of the multi-vehicle problem. In particular, the Voronoi diagram provides a spatial partition of the environment the team of vehicles operate in, where each element of this partition is associated with a unique vehicle from the team. The partition induces, in turn, a graph abstraction of the operating space that is in a one-to-one correspondence with the network abstraction of the team of autonomous vehicles; a fact that can provide both conceptual and analytical advantages during mission planning and execution. In this dissertation, we propose the use of a new class of Voronoi-like partitioning schemes with respect to state-dependent proximity (pseudo-) metrics rather than the Euclidean distance or other generalized distance functions, which are typically used in the literature. An important nuance here is that, in contrast to the Euclidean distance, state-dependent metrics can succinctly capture system theoretic features of each vehicle from the team (e.g., vehicle kinematics), as well as the environment-vehicle interactions, which are induced, for example, by local winds/currents. We subsequently illustrate how the proposed concept of state-dependent Voronoi-like partition can induce local control schemes for problems involving networks of spatially distributed autonomous vehicles by examining different application scenarios.

The process of taking a solid model and producing a machined part requires the time and skillset of a range of professionals, and several hours of part review, process planning, and production. Much of this time is spent creating a methodical step-by-step process plan for creating the part from stock. The work presented here is part of a software package that performs automated process planning for a solid model. This software is capable of not only greatly decreasing the planning time for part production, but also give valuable feedback about the part to the designer, as a time and cost associated with manufacturing the part. In order to generate these parameters, we must simulate all aspects of creating the part. Presented here are models that replicate these aspects. For milling, an automatic tool selection method is presented. Given this tooling, another model uses specific information about the part to generate a tool path length. A machining simulation model calculates relevant parameters, and estimates a time for machining given the tool and tool path determined previously. This time value, along with the machining parameters, is used to estimate the wear to the tooling used in the process. Using the machining time and the tool wear a cost for the process can be determined. Other models capture the time of non-machining production times, and all times are combined with billing rates of machines and operators to present an overall cost for machining a feature on a part. If several such features are required to create the part, these models are applied to each feature, until a complete process plan has been created. Further post processing of the process plan is required. Using a list of available machines, this work considers creating the part on all machines, or any combination of these machines. Candidates for creating the part on specific machines are generated and filtered based on time and cost to keep only the best candidates. These candidates can be returned to the user, who can evaluate, and choose, one candidate. Results are presented for several example parts. / text

The process of quantifying the robustness of a given nonlinear system is not necessarily trivial. If the dynamics of the system in question are not sufficiently involved, then a tight estimate of a bound on system performance may be obtained. As the dynamics of the system concerned become more and more involved, it is often found that using the results existing in the literature provides a very conservative bound on system performance. Therefore, the motivation for this work is to develop a general method to obtain a less conservative estimate of a bound on system performance, compared to the results already available in literature. The scope of this work is limited to two dimensions at present. Note that working in a two dimensional space does not necessarily make the objective easily achievable. This is because quantifying the robustness of a general nonlinear system perturbed by disturbances can very easily become intractable, even on a space with dimension as low as two. The primary contribution of this work is a computational algorithm, the points generated by which are conjectured to lie on the boundary of the smallest robust forward invariant set for a given nonlinear system. A well known path-planning algorithm, available in existing literature, is leveraged to make the algorithm developed computationally efficient. If the system dynamics are not accurately known, then the above computed approximation of an invariant set may cease to be invariant over the given finite time interval for which the computed set is expected to be invariant. Therefore, the secondary contribution of this work is an algorithm monitoring a computed approximation of an invariant set. It is shown that for a certain type of systems, this secondary monitoring algorithm can be used to detect that a computed approximation of an invariant set is about to cease to be invariant, even if the primary algorithm computed the set based on an unsophisticated dynamical model of a system under consideration. The work related to computing approximations of invariant sets is tested mainly with the curve tracking problem in two dimensions. The algorithm monitoring whether a computed approximation of an invariant set is about to cease to be invariant is inspired by work related to detecting Lithium-ion (Li-ion) battery terminal voltage collapse detection.

Η παρούσα διπλωματική ασχολείται με την πλοήγηση κινούμενου ρομπότ. Δεδομένου ενός χώρου με εμπόδια και στόχο, ασχολείται με την δημιουργία ενός αλγορίθμου για την οδήγηση του ρομπότ διαμέσου του χώρου στο στόχο, αποφεύγοντας τα εμπόδια κατά την κίνηση. Επικεντρώνεται σε δίτροχα ρομπότ και αναλύει βήμα βήμα την διαδικασία εύρεση μονοπατιού, δημιουργία τροχιάς και έλεγχο του ρομπότ. / The present thesis deals with the navigation of moving robots. Granted an area with obstacles and target, it deals with the creation of an algorithm for guiding the robot through space at target, avoiding obstacles during movement. It focuses on two-wheeled robots and analyzes step by step the process of finding a path, creating the trajectory and controlling the robot.

Como tópico de fundamental importância na robótica, o planejamento de rotas tem encontrado excelentes resultados nos últimos anos através da utilização de algoritmos baseados no conceito de árvore de exploração rápida, RRT. No entanto, a aplicação desses métodos em sistemas robóticos espaciais revela um cenário ainda a ser explorado. O comportamento não-holonômico e a presença de singularidades dinâmicas são alguns fatores que dificultam a consideração de obstáculos no planejamento de rotas desses sistemas. Além disso, os trabalhos relacionados ao planejamento de movimento para manipuladores espaciais mostram-se concentrados na estratégia ponto-a-ponto, com interesse especial nos aspectos particulares da dinâmica desses sistemas. De modo geral, para manipuladores espaciais, o planejamento de trajetória envolvendo o desvio de obstáculos depende de uma rota previamente computada. Contudo, essa tarefa carece de formulações ou técnicas solidificadas, sobretudo para manipuladores espaciais de base livre flutuante. Com esta motivação, o trabalho proposto nesta dissertação de mestrado cria um planejador de rotas com suporte a desvio de obstáculos para um manipulador espacial planar de base livre flutuante. O modelo dinâmico utilizado é baseado no conceito de manipulador dinamicamente equivalente e incorporado a um algoritmo baseado no conceito de RRT. / As major challenge in the field of robotics, path planning has experienced successful results in recent years by means of the RRT algorithm. However, the application of such algorithms in space manipulators reveals a scenario yet to be explored. The non-holonomic behavior, added to the presence of dynamic singularities are only a few factors that make collision-avoidance path planning of these systems such a hard task. Besides, works in the field of motion planning of space manipulators often concentrate in the strategy pointto- point, with particular interest in the complex dynamics of such systems. As a rule of thumb, collision-avoidance for space manipulators depends on a previous computed path. However, this task still lacks robust formulations, specially in the case of free-floating manipulators. With this motivation, the proposed work creates a collision-avoiding path planning for a free-floating planar manipulator. The dynamic model is based on the Dynamically Equivalent Manipulator and the concept of Rapidly-Exploring Random Trees serves as a frame for the developed algorithm.

Recently, autonomous vehicles have received worldwide attentions from academic research, automotive industry and the general public. In order to achieve a higher level of automation, one of the most fundamental requirements of autonomous vehicles is the capability to respond to internal and external changes in a safe, timely and appropriate manner. Situational awareness and decision making are two crucial enabling technologies for safe operation of autonomous vehicles. This thesis presents a solution for improving the automation level of autonomous vehicles in both situational awareness and decision making aspects by utilising additional domain knowledge such as constraints and influence on a moving object caused by environment and interaction between different moving objects. This includes two specific sub-systems, model based target tracking in environmental perception module and motion planning in path planning module. In the first part, a rigorous Bayesian framework is developed for pooling road constraint information and sensor measurement data of a ground vehicle to provide better situational awareness. Consequently, a new multiple targets tracking (MTT) strategy is proposed for solving target tracking problems with nonlinear dynamic systems and additional state constraints. Besides road constraint information, a vehicle movement is generally affected by its surrounding environment known as interaction information. A novel dynamic modelling approach is then proposed by considering the interaction information as virtual force which is constructed by involving the target state, desired dynamics and interaction information. The proposed modelling approach is then accommodated in the proposed MTT strategy for incorporating different types of domain knowledge in a comprehensive manner. In the second part, a new path planning strategy for autonomous vehicles operating in partially known dynamic environment is suggested. The proposed MTT technique is utilized to provide accurate on-board tracking information with associated level of uncertainty. Based on the tracking information, a path planning strategy is developed to generate collision free paths by not only predicting the future states of the moving objects but also taking into account the propagation of the associated estimation uncertainty within a given horizon. To cope with a dynamic and uncertain road environment, the strategy is implemented in a receding horizon fashion.