O reconhecimento da posição e orientação de objetos em uma imagem é importante para diversos segmentos da engenharia, como robótica, automação industrial e processos de fabricação, permitindo às linhas de produção que utilizam sistemas de visão, melhorias na qualidade e redução do tempo de produção. O presente trabalho consiste na elaboração de um sistema de visão computacional para um robô cilíndrico de cinco graus de liberdade acionado pneumaticamente. Como resultado da aplicação do método desenvolvido, obtêm-se a posição e orientação de peças a fim de que as mesmas possam ser capturadas corretamente pelo robô. Para a obtenção da posição e orientação das peças, utilizou-se o método de cálculo dos momentos para extração de características de uma imagem, além da relação entre suas coordenadas em pixels com o sistema de coordenadas do robô. O desenvolvimento do presente trabalho visou também a integrar a esse sistema de visão computacional, um algoritmo de planejamento de trajetórias do robô, o qual, após receber os valores das coordenadas necessárias, gera a trajetória a ser seguida pelo robô, de forma que este possa pegar a peça em uma determinada posição e deslocá-la até outra posição pré-determinada. Também faz parte do escopo deste trabalho, a integração do sistema de visão, incluindo o planejamento de trajetórias, a um algoritmo de controle dos atuadores com compensação de atrito e a realização de testes experimentais com manipulação de peças. Para a demonstração da aplicação do método através de testes experimentais, foi montada uma estrutura para suportar as câmeras e as peças a serem manipuladas, levando em conta o espaço de trabalho do robô. Os resultados obtidos mostram que o algoritmo proposto de visão computacional determina a posição e orientação das peças permitindo ao robô a captação e manipulação das mesmas. / The recognition of the position and orientation of objects in an image is important for several technological areas in engineering, such as robotics, industrial automation and manufacturing processes, allowing production lines using vision systems, improvements in quality and reduction in production time. The present work consists of the development of a computer vision system for a pneumatically actuated cylindrical robot with five degrees of freedom. The application of the proposed method furnishes the position and orientation of pieces in a way that the robot could properly capture them. Position and orientation of the pieces are determined by means of a technique based on the method of calculating the moments for an image feature extraction and the relationship between their pixels coordinates with the robot coordinate system. The scope of the present work also comprises the integration of the computer vision system with a (previously developed) robot trajectory planning algorithm that use key-point coordinates (transmitted by the vision system) to generate the trajectory that must be followed by the robot, so that, departing from a given position, it moves suitably to another predetermined position. It is also object of this work, the integration of both vision system and trajectory planning algorithm with a (also previously developed) nonlinear control algorithm with friction compensation. Aiming at to demonstrate experimentally the application of the method, a special apparatus was mounted to support cameras and the pieces to be manipulated, taking into account the robot workspace. To validate the proposed algorithm, a case study was performed, with the results showing that the proposed computer vision algorithm determines the position and orientation of the pieces allowing the robot to capture and manipulation thereof.

presente trabalho consolida um estudo para o planejamento de trajetória livre de colisão para um robô pneumático com 5 graus de liberdade aplicando três algoritmos metaheurísticos: algoritmos metaheurísticos por vagalumes, algoritmos metaheurísticos por enxames de partículas e algoritmos genéticos. No que se refere à aplicação de algoritmos metaheurísticos ao estudo de planejamento de trajetória de robôs manipuladores na presença de obstáculos, existem diferentes tipos de técnicas para evitar colisões que consideram os efeitos cinemáticos e dinâmicos na obtenção de trajetórias com o menor tempo, torque, etc. Neste estudo, são propostas contribuições à aplicação dessas técnicas especificamente a robôs manipuladores pneumáticos, sobretudo, no que diz respeito às características específicas dos servoposicionadores pneumáticos, como, por exemplo, a modelagem do atrito desses sistemas, o cálculo da massa equivalente, etc. A metodologia utilizada é definida em duas etapas. A primeira delas consiste na obtenção de pontos intermediários, adquiridos considerando a menor distância entre os mesmos e o ponto final, gerados considerando a presença de obstáculos (cilindros, cubos e esferas) Esses obstáculos são mapeados em regiões de colisão, que constituem restrições para o problema de otimização. A segunda etapa baseia-se no estudo do planejamento de trajetórias: aplicam-se b-splines de 5º e 7º grau na interpolação dos pontos intermediários, com vistas à obtenção de trajetórias que considerem, de um lado, a menor força dos atuadores associada à dinâmica do manipulador em estudo e, de outro, restrições cinemáticas e dinâmicas, determinadas por meio das características operacionais dos servoposicionadores pneumáticos. Os resultados mostram que a metodologia proposta é adequada para tarefas de manipulação de peças na presença de obstáculos, uma vez que os pontos intermediários situam-se fora da região de colisão nos três casos aqui apresentados. Além disso, quanto à segunda etapa, observou-se que as trajetórias de 5º e 7º grau apresentaram resultados similares, de maneira que os erros obtidos poderiam ser melhorados analisando aspectos associados ao controlador do robô em estudo. / The thesis presents a study for collision-free trajectory planning for a pneumatic robot with 5 degrees of freedom applying three metaheuristic algorithms: firefly metaheuristic algorithm, particle swarm optimization and genetic algorithms. As regards the application of metaheuristic algorithms to the study of the trajectory planning of manipulating robots in the presence of obstacles, there are different types of techniques to avoid collisions that consider the kinematic and dynamic effects, obtaining trajectories with the optimal time, torque, etc. In this study, contributions are made to the application of these techniques specifically to pneumatic manipulator robots, particularly with regard to the specific characteristics of pneumatic servo-actuators, such as friction modeling of these systems, calculation of equivalent mass, etc. The methodology used is defined in two steps. The first one consists of obtaining intermediate points, acquired considering the smallest distance between the intermediate points and the final point, generated considering the presence of obstacles (cylinders, cubes and spheres) These obstacles are mapped in collision regions, which are constraints to the optimization problem. The second step is based on the study of the trajectory planning: 5th and 7th degree b-splines are applied in the interpolation of the intermediate points, in order to obtain trajectories that consider the smallest actuator force associated to the dynamics of the manipulator and the kinematic and dynamic constraints, determined by the operational characteristics of pneumatic servo-positioners. The results show that the proposed methodology is suitable for tasks of manipulating parts in the presence of obstacles because the intermediate points are outside the collision region in the three cases presented here. In addition, it was observed that the trajectories of 5th and 7th degree presented similar results, so that the errors obtained could be improved by analyzing aspects associated to the controller of the robot.

presente trabalho consolida um estudo para o planejamento de trajetória livre de colisão para um robô pneumático com 5 graus de liberdade aplicando três algoritmos metaheurísticos: algoritmos metaheurísticos por vagalumes, algoritmos metaheurísticos por enxames de partículas e algoritmos genéticos. No que se refere à aplicação de algoritmos metaheurísticos ao estudo de planejamento de trajetória de robôs manipuladores na presença de obstáculos, existem diferentes tipos de técnicas para evitar colisões que consideram os efeitos cinemáticos e dinâmicos na obtenção de trajetórias com o menor tempo, torque, etc. Neste estudo, são propostas contribuições à aplicação dessas técnicas especificamente a robôs manipuladores pneumáticos, sobretudo, no que diz respeito às características específicas dos servoposicionadores pneumáticos, como, por exemplo, a modelagem do atrito desses sistemas, o cálculo da massa equivalente, etc. A metodologia utilizada é definida em duas etapas. A primeira delas consiste na obtenção de pontos intermediários, adquiridos considerando a menor distância entre os mesmos e o ponto final, gerados considerando a presença de obstáculos (cilindros, cubos e esferas) Esses obstáculos são mapeados em regiões de colisão, que constituem restrições para o problema de otimização. A segunda etapa baseia-se no estudo do planejamento de trajetórias: aplicam-se b-splines de 5º e 7º grau na interpolação dos pontos intermediários, com vistas à obtenção de trajetórias que considerem, de um lado, a menor força dos atuadores associada à dinâmica do manipulador em estudo e, de outro, restrições cinemáticas e dinâmicas, determinadas por meio das características operacionais dos servoposicionadores pneumáticos. Os resultados mostram que a metodologia proposta é adequada para tarefas de manipulação de peças na presença de obstáculos, uma vez que os pontos intermediários situam-se fora da região de colisão nos três casos aqui apresentados. Além disso, quanto à segunda etapa, observou-se que as trajetórias de 5º e 7º grau apresentaram resultados similares, de maneira que os erros obtidos poderiam ser melhorados analisando aspectos associados ao controlador do robô em estudo. / The thesis presents a study for collision-free trajectory planning for a pneumatic robot with 5 degrees of freedom applying three metaheuristic algorithms: firefly metaheuristic algorithm, particle swarm optimization and genetic algorithms. As regards the application of metaheuristic algorithms to the study of the trajectory planning of manipulating robots in the presence of obstacles, there are different types of techniques to avoid collisions that consider the kinematic and dynamic effects, obtaining trajectories with the optimal time, torque, etc. In this study, contributions are made to the application of these techniques specifically to pneumatic manipulator robots, particularly with regard to the specific characteristics of pneumatic servo-actuators, such as friction modeling of these systems, calculation of equivalent mass, etc. The methodology used is defined in two steps. The first one consists of obtaining intermediate points, acquired considering the smallest distance between the intermediate points and the final point, generated considering the presence of obstacles (cylinders, cubes and spheres) These obstacles are mapped in collision regions, which are constraints to the optimization problem. The second step is based on the study of the trajectory planning: 5th and 7th degree b-splines are applied in the interpolation of the intermediate points, in order to obtain trajectories that consider the smallest actuator force associated to the dynamics of the manipulator and the kinematic and dynamic constraints, determined by the operational characteristics of pneumatic servo-positioners. The results show that the proposed methodology is suitable for tasks of manipulating parts in the presence of obstacles because the intermediate points are outside the collision region in the three cases presented here. In addition, it was observed that the trajectories of 5th and 7th degree presented similar results, so that the errors obtained could be improved by analyzing aspects associated to the controller of the robot.

O reconhecimento da posição e orientação de objetos em uma imagem é importante para diversos segmentos da engenharia, como robótica, automação industrial e processos de fabricação, permitindo às linhas de produção que utilizam sistemas de visão, melhorias na qualidade e redução do tempo de produção. O presente trabalho consiste na elaboração de um sistema de visão computacional para um robô cilíndrico de cinco graus de liberdade acionado pneumaticamente. Como resultado da aplicação do método desenvolvido, obtêm-se a posição e orientação de peças a fim de que as mesmas possam ser capturadas corretamente pelo robô. Para a obtenção da posição e orientação das peças, utilizou-se o método de cálculo dos momentos para extração de características de uma imagem, além da relação entre suas coordenadas em pixels com o sistema de coordenadas do robô. O desenvolvimento do presente trabalho visou também a integrar a esse sistema de visão computacional, um algoritmo de planejamento de trajetórias do robô, o qual, após receber os valores das coordenadas necessárias, gera a trajetória a ser seguida pelo robô, de forma que este possa pegar a peça em uma determinada posição e deslocá-la até outra posição pré-determinada. Também faz parte do escopo deste trabalho, a integração do sistema de visão, incluindo o planejamento de trajetórias, a um algoritmo de controle dos atuadores com compensação de atrito e a realização de testes experimentais com manipulação de peças. Para a demonstração da aplicação do método através de testes experimentais, foi montada uma estrutura para suportar as câmeras e as peças a serem manipuladas, levando em conta o espaço de trabalho do robô. Os resultados obtidos mostram que o algoritmo proposto de visão computacional determina a posição e orientação das peças permitindo ao robô a captação e manipulação das mesmas. / The recognition of the position and orientation of objects in an image is important for several technological areas in engineering, such as robotics, industrial automation and manufacturing processes, allowing production lines using vision systems, improvements in quality and reduction in production time. The present work consists of the development of a computer vision system for a pneumatically actuated cylindrical robot with five degrees of freedom. The application of the proposed method furnishes the position and orientation of pieces in a way that the robot could properly capture them. Position and orientation of the pieces are determined by means of a technique based on the method of calculating the moments for an image feature extraction and the relationship between their pixels coordinates with the robot coordinate system. The scope of the present work also comprises the integration of the computer vision system with a (previously developed) robot trajectory planning algorithm that use key-point coordinates (transmitted by the vision system) to generate the trajectory that must be followed by the robot, so that, departing from a given position, it moves suitably to another predetermined position. It is also object of this work, the integration of both vision system and trajectory planning algorithm with a (also previously developed) nonlinear control algorithm with friction compensation. Aiming at to demonstrate experimentally the application of the method, a special apparatus was mounted to support cameras and the pieces to be manipulated, taking into account the robot workspace. To validate the proposed algorithm, a case study was performed, with the results showing that the proposed computer vision algorithm determines the position and orientation of the pieces allowing the robot to capture and manipulation thereof.

Este trabalho trata do planejamento de trajetórias que minimizam as perdas elétricas no KA\'I yxo, um robô escalador de árvores que tem por finalidade realizar monitoramento ambiental em florestas através da coleta de diferentes tipos de dados. Como essa aplicação requer que o robô permaneça em ambientes remotos, o estudo de técnicas que reduzam as perdas de energia a fim de que se aumente o tempo em operação do robô se mostra relevante, sendo a minimização das perdas elétricas uma contribuição importante nesse sentido. Estruturalmente, o KA\'I yxo consiste em um robô bípede com duas garras e quatro ligamentos interconectados por três juntas rotacionais. Além disso, seu mecanismo de andadura foi biologicamente inspirado na forma de locomoção observada em lagartas mede-palmos, o que permitiu tratar o robô como um manipulador industrial, cuja base é o ligamento associado à garra engastada e cujo efetuador é o ligamento associado à garra livre. Com isso, quando conveniente, o robô foi tratado em dois casos, conforme a garra que se encontra engastada. Inicialmente, realizou-se a modelagem matemática do robô, obtendo-se as equações cinemáticas direta e inversa, e dinâmicas, bem como o modelo das juntas segundo a abordagem do controle independente por junta. Posteriormente, formulou-se um problema de controle ótimo, solucionado através de um método numérico que o transformou em um problema de programação quadrática, que por sua vez foi resolvido iterativamente. Por fim, as trajetórias ótimas planejadas foram implementadas no robô real e, como forma de validação, as novas perdas elétricas foram comparadas com as das trajetórias anteriormente executadas pelo robô, determinando-se a correspondente economia de energia. / This work deals with the minimum-energy trajectory planning, related to the electrical losses, in KA\'I yxo, a tree-climbing robot that aims to perform environmental monitoring in forests through the collection of different types of data. As this application requires that the robot remains in remote environments, the study of techniques that reduce energy losses in order to increase the operation time of the robot is shown to be relevant, and the minimization of the electrical losses is an important contribution in this sense. Structurally, KA\'I yxo consists of a biped robot with two claws and four links interconnected by three revolute joints. In addition, its gait mechanism was biologically inspired in the form of locomotion observed in caterpillars, allowing to treat the robot as an industrial manipulator, which base is the link associated with the fixed claw and which end-effector is the link associated with the free claw. In consequence, when convenient, the robot was treated in two cases, according to the claw that is fixed. Initially, the mathematical model of the robot was developed, being obtained the forward and inverse kinematic and dynamic equations, as well as the model of the joints according to the independent joint control approach. Subsequently, an optimal control problem was formulated, which was solved through a numerical method that turned it into a quadratic programming problem, which in turn was solved iteratively. Finally, the planned optimal trajectories were implemented in the real robot and, as a form of validation, the new electrical losses were compared with those of the trajectories previously executed by the robot, being determined the corresponding energy saving.

O reconhecimento da posição e orientação de objetos em uma imagem é importante para diversos segmentos da engenharia, como robótica, automação industrial e processos de fabricação, permitindo às linhas de produção que utilizam sistemas de visão, melhorias na qualidade e redução do tempo de produção. O presente trabalho consiste na elaboração de um sistema de visão computacional para um robô cilíndrico de cinco graus de liberdade acionado pneumaticamente. Como resultado da aplicação do método desenvolvido, obtêm-se a posição e orientação de peças a fim de que as mesmas possam ser capturadas corretamente pelo robô. Para a obtenção da posição e orientação das peças, utilizou-se o método de cálculo dos momentos para extração de características de uma imagem, além da relação entre suas coordenadas em pixels com o sistema de coordenadas do robô. O desenvolvimento do presente trabalho visou também a integrar a esse sistema de visão computacional, um algoritmo de planejamento de trajetórias do robô, o qual, após receber os valores das coordenadas necessárias, gera a trajetória a ser seguida pelo robô, de forma que este possa pegar a peça em uma determinada posição e deslocá-la até outra posição pré-determinada. Também faz parte do escopo deste trabalho, a integração do sistema de visão, incluindo o planejamento de trajetórias, a um algoritmo de controle dos atuadores com compensação de atrito e a realização de testes experimentais com manipulação de peças. Para a demonstração da aplicação do método através de testes experimentais, foi montada uma estrutura para suportar as câmeras e as peças a serem manipuladas, levando em conta o espaço de trabalho do robô. Os resultados obtidos mostram que o algoritmo proposto de visão computacional determina a posição e orientação das peças permitindo ao robô a captação e manipulação das mesmas. / The recognition of the position and orientation of objects in an image is important for several technological areas in engineering, such as robotics, industrial automation and manufacturing processes, allowing production lines using vision systems, improvements in quality and reduction in production time. The present work consists of the development of a computer vision system for a pneumatically actuated cylindrical robot with five degrees of freedom. The application of the proposed method furnishes the position and orientation of pieces in a way that the robot could properly capture them. Position and orientation of the pieces are determined by means of a technique based on the method of calculating the moments for an image feature extraction and the relationship between their pixels coordinates with the robot coordinate system. The scope of the present work also comprises the integration of the computer vision system with a (previously developed) robot trajectory planning algorithm that use key-point coordinates (transmitted by the vision system) to generate the trajectory that must be followed by the robot, so that, departing from a given position, it moves suitably to another predetermined position. It is also object of this work, the integration of both vision system and trajectory planning algorithm with a (also previously developed) nonlinear control algorithm with friction compensation. Aiming at to demonstrate experimentally the application of the method, a special apparatus was mounted to support cameras and the pieces to be manipulated, taking into account the robot workspace. To validate the proposed algorithm, a case study was performed, with the results showing that the proposed computer vision algorithm determines the position and orientation of the pieces allowing the robot to capture and manipulation thereof.

Esta tese trata de um robô bípede em caminhar dinâmico. Neste robô, que normalmente é um sistema sub-atuado, fazemos uso de um disco de inércia que funciona num certo sentido como um atuador adicional. Através deste disco, obtém-se mais liberdade para a elaboração de passos repetitivos e um aumento na robustez. Por outro lado, o sistema de controle dos passos deve controlar, além do passo propriamente dito, também a velocidade do disco, de modo que não sejam saturados os atuadores (motores elétricos). Apresentamos então um controlador capaz de realizar estas ações simultaneamente. / This Thesis is about a bipedal robot in a dynamic walking gait. In this robot, which is usually a under-actuated system, a inertial wheel is employed and acts as an additional actuator. By using this wheel, one can design a cyclic walking gait with increased robustness and with more freedom. On the other hand, the control system must take care of the step itself, and also must ensure that the wheel speed does not exceed the actuators (motors) limits. We present a controller able to perform this tasks.

Le travail de thèse décrit dans ce manuscrit concerne les Systèmes Avancés d’Aide à la Conduite (ADAS) qui sont devenus de nos jours un axe de recherche stratégique chez de nombreux constructeurs automobiles. Ce type de systèmes peuvent être considérés comme la première génération de dispositifs de conduite assistée ou semi-autonome et qui ouvrira la voie aux véhicules pleinement autonomes. La première partie de ce manuscrit concerne l’analyse et la commande pour les applications de contrôle de la dynamique latérale du véhicule – autoguidage par suivi de cible et aide au maintien au centre de la voie (LCA). Dans ce cadre, la sécurité joue un rôle clé, mettant en lumière la mise en oeuvre différentes techniques de commande contrainte pour des modèles linéaires à paramètres variants (LPV). La commande prédictive (MPC) et la commande par interpolation (IBC) ont été sélectionnés dans ce travail. De plus, la conception d’un système de commande robuste qui assure un comportement correct malgré la variation des paramètres du système ou la présence d’incertitudes est une caractéristique critique. Les outils de la théorie de l’invariance positive robuste (RPI) sont pris en considération pour la conception de stratégies de commande robustes LPV par rapport aux larges variations de la vitesse véhicule et aux changements de courbure de la route. Le second axe de cette thèse est la planification optimale de trajectoire pour les manouvres de dépassement et de changement de voie sur autoroute, avec réduction des risques de collision. Pour atteindre cet objectif, la description exhaustive des scénarios possible est présentée, permettant de formuler un problème d’optimisation qui maximise le confort du conducteur et assure la satisfaction des contraintes du système. / The thesis work contained in this manuscript is dedicated to the Advanced Driving Assistance Systems, which has become nowadays a strategic research line in many car companies. This kind of systems can be seen as a first generation of assisted or semi-autonomous driving, that will set the way to fully automated vehicles. The first part focuses on the analysis and control of lateral dynamics control applications - Autosteer by target tracking and the Lane Centering Assistance System (LCA). In this framework, safety plays a key role, bringing into focus the application of different constrained control techniques for linear parametervarying (LPV) models. Model Predictive Control (MPC) and Interpolation Based Control (IBC) have been the selected ones in the present work. In addition, it is a critical feature to design robust control systems that ensure a correct behavior under system's variation of parameters or in the presence of uncertainty. Robust Positive Invariance (RPI) theory tools are considered to design robust LPV control strategies with respect to large vehicle speed variations and curvature of the road changes. The second axis of this thesis is the optimization-based trajectory planning for overtaking and lane change in highways with anti-collision enhancements. To achieve this goal, an exhaustive description of the possible scenarios that may arise is presented, allowing to formulate an optimization problem which maximizes passenger comfort and ensures system constraints' satisfaction.

Comme les robots effectuent de plus en plus de tâches en interaction avec l'homme ou dans un environnement humain, ils doivent assurer la sécurité et le confort des hommes. Dans ce contexte, le robot doit adapter son comportement et agir en fonction des évolutions de l'environnement et des activités humaines. Les robots développés sur la base de l'apprentissage ou d'un planificateur de mouvement ne sont pas en mesure de réagir assez rapidement, c'est pourquoi nous proposons d'introduire un contrôleur de trajectoire intermédiaire dans l'architecture logicielle entre le contrôleur bas niveau et le planificateur de plus haut niveau. Le contrôleur de trajectoire que nous proposons est basé sur le concept de générateur de trajectoire en ligne (OTG), il permet de calculer des trajectoires en temps réel et facilite la communication entre les différents éléments, en particulier le planificateur de chemin, le générateur de trajectoire, le détecteur de collision et le contrôleur. Pour éviter de replanifier toute une trajectoire en réaction à un changement induit par un humain, notre contrôleur autorise la déformation locale de la trajectoire et la modification de la loi d'évolution pour accélérer ou décélérer le mouvement. Le contrôleur de trajectoire peut également commuter de la trajectoire initiale vers une nouvelle trajectoire. Les fonctions polynomiales cubiques que nous utilisons pour décrire les trajectoires fournissent des mouvements souples et de la flexibilité sans nécessiter de calculs complexes. De plus, les algorithmes de lissage que nous proposons permettent de produire des mouvements esthétiques ressemblants à ceux des humains. Ce travail, mené dans le cadre du projet ANR ICARO, a été intégré et validé avec les robots KUKA LWR de la plate-forme robotique du LAAS-CNRS. / In order to perform a large variety of tasks in interaction with human or in human environments, a robot needs to guarantee safety and comfort for humans. In this context, the robot shall adapt its behavior and react to the environment changes and human activities. The robots based on learning or motion planning are not able to adapt fast enough, so we propose to use a trajectory controller as an intermediate control layer in the software structure. This intermediate layer exchanges information with the low level controller and the high level planner. The proposed trajectory controller, based on the concept of Online Trajectory Generation (OTG), allows real time computation of trajectories and easy communication with the different components, including path planner, trajectory generator, collision checker and controller. To avoid the replan of an entire trajectory when reacting to a human behaviour change, the controller must allow deforming locally a trajectory or accelerate/decelerate by modifying the time function. The trajectory controller must also accept to switch from an initial trajectory to a new trajectory to follow. Cubic polynomial functions are used to describe trajectories, they provide smoothness, flexibility and computational simplicity. Moreover, to satisfy the objective of aesthetics, smoothing algorithm are proposed to produce human-like motions. This work, conducted as part of the ANR project ICARO, has been integrated and validated on the KUKA LWR robot platform of LAAS-CNRS.

Path planning that considers accurate vehicle dynamics and obstacle avoidance is an important problem in the area of autonomous driving. This paper describes a method of implementing trajectory planning for autonomous parking in conditions where the starting point and the position of fixed obstacles are uncertain. The narrow spaces and complicated manoeuvres required for parking demands a lot from the trajectory planning algorithm. It needs to have the ability to accurately model vehicle dynamics and find an efficient way around obstacles. Having obstacles in the way of the parking vehicle makes this a nonconvex problem the goal can usually not be reached by travelling in a straight line and finding a perfect trajectory around them is generally not computationally tractable. This paper reviews a two tiered approach to solving this problem. First a rough path is found using a modified Rapidly-exploring Random Tree (RRT) algorithm called Forward-Backward RRT, which runs two treebuilding processes in parallel and constructs a feasible path from where they intersect. Using optimisation this is then improved into a trajectory that is at least a local optimum. These methods will be demonstrated to produce efficient and feasible trajectories that respects the dynamic constraints of the vehicle and avoids collisions.