No description available.

No description available.

Robot swarms are envisioned in applications such as surveillance, agriculture, search-and-rescue operations, and construction. The decentralized nature of swarm intelligence has three key advantages over traditional multi-robot control algorithms: it is scalable, it is fault tolerant, and it is not susceptible to a single point of failure. These advantages are critical to the task of persistent surveillance - where a number of target locations need to be visited as frequently as possible. Unfortunately, in the real world, the autonomous robots that can be used for persistent surveillance have a limited battery life (or fuel capacity). Thus, they need to abandon their surveillance duties to visit a battery swapping station (or refueling depot) a.k.a. €˜depots€™. This €˜down time€™ reduces the frequency of visitation. This problem can be eliminated if the depots themselves were autonomous vehicles that could meet the (surveillance) robots at some point along their path from one target to another. Thus, the robots would spend less time on the 'charging' (or refueling) task. In this thesis we present decentralized control algorithms, and their results, for three stages of the persistent surveillance problem. First, we consider the case where the robots have no energy constraints, and use a decentralized approach to allow the robots choose the €˜best€™ target that they should visit next. While the selection process is decentralized, the robots can communicate with all the other robots in the swarm, and let them know which is their chosen target. We then consider the energy constraints of the robots, and slightly modify the algorithm, so that the robots visit a depot before they run out of energy. Lastly, we consider the case where the depots themselves can move, and communicate with the robots to pick a location and time to meet, to be able to swap the empty battery of a robot, with a fresh one. The goal of persistent surveillance is to visit target locations as frequently as possible, and thus, the performance measurement parameter is chosen to be the median frequency of visitation for all target locations. We evaluate the performance of the three algorithms in an extensive set of simulated experiments.

Robotic swarms are multi-robot systems whose global behavior emerges from local interactions between individual robots and spatially proximal neighboring robots. Each robot can be programmed with several local control laws that can be activated depending on an operator’s choice of global swarm behavior (e.g. flocking, aggregation, formation control, area coverage). In contrast to other multi-robot systems, robotic swarms are inherently scalable since they are robust to addition and removal of members with minimal system reconfiguration. This makes them ideal for applications such as search and rescue, environmental exploration and surveillance. Practical missions often require a combination of swarm behaviors and may have dynamically changing mission goals. However, a robotic swarm is a complex distributed dynamical system, so its state evolution depends on the timing as well as sequence of the supervisory inputs. Thus, it is difficult to predict the effects of an input on the state evolution of the swarm. More specifically, after becoming aware of a change in mission goals, it is unclear at what time a supervisory operator must convey this information to the swarm or which combination of behaviors to use to accomplish the new goals. The main challenges we address in this thesis are characterizing the effects of input timing on swarm performance and using this theory to inform automated composition of swarm behaviors to accomplish updated mission goals. We begin by formalizing the notion of Neglect Benevolence — the idea that delaying the application of an input can sometimes be beneficial to overall swarm performance — and using the developed theory to demonstrate experimentally that humans can learn to approximate optimal input timing. In an adversarial setting, we also demonstrate that by altering only the timing of consensus updates for a subset of the swarm, we can influence the agreement point of the entire swarm. Given a library of swarm behaviors, automated behavior composition consists of identifying a behavior schedule that must specify (1) the appropriate sequence of behaviors and (2) the corresponding duration of execution for each behavior. Applying our notion of Neglect Benevolence, it is clear these two parts are intricately interdependent. By first assuming the durations are known, we present an algorithm to identify the optimal behavior sequence to achieve a desired swarm mission goal when our library contains general swarm behaviors. By restricting our library to consensus-based swarm behaviors, we then relax the assumption on known durations and present an algorithm to simultaneously find the sequence and durations of swarm behaviors to time-optimally accomplish multiple unordered goals.

Drones are unmanned aerial vehicles (UAVs) operated remotely with the help of cameras, GPS, and on-device SD cards. These are used for many applications including civilian as well as military. On the other hand, drone swarms are a fleet of drones that work together to achieve a special goal through swarm intelligence approaches. These provide a lot of advantages such as better coverage, accuracy, increased safety, and improved flexibility when compared to a single drone. However, the deployment of such swarms in an adversarial environment poses significant challenges. This work provides an overview of the current state of research on drone swarms in adversarial environments including algorithms for swarming formation of robotic attack drones with their strengths and weaknesses as well as the attack strategies used by attackers. This work also outlines the common adversarial counter-attack methods to disrupt drone attacks consisting of detection and destruction of drone swarms along with their drawbacks, a counter UAV defense system, and splitting large-scale drones into unconnected clusters. After identifying several challenges, an optimized algorithm is proposed to split the large-scale drone swarms more efficiently.

Robot swarms have recently become of interest in both industry and academia for their potential to perform various difficult or dangerous tasks efficiently. As real robot swarms become more of a possibility, many desire swarms to be controlled or directed by a human, which raises questions regarding how that should be done. Part of the challenge of human-swarm interaction is the difficulty of understanding swarm state and how to drive the swarm to produce emergent behaviors. Human input could inhibit desirable swarm behaviors if their input is poor and has sufficient influence over swarm agents, affecting its overall performance. Thus, with too little influence, human input is useless, but with too much, it can be destructive. We suggest that there is some middle level, or interval, of human influence that allows the swarm to take advantage of useful human input while minimizing the effect of destructive input. Further, we propose that human-swarm interaction schemes can be designed to maintain an appropriate level of human influence over the swarm and maintain or improve swarm performance in the presence of both useful and destructive human input. We test this theory by implementing a piece of software to dynamically moderate influence and then testing it with a simulated honey bee colony performing nest site selection, simulated human input, and actual human input via a user study. The results suggest that moderating influence, as suggested, is important for maintaining high performance in the presence of both useful and destructive human input. However, while our software seems to successfully moderate influence with simulated human input, it fails to do so with actual human input.

Today, software has become deeply woven into the fabric of our lives. The quality of the software we depend on needs to be ensured at every phase of the Software Development Life Cycle (SDLC). An analyst uses the requirements engineering process to gather and analyze system requirements in the early stages of the SDLC. An undetected problem at the beginning of the project can carry all the way through to the deployed product. The Requirements Traceability Matrix (RTM) serves as a tool to demonstrate how requirements are addressed by the design and implementation elements throughout the entire software development lifecycle. Creating an RTM matrix by hand is an arduous task. Manual generation of an RTM can be an error prone process as well. As the size of the requirements and design document collection grows, it becomes more challenging to ensure proper coverage of the requirements by the design elements, i.e., assure that every requirement is addressed by at least one design element. The techniques used by the existing requirements tracing tools take into account only the content of the documents to establish possible links. We expect that if we take into account the relative order of the text around the common terms within the inspected documents, we may discover candidate links with a higher accuracy. The aim of this research is to demonstrate how we can apply machine learning algorithms to software requirements engineering problems. This work addresses the problem of requirements tracing by viewing it in light of the Ant Colony Optimization (ACO) algorithm and a reinforcement learning algorithm. By treating the documents as the starting (nest) and ending points (sugar piles) of a path and the terms used in the documents as connecting nodes, a possible link can be established and strengthened by attracting more agents (ants) onto a path between the two documents by using pheromone deposits. The results of the work show that ACO and RL can successfully establish links between two sets of documents.

Animals such as bees, ants, birds, fish, and others are able to efficiently perform complex coordinated tasks like foraging, nest-selection, flocking and escaping predators without centralized control or coordination. These complex collective behaviors are the result of emergence. Conventionally, mimicking these collective behaviors with robots requires researchers to study actual behaviors, derive mathematical models, and implement these models as algorithms. Since the conventional approach is very time consuming and cumbersome, this thesis uses an emergence-based method for the efficient evolution of collective behaviors. Our method, Grammatical Evolution algorithm for Evolution of Swarm bEhaviors (GEESE), is based on Grammatical Evolution (GE) and extends the literature on using genetic methods to generate collective behaviors for robot swarms. GEESE uses GE to evolve a primitive set of human-provided rules, represented in a BNF grammar, into productive individual behaviors represented by Behavior Tree (BT). We show that GEESE is generic enough, given an initial grammar, that it can be applied to evolve collective behaviors for multiple problems with just a minor change in objective function. Our method is validated as follows: First, GEESE is compared with state-of-the-art genetic algorithms on the canonical Santa Fe Trail problem. Results show that GEESE outperforms the state-of-the-art by a)~providing better solutions given sufficient population size while b)~utilizing fewer evolutionary steps. Second, GEESE is used to evolve collective swarm behavior for a foraging task. Results show that the evolved foraging behavior using GEESE outperformed both hand-coded solutions as well as solutions generated by conventional Grammatical Evolution. Third, the behaviors evolved for single-source foraging task were able to perform well in a multiple-source foraging task, indicating a type of robustness. Finally, with a minor change to the objective function, the same BNF grammar used for foraging can be shown to evolve solutions to the nest-maintenance and the cooperative transport tasks.

An unmanned aerial vehicle (UAV) swarm allows for a more time-efficient method of searching a specified area than a single UAV or piloted plane. There are a variety of factors that affect how well an area is surveyed. We specifically analyzed the effect both vehicle properties and communication had on the swarm search performance. We used non-dimensionalization so the results can be applied to any domain size with any type of vehicle. We found that endurance was the most important factor. Vehicles with good endurance sensed approximately 90% to 100% of the grid, even when other properties were lacking. If the vehicles lacked endurance, the amount of area the vehicles could sense at a given time step became more important and 10% more of the grid was sensed with the increase in sensed area. The maneuverability of the vehicles was measured as the vehicles' radii of turn compared to the search domain size. The maneuverability mattered the most in the middle-range endurance cases. In some cases 30% more of the grid was searched with improving vehicle maneuverability. In addition, we also examined four communication cases with different amounts of information regarding vehicle location. We found communication increased search performance by at least 6.3%. However, increasing the amount of information only changed the performance by 2.3%. We also studied the impact the range of vehicle communication had on search performance. We found that simulations benefited most from increasing the communication range when the amount of area sensed at a given time step was small and the vehicles had good maneuverability. We also extended the optimization to a multi-objective process with the inclusion of target tracking. We analyzed how the different weightings of the objectives affected the performance outcomes. We found that target tracking performance dramatically changes based on the given weighting of each objective and saw an increase of approximately 52%. However, the amount of the grid that was sensed only dropped by approximately 10%.

With the growing accessibility of space, this thesis work sets out to explore space-based swarms to do multipoint magnetometer measurements of current systems embedded within the Aurora Borealis as an initial foray into concepts for space physics applications using swarms of small spacecraft. As a pathfinder, ANDESITE---a 6U CubeSat with eight deployable picosatellites---was built as part of this research. The mission will fly a local network of magnetometers above the Northern Lights. With the spacecraft due to launch on an upcoming ELaNa mission, here we discuss the details of the science motivation, the mathematical framework for current field reconstruction, the particular hardware implementation selected, the calibration procedures, and the pragmatic management needed to realize the spacecraft. After describing ANDESITE and defining its capability, we also propose a follow-on that uses propulsive nodes in a swarm, allowing measurements that can adaptively change to capture the physical phenomena of interest. To do this a flock of satellites needs to fall into the desired formation and maintain it for the duration of the science mission. A simple optimal controller is developed to model the deployment of the satellites. Using a Monte Carlo approach for the uncertain initial conditions, we bound the fuel cost of the mission and test the feasibility of the concept. To illustrate the system analysis needed to effectively design such swarms, this thesis also develops a framework that characterizes the spatial frequency response of the kilometer-scale filter created by the swarm as it flies through various current density structures in the ionospheric plasma. We then subjugate a nominal ANDESITE formation and the controlled swarm specified to the same analysis framework. The choice of sampling scheme and rigorous basic mathematical analysis are essential in the development of a multipoint-measurement mission. We then turn to a novel capability exploiting current trends in the commercial industry. Magnetometers deployed on the largest constellation to date are leveraged as a space-based magnetometer network. The constellation, operated by Planet Labs Inc., consists of nearly 200 satellites in two polar sun-synchronous orbits, with median spacecraft separations on the order of 375 km, and some occasions of opportunity providing much closer spacing. Each spacecraft contains a magneto-inductive magnetometer, able to sample the ambient magnetic field at 0.1 Hz to 10 Hz with <200 nT sensitivity. A feasibility study is presented wherein seven satellites from the Planet constellation were used to investigate space-time patterns in the current systems overlying an active auroral arc over a 10-minute interval. Throughout the this work advantages, limitations, and caveats in exploiting networks of lower quality magnetometers are discussed, pointing out the path forward to creating a global network that can monitor the space environment.