Thesis (Ph.D)--Computing, Georgia Institute of Technology, 2009. / Committee Chair: Dellaert, Frank; Committee Member: Bobick, Aaron; Committee Member: Christensen, Henrik; Committee Member: Leonard, John; Committee Member: Rehg, James. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Thesis (MScEng)-- Stellenbosch University, 2013. / ENGLISH ABSTRACT: This thesis presents the development of a flight control system (FCS) for an unmanned, unpowered parafoil and the integration with an existing parafoil system in collaboration with a team at the University of Cape Town (UCT). The main goal of the FCS is to autonomously guide the parafoil from an arbitrary deployment position to a desired landing target. A nonlinear 8 degrees of freedom (8-DOF) parafoil model by C. Redelinghuys is incorporated into a MATLAB Simulink simulation environment. The non-linear model is numerically linearised and modal decomposition techniques are used to analyse the natural modes of motion. All modes are determined to be stable but a poorly damped lateral payload relative twist mode is present which causes large payload yaw oscillations. The FCS is divided into stability augmentation, control and guidance subcomponents. Stability augmentation is proposed in the form of a yaw rate damper which provides artificial damping for the oscillatory payload twist mode. For control, a yaw rate controller is designed with the aim of a fast response while not exciting the payload twist oscillation. Subsequently, an existing guidance method is implemented for path following. Autonomous path planning and mission control logic is created, including an energy management (EM) method to eliminate excess height and a terminal guidance (TG) phase. The TG phase is the final turn before landing and is the last chance to influence landing accuracy. A TG algorithm is implemented which generates an optimal final turn and can be replanned en route to compensate for unknown wind and other disturbances. The FCS is implemented on existing avionics, integrated with the parafoil system and verified with hardware in the loop (HIL) simulations. Flight tests are presented but are limited to remote control (RC) tests that verify the integration of the avionics and the parafoil system and test preliminary FCS components. / AFRIKAANSE OPSOMMING: Hierdie tesis dra die ontwikkeling voor van ‘n vlug-beheerstelsel (VBS) vir ’n onbemande, onaangedrewe valskerm-sweeftuig (parafoil), asook die integrasie daarvan met ’n bestaande stelsel. Die projek is in samewerking met ’n span van die Universiteit van Kaapstad (UCT) uitgevoer. Die VBS se hoof doel is om die sweeftuig outonoom vanaf ’n arbitrêre beginpunt na ’n gewensde landingsteiken te lei. ’n Nie-lineêre 8 grade van vryheid sweeftuig model deur C. Redelinghuys is in die MATLAB Simulink omgewing geïnkorporeer. Die nie-lineêre model is numeries gelineariseer om ’n lineêre model te verkry, waarna die natuurlike gedrag van die tuig geanaliseer is. ’n Swak gedempte laterale draai ossillasie van die loonvrag is geïdentifiseer. Die VBS is opgedeel in stabiliteitstoevoeging, beheer en leiding. ’n Giertempo-demper (yaw rate damper) is as stabiliteitstoevoeging om die loonvrag ossillasie kunsmatig te demp, voorgestel. ’n Giertempo-beheerder is ontwerp met die klem op ’n vinnige reaksie terwyl die opwekking van die loonvrag ossillasie terselfdetyd verhoed word. Daarna is ’n bestaande metode vir trajekvolging geïmplementeer. Outonome padbeplanning en oorhoofse vlugplan logika is ontwikkel, insluitend ’n energie-bestuur (EB) metode, om van oortollige hoogte ontslae te raak, asook ’n terminale leiding (TL) metode. Die TL fase verwys na die finale draai voor landing en is die laaste kans om die landingsakkuraatheid te beïnvloed. ’n Bestaande TL algoritme is geïmplementeer wat ’n optimale trajek genereer en in staat is om vir wind en ander versteurings te kompenseer deur die trajek deurgaans te herbeplan. Die VBS is op bestaande avionika geïmplementeer, met die sweeftuigstelsel geïntegreer en met behulp van hardeware in die lus (HIL) simulasies geverifieer. Vlugtoetse is voorgedra, maar is egter beperk tot radio beheer vlugte wat die korrekte integrasie van die avionika en die voertuig toets, asook ’n beperkte aantal voormalige VBS toetse.

We design and analyze algorithms for the following two robot navigation problems: 1. TARGET SEARCH. Given a robot located at a point s in the plane, how will a robot navigate to a goal t in the presence of unknown obstacles ? 2. LOCALIZATION. A robot is "lost" in an environment with a map of its surroundings. How will it find its true location by traveling the minimum distance ? Since efficient algorithms for these two problems will make a robot completely autonomous, they have held the interest of both robotics and computer science communities. Previous work has focussed mainly on designing competitive algorithms where the robot's performance is compared to that of an omniscient adversary. For example, a competitive algorithm for target search will compare the distance traveled by the robot with the shortest path from s to t. We analyze these problems from the worst-case perspective, which, in our view, is a more appropriate measure. Our results are : 1. For target search, we analyze an algorithm called Dynamic A*. The robot continuously moves to the goal on the shortest path which it recomputes on the discovery of obstacles. A variant of this algorithm has been employed in Mars Rover prototypes. We show that D* takes O(n log n) time on planar graphs and also show a comparable bound on arbitrary graphs. Thus, our results show that D* combines the optimistic possibility of reaching the goal very soon while competing with depth-first search within a logarithmic factor. 2. For the localization problem, worst-case analysis compares the performance of the robot with the optimal decision tree over the set of possible locations. No approximation algorithm has been known. We give a polylogarithmic approximation algorithm and also show a near-tight lower bound for the grid graphs commonly used in practice. The key idea is to plan travel on a "majority-rule map" which eliminates uncertainty and permits a link to the half-Group Steiner problem. We also extend the problem to polygonal maps by discretizing the domain using novel geometric techniques.

Incremental smoothing and mapping (iSAM) is presented, a novel approach to the simultaneous localization and mapping (SLAM) problem. SLAM is the problem of estimating an observer's position from local measurements only, while creating a consistent map of the environment. The problem is difficult because even very small errors in the local measurements accumulate over time and lead to large global errors. iSAM provides an exact and efficient solution to the SLAM estimation problem while also addressing data association. For the estimation problem, iSAM provides an exact solution by performing smoothing, which keeps all previous poses as part of the estimation problem, and therefore avoids linearization errors. iSAM uses methods from sparse linear algebra to provide an efficient incremental solution. In particular, iSAM deploys a direct equation solver based on QR matrix factorization of the naturally sparse smoothing information matrix. Instead of refactoring the matrix whenever new measurements arrive, only the entries of the factor matrix that actually change are calculated. iSAM is efficient even for robot trajectories with many loops as it performs periodic variable reordering to avoid unnecessary fill-in in the factor matrix. For the data association problem, I present state of the art data association techniques in the context of iSAM and present an efficient algorithm to obtain the necessary estimation uncertainties in real-time based on the factored information matrix. I systematically evaluate the components of iSAM as well as the overall algorithm using various simulated and real-world data sets.

Thesis (MScEng)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: Simultaneous localization and mapping (SLAM) is vital for autonomous robot navigation. The robot must build a map of its environment while tracking its own motion through that map. Although many solutions to this intricate problem have been proposed, one of the most prominent issues that still needs to be resolved is to accurately measure and track landmarks over time. In this thesis we investigate the use of stereo vision for this purpose. In order to find landmarks in images we explore the use of two feature detectors: the scale-invariant feature transform (SIFT) and speeded-up robust features (SURF). Both these algorithms find salient points in images and calculate a descriptor for each point that is invariant to scale, rotation and illumination. By using the descriptors we match these image features between stereo images and use the geometry of the system to calculate a set of 3D landmark measurements. A Taylor approximation of this transformation is used to derive a Gaussian noise model for the measurements. The measured landmarks are matched to landmarks in a map to find correspondences. We find that this process often incorrectly matches ambiguous landmarks. To find these mismatches we develop a novel outlier detection scheme based on the random sample consensus (RANSAC) framework. We use a similarity transformation for the RANSAC model and derive a probabilistic consensus measure that takes the uncertainties of landmark locations into account. Through simulation and practical tests we find that this method is a significant improvement on the standard approach of using the fundamental matrix. With accurately identified landmarks we are able to perform SLAM. We investigate the use of three popular SLAM algorithms: EKF SLAM, FastSLAM and FastSLAM 2. EKF SLAM uses a Gaussian distribution to describe the systems states and linearizes the motion and measurement equations with Taylor approximations. The two FastSLAM algorithms are based on the Rao-Blackwellized particle filter that uses particles to describe the robot states, and EKFs to estimate the landmark states. FastSLAM 2 uses a refinement process to decrease the size of the proposal distribution and in doing so decreases the number of particles needed for accurate SLAM. We test the three SLAM algorithms extensively in a simulation environment and find that all three are capable of very accurate results under the right circumstances. EKF SLAM displays extreme sensitivity to landmark mismatches. FastSLAM, on the other hand, is considerably more robust against landmark mismatches but is unable to describe the six-dimensional state vector required for 3D SLAM. FastSLAM 2 offers a good compromise between efficiency and accuracy, and performs well overall. In order to evaluate the complete system we test it with real world data. We find that our outlier detection algorithm is very effective and greatly increases the accuracy of the SLAM systems. We compare results obtained by all three SLAM systems, with both feature detection algorithms, against DGPS ground truth data and achieve accuracies comparable to other state-of-the-art systems. From our results we conclude that stereo vision is viable as a sensor for SLAM. / AFRIKAANSE OPSOMMING: Gelyktydige lokalisering en kartering (simultaneous localization and mapping, SLAM) is ’n noodsaaklike proses in outomatiese robot-navigasie. Die robot moet ’n kaart bou van sy omgewing en tegelykertyd sy eie beweging deur die kaart bepaal. Alhoewel daar baie oplossings vir hierdie ingewikkelde probleem bestaan, moet een belangrike saak nog opgelos word, naamlik om landmerke met verloop van tyd akkuraat op te spoor en te meet. In hierdie tesis ondersoek ons die moontlikheid om stereo-visie vir hierdie doel te gebruik. Ons ondersoek die gebruik van twee beeldkenmerk-onttrekkers: scale-invariant feature transform (SIFT) en speeded-up robust features (SURF). Altwee algoritmes vind toepaslike punte in beelde en bereken ’n beskrywer vir elke punt wat onveranderlik is ten opsigte van skaal, rotasie en beligting. Deur die beskrywer te gebruik, kan ons ooreenstemmende beeldkenmerke soek en die geometrie van die stelsel gebruik om ’n stel driedimensionele landmerkmetings te bereken. Ons gebruik ’n Taylor- benadering van hierdie transformasie om ’n Gaussiese ruis-model vir die metings te herlei. Die gemete landmerke se beskrywers word dan vergelyk met dié van landmerke in ’n kaart om ooreenkomste te vind. Hierdie proses maak egter dikwels foute. Om die foutiewe ooreenkomste op te spoor het ons ’n nuwe uitskieterherkenningsalgoritme ontwikkel wat gebaseer is op die RANSAC-raamwerk. Ons gebruik ’n gelykvormigheidstransformasie vir die RANSAC-model en lei ’n konsensusmate af wat die onsekerhede van die ligging van landmerke in ag neem. Met simulasie en praktiese toetse stel ons vas dat die metode ’n beduidende verbetering op die standaardprosedure, waar die fundamentele matriks gebruik word, is. Met ons akkuraat geïdentifiseerde landmerke kan ons dan SLAM uitvoer. Ons ondersoek die gebruik van drie SLAM-algoritmes: EKF SLAM, FastSLAM en FastSLAM 2. EKF SLAM gebruik ’n Gaussiese verspreiding om die stelseltoestande te beskryf en Taylor-benaderings om die bewegings- en meetvergelykings te lineariseer. Die twee FastSLAM-algoritmes is gebaseer op die Rao-Blackwell partikelfilter wat partikels gebruik om robottoestande te beskryf en EKF’s om die landmerktoestande af te skat. FastSLAM 2 gebruik ’n verfyningsproses om die grootte van die voorstelverspreiding te verminder en dus die aantal partikels wat vir akkurate SLAM benodig word, te verminder. Ons toets die drie SLAM-algoritmes deeglik in ’n simulasie-omgewing en vind dat al drie onder die regte omstandighede akkurate resultate kan behaal. EKF SLAM is egter baie sensitief vir foutiewe landmerkooreenkomste. FastSLAM is meer bestand daarteen, maar kan nie die sesdimensionele verspreiding wat vir 3D SLAM vereis word, beskryf nie. FastSLAM 2 bied ’n goeie kompromie tussen effektiwiteit en akkuraatheid, en presteer oor die algemeen goed. Ons toets die hele stelsel met werklike data om dit te evalueer, en vind dat ons uitskieterherkenningsalgoritme baie effektief is en die akkuraatheid van die SLAM-stelsels beduidend verbeter. Ons vergelyk resultate van die drie SLAM-stelsels met onafhanklike DGPS-data, wat as korrek beskou kan word, en behaal akkuraatheid wat vergelykbaar is met ander toonaangewende stelsels. Ons resultate lei tot die gevolgtrekking dat stereo-visie ’n lewensvatbare sensor vir SLAM is.