This thesis focuses on the theory and implementation of visual navigation techniques for Autonomous Air Vehicles in outdoor environments. The target of this study is to fuse and cooperatively develop an incremental map for multiple air vehicles under the application of Simultaneous Location and Mapping (SLAM). Without loss of generality, two unmanned air vehicles (UAVs) are investigated for the generation of ground maps from current and a priori data. Each individual UAV is equipped with inertial navigation systems and external sensitive elements which can provide the possible mixture of visible, thermal infrared (IR) image sensors, with a special emphasis on the stereo digital cameras. The corresponding stereopsis is able to provide the crucial three-dimensional (3-D) measurements. Therefore, the visual aerial navigation problems tacked here are interpreted as stereo vision based SLAM (vSLAM) for both single and multiple UAVs applications. To begin with, the investigation is devoted to the methodologies of feature extraction. Potential landmarks are selected from airborne camera images as distinctive points identified in the images are the prerequisite for the rest. Feasible feature extraction algorithms have large influence over feature matching/association in 3-D mapping. To this end, effective variants of scale-invariant feature transform (SIFT) algorithms are employed to conduct comprehensive experiments on feature extraction for both visible and infrared aerial images. As the UAV is quite often in an uncertain location within complex and cluttered environments, dense and blurred images are practically inevitable. Thus, it becomes a challenge to find feature correspondences, which involves feature matching between 1st and 2nd image in the same frame, and data association of mapped landmarks and camera measurements. A number of tests with different techniques are conducted by incorporating the idea of graph theory and graph matching. The novel approaches, which could be tagged as classification and hypergraph transformation (HGTM) based respectively, have been proposed to solve the data association in stereo vision based navigation. These strategies are then utilised and investigated for UAV application within SLAM so as to achieve robust matching/association in highly cluttered environments. The unknown nonlinearities in the system model, including noise would introduce undesirable INS drift and errors. Therefore, appropriate appraisals on the pros and cons of various potential data filtering algorithms to resolve this issue are undertaken in order to meet the specific requirements of the applications. These filters within visual SLAM were put under investigation for data filtering and fusion of both single and cooperative navigation. Hence updated information required for construction and maintenance of a globally consistent map can be provided by using a suitable algorithm with the compromise between computational accuracy and intensity imposed by the increasing map size. The research provides an overview of the feasible filters, such as extended Kalman Filter, extended Information Filter, unscented Kalman Filter and unscented H Infinity Filter. As visual intuition always plays an important role for humans to recognise objects, research on 3-D mapping in textures is conducted in order to fulfil the purpose of both statistical and visual analysis for aerial navigation. Various techniques are proposed to smooth texture and minimise mosaicing errors during the reconstruction of 3-D textured maps with vSLAM for UAVs. Finally, with covariance intersection (CI) techniques adopted on multiple sensors, various cooperative and data fusion strategies are introduced for the distributed and decentralised UAVs for Cooperative vSLAM (C-vSLAM). Together with the complex structure of high nonlinear system models that reside in cooperative platforms, the robustness and accuracy of the estimations in collaborative mapping and location are achieved through HGTM association and communication strategies. Data fusion among UAVs and estimation for visual navigation via SLAM were impressively verified and validated in conditions of both simulation and real data sets.

Thesis (MScEng)--Stellenbosch University, 2012 / ENGLISH ABSTRACT: This thesis presents the design and implementation of an autonomous navigational system and the automation of a practical demonstrator vehicle. It validates the proposed navigation architecture using simple functional navigational modules on the said vehicle. The proposed navigation architecture is a hierarchical structure, with a mission planner at the top, followed by the route planner, the path planner and a vehicle controller with the vehicle hardware at the base. A vehicle state estimator and mapping module runs in parallel to provide feedback data. The controls of an all terrain vehicle are electrically actuated and equipped with feedback sensors to form a complete drive-by-wire solution. A steering controller and velocity control state machine are designed and implemented on an existing on-board controller that includes a six degrees-of-freedom kinematic state estimator. A lidar scanner detects obstacles. The lidar data is mapped in real time to a local three-dimensional occupancy grid using a Bayesian update process. Each lidar beam is projected within the occupancy grid and the occupancy state of a ected cells is updated. A lidar simulation environment is created to test the mapping module before practical implementation. For planning purposes, the three-dimensional occupancy grid is converted to a two-dimensional drivability map. The path planner is an adapted rapidly exploring random tree (RRT) planner, that assumes Dubins car kinematics for the vehicle. The path planner optimises a cost function based on path length and a risk factor that is derived from the drivability map. A simple mission planner that accepts user-de ned waypoints as objectives is implemented. Practical tests veri ed the potential of the navigational structure implemented in this thesis. / AFRIKAANSE OPSOMMING: In hierdie tesis word die ontwerp en implementering van 'n outonome navigasiestelsel weergegee, asook die outomatisering van 'n praktiese demonstrasievoertuig. Dit regverdig die voorgestelde navigasie-argitektuur op die bogenoemde voertuig deur gebruik te maak van eenvoudige, funksionele navigasie-modules. Die voorgestelde navigasie-argitektuur is 'n hi erargiese struktuur, met die missie-beplanner aan die bo-punt, gevolg deur die roetebeplanner, die padbeplanner en voertuigbeheerder, met die voertuighardeware as basisvlak. 'n Voertuigtoestandsafskatter en karteringsmodule loop in parallel om terugvoer te voorsien. Die kontroles van 'n vierwiel-motor ets is elektries geaktueer en met terugvoersensors toegerus om volledig rekenaarbeheerd te wees. 'n Stuur-beheerder en 'n snelheid-toestandmasjien is ontwerp en ge mplementeer op 'n bestaande aanboordverwerker wat 'n kinematiese toestandsafskatter in ses grade van vryheid insluit. 'n Lidar-skandeerder registreer hindernisse. Die lidar-data word in re ele tyd na 'n lokale drie-dimensionele besettingsrooster geprojekteer deur middel van 'n Bayesiese opdateringsproses. Elke lidar-straal word in die besettingsrooster geprojekteer en die besettingstoestand van betrokke selle word opdateer. 'n Lidar-simulasie-omgewing is geskep om die karteringsmodule te toets voor dit ge mplementeer word. Die drie-dimensionele besettingsrooster word na 'n twee-dimensionele rybaarheidskaart verwerk vir beplanningsdoeleindes. Die padbeplanner is 'n aangepaste spoedig-ontdekkende-lukrake-boom en neem Dubinskar kinematika vir die voertuig aan. Die padbeplanner optimeer 'n koste-funksie, gebaseer op padlengte en 'n risiko-faktor, wat vanaf die rybaarheidskaart verkry word. 'n Eenvoudige missie-beplanner, wat via-punte as doelstellings neem, is ge mplementeer. Praktiese toetsritte veri eer die potensiaal van die navigasiestruktuur, soos hier beskryf.

Veículos autônomos terrestres são um tipo de veículo motorizado guiado de forma autônoma por um sistema computacional, sem necessidade de intervenção humana. Esta pesquisa analisa a Tomada de Decisão autônoma necessária para este tipo de veículo, assim como os processos de navegação e as estruturas de dados que a suportam. Sobre esta análise propõe-se uma arquitetura de Tomada de Decisão para navegação autônoma baseada em dois ideias principais: a sistematização das fontes de dados com as quais o veículo deve interagir em sua navegação em uma hierarquia de prioridades de tratamento e o desenvolvimento de uma estrutura de dados chamada de Grade de Prioridades que permite definir para qual região do ambiente o veículo deve se locomover. Para suportar a arquitetura, formaliza-se um conjunto de processos recomendados de navegação robótica (percepção, posicionamento, planejamento e estratégia de movimento), organizados para suportar a integração com recursos de outras pesquisas do segmento da Robótica Móvel. Para validação da arquitetura, desenvolve-se um sistema de navegação robótica, integrada à uma plataforma robótica real, e realiza-se um conjunto de testes para simular o comportamento da arquitetura em situações de navegação específicas. / Autonomous ground vehicles are a type of motor vehicle autonomously guided by a computer system without human intervention. This research analyzes the autonomous decision making required for this type of vehicle as well as the processes of navigation and data structures that support it. On this analysis, is proposed an architecture of decision making for autonomous navigation based on two fundamental ideas: the systematization of data sources with which a vehicle must interact in their navigation in a hierarchy of priorities and the development of a special data structure called Grid Priorities that defines which region of the environment the vehicle must be moved. Supporting the architecture, a set of processes for robotic navigation (perception, positioning, planning and motion strategy) are proposed and organized to support integration with other research resources in the segment of Mobile Robotics. For validate the architecture, is developed a system of robotic navigation, integrated with a real robotic platform, and is performed a set of tests to simulate the behavior of the architecture in specific situations of navigation.

O emprego de veículos autônomos é uma prática comumente adotada para a melhoria da produtividade no setor agrícola. No entanto, o custo computacional é um fator limitante na implementação desses dispositivos autônomos. A alternativa apresentada neste trabalho consistiu no desenvolvimento de um dispositivo de hardware dedicado para a navegação de robôs móveis agrícolas, o qual indica áreas navegáveis e não navegáveis, além do ângulo de inclinação do veículo em relação à linha de plantio. O desenvolvimento do projeto foi baseado em um método de extração de características visuais locais por meio do processamento de imagens coloridas obtidas por uma câmera de vídeo. O circuito foi implementado por meio de uma ferramenta de desenvolvimento baseado em um FPGA de baixo custo. O circuito consiste nas etapas de classificação, processamento morfológico e extração das linhas de navegação. Na primeira etapa, os pixels são classificados a partir do modelo de cores HSL em classes que representam as áreas passíveis e não passíveis de navegação. Posteriormente, a etapa de processamento morfológico realiza as tarefas de filtragem, agrupamento e extração de bordas. O processamento morfológico é realizado por meio de um arranjo de unidades de processamento dedicadas. Cada unidade pode realizar uma operação básica de morfologia matemática. O elemento estruturante utilizado na operação, bem como a operação realizada pela unidade, é configurado por meio de parâmetros do projeto. O processo de extração das linhas de orientação é realizado por meio do método de regressão linear por mínimos quadrados. A arquitetura proposta no projeto permitiu o processamento em tempo real de imagens para a aplicação de navegação autônoma de robôs móveis em ambientes agrícolas. / The use of autonomous vehicles is a generally adopted practice to improve the productivity in the agriculture sector. However, the computer requirements are a limiting factor for implementation of these autonomous devices. The alternative shown in this paper is the design of a dedicated hardware for the autonomous agricultural robot navigation. The project development was based on a local visual feature extraction method by processing digital images obtained from a color video camera. The circuit was implemented through a development tool based on a low cost FPGA. The circuit consists of stages of classification, morphological processing and guidance line extraction. In the first stage, the pixels are classified through HSL color model into classes that represent suitable and unsuitable area for navigation. Then, the morphological processing stage performs filtering, grouping and edge detection tasks. The morphological processing is carried out by an arrangement of dedicated processing units. Each unit can perform a basic operation of mathematical morphology. The structuring element used in the operation and the operation performed by the unit are configured through project parameters. The guidance line extraction process is performed through the linear regression method by least square. The architecture proposed in the design allowed the real-time image processing in autonomous robot navigation applications in agricultural environments.

O emprego de veículos autônomos é uma prática comumente adotada para a melhoria da produtividade no setor agrícola. No entanto, o custo computacional é um fator limitante na implementação desses dispositivos autônomos. A alternativa apresentada neste trabalho consistiu no desenvolvimento de um dispositivo de hardware dedicado para a navegação de robôs móveis agrícolas, o qual indica áreas navegáveis e não navegáveis, além do ângulo de inclinação do veículo em relação à linha de plantio. O desenvolvimento do projeto foi baseado em um método de extração de características visuais locais por meio do processamento de imagens coloridas obtidas por uma câmera de vídeo. O circuito foi implementado por meio de uma ferramenta de desenvolvimento baseado em um FPGA de baixo custo. O circuito consiste nas etapas de classificação, processamento morfológico e extração das linhas de navegação. Na primeira etapa, os pixels são classificados a partir do modelo de cores HSL em classes que representam as áreas passíveis e não passíveis de navegação. Posteriormente, a etapa de processamento morfológico realiza as tarefas de filtragem, agrupamento e extração de bordas. O processamento morfológico é realizado por meio de um arranjo de unidades de processamento dedicadas. Cada unidade pode realizar uma operação básica de morfologia matemática. O elemento estruturante utilizado na operação, bem como a operação realizada pela unidade, é configurado por meio de parâmetros do projeto. O processo de extração das linhas de orientação é realizado por meio do método de regressão linear por mínimos quadrados. A arquitetura proposta no projeto permitiu o processamento em tempo real de imagens para a aplicação de navegação autônoma de robôs móveis em ambientes agrícolas. / The use of autonomous vehicles is a generally adopted practice to improve the productivity in the agriculture sector. However, the computer requirements are a limiting factor for implementation of these autonomous devices. The alternative shown in this paper is the design of a dedicated hardware for the autonomous agricultural robot navigation. The project development was based on a local visual feature extraction method by processing digital images obtained from a color video camera. The circuit was implemented through a development tool based on a low cost FPGA. The circuit consists of stages of classification, morphological processing and guidance line extraction. In the first stage, the pixels are classified through HSL color model into classes that represent suitable and unsuitable area for navigation. Then, the morphological processing stage performs filtering, grouping and edge detection tasks. The morphological processing is carried out by an arrangement of dedicated processing units. Each unit can perform a basic operation of mathematical morphology. The structuring element used in the operation and the operation performed by the unit are configured through project parameters. The guidance line extraction process is performed through the linear regression method by least square. The architecture proposed in the design allowed the real-time image processing in autonomous robot navigation applications in agricultural environments.

<p>The field of autonomous vehicle navigation and localization is a highly active research</p><p>topic. The aim of this thesis is to evaluate the feasibility to use outdoor visual navigation in a semi-structured environment. The goal is to develop a visual navigation system for an autonomous golf ball collection vehicle operating on driving ranges.</p><p>The image feature extractors SIFT and PCA-SIFT was evaluated on an image database</p><p>consisting of images acquired from 19 outdoor locations over a period of several weeks to</p><p>allow different environmental conditions. The results from these tests show that SIFT-type</p><p>feature extractors are able to find and match image features with high accuracy. The results also show that this can be improved further by a combination of a lower nearest neighbour threshold and an outlier rejection method to allow more matches and a higher ratio of correct matches. Outliers were found and rejected by fitting the data to a homography model with the RANSAC robust estimator algorithm. </p><p>A simulator was developed to evaluate the suggested system with respect to pixel noise from illumination changes, weather and feature position accuracy as well as the distance to features, path shapes and the visual servoing target image (milestone) interval. The system was evaluated on a total of 3 paths, 40 test combinations and 137km driven. The results show that with the relatively simple visual servoing navigation system it is possible to use mono-vision as a sole sensor and navigate semi-structured outdoor environments such as driving ranges.</p>

This thesis presents a novel design paradigm of mobile robots: the Hybrid Mobile Robot system. It consists of a combination of parallel and serially connected links resulting in a hybrid mechanism that includes a mobile robot platform for locomotion and a manipulator arm for manipulation, both interchangeable functionally. All state-of-the-art mobile robots have a separate manipulator arm module attached on top of the mobile platform. The platform provides mobility and the arm provides manipulation. Unlike them, the new design has the ability to interchangeably provide locomotion and manipulation capability, both simultaneously. This was accomplished by integrating the locomotion platform and the manipulator arm as one entity rather than two separate and attached modules. The manipulator arm can be used as part of the locomotion platform and vice versa. This paradigm significantly enhances functionality. The new mechanical design was analyzed with a virtual prototype that was developed with MSC Adams Software. Simulations were used to study the robot’s enhanced mobility through animations of challenging tasks. Moreover, the simulations were used to select nominal robot parameters that would maximize the arm’s payload capacity, and provide for locomotion over unstructured terrains and obstacles, such as stairs, ditches and ramps. The hybrid mobile robot also includes a new control architecture based on embedded on-board wireless communication network between the robot’s links and modules such as the actuators and sensors. This results in a modular control architecture since no cable connections are used between the actuators and sensors in each of the robot links. This approach increases the functionality of the mobile robot also by providing continuous rotation of each link constituting the robot. The hybrid mobile robot’s novel locomotion and manipulation capabilities were successfully experimented using a complete physical prototype. The experiments provided test results that support the hypothesis on the qualitative and quantitative performance of the mobile robot in terms of its superior mobility, manipulation, dexterity, and ability to perform very challenging tasks. The robot was tested on an obstacle course consisting of various test rigs including man–made and natural obstructions that represent the natural environments the robot is expected to operate on.

This thesis presents a novel design paradigm of mobile robots: the Hybrid Mobile Robot system. It consists of a combination of parallel and serially connected links resulting in a hybrid mechanism that includes a mobile robot platform for locomotion and a manipulator arm for manipulation, both interchangeable functionally. All state-of-the-art mobile robots have a separate manipulator arm module attached on top of the mobile platform. The platform provides mobility and the arm provides manipulation. Unlike them, the new design has the ability to interchangeably provide locomotion and manipulation capability, both simultaneously. This was accomplished by integrating the locomotion platform and the manipulator arm as one entity rather than two separate and attached modules. The manipulator arm can be used as part of the locomotion platform and vice versa. This paradigm significantly enhances functionality. The new mechanical design was analyzed with a virtual prototype that was developed with MSC Adams Software. Simulations were used to study the robot’s enhanced mobility through animations of challenging tasks. Moreover, the simulations were used to select nominal robot parameters that would maximize the arm’s payload capacity, and provide for locomotion over unstructured terrains and obstacles, such as stairs, ditches and ramps. The hybrid mobile robot also includes a new control architecture based on embedded on-board wireless communication network between the robot’s links and modules such as the actuators and sensors. This results in a modular control architecture since no cable connections are used between the actuators and sensors in each of the robot links. This approach increases the functionality of the mobile robot also by providing continuous rotation of each link constituting the robot. The hybrid mobile robot’s novel locomotion and manipulation capabilities were successfully experimented using a complete physical prototype. The experiments provided test results that support the hypothesis on the qualitative and quantitative performance of the mobile robot in terms of its superior mobility, manipulation, dexterity, and ability to perform very challenging tasks. The robot was tested on an obstacle course consisting of various test rigs including man–made and natural obstructions that represent the natural environments the robot is expected to operate on.

The field of autonomous vehicle navigation and localization is a highly active research topic. The aim of this thesis is to evaluate the feasibility to use outdoor visual navigation in a semi-structured environment. The goal is to develop a visual navigation system for an autonomous golf ball collection vehicle operating on driving ranges. The image feature extractors SIFT and PCA-SIFT was evaluated on an image database consisting of images acquired from 19 outdoor locations over a period of several weeks to allow different environmental conditions. The results from these tests show that SIFT-type feature extractors are able to find and match image features with high accuracy. The results also show that this can be improved further by a combination of a lower nearest neighbour threshold and an outlier rejection method to allow more matches and a higher ratio of correct matches. Outliers were found and rejected by fitting the data to a homography model with the RANSAC robust estimator algorithm. A simulator was developed to evaluate the suggested system with respect to pixel noise from illumination changes, weather and feature position accuracy as well as the distance to features, path shapes and the visual servoing target image (milestone) interval. The system was evaluated on a total of 3 paths, 40 test combinations and 137km driven. The results show that with the relatively simple visual servoing navigation system it is possible to use mono-vision as a sole sensor and navigate semi-structured outdoor environments such as driving ranges.

In this thesis, I study the computational advantages of the allocentric represen- tation as compared to the egocentric representation for autonomous local navigation. Whereas in the allocentric framework, all variables of interest are represented with respect to a coordinate frame attached to an object in the scene, in the egocentric one, they are always represented with respect to the robot frame at each time step. In contrast with well-known results in the Simultaneous Localization and Mapping literature, I show that the amounts of nonlinearity of these two representations, where poses are elements of Lie-group manifolds, do not affect the accuracy of Gaussian- based filtering methods for perception at both the feature level and the object level. Furthermore, although these two representations are equivalent at the object level, the allocentric filtering framework is better than the egocentric one at the feature level due to its advantages in the marginalization process. Moreover, I show that the object- centric perspective, inspired by the allocentric representation, enables novel linear- time filtering algorithms, which significantly outperform state-of-the-art feature-based filtering methods with a small trade-off in accuracy due to a low-rank approximation. Finally, I show that the allocentric representation is also better than the egocentric representation in Model Predictive Control for local trajectory planning and obstacle avoidance tasks.