The present investigation focuses on the development of computationally efficient path planning algorithms for autonomous ground vehicles. The approach selected is based on a heuristic hill climbing local search. The cost index employed incorporates a traversability cost average, which offers two primary benefits: 1) the average extends the region of knowledge of the search algorithm, increasing optimality of the solution; and 2) the avoidance of hazardous regions is added to the decision making process. A binary traversability map representation is first utilized to analyze the performance of the enhanced heuristic hill climbing algorithm in comparison to the more traditional techniques. Next, the search algorithm is applied to a multi-valued traversability map to test the capabilities of the algorithm over natural terrain. For this purpose, a digital elevation map is automatically processed to obtain multi-valued traversability values through the de nition of a roughness, inclination and step index. The complete path planning architecture for natural terrain then consists of a three step approach, computation of the multi-valued traversability map, implementation of the enhanced heuristic hill climbing search algorithm, and a path relaxation step. This last step is employed to fine-tune and smooth the trajectory, eliminating sharp turns caused by the regular characteristics of the search space. / text

To avoid getting stuck or causing damage to a vehicle or its surroundings a driver must be able to identify obstacles and adapt speed to ground conditions. An automatically controlled vehicle must be able to handle these identifications and adjustments by itself using sensors, actuators and control software. By storing properties of the surroundings in a map, a vehicle revisiting an area can benefit from prior information. Rough ground may cause oscillations in the vehicle chassis. These can be measured by on-board motion sensors. For obstacle detection, a representation of the geometry of the surroundings can be created using range sensors. Information on where it is suitable to drive, called traversability, can be generated based on these kinds of sensor measurements. In this work, real semi-autonomous mobile robots have been used to create traverasbility maps in both simulated and real outdoor environments. Seeking out problems through experiments and implementing algorithms in an attempt to solve them has been the core of the work. Finding large obstacles in the vicinity of a vehicle is seldom a problem; accurately identifying small near-ground obstacles is much more difficult, however. The work additionally includes both high-level path planning, where no obstacle details are considered, and more detailed planning for finding an obstacle free path. How prior maps can be matched and merged in preparation for path planning operations is also shown. To prevent collisions with unforeseen objects, up-to-date traversability information is used in local-area navigation and obstacle avoidance.

Off-road autonomy is a challenging topic that requires robust systems to both understand and navigate complex environments. While on-road autonomy has seen a major expansion in recent years in the consumer space, off-road systems are mostly relegated to niche applications. However, these applications can provide safety and navigation to dangerous areas that are the most suited for autonomy tasks. Traversability analysis is at the core of many of the algorithms employed in these topics. In this thesis, a Clearpath Robotics Jackal vehicle is equipped with a 3D Ouster laser scanner to define and traverse off-road environments. The Mississippi State University Autonomous Vehicle Simulator (MAVS) and the Navigating All Terrains Using Robotic Exploration (NATURE) autonomy stack are used in conjunction with the small-scale vehicle platform to traverse uneven terrain and collect data. Additionally, the NATURE stack is used as a point of comparison between a MAVS simulated and physical Clearpath Robotics Jackal vehicle in testing.

Scene perception and traversability analysis are real challenges for autonomous driving systems. In the context of off-road autonomy, there are additional challenges due to the unstructured environments and the existence of various vegetation types. It is necessary for the Autonomous Ground Vehicles (AGVs) to be able to identify obstacles and load-bearing surfaces in the terrain to ensure a safe navigation (McDaniel et al. 2012). The presence of vegetation in off-road autonomy applications presents unique challenges for scene understanding: 1) understory vegetation makes it difficult to detect obstacles or to identify load-bearing surfaces; and 2) trees are usually regarded as obstacles even though only trunks of the trees pose collision risk in navigation. The overarching goal of this dissertation was to study traversability analysis in unstructured forested terrains for off-road autonomy using LIDAR data. More specifically, to address the aforementioned challenges, this dissertation studied the impacts of the understory vegetation density on the solid obstacle detection performance of the off-road autonomous systems. By leveraging a physics-based autonomous driving simulator, a classification-based machine learning framework was proposed for obstacle detection based on point cloud data captured by LIDAR. Features were extracted based on a cumulative approach meaning that information related to each feature was updated at each timeframe when new data was collected by LIDAR. It was concluded that the increase in the density of understory vegetation adversely affected the classification performance in correctly detecting solid obstacles. Additionally, a regression-based framework was proposed for estimating the understory vegetation density for safe path planning purposes according to which the traversabilty risk level was regarded as a function of estimated density. Thus, the denser the predicted density of an area, the higher the risk of collision if the AGV traversed through that area. Finally, for the trees in the terrain, the dissertation investigated statistical features that can be used in machine learning algorithms to differentiate trees from solid obstacles in the context of forested off-road scenes. Using the proposed extracted features, the classification algorithm was able to generate high precision results for differentiating trees from solid obstacles. Such differentiation can result in more optimized path planning in off-road applications.

The focus of this dissertation is to improve autonomous navigation in unstructured terrain conditions, with specific application to unmanned casualty extraction in disaster scenarios. Robotic systems are being widely employed for search and rescue applications, especially in disaster scenarios. But a majority of these are focused solely on the search aspect of the problem. This dissertation proposes a conceptual design of a Semi-Autonomous Victim Extraction Robot (SAVER) capable of safe and effective unmanned casualty extraction, thereby reducing the risk to the lives of first responders. In addition, the proposed design addresses the limitations of existing state-of-the-art rescue robots specifically in the aspect of head and neck stabilization as well as fast and safe evacuation. One of the primary capabilities needed for effective casualty extraction is reliable navigation in unstructured terrain conditions. Autonomous navigation in unstructured terrain, particularly for systems with tracked locomotion mode involves unique challenges in path planning and trajectory tracking. The dynamics of robot-terrain interaction, along with additional factors such as slip experienced by the vehicle, slope of the terrain, and actuator limitations of the robotic system, need to be taken into consideration. To realize these capabilities, this dissertation proposes a hybrid navigation architecture that employs a physics engine to perform fast and accurate state expansion inside a graph-based planner. Tracked skid-steer systems experience significant slip, especially while turning. This greatly affects the trajectory tracking accuracy of the robot. In order to enable efficient trajectory tracking in varying terrain conditions, this dissertation proposes the use of an active disturbance rejection controller. The proposed controller is capable of estimating and counter acting the effects of slip in real-time to improve trajectory tracking. As an extension of the above application, this dissertation also proposes the use of support vector machine architecture to perform terrain identification, solely based on the estimated slip parameters. Combining all of the above techniques, an overall architecture is proposed to assist and inform tele-operation of tracked robotic systems in unstructured terrain conditions. All of the above proposed techniques have been validated through simulations and experiments in indoor and simple outdoor terrain conditions. / Doctor of Philosophy / This dissertation explores ways to improve autonomous navigation in unstructured terrain conditions, with specific applications to unmanned casualty extraction in disaster scenarios. Search and rescue applications often put the lives of first responders at risk. Using robotic systems for human rescue in disaster scenarios can keep first responders out of danger. To enable safe robotic casualty extraction, this dissertation proposes a novel rescue robot design concept named SAVER. The proposed design concept consists of several subsystems including a declining stretcher bed, head and neck support system, and robotic arms that conceptually enable safe casualty manipulation and extraction based on high-level commands issued by a remote operator. In order to enable autonomous navigation of the proposed conceptual system in challenging outdoor terrain conditions, this dissertation proposes improvements in planning, trajectory tracking control and terrain estimation. The proposed techniques are able to take into account the dynamic effects of robot-terrain interaction including slip experienced by the vehicle, slope of the terrain and actuator limitations. The proposed techniques have been validated through simulations and experiments in indoor and simple outdoor terrain conditions. The applicability of the above techniques in improving tele-operation of rescue robotic systems in unstructured terrain is also discussed at the end of this dissertation.

Les travaux de cette thèse adressent la problématique de la coopération aéro-terrestre pour la cartographie de l’espace navigable. La nécessité d’une carte pour la navigation et la planification de chemins pour les robots terrestres n’est plus à prouver. L’utilisation d’une coopération aéro-terrestre pour créer une carte navigable à destination du robot terrestre a plusieurs intérêts. Premièrement, le drone peut cartographier rapidement une zone grâce à son champ de vision étendu et ses capacités de déplacement. Deuxièmement, la fusion des cartes créées par ces deux agents permet de tirer le meilleur profit des deux points de vue : la cohérence de la vue aérienne globale et la précision de la vue terrestre locale. Pour répondre à cette problématique, nous proposons une méthode qui s’appuie sur la création de cartes hybrides et leur fusion. Les cartes sont construites en utilisant le squelette de l’espace navigable terrestre comme support d’un graphe contenant également des informations métriques locales de l’environnement. La mise en correspondance des cartes aérienne et terrestre s’effectue à l’aide d’un appariement point à point déterminé grâce à une mesure de dissimilarité appropriée. Cette dernière est définie pour répondre aux critères d’invariance et de discriminance dans ce contexte. La mise en correspondance est ensuite utilisée pour fusionner les cartes entre elles. Les cartes fusionnées peuvent être utilisées par le robot au sol pour effectuer sa mission. Elles permettent également de propager des informations telles que des coordonnées GPS à des robots et dans des lieux où ce dispositif n’est pas disponible. Des expérimentations en environnements virtuels et réels sont réalisées pour valider cette approche et en tracer les perspectives. / This work aims to study the problem of air-ground robotic cooperation for collaborative traversability mapping. The need for a map for navigation and path planning for terrestrial robots is no longer to be proven. The use of air-ground cooperation to create a navigable map for the ground robots has several interests. First, the drone can quickly map an area through its large field of vision and traveling capabilities. Second, the fusion of maps based on these two agents makes it possible to draw the best benefits from both points of views: the coherence of the global aerial view and the accuracy of the local ground view. To answer this problem, we propose a method that relies on the construction of a unified model of hybrid maps and their fusion.The maps are built using the skeleton of the traversability space as a support for graphs also containing local metric and potentialy semantic information of the environment. The maching of aerial and ground maps is done using a point to point correlation based on an appropriate dissimilarity measure. This measure is defined to meet invariance and discriminance criteria. The matching is then used to merge the maps into an augmented traversability map. The merged maps can be used by the ground robot to perform its mission. They also make it possible to deploy information such as GPS coordinates to robots in GPS denied environments. Experiments in virtual and real world environments have been carried out to validate this approach and map out future perspetives.

Abstract Cross-country route optimization, particularly from a pedestrian’s perspective, is a relatively uncommon research topic that has many application possibilities. In this research, route optimization is examined in the context of forest inventories. The background for the research is the change in the forest data collection practices carried out by the Finnish Forest Centre. In this new inventory procedure, targets to be inventoried in the field are often located far apart from each other. The research indicated that the collection of data from sparsely distributed targets is comparatively inefficient. In order to address this issue, a method allowing the traversability of cross-country terrain to be expressed in a numeric form was developed such that it makes cross-country route optimization possible. In addition, a method for the determination of a route inside an areal object, allowing the collection of reliable inventory data from the target, was constructed in the study. Finally, the route optimization method developed in the study was tested in actual field work. The main hypothesis for the research was that it is possible to apply the route optimization method to forest inventory, and that it would be considered useful. The result of the study was that the method is, indeed, suitable for forest data collection. However, the results also suggested that route optimization does not necessarily make the work more efficient, but its utility depends on the qualities of the field workers and the area where the targets are located. The results have both theoretical and practical significance. The route optimization system constructed in the study is the most accurate national system realized thus far which has also been tested and evaluated in actual field work. A number of ancillary GIS-based analyses for route optimization were also developed in the study, and they turned out to be suitable for the calculation of inventory routes for field workers. A new route optimization problem, coined as the Areal Inventory Problem (AIP), was defined during the research. While the route optimization procedure developed in the study can be put into operation in the forest data collection practices of the Finnish Forest Centre, many of its principles are also applicable to purposes outside the domain of forestry. Data needed in other applications can be tailored using the methods presented in this research. Several prospects and needs for further research and development were recognized. By addressing these questions, the route optimization procedure can be further improved, while also strengthening the theoretical knowledge concerning cross-country route optimization. / Tiivistelmä Reitinoptimointi maastossa, etenkin jalankulkijan näkökulmasta, on melko vähän tutkittu aihe, jolla on erilaisia sovellusmahdollisuuksia. Tässä tutkimuksessa reitinoptimointia on tarkasteltu metsäninventoinnin näkökulmasta. Tutkimuksen taustana on Suomen metsäkeskuksen metsävaratiedon keruun menetelmien uudistuminen, jonka myötä maastossa inventoidaan hajallaan sijaitsevia kohteita. Tutkimuksessa havaittiin, että hajallaan sijaitsevien kohteiden inventointi on melko tehotonta. Tämän vuoksi kehitettiin menetelmä, jossa maaston kulkukelpoisuutta voidaan kuvata numeerisessa muodossa niin, että se mahdollistaa reitinoptimoinnin. Lisäksi luotiin menetelmä, jolla voidaan tuottaa inventointireitti aluemaisen kohteen sisälle niin, että kohteelta voidaan kerätä riittävän luotettavat tiedot. Lopuksi menetelmää testattiin metsävaratiedon keruun tuotantotyössä. Hypoteesina oli, että reitinoptimointia on mahdollista soveltaa metsäninventoinnissa ja että menetelmä koettaisiin hyödylliseksi. Tutkimuksessa vahvistettiin menetelmän soveltuvuus metsäninventointiin. Samalla havaittiin, ettei reitinoptimointia voida aukottomasti todistaa työtä tehostavaksi, vaan sen hyödyllisyys riippuu maastotyöntekijän ja maastotyöalueen ominaisuuksista. Tutkimustuloksilla on sekä teoreettista että käytännöllistä merkitystä. Tutkimuksessa luotiin tähän mennessä tarkin kotimainen reitinoptimointimenetelmä, jota on myös testattu maastossa. Samalla kehitettiin reitinoptimointiin liittyviä paikkatietomenetelmiä ja havaittiin, että paikkatietojärjestelmällä on mahdollista tuottaa maastotyöntekijän apuvälineeksi sopivia inventointireittejä. Tutkimuksen aikana määriteltiin uusi reitinlaskentaongelma, aluemaisen kohteen inventoinnin ongelma (AIP). Reitinoptimointimenetelmä on otettavissa käyttöön metsävaratiedon keruussa Suomen metsäkeskuksessa, ja sitä voidaan soveltaa myös metsäalan ulkopuolella. Tutkimuksessa esitellyillä menetelmillä voidaan tuottaa sovellustarvetta vastaavat aineistot reitinlaskennan lähtötiedoiksi. Tutkimuksessa tunnistettiin monia jatkotutkimus- ja kehittämistarpeita. Näihin kysymyksiin vastaamalla voidaan luoda yhä paremmin toimiva työkalu metsävaratiedon keruun apuvälineeksi ja syventää edelleen teoreettista tietämystä reitinoptimoinnista maastossa.

This thesis project aims to learn and understand more about implementing a path planner to the unmanned ground vehicle (UGV), UGV Husky, specifically its traversability algorithm, and investigate how it could be further improved. A surrounding grid is generated around the UGV where each cell contains information connected to its traversability. The traversability filter is given this information to score how possible it is to traverse to the cell with regard to angular slope, terrain roughness, and step height. The three parameters have each a critical value that works as a limit where if one of the three parameters were to exceed the critical value then the cell would not be estimated to be traversable. The current problem is that their critical value for angular slope, step height, and terrain roughness are decided arbitrarily and mostly through simulation. To solve this problem, formulas are derived that focus on geometrical aspects of a UGV to define the limits in focus on slope and step. The formulas give threshold values applied to the code and are run in simulation. To validate this, hardware experiments are done to compare simulation and reality. This is to observe and learn if the simulations are good representations of reality and if the threshold values are correct. The results show that the thresholds are good estimations of the UGV Husky's limits. This is if one takes into consideration that other important factors are not included or known, such as the ground conditions in the actual experiments. The simulation studies also prove that Gazebo simulations are not good representations of reality to test terrain difficulties because of simplified physical representation, giving unreliable limits. Based on the successful implementation of the geometrically derived threshold values for slope and step, further work could include similarly derived threshold values for terrain roughness, and attempt to optimize the variables that are in the traversability formula. / Syftet med detta examensabete är attutveckla förståelsen av en ruttplaneringsalgoritm, specifikt dess framkomlighets analays, och kolla hur det går att förbättra den. Problemet som diskuteras i denna rapport är hur tröskelvärdena för vinkellutning, högsta steghöjd och terrängens grovhet är godtyckligt valda och i flesta fall från simuleringsmiljöer eller flera verklighetstester. För att lösa detta problem foukseras det på att utveckla en formel som endast kollar på de geometriska aspekterna av fordonets vinkelgräns och steghöjd. Denna formel blir testad genom att applicera de framräknade tröskelvärdena till simuleringsmiljön och observera ifall det stämmer att UGVn som användts (UGV Husky) har dessa begränsningar. För validering görs tester också i verkligheten för att se hur relationen mellan simulering och verklighet är. Resultaten visar att värdena är bra uppskattningar till vad UGV Husky klarar i verkligheten om man tar i åtanke att viktiga faktorer har inte tagits med exempelvis markförhållanden. Simulering i förhållande till verklighet är inte en bra representation på grund av dålig upplösning av modeleringen av UGVn vilket ger opålitliga gränser. Nästa steg skulle framöver vara att ta med terrängförhållanden i beräkningarna och optimera flera variabler i formeln.