Matching Items (2)
Filtering by
- All Subjects: Communication Graph
- Genre: Academic theses
- Creators: Berman, Spring M
- Member of: ASU Electronic Theses and Dissertations
Description
Robotic technology is advancing to the point where it will soon be feasible to deploy massive populations, or swarms, of low-cost autonomous robots to collectively perform tasks over large domains and time scales. Many of these tasks will require the robots to allocate themselves around the boundaries of regions or features of interest and achieve target objectives that derive from their resulting spatial configurations, such as forming a connected communication network or acquiring sensor data around the entire boundary. We refer to this spatial allocation problem as boundary coverage. Possible swarm tasks that will involve boundary coverage include cooperative load manipulation for applications in construction, manufacturing, and disaster response.
In this work, I address the challenges of controlling a swarm of resource-constrained robots to achieve boundary coverage, which I refer to as the problem of stochastic boundary coverage. I first examined an instance of this behavior in the biological phenomenon of group food retrieval by desert ants, and developed a hybrid dynamical system model of this process from experimental data. Subsequently, with the aid of collaborators, I used a continuum abstraction of swarm population dynamics, adapted from a modeling framework used in chemical kinetics, to derive stochastic robot control policies that drive a swarm to target steady-state allocations around multiple boundaries in a way that is robust to environmental variations.
Next, I determined the statistical properties of the random graph that is formed by a group of robots, each with the same capabilities, that have attached to a boundary at random locations. I also computed the probability density functions (pdfs) of the robot positions and inter-robot distances for this case.
I then extended this analysis to cases in which the robots have heterogeneous communication/sensing radii and attach to a boundary according to non-uniform, non-identical pdfs. I proved that these more general coverage strategies generate random graphs whose probability of connectivity is Sharp-P Hard to compute. Finally, I investigated possible approaches to validating our boundary coverage strategies in multi-robot simulations with realistic Wi-fi communication.
In this work, I address the challenges of controlling a swarm of resource-constrained robots to achieve boundary coverage, which I refer to as the problem of stochastic boundary coverage. I first examined an instance of this behavior in the biological phenomenon of group food retrieval by desert ants, and developed a hybrid dynamical system model of this process from experimental data. Subsequently, with the aid of collaborators, I used a continuum abstraction of swarm population dynamics, adapted from a modeling framework used in chemical kinetics, to derive stochastic robot control policies that drive a swarm to target steady-state allocations around multiple boundaries in a way that is robust to environmental variations.
Next, I determined the statistical properties of the random graph that is formed by a group of robots, each with the same capabilities, that have attached to a boundary at random locations. I also computed the probability density functions (pdfs) of the robot positions and inter-robot distances for this case.
I then extended this analysis to cases in which the robots have heterogeneous communication/sensing radii and attach to a boundary according to non-uniform, non-identical pdfs. I proved that these more general coverage strategies generate random graphs whose probability of connectivity is Sharp-P Hard to compute. Finally, I investigated possible approaches to validating our boundary coverage strategies in multi-robot simulations with realistic Wi-fi communication.
ContributorsPeruvemba Kumar, Ganesh (Author) / Berman, Spring M (Thesis advisor) / Fainekos, Georgios (Thesis advisor) / Bazzi, Rida (Committee member) / Syrotiuk, Violet (Committee member) / Taylor, Thomas (Committee member) / Arizona State University (Publisher)
Created2016
Description
Existing robotic excavation research has been primarily focused on lunar mining missions or simple traffic control in confined tunnels, however little work attempts to bring collective excavation into the realm of human infrastructure. This thesis explores a decentralized approach to excavation processes, where traffic laws are borrowed from swarms of fire ants (Solenopsis invicta) or termites (Coptotermes formosanus) to create decision rules for a swarm of robots working together and organizing effectively to create a desired final excavated pattern.
First, a literature review of the behavioral rules of different types of insect colonies and the resulting structural patterns over the course of excavation was conducted. After identifying pertinent excavation laws, three different finite state machines were generated that relate to construction, search and rescue operations, and extraterrestrial exploration. After analyzing these finite state machines, it became apparent that they all shared a common controller. Then, agent-based NetLogo software was used to simulate a swarm of agents that run this controller, and a model for excavating behaviors and patterns was fit to the simulation data. This model predicts the tunnel shapes formed in the simulation as a function of the swarm size and a time delay, called the critical waiting period, in one of the state transitions. Thus, by controlling the individual agents' behavior, it was possible to control the structural outcomes of collective excavation in simulation.
To create an experimental testbed that could be used to physically implement the controller, a small foldable robotic platform was developed, and it's capabilities were tested in granular media. In order to characterize the granular media, force experiments were conducted and parameters were measured for resistive forces during an excavation cycle. The final experiment verified the robot's ability to engage in excavation and deposition, and to determine whether or not to begin the critical waiting period. This testbed can be expanded with multiple robots to conduct small-scale experiments on collective excavation, such as further exploring the effects of the critical waiting period on the resulting excavation pattern. In addition, investigating other factors like tuning digging efficiency or deposition proximity could help to transition the proposed bio-inspired swarm excavation controllers to implementation in real-world applications.
First, a literature review of the behavioral rules of different types of insect colonies and the resulting structural patterns over the course of excavation was conducted. After identifying pertinent excavation laws, three different finite state machines were generated that relate to construction, search and rescue operations, and extraterrestrial exploration. After analyzing these finite state machines, it became apparent that they all shared a common controller. Then, agent-based NetLogo software was used to simulate a swarm of agents that run this controller, and a model for excavating behaviors and patterns was fit to the simulation data. This model predicts the tunnel shapes formed in the simulation as a function of the swarm size and a time delay, called the critical waiting period, in one of the state transitions. Thus, by controlling the individual agents' behavior, it was possible to control the structural outcomes of collective excavation in simulation.
To create an experimental testbed that could be used to physically implement the controller, a small foldable robotic platform was developed, and it's capabilities were tested in granular media. In order to characterize the granular media, force experiments were conducted and parameters were measured for resistive forces during an excavation cycle. The final experiment verified the robot's ability to engage in excavation and deposition, and to determine whether or not to begin the critical waiting period. This testbed can be expanded with multiple robots to conduct small-scale experiments on collective excavation, such as further exploring the effects of the critical waiting period on the resulting excavation pattern. In addition, investigating other factors like tuning digging efficiency or deposition proximity could help to transition the proposed bio-inspired swarm excavation controllers to implementation in real-world applications.
ContributorsHaggerty, Zz Mae (Author) / Berman, Spring M (Thesis advisor) / Aukes, Daniel (Committee member) / Marvi, Hamid (Committee member) / Arizona State University (Publisher)
Created2018