Thesis (PhD)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: This research focuses on the development of new efficient algorithms for multi-path planning and multi-rigid body constrained attitude control. The work is motivated by current and future applications of these algorithms in: intelligent control of multiple autonomous aircraft and spacecraft systems; control of multiple mobile and industrial robot systems; control of intelligent highway vehicles and traffic; and air and sea traffic control. We shall collectively refer to the class of mobile autonomous systems as “agents”. One of the challenges in developing and applying such algorithms is that of complexity resulting from the nontrivial agent dynamics as agents interact with other agents, and their environment. In this work, some of the current approaches are studied with the intent of exposing the complexity issues associated them, and new algorithms with reduced computational complexity are developed, which can cope with interaction constraints and yet maintain stability and efficiency. To this end, this thesis contributes the following new developments to the field of multipath planning and multi-body constrained attitude control: • The introduction of a new LMI-based approach to collision avoidance in 2D and 3D spaces. • The introduction of a consensus theory of quaternions by applying quaternions directly with the consensus protocol for the first time. • A consensus and optimization based path planning algorithm for multiple autonomous vehicle systems navigating in 2D and 3D spaces. • A proof of the consensus protocol as a dynamic system with a stochastic plant matrix. • A consensus and optimization based algorithm for constrained attitude synchronization of multiple rigid bodies. • A consensus and optimization based algorithm for collective motion on a sphere. / AFRIKAANSE OPSOMMING: Hierdie navorsing fokus op die ontwikkeling van nuwe koste-effektiewe algoritmes, vir multipad-beplanning en veelvuldige starre-liggaam beperkte standbeheer. Die werk is gemotiveer deur huidige en toekomstige toepassing van hierdie algoritmes in: intelligente beheer van veelvuldige outonome vliegtuig- en ruimtevaartuigstelsels; beheer van veelvuldige mobiele en industrile robotstelsels; beheer van intelligente hoofwegvoertuie en verkeer; en in lug- en see-verkeersbeheer. Ons sal hier “agente” gebruik om gesamentlik te verwys na die klas van mobiele outonome stelsels. Een van die uitdagings in die ontwikkeling en toepassing van sulke algoritmes is die kompleksiteit wat spruit uit die nie-triviale agentdinamika as gevolg van die interaksie tussen agente onderling, en tussen agente en hul omgewing. In hierdie werk word sommige huidige benaderings bestudeer met die doel om die kompleksiteitskwessies wat met hulle geassosieer word, bloot te l^e. Verder word nuwe algoritmes met verminderde berekeningskompleksiteit ontwikkel. Hierdie algoritmes kan interaksie-beperkings hanteer, en tog stabiliteit en doeltreffendheid behou. Vir hierdie doel dra die proefskrif die volgende nuwe ontwikkelings by tot die gebied van multipad-beplanning van multi-liggaam beperkte standbeheer: • Die voorstel van ’n nuwe LMI-gebasseerde benadering tot botsingsvermyding in 2D en 3D ruimtes. • Die voorstel van ’n konsensus-teorie van “quaternions” deur “quaternions” vir die eerste keer met die konsensusprotokol toe te pas. • ’n Konsensus- en optimeringsgebaseerde padbeplanningsalgoritme vir veelvoudige outonome voertuigstelsels wat in 2D en 3D ruimtes navigeer. • Die bewys van ’n konsensusprotokol as ’n dinamiese stelsel met ’n stochastiese aanlegmatriks. • ’n Konsensus- en optimeringsgebaseerde algoritme vir beperkte stand sinchronisasie van veelvoudige starre liggame. • ’n Konsensus- en optimeringsgebaseerde algoritme vir kollektiewe beweging op ’n sfeer.

Este trabalho propõe um sistema de manipulação robótica para interação física segura com objetos ou humanos em ambientes não estruturados. A proposta considera a execução de tarefas de manipulação e a prevenção e tratamento de colisões utilizando apenas uma lei de controle, o controle de impedância. A inovação científica consiste em um sistema multifuncional implementado com uma única lei de controle em contraste com os sistemas já existem que utilizam chaveamento entre controladores para cada diferente funcionalidade do sistema, e que apresentam diversas desvantagens como instabilidade e oscilações, aumento da complexidade de programação, entre outras. Inicialmente é proposto um planejador de manipulação e regrasping baseado na combinação de trajetórias suaves e na adaptação dos parâmetros de um controle de impedância em tempo de execução. A mudança da impedância para cada etapa é obtida pela modificação dos parâmetros de inércia, rigidez e amortecimento do controlador. A estabilidade desta mudança dinâmica é possível pela utilização de trajetórias suaves obtidas com planejador Squeezed Screw modificado, cujas trajetórias geradas são livres de descontinuidades na posição e na velocidade. Adicionalmente, a prevenção de colisões é realizada com o auxílio de campos potenciais de forças de repulsão formados pela análise de dados de um sistema de visão também proposto. Estes mesmos dados são utilizados para a construção de um mapa de impedâncias ao redor do objeto cuja finalidade é suavizar efeitos de colisões indesejadas. Experimentos com um robô de arquitetura aberta e com um sistema de visão de baixo custo foram realizados na execução tarefa de manipulação de referência para se avaliar o desempenho da metodologia proposta em diferentes condições de operação encontradas em ambientes não estruturados, como por exemplo: erros de medida de posição, de calibração, ocorrência de colisões, etc. A tarefa de manipulação eleita foi a reorientação em 60° de um objeto circular no plano. Os resultados obtidos nos experimentos mostram a capacidade do controle de impedância associado a trajetórias suaves de realizar a tarefa eleita segundo avaliação utilizando como métricas de desempenho a porcentagem de reorientação, que apresentou uma média de 80% mesmo na presença de erros de medida do sensor de visão e erros de determinação da posição do objeto. / Recent applications in various robotics areas consider interaction between robots and objects or humans in non-structured environments. Under these conditions, in addition to the desire of robots to be able to perform their main tasks, handling, navigation, rehabilitation, etc, it is also desired to prevent and properly handle possible unwanted collisions, whether with objects, with other robots, animals or humans. There are several proposed methods for avoidance, handling and reaction for collisions, however, a widely used strategy is the controller switching between different robot states. There are several drawbacks within this strategy: instability and oscillation, increased programming complexity and consequent increased failure risk, need for different sensors and consequent increase in cost, among others. This work proposes a system applied to the robotic manipulation which is based on only one control law, the impedance control, whose expected capacity is, further performing manipulation tasks, avoidance and handling of potential undesired collisions. It is initially proposed a manipulation planner based the combination of smooth trajectories and the adjustment of parameters an impedance control at runtime. The change of impedance for each phase is achieved by modifying the parameters: mass, spring and damping controller. The stability of this dynamic change is possible by using smooth trajectories obtained with a modified Squeezed Screw trajectory planner, whose paths are discontinuities free in the position and speed. Additionally, collision avoidance is achieved through potential fields the repulsive forces of formed by analysis of data vision. The same data is used to construct an impedance map surrounding the object which objective is collision handling. Experiments with an open architecture robot and a low cost vision system are carried out in the execution of a benchmark manipulation task to evaluate the proposal performance under different operating conditions found in unstructured environments, for example, position measurement errors, calibration problems, occurrence of collisions, among others.

Simulating realistic human behavior on a virtual avatar presents a difficult task. Because the simulated environment does not adhere to the same scientific principles that we do in the existent world, the avatar becomes capable of achieving infeasible postures. In an attempt to obtain realistic human simulation, real world constraints are imposed onto the non-sentient being. One such constraint, and the topic of this thesis, is self-collision avoidance. For the purposes of this topic, a posture will be defined solely as a collection of angles formed by each joint on the avatar. The goal of self-collision avoidance is to eliminate the formation of any posture where multiple body parts are attempting to occupy the exact same space. My work necessitates an extension of this definition to also include collision avoidance with objects attached to the body, such as a backpack or armor. In order to prevent these collisions from occurring, I have implemented an effort-based approach for correcting afflicted postures. This technique specifically pertains to postures that are sequenced together with the objective of animating the avatar. As such, the animation's coherence and defining characteristics must be preserved. My approach to this problem is unique in that it strategically blends the concept of keyframe interpolation with an optimization-based strategy for posture prediction. Although there has been considerable work done with methods for keyframe interpolation, there has been minimal progress towards integrating a realistic collision response strategy. Additionally, I will test this optimization-based approach through the use of a complex kinematic human model and investigate the use of the results as input to an existing dynamic motion prediction system.

Due to the nature of tunnels, a driver in an underground mine may find themselves driving without much vision of the road up ahead. The tunnels usually allow for traffic in both directions but are often only wide enough for a single vehicle. To let vehicles pass each other meeting slots have been carved into the tunnel walls, where one can park while the other passes. Because of the limited vision, however, it is unlikely that a meeting with another vehicle will occur directly next to such a meeting slot. Instead, one of the vehicles must reverse to the closest meeting slot in order to let the other pass. This makes mine tunnels a very inhospitable driving environment, causing disruptions to traffic flow throughout the mine. Unfortunately, typical traffic management or scheduling solutions are not useful, as real-time positioning for the vehicles is often poor while network connectivity cannot be guaranteed in the mine environment. This thesis presents a solution which will avoid situations where a driver needs to back up, and instead present meeting slots in which to park ahead of time. This is done by calculating velocity probability distributions for road segments from historical data and using these to estimate arrival times to meeting slots. In addition, a more comprehensive solution is presented, taking into account the accuracy of positioning, outdated information due to poor connections and more complicated scenarios. The results show that estimating arrival times using only historical data is a very feasible technology, which can realistically be implemented today. Such an implementation could, in the author's opinion, improve driver safety and efficiency significantly, compared to a driver having no information or simply knowing rough positions of nearby vehicles. This being said, there are still steps that can be taken to improve the solution and to develop a more comprehensive system overall.

A suite of new collision avoidance systems (CAS) is presented for use in heavy vehicles whose structure and size necessarily impede driver visibility is introduced. The main goal of the project is to determine the appropriate use of each of the commercially available technologies and, where possible, produce a low cost variant suitable for use in proximity detection on large mining industry haul trucks. CAS variants produced were subjected to a field demonstration and, linked to the output from the earlier CAS 1 project, (a production high-definition in-cabin video monitor and r/f tagging system). The CAS 2 system used low cost Doppler continuous wave radar antennae coupled to the CAS 1 monitor to indicate the presence of an object moving at any speed above 3 Km/h relative to the antennae. The novelty of the CAS 3 system lies in the design of 3 interconnected, modules. The modules are 8 radar antennae (as used in CAS 2) modules located on the truck, software to interface with the end user (i.e. the drivers of the trucks) and a display unit. Modularisation enables the components to be independently tested, evaluated and replaced when in use. The radar antennae modules and the system as a whole are described together with the empirical tests conducted and results obtained. The tests, drawing on Monte-Carlo simulation techniques, demonstrate both the 'correctness' of the implementations and the effectiveness of the system. The results of the testing of the final prototype unit were highly successful both as a computer simulation level and in practical tests on light vehicles. A number of points, (as a consequence of the field test), are reviewed and their application to future projects discussed.

This thesis is concerned with automotive active safety, and a central theme is a new safety function called Emergency Lane Assist (ELA). Automotive safety is often categorised into passive and active safety, where passive safety is concerned with reducing the effects of accidents and active safety aims at avoiding them. ELA detects lane departure manoeuvres that are likely to result in a collision and prevents them by applying a steering wheel torque. The ELA concept is based on traffic accident statistics, i.e., it is designed to give maximum safety based on information about real life traffic accidents. The ELA function puts tough requirements on the accuracy of the information from the sensors, in particular the road shape and the position of surrounding objects, and on robust threat assessment. Several signal processing methods have been developed and evaluated in order to improve the accuracy of the sensor information, and these improvements are also analysed in how they relate to the ELA requirements. Different threat assessment methods are also studied, and a common element in both the signal processing and the threat assessment is that they are based on driver behaviour models, i.e., they utilise the fact that depending on the traffic situation, drivers are more likely to behave in certain ways than others. Most of the methods are general and can be, and hopefully also will be, applied also in other safety systems, in particular when a complete picture of the vehicle surroundings is considered, including information about road and lane shape together with the position of vehicles and infrastructure. All methods in the thesis have been evaluated on authentic sensor data from actual and relevant traffic environments.

Kinodynamic motion planning is an important problem in robotics. It consists of planning the dynamic motion of a robotic system taking into account its kinematic and dynamic constraints. For this class of problems, high dimensionality is a major difficulty and finding an exact time optimal robot motion trajectory is proven to be NP-hard. Probabilistic approximate techniques have therefore been proposed in the literature to solve particular problem instances. These methods include Randomized Potential Field Planners (RPP), Probabilistic Roadmaps (PRM) and Rapidly Exploring Random Trees (RRT). When physical obstacles and differential constraints are added to the problem, applying RPPs or PRMs encounter difficulties. In order to handle these difficulties, RRTs have been proposed. In this study, we consider a multiple camera industrial inspection problem where the concurrent motion of these cameras needs to be planned. The cameras are required to capture maximum number of defect locations while globally avoiding collisions with each other and with obstacles. Our approach is to consider a solution to the kinodynamic planning problem of multiple camera inspection by making use of the RRT algorithm. We explore and resolve issues arising when RRTs are applied to this specific problem class. Along these lines, we consider the cases of a single camera without obstacles and then with obstacles. Then, we attempt to extend the study to the case of multiple camera where we also need to avoid collisions between cameras. We present simulation results to show the performance of our RRT based approach to different instrument configurations and compare with existing deterministic approaches.

<p>This Master’s thesis is a pilot study that investigates different systems to drive autonomous and non-autonomous vehicles simultaneously on test tracks. The thesis includes studies of communication, positioning, collision avoidance, and techniques for surveillance of vehicles which are suitable for implementation. The investigation results in a suggested system outline.</p><p>Differential GPS combined with laser scanner vision is used for vehicle state estimation (position, heading, velocity, etc.). The state information is transmitted with IEEE 802.11 to all surrounding vehicles and surveillance center. With this information a Kalman prediction of the future position for all vehicles can be estimated and used for collision avoidance.</p>

Σκοπός αυτής της διπλωματικής εργασίας είναι να αναπτυχθεί ένα μοντέλο αποφυγής συγκρόυσεων μεταξύ των οχημάτων μέσω της επικοινωνίας αυτών. Το σύστημα αυτό θα πρέπει να αναγνωρίζει τις περιπτώσεις που εγκυμονούν κίνδυνο μέσω της ανταλλαγής μηνυμάτων από τα οχήματα κάθε χρονική στιγμή και μέσα από διάφορους μηχανισμούς που επιτελούνται από αυτό, τελικά, να επεμβαίνει και να αποτρέπει τη σύγκρουση ή να ειδοποιεί τον οδηγό ώστε αυτός να αντιδράσει εγκαίρως. Για να το πετύχουμε αυτό ακολουθήσαμε τα εξής βήματα: 1. Προσομοιώσαμε τη λειτουργία μίας συσκευής GPS. 2. Σχεδιάσαμε λεκτικά και γραφικά τα μοντέλα κίνησης στα οποία θα τρέχει το σύστημά μας. 3. Ορίσαμε ένα πρωτόκολλο ανταλλαγής μηνυμάτων και προειδοποίησης σε περίπτωση συγκρουσης για αυτά τα μοντέλα κίνησης. 4. Αναπτύξαμε το σύστημα μέσω της matlab, λαμβάνοντας υπόψιν το πρωτόκολλο και τα σενάρια κίνησης των προηγούμενων βημάτων. 5. Κατασκευάσαμε μία διεπαφή εποπτίας και ελέγχου όλου του συστήματος. 6. Τέλος, κατασκευάσαμε ένα GUI ειδοποίησης του οδηγού σε περιπτώσεις κινδύνου. / Distributed traffic Control for Optimisation of the Safety Conditions.

This Master’s thesis is a pilot study that investigates different systems to drive autonomous and non-autonomous vehicles simultaneously on test tracks. The thesis includes studies of communication, positioning, collision avoidance, and techniques for surveillance of vehicles which are suitable for implementation. The investigation results in a suggested system outline. Differential GPS combined with laser scanner vision is used for vehicle state estimation (position, heading, velocity, etc.). The state information is transmitted with IEEE 802.11 to all surrounding vehicles and surveillance center. With this information a Kalman prediction of the future position for all vehicles can be estimated and used for collision avoidance.