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.

No description available.

No description available.

No description available.

Modern robotics demonstrates the reality of near sci-fi solutions regularly. Swarms of interconnected robotic agents have been proven to have benefits in scalability, robustness, and efficiency. In communication restricted environments, such teams of robots are often required to support their own navigation, planning, and decision making processes, through use of onboard processors and collaboration. Example scenarios that exhibit restriction include unmanned underwater surveys and robots operating in indoor or remote environments without cloud connectivity. We begin this thesis by discussing multi-agent state estimation and it's observability properties, specifically for the case of an agent-to-agent range measurement system. For this case, inspired by navigation requirements underwater, we derive several conditions under which the system's state is guaranteed to be locally weakly observable. Ensuring a state is observable is necessary to maintain an estimate of it via filters, thus observability is required to support higher level navigation and planning. We conclude this section by creating an observability-based planner to control a subset of the agents' inputs. For the next contribution, we discuss scalability for coverage maximizing path planners. Typically planning for many individual robots incurs significant computational complexity which increases exponentially with the number of agents, this is often exacerbated when the objective function is collaborative as in coverage optimization. To maintain feasibility while planning for a large team of robots, we call upon a powerful relation from combinatorics which utilizes the greedy selection algorithm and a matroid condition to create an efficient planner that maintains a fixed performance ratio when compared to the optimal path. We then introduce a motivating example of autonomously assisted search and rescues using multiple aerial agents, and derive planners and models to suit the application. The framework begins by estimating the likely locations of a lost person through a Monte Carlo simulation, yielding a heatmap covering the area of interest. The heatmap is then used in combination with parametrized agent trajectories and a machine learning optimization algorithm to maximize the search efficiency. The search and rescues use case provides an excellent computational testbed for the final portion of the work. We close by discussing a computation architecture to support multi-agent system autonomy. Modern robotic autonomy results, especially computer vision and machine learning algorithms, often require large amounts of processing to yield quality results. With general purpose computing devices reaching a progression barrier, one that is not expected to be solved in the near term, increasingly devices must be designed with their end purposes in mind. To better support autonomy in multi-agent systems, we propose to use a distributed cluster of embedded processors which allows the sharing of computation and storage resources among the component members with minimal communication overhead. Our proposed architecture is composed of mature softwares already well-known in the robotics community, Kubernetes and the robot operating system, allowing ease of use and interoperability with existing algorithms. / Doctor of Philosophy / The traditional approach of robotics typically uses a single large platform capable of accomplishing all tasks assigned to it. However, it has been discovered that deploying multiple smaller platforms, each with their own processor and specific expertise, can have massive performance benefits compared to previous approaches. This development has been driven largely by readily available computing and mobility hardware. Termed as multi-agent systems, they can excel in areas that benefit from multiple perspectives, simultaneous task execution, and redundancy. In addition, planning algorithms developed for previous approaches often can map well onto multi-agent systems, provided there is adequate computational support. In cases where network or cloud connectivity is limited, teams of agents must use their own processors and sensors to make decisions and communicate. However, often an individual agent's computing hardware is limited in mass or size, thus limiting it's processing capabilities. In this work we will first discuss several multi-agent system algorithms, starting with estimation and navigation and ending with area search. We then conclude the work by proposing a novel architecture designed to distribute the computation load across the team in a highly scalable way.

Pursuit-evasion games are the subject of a variety of research initiatives seeking to provide some level of autonomy to mobile, robotic vehicles with on-board controllers. Applications of these controllers include defense topics such as unmanned aerial vehicle (UAV) and unmanned underwater vehicle (UUV) navigation for threat surveillance, assessment, or engagement. Controllers implementing pursuit-evasion algorithms are also used for improving everyday tasks such as driving in traffic when used for collision avoidance maneuvers. Currently, pursuit-evasion tactics are incorporated into the control by solving the Hamilton-Jacobi-Isaacs (HJI) equation explicitly, simplifying the solution using approximate dynamic programming, or using a purely finite-horizon approach. Unfortunately, these methods are either subject to difficulties of long computational times or having no guarantees of succeeding in the pursuit-evasion game. This leads to more difficulties of implementing these tactics on-line in a real robotic scenario where the opposing agent may not be known before the maneuver is required. This dissertation presents a novel method of solving the HJI equation by partitioning the state space into regions of local, finite horizon control laws. As a result, the HJI equation can be reduced to solving the Hamilton-Jacobi-Bellman equation recursively as information is received about an opposing agent. Adding complexity to the problem structure results in a decreased calculation time to allow pursuit-evasion tactics to be calculated on-board an agent during a scenario. The algorithms and implementation methods are given explicitly and illustrated with an example of two robotic vehicles in a collision avoidance maneuver. / Ph. D.

The capability to perform rendezvous and proximity operations about space objects is central to the next generation of space situational awareness. The ability to diagnose and respond to spacecraft anomalies is often hampered by the lack of capability to perform inspection or testing on the target vehicle in flight. While some limited ability to perform inspection can be provided by an extensible boom, such as the robotic arms deployed on the space shuttle and space station, a free-flying companion vehicle provides maximum flexibility of movement about the target. Safe and efficient utilization of a companion vehicle requires trajectories capable of minimizing spacecraft resources, e.g., time or fuel, while adhering to complex path and state constraints. This paper develops an efficient solution method capable of handling complex constraints based on a grid search A* algorithm and compares solution results against a state-of-the-art nonlinear optimization method. Trajectories are investigated that include nonlinear constraints, such as complex keep-out-regions and thruster plume impingement, that may be required for inspection of a specific target area in a complex environment. This work is widely applicable and can be expanded to apply to a variety of satellite relative motion trajectory planning problems. / The capability to perform rendezvous and proximity operations about space objects is central to the next generation of space situational awareness. The ability to diagnose and respond to spacecraft anomalies is often hampered by the lack of capability to perform inspection or testing on the target vehicle in flight. While some limited ability to perform inspection can be provided by an extensible boom, such as the robotic arms deployed on the space shuttle and space station, a free-flying companion vehicle provides maximum flexibility of movement about the target. Safe and efficient utilization of a companion vehicle requires trajectories capable of minimizing spacecraft resources, e.g., time or fuel, while adhering to complex path and state constraints. This paper develops an efficient solution method capable of handling complex constraints based on a grid search A* algorithm and compares solution results against a state-of-the-art nonlinear optimization method. Trajectories are investigated that include complex nonlinear constraints, such as complex keep-out-regions and thruster plume impingement, that may be required for inspection of a specific target area in a complex environment. This work is widely applicable and can be expanded to apply to a variety of satellite relative motion trajectory planning problems. / Master of Science / The ability of one satellite to perform actions near a second space satellite or other space object is important for understanding the space environment and accomplishing space mission goals. The development of a method to plan the path that one satellite takes near a second satellite such that fuel usage is minimized and other constraints satisfied is important for accomplishing mission goals. This thesis focuses on developing a fast solution method capable of handling complex constraints that can be applied to plan paths satellite relative motion operations. The solution method developed in this thesis is then compared to an existing solution method to determine the efficiency and accuracy of the method.

The thesis details the development of computer vision and path planning algorithms in order to map an area via UAV aerial imagery and aid a UGV in navigating a roadway when the road conditions are not previously known (i.e. disaster situations). Feature detection was used for transform calculation and image warping to create mosaics. A continuous extension using dynamic cropping based on newly gathered images was used to improve performance and computation time. Road detection using k-means segmentation and binary image morphing was applied to aerial imagery with image shifting tracked by the mosaicking to develop a large road map. Improvements to computation time were developed using k-means for calibration at intervals and nearest neighbor calculating for each image. This showed a greatly reduced computation time for a series of images with only 1-2% error compared to regular k-means segmentation. Path planning for the UAV utilized a traveling wave applied to the traveling salesman genetic algorithm solution to prioritize close targets and facilitate UGV deployment. Based on the large map of road locations and road detection method, the Rapidly-exploring Random Tree (RRT) algorithm was modified for real-time application and efficient data processing. Considerations of incomplete maps and goal adjustments was also incorporated. Finally, aerial imagery from an actual UAV flight was processed using these algorithms to validate and test flight parameters. Testing of different flight parameters showed the desired image overlay of 50% to give accurate mosaics. It also helped to develop a benchmark for the altitude, image resolution and frequency for flights. Vehicle requirements and algorithm limitations for future applications of this system are also discussed. / Master of Science