A Geometric Combinatorial Satisfiability Approach to Automating Free Flight in the Airspaceby James W. Herriot

This dissertation details a research project whose aim is to contribute to research on automating and optimizing the aggregate trajectories of arriving aircraft flights in the terminal airspace inspired by the principles of free flight. A software simulation was designed and developed to model dynamic generation of airspace flight paths from top-of-descent to landing. Although this research is conceived to apply generally to automatically generating safely separated flight paths in the wider airspace, this work focuses on airspace local to a particular airport with one or more runways available for landing arriving aircraft. This approach is robust within a dynamic airspace which is frequently changing due to weather, runway reversals, miss approaches, and aircraft traffic.

The methodology described here employs a trio of geometry, combinatorics, and satisfiability. The unique uniform triangular/hexagonal geometry enables the generation of a large number of similar flight path segments (analogous to pixels), which when joined together form the vast combinatorics of all possible 4DT flight paths for aircraft headed to these runways. In this combinatoric form, these numerous flight path candidates are then handed off to a satisfiability solver, searching for a suite of overall optimal flight paths. This approach generalizes solving for an ensemble of efficient flight paths within a dynamic changing airspace, making way for efficient optimization and automation of aircraft routes.

The spoked bicycle wheel is one of the most ubiquitous tensioned structures in the world and its assembly and tensioning is largely automated. Nevertheless, the algorithms employed in the tensioning process are heuristics that essentially mimic a skilled human worker. While these heuristic can yield very well-tensioned wheels, they are not efficient and occasionally do not converge, requiring manual intervention.

This work describes an in-situ empirical modeling technique of a conventional bicycle wheel employed to determine the optimal tension adjustments necessary to align the wheel in lateral and radial directions while targeting a desired uniform spoke tension. The technique allows the mean tension of the spokes to be adjusted independently from variations around the mean. Additionally, a control algorithm is developed that uses lateral feedback and predicted intermediate wheel states to bring the wheel into alignment to the desired tension in a single iteration of adjustments of the tension of the spokes. First the method is simulated on randomly tensioned wheels. Then the algorithm is demonstrated experimentally on an actual bicycle wheel.

Robots are frequently being used to explore environments that are largely inaccessible to humans. Most people are familiar with the ground rovers such as Spirit, Opportunity, and Curiosity that are on Mars. Autonomous underwater vehicles are becoming more widely used to conduct oceanographic surveys, particularly in places that people cannot go, such as under the polar ice caps. A large part of increasing the utility of these robotic missions will involve giving the robots significantly enhanced autonomy, particularly when it comes to planning precisely what aspects of the environment to survey and sample.

Much of the research on robotic path planning has focused on finding minimal cost paths between two points, and being able to rapidly re-plan when environmental conditions change. Less research has been done into how robots should plan paths that allow them to maximize utility, such as information gathered. One of the primary reasons for this is that finding the optimal solution to the maximization problem is NP-hard, and thus cannot be computed in a tractable amount of time, much less in real time.

This dissertation presents a computationally tractable method for allowing robots to plan paths that can approximately maximize information gathered while satisfying any relevant horizon constraints, such as a deadline. It builds atop existing algorithms known to be capable of rapid planning and re-planning, such as D*. The algorithm utilizes these methods for computing lowest-cost paths between nodes in the environment, and then planning which nodes to search based on a function of both the cost of exploration and the expected amount of information contained at the nodes. Experimental results in small environments show that the algorithm will mostly generate paths that are at least 75% of optimal.

The use of autonomous systems is burgeoning in the world for applications in many fields from scientific, industrial, to military. At the same time, advances in semiconductor technology have enabled ever smaller, complex, and use-specific microprocessors and microcontrollers. This work details the design and implementation of an open source real-time hardware controller for resource-constrained autonomous vehicles and systems. It is intended to be integrated inside a distributed control architecture consisting of the real-time hardware controller, a guidance and navigation computer, and an edge tensor processing unit for machine learning inferences. While the latter two processors are commercially available, a dedicated, modular real-time controller is not, providing the motivation for this work. To demonstrate the versatility of our open source real-time controller we present several use cases including a ground vehicle, marine vessel, quadcopter, and fixed-wing aircraft. The power of the distributed architecture is the ability to solve complex sensing, guidance, navigation, and control challenges even in resource-constrained systems. One such challenge is the simultaneous localization of an autonomous system while mapping an environment. In this work we develop the components of a novel hybrid sensor combining a visual camera and LiDAR sensor that is mounted on the ground vehicle. This sensor is trained to recognize landmarks in the environment using object detection frameworks and deployed on the edge tensor processing unit. At the same time, the LiDAR sensor provides range and bearing information for objects within its field of view. By combining the two we can get fast detections of arbitrary landmarks in the environment as well as determine their position relative to the sensor, thus enabling simultaneous localization and mapping functionality.

Very small spacecraft, called SmallSats, CubeSats, and NanoSats, have become very popular due to their low-cost, complexity, and availability of launch platforms (as extra payloads). These small satellites enable a future of low-cost satellite constellations to accomplish various space missions. The Generalized Nanosatellite Avionics Testbed (G-NAT) lab at NASA Ames Research Center in collaboration with UC Santa Cruz has developed a laboratory to verify sensor and actuator performance requirements of CubeSats in a standardized testing facility equipped with an ultra low-cost attitude truth system based on a camera tracking of visual fiducials. This work rst developed ultra low-cost real-time streaming attitude truth system that is self-calibrating, portable and scalable. The attitude truth system is cross-platform and can be used at various CubeSat testing facilities to track to CubeSat attitude (angular and translational position in the inertial reference frame). Attitude truth system accuracy and robustness improvements were made to rectify highly variant attitude observations during quick maneuvers using an extended Kalman filter. The attitude truth system, implemented with the extended Kalman lter, was able to sustain estimation standard deviation values of +/- 1.30 degrees, +/- 1.30 degrees, and +/- 0.61 degrees in roll, pitch and yaw, respectively. The finalized truth system with the extended Kalman lter was used as validation for testing and verification of on-board CubeSat attitude estimation. Two attitude estimation algorithms explored, were TRIAD (Tri-Axial Attitude Determination) and the complementary filter. Both algorithms were implemented using low-cost IMU sensors and solar photodiodes on a CubeSat testbed. The tests verified that the complementary filter algorithm is more accurate than TRIAD using the same sensor suite when measured by the attitude truth system; the complementary filter performed better than TRIAD by 3.3 degrees, 3.3 degrees and 2.6 degrees in roll, pitch and yaw, respectively according to the attitude truth system with extended Kalman filter.

Containing a wildfire requires an efficient response and persistent monitoring. A crucial aspect is the ability to search for the boundaries of the wildfire by exploring a wide area. However, even as wildfires are increasing today, the number of available monitoring systems that can provide support is decreasing, creating an operational gap and slow response in such urgent situations. Many natural and national security phenomena have a similar need for monitoring the propagating periphery of a hazardous substance or security threat.

The objective of this thesis is to estimate a propagating boundary and create a system that works in real time. It focuses on an autonomous system that suppresses uncertainty, investigating to what extent binary measurements away from the periphery can be used to predict the boundary and its spread rate. It proposes a coordination strategy with a new methodology for estimating the periphery of a propagating phenomenon using quantized observations. The method is tested in a simulation of an autonomous system with multiple unmanned aerial vehicle models that gather local measurements and share the information with a centralized ground control system. The estimate the system generates then incorporated into an allocation algorithm, weighing uncertainty and the rate of change of the uncertainty, reassign the UAV trajectory in order to suppress the uncertainty.

The complete system design, tested on the high-fidelity simulation, demonstrates that steering the vehicles towards the highest perpendicular uncertainty generates the best predictions. The results indicate that the new coordination scheme has a large beneficial impact on uncertainty suppression. By using the developed coordination algorithm and the adopted flight control system, the vehicles can follow the desired trajectory to reduce the uncertainty and the errors in predicting the periphery across a range of wind and terrain conditions.

Algorithms based on traditional notion of tracking as a state estimation problem

yield just a single interpretation of the data. For some applications, the ability to

identify ambiguities and compare different interpretations using a well-defined measure

of confidence is critical. Such applications require a direct solution to the data association

problem in order to characterize the relevant uncertainty. This notion of tracking

has received relatively little attention largely due to a failure to recognize its utility

beyond maintaining the state estimation process. As a result, the options available to

the practitioner are limited and the performance of statistical data association models

is not well understood, especially in terms of the quality of the sample they produce.

This work has sought to change that by developing a new data association

model that extends the scope and flexibility of existing models. The questions of how

to specify an objective prior distribution over data association hypotheses and how

to efficiently perform inference on the high-dimensional posterior distribution are very

much open. To help provide answers, we considered numerous different priors, including

Bayesian nonparametric models and several models never before applied to tracking.

With regard to inference, we considered various implementations of Markov chain Monte

Carlo (MCMC) and population Monte Carlo (PMC) samplers. A comprehensive evaluation

was performed in the context of a wide-area radar surveillance application.

Approximately 11 million Americans live with Parkinson’s Disease (PD) or Essential Tremor (ET), and the current standard of care is inadequate. Diagnostic methods rely on qualitative observations rather than quantitative metrics and treatments are often prohibitively expensive or riddled with side effects. This work first develops a non-intrusive wearable device that can perform an automated diagnosis of PD and ET. Next, it develops an algorithm for attitude estimation of the human wrist. Finally, it develops a prototype for a wearable tremor suppression device. The diagnostic device was tested with a group of 30 healthy volunteers who had been educated on the motion characteristics of PD and ET. A 99.9% classification accuracy was achieved during this test. The attitude estimation algorithm was tested with the help of a mechanical test rig that simulated tremor. During a highly dynamic oscillation, the attitude estimate achieved an RMS error of less than 1 degree. This same mechanical test rig was used to evaluate the effectiveness of the tremor suppression prototype. Settings on the rig were adjusted to test tremors of varying amplitude and frequency. The device was able to attenuate tremor amplitude by an average of 60.96% across the configurations tested.

All past NASA planetary rovers have only been able to traverse celestial surfaces at a maximum speed of 0.05-0.09 m/s (0.11-0.20 mph). There is motivation to operate rovers more autonomously and to increase their speeds upwards to 3m/s on flat hard ground, which is considered fast for planetary rovers. In this thesis, a novel roughness metric is used to create a speed map and provide planetary rovers with information about the terrain. The provided information is intrinsic to the terrain regarding its roughness and speed allowing the rover to safely travel over smooth and rough terrain. The results of this method will benefit path planning algorithms and control operators in improving mission efficiency.

Animal tracking collars have proven incredibly useful to biologists providing insights into range, physiology, and environmental interaction. Current collars rely on scheduled sampling of GPS that must be preset at deployment (though advanced ones can modify the schedule through radio communications). This work details the design and development of a third generation of Mountain Lion tracking collar that can identify animal behavior in situ using advanced onboard sensors. The power-aware collar relies on triaxial accelerometers and magnetometers and signal processing techniques to classify behavior and dynamically scale its sampling for higher fidelity during interesting periods and sleeping power hungry sensors during uninteresting ones. An analysis of sensor performance and down selection is presented, along with software and hardware required to implement the collar. The resulting collar is capable of sampling its primary sensors at a high data rate (50Hz/5Hz respectively) and still last over three years on a typical battery using a low power processor. Data is logged to an onboard microSD card, and several steps have been included to ensure data integrity and recovery in the case of faults in the microSD card. It is shown that the largest power draw on the system will be the VHF/UHF radio link, and that the embedded processor on the collar should be used to minimize the time spent transmitting data by using a dedicated symbol table to encode behavior and positions for interesting events in the animal life.