Thesis (MScEng)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: In order to navigate dynamic, cluttered environments safely, fully autonomous Unmanned Aerial Vehicles (UAVs) are required to plan conflict-free trajectories between two states in position-time space efficiently and reliably. Kinodynamic planning for vehicles with non-holonomic dynamic constraints is an NP-hard problem which is usually addressed using sampling-based, probabilistically complete motion planning algorithms. These algorithms are often applied in conjunction with a finite set of simple geometric motion primitives which encapsulate the dynamic constraints of the vehicle. This ensures that composite trajectories generated by the planning algorithm adhere to the vehicle dynamics. For many vehicles, accurate tracking of position-based trajectories is a non-trivial problem which demands complicated control techniques with high energy requirements. In an effort to reduce control complexity and thus also energy consumption, a generic Local Planning Method (LPM), able to plan trajectories based on implicitly-defined motion primitives, is developed in this project. This allows the planning algorithm to construct trajectories which are based on simulated results of vehicle motion under the control of a rudimentary auto-pilot, as opposed to a more complicated position-tracking system. The LPM abstracts motion primitives in such a way that it may theoretically be made applicable to various vehicles and control systems through simple substitution of the motion primitive set. The LPM, which is based on a variation of the Levenberg-Marquardt Algorithm (LMA), is integrated into a well-known Probabilistic Roadmap (PRM) kinodynamic planning algorithm which is known to work well in dynamic and cluttered environments. The complete motion planning algorithm is tested thoroughly in various simulated environments, using a vehicle model and controllers which have been previously verified against a real UAV during practical flight tests. / AFRIKAANSE OPSOMMING: Ten einde dinamiese, voorwerpryke omgewings veilig te navigeer, word daar vereis dat volledig-outonome onbemande lugvoertuie konflikvrye trajekte tussen twee posisie-tydtoestande doeltreffend en betroubaar kan beplan. Kinodinamiese beplanning is ’n NPmoeilike probleem wat gewoonlik deur middel van probabilisties-volledige beplanningsalgoritmes aangespreek word . Hierdie algoritmes word dikwels in kombinasie met ’n eindige stel eenvoudige geometriese maneuvers, wat die dinamiese beperkings van die voertuig omvat, ingespan. Sodanig word daar verseker dat trajekte wat deur die beplaningsalgoritme saamgestel is aan die dinamiese beperkings van die voertuig voldoen. Vir baie voertuie, is die akkurate volging van posisie-gebaseerde trajekte ’n nie-triviale probleem wat die gebruik van ingewikkelde, energie-intensiewe beheertegnieke vereis. In ’n poging om beheer-kompleksiteit, en dus energie-verbruik, te verminder, word ’n generiese plaaslike-beplanner voorgestel. Hierdie algoritme stel die groter kinodinamiese beplanner in staat daartoe om trajekte saam te stel wat op empiriese waarnemings van voertuig-trajekte gebaseer is. ’n Eenvoudige beheerstelsel kan dus gebruik word, in teenstelling met die meer ingewikkelde padvolgingsbeheerders wat benodig word om eenvoudige geometriese trajekte akkuraat te volg. Die plaaslike-beplanner abstraeer maneuvers in so ’n mate dat dit teoreties op verskeie voertuie en beheerstelsels van toepassing gemaak kan word deur eenvoudig die maneuver-stel te vervang. Die plaaslike-beplanner, wat afgelei is van die Levenberg-Marquardt-Algoritme (LMA), word in ’n welbekende “Probabilistic Roadmap” (PRM) kinodinamiese-beplanningsalgoritme geïntegreer. Dit word algemeen aanvaar dat die PRM effektief werk in dinamiese, voorwerpryke omgewings. Die volledige beplanningsalgoritme word deeglik in verskeie, gesimuleerde omgewings getoets op ’n voertuig-model en -beheerders wat voorheen vir akkuraatheid teenoor ’n werklike voertuig gekontroleer is tydens praktiese vlugtoetse.

Thesis (MScEng)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: This project concerns motion planning for a rotary wing UAV, where vehicle controllers are already in place, and map data is readily available to a collision detection module. In broad terms, the goal of the motion planning algorithm is to provide a safe (i.e. obstacle free) flight path between an initial- and goal waypoint. This project looks at two specific motion planning algorithms, the Rapidly Exploring Random Tree (or RRT*), and the Probabilistic Roadmap Method (or PRM). The primary focus of this project is learning how these algorithms behave in specific environments and an in depth analysis is done on their differences. A secondary focus is the execution of planned paths via a Simulink simulation and lastly, this project also looks at the effect of path replanning. The work done in this project enables a rotary wing UAV to autonomously navigate an uncertain, dynamic and cluttered environment. The work also provides insight into the choice of an algorithm for a given environment: knowing which algorithm performs better can save valuable processing time and will make the entire system more responsive. / AFRIKAANSE OPSOMMING: ’n Tipiese vliegstuuroutomaat is daartoe in staat om ’n onbemande lugvaartvoertuig (UAV) so te stuur dat ’n stel gedefinieerde punte gevolg word. Die punte moet egter vooraf beplan word, en indien enige verandering nodig is (bv. as gevolg van veranderinge in die omgewing) is dit nodig dat ’n menslike operateur betrokke moet raak. Vir voertuie om ten volle outonoom te kan navigeer, moet die voertuig in staat wees om te kan reageer op veranderende situasies. Vir hierdie doel word kinodinamiese beplanningsalgoritmes en konflikdeteksiemetodes gebruik. Hierdie projek behels kinodinamiese beplanningsalgoritmes vir ’n onbemande helikopter, waar die beheerders vir die voertuig reeds in plek is, en omgewingsdata beskikbaar is vir ’n konflikdeteksie-module. In breë terme is die doel van die kinodinamiese beplanningsalgoritme om ’n veilige (d.w.s ’n konflikvrye) vlugpad tussen ’n begin- en eindpunt te vind. Hierdie projek kyk na twee spesifieke kinodinamiese beplanningsalgoritmes, die “Rapidly exploring Random Tree*” (of RRT*), en die “Probabilistic Roadmap Method” (of PRM). Die primêre fokus van hierdie projek is om die gedrag van hierdie algoritmes in spesifieke omgewings te analiseer en ’n volledige analise te doen op hul verskille. ’n Sekondêre fokus is die uitvoering van ’n beplande vlugpad d.m.v ’n Simulink-simulasie, en laastens kyk hierdie projek ook na die effek van padherbeplanning. Die werk wat gedoen is in hierdie projek stel ’n onbemande helikopter in staat om outonoom te navigeer in ’n onsekere, dinamiese en besige omgewing. Die werk bied ook insig in die keuse van ’n algoritme vir ’n gegewe omgewing: om te weet watter algoritme beter uitvoertye het kan waardevolle verwerkingstyd bespaar, en verseker dat die hele stelsel vinniger kan reageer.

Planejamento de movimento tem o propósito de determinar quais movimentos o robô deve realizar para que alcance posições ou configurações desejadas no ambiente sem que ocorram colisões com obstáculos. É comum na robótica móvel simplificar o planejamento de movimento representando o robô pelas coordenadas do seu centro e desconsiderando qualquer restrição cinemática e dinâmica de movimento. Entretanto, a maioria dos robôs móveis possuem restrições cinemáticas não-holonômicas, e para algumas tarefas e robôs, é importante considerar tais restrições juntamente com o modelo dinâmico do robô na tarefa de planejamento. Assim é possível determinar um caminho que possa ser de fato seguido pelo robô. Nesse trabalho é proposto um método de planejamento cinemático-dinâmico que permite planejar trajetórias para robôs móveis usando malhas de estados. Essa abordagem considera a cinemática e a dinâmica do robô para gerar trajetórias possíveis de serem executadas e livre de colisões com obstáculos. Quando obstáculos não representados no mapa são detectados pelos sensores do robô, uma nova trajetória é gerada para desviar desses obstáculos. O planejamento de movimento utilizando malhas de estados foi associado a um algoritmo de desvio de obstáculos baseado no método da janela dinâmica (DWA). Esse método é responsável pelo controle de seguimento de trajetória, garantindo a segurança na realização da tarefa durante a navegação. As trajetórias planejadas foram executadas em duas plataformas distintas. Essas plataformas foram utilizadas em tarefas de navegação em ambientes simulados interno e externo e em ambientes reais. Para navegação em ambientes internos utilizou-se o robô móvel Pioneer 3AT e para navegação em ambientes externos utilizou-se o veículo autônomo elétrico CaRINA 1 que está sendo desenvolvido no ICMC-USP com apoio do Instituto Nacional de Ciência e Tecnologia em Sistemas Embarcados Críticos (INCT-SEC). / Motion planning aims to determine which movements the robot must accomplish to reach a desired position or configuration in the environment without the occurrence of collisions with obstacles. It is common in mobile robotics to simplify the motion planning representing the robot by the coordinates of its center of gravity and ignoring any kinematic and dynamic constraint motion. However, most mobile robots have non-holonomic kinematic constraints, and for some tasks and robots, it is important to consider these constraints together with the dynamic model of the robot in task planning. Thus it is possible to determine a path that can actually be followed by the robot. Here we propose a method for kinematic-dynamic path planning using lattice states. This approach considers the kinematic and dynamic of the robot to generate generate feasible trajectories free of collisions with obstacles. When obstacles not represented on the map are detected by the sensors of the robot, a new trajectory is generated to avoid these obstacles. The motion planning using lattice state was associated with an obstacle avoidance algorithm based on the dynamic window approach (DWA). This method is responsible for trajectory tracking to ensure safety in navigation tasks. This method was applied in two distinct platforms. These platforms were used for navigation tasks in both indoor and outdoor simulated environments, as well as, in real environments. For navigation in indoor environments we used a Pioneer 3AT robot and for outdoor navigation we used the autonomous electric vehicle CaRINA1 being developed at ICMC-USP with support National Institute of Science and Technology in Critical Embedded Systems (INCT-SEC).

Motion planning is central to the efficient operation and autonomy of robots in the industry. Generally, motion planning of industrial robots is treated in a two-step approach. First, a geometric path between the start and goal position is planned where the objective is to achieve as short path as possible together with avoiding obstacles. Alternatively, a pre-defined geometric path is provided by the end user. Second, the velocity profile along the geometric path is calculated accounting for system dynamics together with other constraints. This approach is computationally efficient, but yield sub-optimal solutions as the system dynamics is not considered in the first step when the geometric path is planned. In this thesis, an alternative to the two-step approach is investigated and a trajectory planner is designed and implemented which plans both the geometric path and the velocity profile simultaneously. The motion planning problem is formulated as an optimal control problem, which is solved by a direct collocation method where the trajectory is parametrised by splines, and the spline nodes and knots are used as optimization variables. The implemented trajectory planner is evaluated in simulations, where the planner is applied to a simple planar elbow robot and ABB's SCARA robot IRB 910SC. Trade-off between computation time and optimality is identified and the results indicate that the trajectory planner yields satisfactory solutions. On the other hand, the simulations indicate that it is not possible to apply the proposed method on a real robot in real-time applications without significant modifications in the implementation to decrease the computation time.

This thesis is concerned with the robots' motion planning problem. In particular it is focused on the path planning and motion planning for Autonomously Guided Vehicles (AGVs) in well-structured, two-dimensional static and dynamic environments. Two algorithms are proposed for solving the aforementioned problems. The first algorithm establishes the shortest collision-semi-free path for an AGV from its start point to its goal point, in a two-dimensional static environment populated by simple polygonal obstacles. This algorithm constructs and searches a reduced visibility graph, within the AGV's configuration space, using heuristic information about the problem domain. The second algorithm establishes the time minimal collision-semi-free motion for an AGV, from its start point to is goal point, in a two-dimensional dynamic environment populated by simple polygonal obstacles. This algorithm considers the AGV's spacetime configuration space, thus reducing the dynamic motion planning problem to the static path planning problem. A reduced visibility graph is then constructed and searched using information about the problem domain, in the AGV's space-time configuration space in order to establish the time-minimal motion between the AGV's start and goal configurations. The latter algorithm is extended to solve more complicated instances of the dynamic motion planning problem, where the AGV's environment is populated by obstacles, which change their size as well as their position over time and obstacles, which have piecewise linear motion. The proposed algorithms can be used to efficiently and safely navigate AGVs in well structured environments. For example, for the navigation of an AGV, in industrial environments, where it operates as part of the manufacturing process or in chemical and nuclear plants, where the hostile environment is inaccessible to humans. The main contributions in this thesis are, the systematic study of the V*GRAPH algorithm and identification of its methodic and algorithmic deficiencies; recommendation of corrections and further improvements on the V* GRAPH algorithm, which in turn lead to the proposition of the V*MECHA algorithm for robot path planning; proposition of the D*MECHA algorithm for motion planning in dynamic environments; extension to the D*MECHA algorithm to solve more complicated instances of the dynamic robot motion planning problem; discussion of formal proofs of the proposed algorithms' correctness and optimality and critical comparisons with existing similar algorithms for solving the motion planning problem.

Les protéines sont des macromolécules participant à d’importants processus biophysiques de la vie des organismes. Or, il a été démontré que des variations de leur structure peuvent conduire à des changements de fonction en lien avec certaines maladies telles que celles associées à des processus neurodégénératifs. Ainsi, tant pour la communauté scientifique que pour l’industrie médicale, il est capital d’avoir une meilleure compréhension de la structure de ces protéines, ainsi que de leurs interactions avec d’autres molécules, ce en vue d’inventer et d’évaluer de nouveaux médicaments.Au cours de ces travaux de thèse, nous nous sommes particulièrement intéressés au développement de nouvelles méthodes de recherche de chemins biologiquement faisables entre deux états connus pour un système composé d’une protéine ou d’une protéine et d’un ligand. Au cours des dernières décennies, une grande quantité d’approches algorithmiques ont été proposées pour faire face à ce problème. Pourtant, les méthodes développées sont encore aujourd’hui confrontées à deux grands défis : d’une part la haute dimension des espaces de recherche, associée au grand nombre d’atomes impliqués, d’autre part la complexité des interactions entre ces atomes.Cette dissertation propose deux nouvelles méthodes pour obtenir de manière efficace des chemins pertinents pour des systèmes moléculaires. Ces méthodes sont rapides et génèrent des solutions qui peuvent ensuite être analysées ou améliorées à l’aide de méthodes d’avantage spécialisées. La première approche proposée produit des chemins d’interpolation pour systèmes biomoléculaires, à l’aide des approches dites aussi-rigides-que-possible, (ARAP) utilisées en animation graphique. Cette méthode est robuste et génère des solutions préservant au mieux la rigidité du système d’origine. Une extension de cette méthode basée sur des critères énergétiques a également été proposée et s’est avérée capable d’améliorer de manière significative les chemins solution. Cependant, pour les scénarios nécessitant de complexes déformations, cette approche géométrique peut conduire à des chemins solution non naturels. Nous avons donc proposé une seconde méthode appelée ART-RRT, qui utilise l’approche ARAP pour réduire la dimensionalité de l’espace et la combine avec les arbres d’exploration RRT (Rapidely-exploring Random Tree) issus de la Robotique, afin d’explorer efficacement les chemins possibles de l’espace.En plus de fournir une variété de solutions en temps raisonnable, cette ART-RRT produit des chemins de faible énergie, sans collision et dont la rigidité est préservée autant que possible. Des versions monodirectionnelles de bidirectionelles de cette méthode ont été proposées et appliquées respectivement à la recherche de chemin d’extraction d’un ligand hors du site actif d’une protéine, ainsi qu’a la recherche de chemin de transition conformationnelle pour protéine seule. Les solutions trouvées se sont avérées être en accord avec les données expérimentales ainsi qu’avec les solutions issues de l’état de l’art. / Proteins are macromolecules participating in important biophysical processes of living organisms. It has been shown that changes in protein structures can lead to changes in their functions and are found linked to some diseases such as those related to neurodegenerative processes. Hence, an understanding of their structures and interactions with other molecules such as ligands is of major concern for the scientific community and the medical industry for inventing and assessing new drugs.In this dissertation, we are particularly interested in developing new methods to find for a system made of a single protein or a protein and a ligand, the pathways that allow changing from one state to another. During past decade, a vast amount of computational methods has been proposed to address this problem. However, these methods still have to face two challenges: the high dimensionality of the representation space, associated to the large number of atoms in these systems, and the complexity of the interactions between these atoms.This dissertation proposes two novel methods to efficiently find relevant pathways for such biomolecular systems. The methods are fast and their solutions can be used, analyzed or improved with more specialized methods. The first proposed method generates interpolation pathways for biomolecular systems using the As-Rigid-As-Possible (ARAP) principle from Computer Graphics. The method is robust and the generated solutions preserve at best the local rigidity of the original system. An energy-based extension of the method is also proposed, which significantly improves the solution paths. However, in scenarios requiring complex deformations, this geometric approach may still generate unnatural paths. Therefore, we propose a second method called ART-RRT, which combines the ARAP principle for reducing the dimensionality, with the Rapidly-exploring Random Trees from Robotics for efficiently exploring possible pathways. This method not only gives a variety of pathways in reasonable time but the pathways are also low-energy and clash-free, with the local rigidity preserved as much as possible. The mono-directional and bi-directional versions of the ART-RRT method were applied for finding ligand-unbinding and protein conformational transition pathways, respectively. The results are found to be in good agreement with experimental data and other state-of-the-art solutions.

Robôs manipuladores vem desempenhando um importante papel em operações orbitais, e isso foi possível devido ao grande avanço da robótica espacial nas últimas décadas. Porém, o planejamento do movimento ainda é considerado um dos maiores desafios nesse campo, embora diversos métodos e considerações tenham sido propostas para resolver esse problema. As primeiras contribuições na área de planejamento de movimento dependiam de uma representação explícita do espaço de configuração do robô. Dessa forma, o planejamento de movimento para sistemas robóticos com muitos graus de liberdade era impraticável. Para lidar com esse problema, surgiram os métodos baseados em amostragem, dentre eles, o método de Árvore Aleatória de Exploração Rápida - RRT (do inglês, Rapidly- Exploring Random Tree). Estes métodos, ao invés da construção de todo o conjunto de configurações livre de colisões, requerem apenas a verificação de colisão com obstáculos para um conjunto discreto e finito de configurações do robô. Consequentemente, para este tipo de problema, são métodos mais vantajosos em termos computacionais. Com esta motivação, o presente trabalho tem como objetivo o desenvolvimento de um planejador de rota e de um planejador de trajetória para um robô manipulador espacial de base livre flutuante com dois braços, ambos planejadores com suporte a desvio de obstáculos estáticos. O conceito de manipulador dinamicamente equivalente é utilizado para modelar o manipulador espacial. Isso permite que o planejamento seja feito para um manipulador de base fixa subatuado dinamicamente equivalente ao manipulador de base livre flutuante. Os algoritmos baseados em amostragem RRT* e RRTControl disponibilizados na biblioteca OMPL (do inglês, Open Motion Planning Library) foram adaptados para resolver este problema de planejamento. O algoritmo RRT* é usado para o planejamento de rota, e o RRTControl para o planejamento de trajetória. Ambos planejadores utilizam o espaço de configuração das juntas do robô. Para possibilitar que a orientação e posição final dos dois efetuadores do robô pudessem ser especificadas no espaço da tarefa, um algoritmo de cinemática inversa baseado em algoritmo genético também foi desenvolvido para encontrar a solução da cinemática inversa do manipulador. / Robot manipulator has played an important role in orbital missions and this was possible due to the advance of space robotics in recent decades. However, motion planning is still considered one of the biggest challenges of the field though various methods and considerations were proposed by researchers to handle this problem. The first contributions in this field were dependent on an explicit representation of the free configuration space. Consequently, it was impractical to solve the motion planning problem for robotic systems with many degrees of freedom. In order to cope with this limitation, sampling-based methods were proposed, in particular, the Rapidly-Exploring Random Tree – RRT. Sampling-based methods only requires a procedure to verify collision with obstacles for a discrete amount of robot configuration during planning. Therefore, they are more advantageous in computational terms. In this work a path planner and a trajectory planner were developed for a free-floating planar manipulator with two arms with support for static obstacle avoidance. The Dynamically Equivalent Manipulator approach was used for modelling the robot. Thus, the planners were developed based on a fixed-base underactuated manipulator model which is dynamically equivalent to the free-floating manipulator. The sampling-based algorithms RRT* and RRTControl of the Open Motion Planning Library (OMPL) were adapted to solve this motion planning problem. The RRT* were used for path planning, and the RRTControl for trajectory planning, both carried out in the robot joint space. As the desired orientations and positions of the two end-effectors were specified in the task-space, a genetic algorithm was also developed to compute the inverse kinematics of the manipulator.

Motion planning is defined as the problem of computing a feasible trajectory for an agent to follow. It is a well-studied problem with applications in fields such as robotics, control theory and artificial intelligence. In the last decade there has been an increased interest in algorithms for motion planning under uncertainty where the agent does not know the state of the environment due to, e.g. motion and sensing uncertainties. One approach is to generate an initial feasible trajectory using for example an algorithm such as RRT* and then improve that initial trajectory using local optimization. This thesis proposes a new modification of the RRT* algorithm that can be used to generate initial paths from which initial trajectories for the local optimization step can be generated. Unlike standard RRT*, the modified RRT* generates multiple paths at the same time, all belonging to different families of solutions (homotopy classes). Algorithms for motion planning under uncertainty that rely on local optimization of trajectories can use trajectories generated from these paths as initial solutions. The modified RRT* is implemented and its performance with respect to computation time and number of paths found is evaluated on simple scenarios. The evaluations show that the modified RRT* successfully computes solutions in multiple homotopy classes. Two methods for motion planning under uncertainty, Trajectory-optimized LQG (T-LQG), and a belief space variant of iterative LQG (iLQG) are implemented and combined with the modified RRT*. The performance with respect to cost function improvement, computation time and success rate when following the optimized trajectories for the two methods are evaluated in a simulation study. The results from the simulation studies show that it is advantageous to generate multiple initial trajectories. Some initial trajectories, due to for example passing through narrow passages or through areas with high uncertainties, can only be slightly improved by trajectory optimization or results in trajectories that are hard to follow or with a high collision risk. If multiple initial trajectories are generated the probability is higher that at least one of them will result in an optimized trajectory that is easy to follow, with lower uncertainty and lower collision risk than the initial trajectory. The results also show that iLQG is much more computationally expensive than T-LQG, but that it is better at computing control policies to follow the optimized trajectories.

abstract: Most planning agents assume complete knowledge of the domain, which may not be the case in scenarios where certain domain knowledge is missing. This problem could be due to design flaws or arise from domain ramifications or qualifications. In such cases, planning algorithms could produce highly undesirable behaviors. Planning with incomplete domain knowledge is more challenging than partial observability in the sense that the planning agent is unaware of the existence of such knowledge, in contrast to it being just unobservable or partially observable. That is the difference between known unknowns and unknown unknowns. In this thesis, I introduce and formulate this as the problem of Domain Concretization, which is inverse to domain abstraction studied extensively before. Furthermore, I present a solution that starts from the incomplete domain model provided to the agent by the designer and uses teacher traces from human users to determine the candidate model set under a minimalistic model assumption. A robust plan is then generated for the maximum probability of success under the set of candidate models. In addition to a standard search formulation in the model-space, I propose a sample-based search method and also an online version of it to improve search time. The solution presented has been evaluated on various International Planning Competition domains where incompleteness was introduced by deleting certain predicates from the complete domain model. The solution is also tested in a robot simulation domain to illustrate its effectiveness in handling incomplete domain knowledge. The results show that the plan generated by the algorithm increases the plan success rate without impacting action cost too much. / Dissertation/Thesis / Masters Thesis Computer Science 2020

This master’s thesis describes equations of motion for dynamic model of nonholonomic constrained system, namely the trident robotic snakes. The model is studied in the form of Lagrange's equations and D’Alembert’s principle is applied. Actually this thesis is a continuation of the study going at VUT about the simulations of non-holonomic mechanisms, specifically robotic snakes. The kinematics model was well-examined in the work of of Byrtus, Roman and Vechetová, Jana. So here we provide equations of motion and address the motion planning problem regarding dynamics of the trident snake equipped with active joints through basic examples and propose a feedback linearization algorithm.