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

This work focuses on the development and implementation of an autonomous path planning and obstacle avoidance algorithm for an autonomous surface vehicle (ASV) in a riverine environment. The algorithm effectively handles trap situations, which occur when the river bends away from the destination. In addition, the algorithm uses real-time sensor feedback to avoid obstacles. A general global route is proposed based on an a priori shoreline map. Then, local paths are calculated considering both the a priori data and measurements received from an obstacle sensor. These paths roughly follow the global path. The algorithm was tested on an ASV equipped with basic navigational sensors and an omnidirectional camera for obstacle detection, and experimentation verified its effectiveness. / Master of Science

Presented in this thesis is a collision avoidance algorithm designed around an arc path model. The algorithm was designed for use on Virginia Tech robots entered in the 2003 and 2004 Intelligent Ground Vehicle Competition (IGVC) and on our 2004 entry into the DARPA Grand Challenge. The arc path model was used because of the simplicity of the calculations and because it can accurately represent the base kinematics for Ackerman or differentially steered vehicles. Clothoid curves have been used in the past to create smooth paths with continuously varying curvature, but clothoids are computationally intensive. The circular arc algorithm proposed here is designed with simplicity and versatility in mind. It is readily adaptable to ground vehicles of any size and shape. The algorithm is also designed to run with minimal tuning. The algorithm can be used as a stand alone reactive collision avoidance algorithm in simple scenarios, but it can be better optimized for speed and safety when guided by a global path planner. A complete navigation architecture is presented as an example of how obstacle avoidance can be incorporated in the algorithm. / Master of Science

We present a new trajectory generation algorithm for autonomous guidance and control of unmanned vehicles from a given starting point to a given target location. We build and update incomplete a priori maps of the operating environment in real time using onboard sensors and compute level sets on the map reflecting the minimal cost of traversal from the current vehicle location to the goal. We convert the trajectory generation problem into a finite-time-horizon optimal control problem using the computed level sets as terminal costs in a receding horizon framework and transform it into a simpler nonlinear programming problem by discretization of the candidate control and state histories. We ensure feasibility of the generated trajectories by constraining the solution of the optimization problem using a simplified vehicle model. We provide strong performance guarantees by checking for stability of the algorithm through the test of matching conditions at the end of each iteration. The algorithm thus explicitly incorporates the vehicle dynamics and constraints and generates trajectories realizable by the vehicle in the field. Successful preliminary field demonstrations and complete simulation results for a marine unmanned surface vehicle demonstrate the efficacy of the proposed approach for fast operations in poorly characterized riverine environments. / Master of Science