The game "Generalized Kayles (or Independence Achievement)" is played by two players A and B on an arbitrary graph G. The players alternate removing a vertex and its neighbors from G, the winner being the last player with a nonempty set from which to choose. In this thesis, we present winning strategies for some paths.

In Wilderness Search and Rescue (WiSAR), the incident commander (IC) creates a probability distribution map of the likely location of the missing person. This map is important because it guides the IC in allocating search resources and coordinating efforts, but it often depends almost exclusively on prior experience and subjective judgment. We propose a Bayesian model that utilizes publicly available terrain features data to help model lost-person behaviors. This approach enables domain experts to encode uncertainty in their prior estimations and also make it possible to incorporate human-behavior data collected in the form of posterior distributions, which are used to build a first-order Markov transition matrix for generating a temporal, posterior predictive probability distribution map. The map can work as a base to be augmented by search and rescue workers to incorporate additional information. Using a Bayes Chi-squared test for goodness-of-fit, we show that the model fits a synthetic dataset well. This model also serves as a foundation of a larger framework that allows for easy expansion to incorporate additional factors such as season and weather conditions that affect the lost-person's behaviors. Once a probability distribution map is in place, areas with higher probabilities are searched first in order to find the missing person in the shortest expected time. When using a Unmanned Aerial Vehicle (UAV) to support search, the onboard video camera should cover as much of the important areas as possible within a set time. We explore several algorithms (with and without set destination) and describe some novel techniques in solving this path-planning problem and compare their performances against typical WiSAR scenarios. This problem is NP-hard, but our algorithms yield high quality solutions that approximate the optimal solution, making efficient use of the limited UAV flying time. The capability of planning a path with a set destination also enables the UAV operator to plan a path strategically while letting the UAV plan the path locally.

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.

As English expands across the world, quality English teachers are increasingly needed. However, reports that even well-trained TESOL professionals have a hard time obtaining stable employment are prevalent. This study sought to provide some solid evidence about employment trends in TESOL. It is based on a survey administered to alumni who graduated between the years of 1973 and 2008 from Brigham Young University's TESOL program. The results indicate that graduates spend about half of their career time in TESOL-related employment. Most are involved in teaching, but jobs in administration, materials development,or testing are more likely to be full-time and offer benefits. Graduates spend little time in EFL positions, but these jobs are the most likely to be full-time and offer benefits. A surprising amount of time was spent unemployed by choice, and the majority of graduates report salary satisfaction, indicating that perhaps the field attracts those who are not looking for stable, full-time employment. These findings are useful for those anticipating a career in TESOL and for teacher educators. They likewise add a valuable contribution to the small body of literature focused on TESOL employment.

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ö.

No description available.

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.

The positional Burrows-Wheeler transform (PBWT) is a foundational data structure for representing haplotype matches of biobank scale. Once the PBWT panel of a set of haplotypes are constructed, efficient algorithms are available for “All vs. All” positional substring matching, finding exact matches of substrings in pre-aligned strings, for haplotypes within the panel, and “One vs. All” positional substring match query for an out-of-panel haplotype against all haplotypes in the panel. While the original PBWT was designed from linear reference genomes, GBWT was proposed to extend PBWT to genome graphs that allow large insertions and deletions. However, there are no GBWT algorithms for haplotype matching. In this work, we develop the efficient algorithms for “All vs. All” and “One vs. All” haplotype set-maximal and long matching algorithms for GBWT. For a GBWT containing a panel of paths P, we show algorithms similar to the matching algorithms of PBWT. Our algorithms achieves theoretically optimal time complexity to output all “All vs. All” matches in time linear to the size of the input panel (O(∑|Pi| + |out put|)), and quasilinear time to the length of the query path for “One vs. All” path match queries (O(|Q| log σ + |out put| log σ ), where σ is the maximum out- degree in the GBWT and out put is the set of discovered path matches). Under the constant σ assumption made by gPBWT and GBWT, these algorithms are in fact linear. Our algorithms open the possibilities for applications of efficient positional substring matching in pangenome references such as identical-by-descent (IBD) segment identification and genotype imputation.