Search operations can be described by the interaction between three entities: the target, the sensor, and the environment. Past treatments of the search problem have focused primarily on the interaction between the sensor and the target. The effects that the environment has on the target and sensor have been greatly simplified or ignored completely. The wilderness search and rescue scenario is one case in which these interactions cannot be safely ignored. Using the wilderness search and rescue problem as our motivating example, we develop an algorithm for planning search paths for a small unmanned aerial vehicle (UAV) over rough terrain environments that provide complete coverage of the specified terrain region while minimizing effort wasted on duplicate coverage. The major components of this algorithm include 1) breaking the search region into smaller sub-regions that are easier to deal with, and 2) planning the search for each of these sub-regions. The original contributions of this thesis focus on the latter of these two components. We use a method based on the directional offset of terrain contours to produce paths on the terrain for the sensor to observe as the UAV follows the flight path. We then employ directional-offset methods again by moving in the direction along the terrain normal from the sensor path to generate a flight path that lies in the air a specified distance away from the points on the terrain that are to be observed. These two paths are linked in a way that provides the sensor with an ample viewing opportunity of the terrain regions below. We implement this planning algorithm in software with Matlab, and provide a complete simulation of a UAV that follows the planned search pattern. Our planning algorithm produced search paths that were 94 to 100 percent complete in test scenarios for several rough-terrain regions. Missed regions for these plans were near the search boundaries, and coverage could easily be provided by subsequent plans. We recommend the study of region segmentation, with careful consideration of planning algorithms as the major focus of future work.

The work in this thesis is on two topics. The first topic focuses on collaboration between a UAV and a UGV to track a moving ground target. The second topic focuses on deriving a guidance law for a small-scale controllable projectile to be guided into a target. For the first topic, we implement a path planning algorithm in a hardware system for a UAV and UGV to track a ground target. The algorithm is designed for urban environments where it is common for objects to obstruct sensors located on the UAV and the UGV. During the hardware system's implementation, multiple problems prevented the hardware system from functioning properly. We will describe solutions to these problems. For the second topic, we develop a guidance law for a small-scale controllable projectile using Lyapunov analysis techniques. We implement a PID controller on the body-axes pitch rate and yaw rate of the projectile such that the behavior of the pitch rate and yaw rate can be approximated as a second order system. We derive inputs for the pitch rate and yaw rate using backstepping and adaptive control techniques. The guidance law we develop guarantees the rocket will point at its intended destination. Additionally, we present expressions for the kinematics and dynamics of the rocket's motion and define the forces and moments that act on the rocket's body.

This thesis project investigates a method for performing dynamic path planning in three dimensions, targeting the application of autonomous unmanned aerial vehicles (UAVs).  Three different path planning algorithms are evaluated, based on the framework of rapidly-exploring random trees (RRTs): the original RRT, RRT*, and a proposed variant called RRT-u, which differs from the two other algorithms by considering dynamic constraints and using piecewise constant accelerations for edges in the planning tree. The path planning is furthermore applied for unexplored environments. In order to select a path when there are unexplored parts between the vehicle and the goal, it is proposed to test paths to the goal location from every vertex in the planning graph to get a preliminary estimate of the total cost for each partial path in the planning tree. The path with the lowest cost given the available information can thus be selected, even though it partly goes through unknown space. For cases when no preliminary paths can be obtained due to obstacles, dynamic resizing of the sampling region is implemented increasing the region from which new nodes are sampled. This method using each of the three different algorithms variants, RRT, RRT*, and RRT-u, is tested for performance and the three variants are compared against each other using several test cases in a realistic simulation environment.  Keywords / Detta examensarbete undersöker metoder för att utföra dynamisk ruttplanering i tre dimensioner, med applicering på obemannade luftfarkoster. Tre olika ruttplaneringsalgoritmer testas, vilka är baserade på snabbt-utforskande slumpmässiga träd (RRT): den ursprungliga RRT, RRT*, och en föreslagen variant, RRT-u, vilken skiljer sig från dom två första algoritmerna genom att ta hänsyn till dynamiska begränsningar och använda konstanta accelerationer över delar av rutten. Ruttplaneraren används också i okända miljöer. För att välja en rutt när det finns outforskade delar mellan farkosten och målet föreslås det att testa rutten till målpunkten från varje nod i som ingår i planeringsträdet för att erhålla en preliminär total kostnad till målpunkten. Rutten med lägsta kostanden kan då väljas, givet tillgänglig information, även om den delvis går genom outforskade delar. För tillfällen när inga preliminära rutter kan erhållas på grund av hinder har dynamisk storleksjustering av samplingsområdet implementerats för att öka området från vilket nya noder samplas. Den här metoden har testats med dom tre olika algoritmvarianterna, RRT, RRT*, och RRT-u, och dom tre varianterna jämförs med avseende på prestanda i ett flertal testfall i en realistisk simuleringsmiljö.

Efforts to learn more about the oceans that surround us have increased dramatically as the technological ability to do so grows. Autonomous Underwater Vehicles (AUVs) are one such technological advance. They allow for rapid deployment and can gather data quickly in places and ways that traditional measurement systems (bouys, profilers, etc.) cannot. A ROMS-based data assimilation method was developed that intelligently plans for and integrates AUV measurements with the goal of minimizing model standard deviation. An algorithm developed for this system is first described that optimizes paths for AUVs that seeks to improve the model by gathering data in high-interest locations. This algorithm and its effect on the ocean model are tested by comparing the results of missions made with the algorithm and missions created by hand. The results of the experiments demonstrate that the system is successful in improving the ROMS ocean model. Also shown are results comparing optimized missions and unoptimized missions.

In this thesis, the viability of decentralized, noncooperative multi-robot path planning algorithms is tested. Three algorithms based on the Batch Informed Trees (BIT*) algorithm are presented. The first of these algorithms combines Optimal Reciprocal Collision Avoidance (ORCA) with BIT*. The second of these algorithms uses BIT* to create a path which the robots then follow using an artificial potential field (APF) method. The final algorithm is a version of BIT* that supports replanning. While none of these algorithms take advantage of sharing information between the robots, the algorithms are able to guide the robots to their desired goals, with the algorithm that combines ORCA and BIT* having the robots successfully navigate to their goals over 93% for multiple environments with teams of two to eight robots.

Every year, the ports of entry of the continental United States receive millions of containers from container ships for processing. These containers contain everything that the country imports, and sometimes regulated items can be hidden inside them in attempt to smuggle them illegally into the country. Some of these items may be radioactive material meant for criminal purposes and represent a threat to national security. The containers are currently being scanned for radioactivity as they leave the port, but before leaving the port, containers can sit inside the port for weeks. It can be beneficial to scan these containers before they are picked up to catch the illegal material sooner and reduce the risk of danger to those nearby. Uncrewed Aerial Systems can be useful for scanning container stacks in container fields since they can be attached with sensors and reach heights that are difficult for humans. They can also scan autonomously, requiring less over watch from people. This thesis attempts to solve the problem of autonomous search by using an initial 3D scan of the search area to input into a 3D path planning algorithm to generate a flight path that will sufficiently scan the search area while minimizing flight time. Coverage is a main area of concern, as well is computational complexity and time. In order to maintain security of the aircraft, the path must be generated on-board the aircraft, and as such use on-board, lightweight, computers. The approach taken in this thesis is by breaking the problem down into 2D layers, and then developing paths on each layer based on where the obstacles are. In order to maximize coverage, contours are generated around the obstacles. The vertices of the contours are then treated like points to visit in a Travelling Salesman Problem. To incentivize paths that run alongside the obstacles for better radiation detection, paths that do not run close to the obstacles are given a higher cost than those that do, resulting in a cost-minimizing path planning algorithm yielding paths that stay close to obstacles. The Travelling Salesman Problem algorithm then yields the most time effective path to cover the area while maintaining a distance healthy for radiation scanning from the obstacles. / Master of Science / Every year, the ports of entry of the continental United States receive millions of containers from container ships for processing. These containers contain everything that the country imports, and sometimes regulated items can be hidden inside them in attempt to smuggle them illegally into the country. Some of these items may be radioactive material meant for criminal purposes and represent a threat to national security. It can be beneficial to scan these containers before they are picked up to catch the illegal material sooner and reduce the risk of danger to those nearby. Uncrewed Aerial Systems can be useful for scanning container stacks in container fields since they can be attached with sensors and reach heights that are difficult for humans. They can also scan autonomously, requiring less over watch from people. This thesis attempts to solve the problem of autonomous search by using an initial 3D scan of the search area to input into a 3D path planning algorithm to sufficiently scan the search area while minimizing flight time.

Underwater robotic vehicles are used in a variety of environments that would be dangerous for humans. For these vehicles to be successful, they need to be tolerant of a variety of internal and external faults. To be resilient to internal faults, the system must be capable of determining the source of faulty behavior. However many different faults within a robotic vehicle can create identical faulty behavior, which makes the vehicles impossible to diagnose using conventional methods. I propose a novel active diagnosis method for differentiating between faults that would otherwise have identical behavior. I apply this method to a communication system and a power distribution system in a robotic vehicle and show that active diagnosis is successful in diagnosing partially observable faults. An example of an external fault is inter-robot communication in underwater robotics. The primary communication method for underwater vehicles is acoustic communication which relies heavily on line-of-sight tracking and range. This can cause severe packet loss between agents when a vehicle is operating around obstacles. I propose novel path-planning methods for an Autonomous Underwater Vehicle (AUV) that ferries messages between agents. I applied this method to a custom underwater simulator and illustrate how it can be used to preserve at least twice as many packets sent between agents than would be obtained using conventional methods.

La representación del entorno juega un papel crucial en la navegación autónoma. A esta representación, se le suele denominar en la literatura como mapa, y su construcción suele realizarse mediante vehículos de mapeado dedicados. Sin embargo, aunque este tipo de mapas son muy precisos a nivel local, presentan el inconveniente de ser globalmente inconsistentes debido a la acumulación de pequeños errores que se hacen relevantes cuando los mapas crecen en tamaño. En la presente tesis doctoral, se propone como alternativa, la navegación autónoma basada en mapas públicos geo-referenciados. Este tipo de mapas, a diferencia de los construidos mediante vehículos de mapeado, son por naturaleza globalmente consistentes debido a que proceden de imágenes aéreas que se encuentran geo-referenciadas. Esto, además de ser una ventaja en sí misma, conlleva otro tipo de beneficios, como la no dependencia de un proceso de mapeado, o la posibilidad de navegar sin restricciones en el tamaño del entorno. No obstante, la integración de los mapas públicos geo-referenciados introduce algunas particularidades en la implementación de los algoritmos de navegación autónoma. Durante la investigación que se expone en esta memoria, se han desarrollado diferentes métodos para abordar dichas particularidades. En el módulo de localización, la representación de mapas geo-referenciados introduce la dependencia de un tipo de marcas que deben ser observables, tanto desde imágenes por satélite, como desde los sensores locales del vehículo. Esta restricción genera representaciones escasas que, a menudo, resultan en zonas ambiguas para la asociación de datos (efecto aliasing). Para abordar estos temas, se han desarrollado diferentes métodos robustos, como Delta-Angle Lane Markings Representation, una estrategia de representación para el proceso de asociación de datos, y Distance-Compatible SAmple Consensus, un método de asociación de datos. Para mitigar el efecto del aliasing en el módulo de localización, también se han empleado capacidades de autoajuste, que modifican de manera dinámica la configuración del método de asociación de datos en función de la pseudo-entropía medida en las observaciones. Por otra parte, para el módulo de planificación de rutas, se ha desarrollado un método llamado Naive-Valley-Path que corrige las imprecisiones locales intrínsecas en los mapas públicos. Todos estos métodos han sido comparados con sus homólogos en el estado del arte, demostrando en todos los casos mejoras que han resultado en contribuciones de gran impacto para la comunidad científica. / La presente tesis doctoral ha sido financiada por la Conselleria d’Innovació, Universitats, Ciència i Societat Digital de la Generalitat Valenciana y el Fondo Social Europeo de la Unión Europea a través de las subvenciones ACIF/2019/088 y BEFPI/2021/069.

No description available.

No description available.