Matching Items (10)
Description
This thesis considers two problems in the control of robotic swarms. Firstly, it addresses a trajectory planning and task allocation problem for a swarm of resource-constrained robots that cannot localize or communicate with each other and that exhibit stochasticity in their motion and task switching policies. We model the population dynamics of the robotic swarm as a set of advection-diffusion- reaction (ADR) partial differential equations (PDEs).
Specifically, we consider a linear parabolic PDE model that is bilinear in the robots' velocity and task-switching rates. These parameters constitute a set of time-dependent control variables that can be optimized and transmitted to the robots prior to their deployment or broadcasted in real time. The planning and allocation problem can then be formulated as a PDE-constrained optimization problem, which we solve using techniques from optimal control. Simulations of a commercial pollination scenario validate the ability of our control approach to drive a robotic swarm to achieve predefined spatial distributions of activity over a closed domain, which may contain obstacles. Secondly, we consider a mapping problem wherein a robotic swarm is deployed over a closed domain and it is necessary to reconstruct the unknown spatial distribution of a feature of interest. The ADR-based primitives result in a coefficient identification problem for the corresponding system of PDEs. To deal with the inherent ill-posedness of the problem, we frame it as an optimization problem. We validate our approach through simulations and show that reconstruction of the spatially-dependent coefficient can be achieved with considerable accuracy using temporal information alone.
Specifically, we consider a linear parabolic PDE model that is bilinear in the robots' velocity and task-switching rates. These parameters constitute a set of time-dependent control variables that can be optimized and transmitted to the robots prior to their deployment or broadcasted in real time. The planning and allocation problem can then be formulated as a PDE-constrained optimization problem, which we solve using techniques from optimal control. Simulations of a commercial pollination scenario validate the ability of our control approach to drive a robotic swarm to achieve predefined spatial distributions of activity over a closed domain, which may contain obstacles. Secondly, we consider a mapping problem wherein a robotic swarm is deployed over a closed domain and it is necessary to reconstruct the unknown spatial distribution of a feature of interest. The ADR-based primitives result in a coefficient identification problem for the corresponding system of PDEs. To deal with the inherent ill-posedness of the problem, we frame it as an optimization problem. We validate our approach through simulations and show that reconstruction of the spatially-dependent coefficient can be achieved with considerable accuracy using temporal information alone.
ContributorsElamvazhuthi, Karthik (Author) / Berman, Spring Melody (Thesis advisor) / Peet, Matthew Monnig (Committee member) / Mittelmann, Hans (Committee member) / Arizona State University (Publisher)
Created2014
Description
Robotic swarms can potentially perform complicated tasks such as exploration and mapping at large space and time scales in a parallel and robust fashion. This thesis presents strategies for mapping environmental features of interest – specifically obstacles, collision-free paths, generating a metric map and estimating scalar density fields– in an unknown domain using data obtained by a swarm of resource-constrained robots. First, an approach was developed for mapping a single obstacle using a swarm of point-mass robots with both directed and random motion. The swarm population dynamics are modeled by a set of advection-diffusion-reaction partial differential equations (PDEs) in which a spatially-dependent indicator function marks the presence or absence of the obstacle in the domain. The indicator function is estimated by solving an optimization problem with PDEs as constraints. Second, a methodology for constructing a topological map of an unknown environment was proposed, which indicates collision-free paths for navigation, from data collected by a swarm of finite-sized robots. As an initial step, the number of topological features in the domain was quantified by applying tools from algebraic topology, to a probability function over the explored region that indicates the presence of obstacles. A topological map of the domain is then generated using a graph-based wave propagation algorithm. This approach is further extended, enabling the technique to construct a metric map of an unknown domain with obstacles using uncertain position data collected by a swarm of resource-constrained robots, filtered using intensity measurements of an external signal. Next, a distributed method was developed to construct the occupancy grid map of an unknown environment using a swarm of inexpensive robots or mobile sensors with limited communication. In addition to this, an exploration strategy which combines information theoretic ideas with Levy walks was also proposed. Finally, the problem of reconstructing a two-dimensional scalar field using observations from a subset of a sensor network in which each node communicates its local measurements to its neighboring nodes was addressed. This problem reduces to estimating the initial condition of a large interconnected system with first-order linear dynamics, which can be solved as an optimization problem.
ContributorsRamachandran, Ragesh Kumar (Author) / Berman, Spring M (Thesis advisor) / Mignolet, Marc (Committee member) / Artemiadis, Panagiotis (Committee member) / Marvi, Hamid (Committee member) / Robinson, Michael (Committee member) / Arizona State University (Publisher)
Created2018
Description
This thesis presents an approach to design and implementation of an adaptive boundary coverage control strategy for a swarm robotic system. Several fields of study are relevant to this project, including; dynamic modeling, control theory, programming, and robotic design. Tools and techniques from these fields were used to design and implement a model simulation and an experimental testbed. To achieve this goal, a simulation of the boundary coverage control strategy was first developed. This simulated model allowed for concept verification for different robot groups and boundary designs. The simulation consisted of a single, constantly expanding circular boundary with a modeled swarm of robots that autonomously allocate themselves around the boundary. Ultimately, this simulation was implemented in an experimental testbed consisting of mobile robots and a moving boundary wall to exhibit the behaviors of the simulated robots. The conclusions from this experiment are hoped to help make further advancements to swarm robotic technology. The results presented show promise for future progress in adaptive control strategies for robotic swarms.
ContributorsMurphy, Hunter Nicholas (Author) / Berman, Spring (Thesis director) / Marvi, Hamid (Committee member) / Mechanical and Aerospace Engineering Program (Contributor) / Barrett, The Honors College (Contributor)
Created2017-05
Description
Swarms of low-cost, autonomous robots can potentially be used to collectively perform tasks over large domains and long time scales. The design of decentralized, scalable swarm control strategies will enable the development of robotic systems that can execute such tasks with a high degree of parallelism and redundancy, enabling effective operation even in the presence of unknown environmental factors and individual robot failures. Social insect colonies provide a rich source of inspiration for these types of control approaches, since they can perform complex collective tasks under a range of conditions. To validate swarm robotic control strategies, experimental testbeds with large numbers of robots are required; however, existing low-cost robots are specialized and can lack the necessary sensing, navigation, control, and manipulation capabilities.
To address these challenges, this thesis presents a formal approach to designing biologically-inspired swarm control strategies for spatially-confined coverage and payload transport tasks, as well as a novel low-cost, customizable robotic platform for testing swarm control approaches. Stochastic control strategies are developed that provably allocate a swarm of robots around the boundaries of multiple regions of interest or payloads to be transported. These strategies account for spatially-dependent effects on the robots' physical distribution and are largely robust to environmental variations. In addition, a control approach based on reinforcement learning is presented for collective payload towing that accommodates robots with heterogeneous maximum speeds. For both types of collective transport tasks, rigorous approaches are developed to identify and translate observed group retrieval behaviors in Novomessor cockerelli ants to swarm robotic control strategies. These strategies can replicate features of ant transport and inherit its properties of robustness to different environments and to varying team compositions. The approaches incorporate dynamical models of the swarm that are amenable to analysis and control techniques, and therefore provide theoretical guarantees on the system's performance. Implementation of these strategies on robotic swarms offers a way for biologists to test hypotheses about the individual-level mechanisms that drive collective behaviors. Finally, this thesis describes Pheeno, a new swarm robotic platform with a three degree-of-freedom manipulator arm, and describes its use in validating a variety of swarm control strategies.
To address these challenges, this thesis presents a formal approach to designing biologically-inspired swarm control strategies for spatially-confined coverage and payload transport tasks, as well as a novel low-cost, customizable robotic platform for testing swarm control approaches. Stochastic control strategies are developed that provably allocate a swarm of robots around the boundaries of multiple regions of interest or payloads to be transported. These strategies account for spatially-dependent effects on the robots' physical distribution and are largely robust to environmental variations. In addition, a control approach based on reinforcement learning is presented for collective payload towing that accommodates robots with heterogeneous maximum speeds. For both types of collective transport tasks, rigorous approaches are developed to identify and translate observed group retrieval behaviors in Novomessor cockerelli ants to swarm robotic control strategies. These strategies can replicate features of ant transport and inherit its properties of robustness to different environments and to varying team compositions. The approaches incorporate dynamical models of the swarm that are amenable to analysis and control techniques, and therefore provide theoretical guarantees on the system's performance. Implementation of these strategies on robotic swarms offers a way for biologists to test hypotheses about the individual-level mechanisms that drive collective behaviors. Finally, this thesis describes Pheeno, a new swarm robotic platform with a three degree-of-freedom manipulator arm, and describes its use in validating a variety of swarm control strategies.
ContributorsWilson, Sean Thomas (Author) / Berman, Spring M (Thesis advisor) / Artemiadis, Panagiotis (Committee member) / Sugar, Thomas (Committee member) / Rodriguez, Armando A (Committee member) / Taylor, Jesse (Committee member) / Arizona State University (Publisher)
Created2017
Description
Currently, one of the biggest limiting factors for long-term deployment of autonomous systems is the power constraints of a platform. In particular, for aerial robots such as unmanned aerial vehicles (UAVs), the energy resource is the main driver of mission planning and operation definitions, as everything revolved around flight time. The focus of this work is to develop a new method of energy storage and charging for autonomous UAV systems, for use during long-term deployments in a constrained environment. We developed a charging solution that allows pre-equipped UAV system to land on top of designated charging pads and rapidly replenish their battery reserves, using a contact charging point. This system is designed to work with all types of rechargeable batteries, focusing on Lithium Polymer (LiPo) packs, that incorporate a battery management system for increased reliability. The project also explores optimization methods for fleets of UAV systems, to increase charging efficiency and extend battery lifespans. Each component of this project was first designed and tested in computer simulation. Following positive feedback and results, prototypes for each part of this system were developed and rigorously tested. Results show that the contact charging method is able to charge LiPo batteries at a 1-C rate, which is the industry standard rate, maintaining the same safety and efficiency standards as modern day direct connection chargers. Control software for these base stations was also created, to be integrated with a fleet management system, and optimizes UAV charge levels and distribution to extend LiPo battery lifetimes while still meeting expected mission demand. Each component of this project (hardware/software) was designed for manufacturing and implementation using industry standard tools, making it ideal for large-scale implementations. This system has been successfully tested with a fleet of UAV systems at Arizona State University, and is currently being integrated into an Arizona smart city environment for deployment.
ContributorsMian, Sami (Author) / Panchanathan, Sethuraman (Thesis advisor) / Berman, Spring (Committee member) / Yang, Yezhou (Committee member) / McDaniel, Troy (Committee member) / Arizona State University (Publisher)
Created2018
Description
Numerous works have addressed the control of multi-robot systems for coverage, mapping, navigation, and task allocation problems. In addition to classical microscopic approaches to multi-robot problems, which model the actions and decisions of individual robots, lately, there has been a focus on macroscopic or Eulerian approaches. In these approaches, the population of robots is represented as a continuum that evolves according to a mean-field model, which is directly designed such that the corresponding robot control policies produce target collective behaviours.
This dissertation presents a control-theoretic analysis of three types of mean-field models proposed in the literature for modelling and control of large-scale multi-agent systems, including robotic swarms. These mean-field models are Kolmogorov forward equations of stochastic processes, and their analysis is motivated by the fact that as the number of agents tends to infinity, the empirical measure associated with the agents converges to the solution of these models. Hence, the problem of transporting a swarm of agents from one distribution to another can be posed as a control problem for the forward equation of the process that determines the time evolution of the swarm density.
First, this thesis considers the case in which the agents' states evolve on a finite state space according to a continuous-time Markov chain (CTMC), and the forward equation is an ordinary differential equation (ODE). Defining the agents' task transition rates as the control parameters, the finite-time controllability, asymptotic controllability, and stabilization of the forward equation are investigated. Second, the controllability and stabilization problem for systems of advection-diffusion-reaction partial differential equations (PDEs) is studied in the case where the control parameters include the agents' velocity as well as transition rates. Third, this thesis considers a controllability and optimal control problem for the forward equation in the more general case where the agent dynamics are given by a nonlinear discrete-time control system. Beyond these theoretical results, this thesis also considers numerical optimal transport for control-affine systems. It is shown that finite-volume approximations of the associated PDEs lead to well-posed transport problems on graphs as long as the control system is controllable everywhere.
This dissertation presents a control-theoretic analysis of three types of mean-field models proposed in the literature for modelling and control of large-scale multi-agent systems, including robotic swarms. These mean-field models are Kolmogorov forward equations of stochastic processes, and their analysis is motivated by the fact that as the number of agents tends to infinity, the empirical measure associated with the agents converges to the solution of these models. Hence, the problem of transporting a swarm of agents from one distribution to another can be posed as a control problem for the forward equation of the process that determines the time evolution of the swarm density.
First, this thesis considers the case in which the agents' states evolve on a finite state space according to a continuous-time Markov chain (CTMC), and the forward equation is an ordinary differential equation (ODE). Defining the agents' task transition rates as the control parameters, the finite-time controllability, asymptotic controllability, and stabilization of the forward equation are investigated. Second, the controllability and stabilization problem for systems of advection-diffusion-reaction partial differential equations (PDEs) is studied in the case where the control parameters include the agents' velocity as well as transition rates. Third, this thesis considers a controllability and optimal control problem for the forward equation in the more general case where the agent dynamics are given by a nonlinear discrete-time control system. Beyond these theoretical results, this thesis also considers numerical optimal transport for control-affine systems. It is shown that finite-volume approximations of the associated PDEs lead to well-posed transport problems on graphs as long as the control system is controllable everywhere.
ContributorsElamvazhuthi, Karthik (Author) / Berman, Spring Melody (Thesis advisor) / Kawski, Matthias (Committee member) / Kuiper, Hendrik (Committee member) / Mignolet, Marc (Committee member) / Peet, Matthew (Committee member) / Arizona State University (Publisher)
Created2019
Description
In certain ant species, groups of ants work together to transport food and materials back to their nests. In some cases, the group exhibits a leader-follower behavior in which a single ant guides the entire group based on its knowledge of the destination. In some cases, the leader role is occupied temporarily by an ant, only to be replaced when an ant with new information arrives. This kind of behavior can be very useful in uncertain environments where robot teams work together to transport a heavy or bulky payload. The purpose of this research was to study ways to implement this behavior on robot teams.
In this work, I combined existing dynamical models of collective transport in ants to create a stochastic model that describes these behaviors and can be used to control multi-robot systems to perform collective transport. In this model, each agent transitions stochastically between roles based on the force that it senses the other agents are applying to the load. The agent’s motion is governed by a proportional controller that updates its applied force based on the load velocity. I developed agent-based simulations of this model in NetLogo and explored leader-follower scenarios in which agents receive information about the transport destination by a newly informed agent (leader) joining the team. From these simulations, I derived the mean allocations of agents between “puller” and “lifter” roles and the mean forces applied by the agents throughout the motion.
From the simulation results obtained, we show that the mean ratio of lifter to puller populations is approximately 1:1. We also show that agents using the role update procedure based on forces are required to exert less force than agents that select their role based on their position on the load, although both strategies achieve similar transport speeds.
In this work, I combined existing dynamical models of collective transport in ants to create a stochastic model that describes these behaviors and can be used to control multi-robot systems to perform collective transport. In this model, each agent transitions stochastically between roles based on the force that it senses the other agents are applying to the load. The agent’s motion is governed by a proportional controller that updates its applied force based on the load velocity. I developed agent-based simulations of this model in NetLogo and explored leader-follower scenarios in which agents receive information about the transport destination by a newly informed agent (leader) joining the team. From these simulations, I derived the mean allocations of agents between “puller” and “lifter” roles and the mean forces applied by the agents throughout the motion.
From the simulation results obtained, we show that the mean ratio of lifter to puller populations is approximately 1:1. We also show that agents using the role update procedure based on forces are required to exert less force than agents that select their role based on their position on the load, although both strategies achieve similar transport speeds.
ContributorsGah, Elikplim (Author) / Berman, Spring M (Thesis advisor, Committee member) / Pavlic, Theodore (Committee member) / Marvi, Hamidreza (Committee member) / Arizona State University (Publisher)
Created2020
Description
The problem of modeling and controlling the distribution of a multi-agent system has recently evolved into an interdisciplinary effort. When the agent population is very large, i.e., at least on the order of hundreds of agents, it is important that techniques for analyzing and controlling the system scale well with the number of agents. One scalable approach to characterizing the behavior of a multi-agent system is possible when the agents' states evolve over time according to a Markov process. In this case, the density of agents over space and time is governed by a set of difference or differential equations known as a {\it mean-field model}, whose parameters determine the stochastic control policies of the individual agents. These models often have the advantage of being easier to analyze than the individual agent dynamics. Mean-field models have been used to describe the behavior of chemical reaction networks, biological collectives such as social insect colonies, and more recently, swarms of robots that, like natural swarms, consist of hundreds or thousands of agents that are individually limited in capability but can coordinate to achieve a particular collective goal.
This dissertation presents a control-theoretic analysis of mean-field models for which the agent dynamics are governed by either a continuous-time Markov chain on an arbitrary state space, or a discrete-time Markov chain on a continuous state space. Three main problems are investigated. First, the problem of stabilization is addressed, that is, the design of transition probabilities/rates of the Markov process (the agent control parameters) that make a target distribution, satisfying certain conditions, invariant. Such a control approach could be used to achieve desired multi-agent distributions for spatial coverage and task allocation. However, the convergence of the multi-agent distribution to the designed equilibrium does not imply the convergence of the individual agents to fixed states. To prevent the agents from continuing to transition between states once the target distribution is reached, and thus potentially waste energy, the second problem addressed within this dissertation is the construction of feedback control laws that prevent agents from transitioning once the equilibrium distribution is reached. The third problem addressed is the computation of optimized transition probabilities/rates that maximize the speed at which the system converges to the target distribution.
This dissertation presents a control-theoretic analysis of mean-field models for which the agent dynamics are governed by either a continuous-time Markov chain on an arbitrary state space, or a discrete-time Markov chain on a continuous state space. Three main problems are investigated. First, the problem of stabilization is addressed, that is, the design of transition probabilities/rates of the Markov process (the agent control parameters) that make a target distribution, satisfying certain conditions, invariant. Such a control approach could be used to achieve desired multi-agent distributions for spatial coverage and task allocation. However, the convergence of the multi-agent distribution to the designed equilibrium does not imply the convergence of the individual agents to fixed states. To prevent the agents from continuing to transition between states once the target distribution is reached, and thus potentially waste energy, the second problem addressed within this dissertation is the construction of feedback control laws that prevent agents from transitioning once the equilibrium distribution is reached. The third problem addressed is the computation of optimized transition probabilities/rates that maximize the speed at which the system converges to the target distribution.
ContributorsBiswal, Shiba (Author) / Berman, Spring (Thesis advisor) / Fainekos, Georgios (Committee member) / Lanchier, Nicolas (Committee member) / Mignolet, Marc (Committee member) / Peet, Matthew (Committee member) / Arizona State University (Publisher)
Created2020
Description
The world is filled with systems of entities that collaborate in motion, both natural and engineered. These cooperative distributed systems are capable of sophisticated emergent behavior arising from the comparatively simple interactions of their members. A model system for emergent collective behavior is programmable matter, a physical substance capable of autonomously changing its properties in response to user input or environmental stimuli. This dissertation studies distributed and stochastic algorithms that control the local behaviors of individual modules of programmable matter to induce complex collective behavior at the macroscale. It consists of four parts. In the first, the canonical amoebot model of programmable matter is proposed. A key goal of this model is to bring algorithmic theory closer to the physical realities of programmable matter hardware, especially with respect to concurrency and energy distribution. Two protocols are presented that together extend sequential, energy-agnostic algorithms to the more realistic concurrent, energy-constrained setting without sacrificing correctness, assuming the original algorithms satisfy certain conventions. In the second part, stateful distributed algorithms using amoebot memory and communication are presented for leader election, object coating, convex hull formation, and hexagon formation. The first three algorithms are proven to have linear runtimes when assuming a simplified sequential setting. The final algorithm for hexagon formation is instead proven to be correct under unfair asynchronous adversarial activation, the most general of all adversarial activation models. In the third part, distributed algorithms are combined with ideas from statistical physics and Markov chain design to replace algorithm reliance on memory and communication with biased random decisions, gaining inherent self-stabilizing and fault-tolerant properties. Using this stochastic approach, algorithms for compression, shortcut bridging, and separation are designed and analyzed. Finally, a two-pronged approach to "programming" physical ensembles is presented. This approach leverages the physics of local interactions to pair theoretical abstractions of self-organizing particle systems with experimental robot systems of active granular matter that intentionally lack digital computation and communication. By physically embodying the salient features of an algorithm in robot design, the algorithm's theoretical analysis can predict the robot ensemble's behavior. This approach is applied to phototaxing, aggregation, dispersion, and object transport.
ContributorsDaymude, Joshua (Author) / Richa, Andréa W (Thesis advisor) / Scheideler, Christian (Committee member) / Randall, Dana (Committee member) / Pavlic, Theodore (Committee member) / Gil, Stephanie (Committee member) / Arizona State University (Publisher)
Created2021
Description
As technological advancements in silicon, sensors, and actuation continue, the development of robotic swarms is shifting from the domain of science fiction to reality. Many swarm applications, such as environmental monitoring, precision agriculture, disaster response, and lunar prospecting, will require controlling numerous robots with limited capabilities and information to redistribute among multiple states, such as spatial locations or tasks. A scalable control approach is to program the robots with stochastic control policies such that the robot population in each state evolves according to a mean-field model, which is independent of the number and identities of the robots. Using this model, the control policies can be designed to stabilize the swarm to the target distribution. To avoid the need to reprogram the robots for different target distributions, the robot control policies can be defined to depend only on the presence of a “leader” agent, whose control policy is designed to guide the swarm to a particular distribution. This dissertation presents a novel deep reinforcement learning (deep RL) approach to designing control policies that redistribute a swarm as quickly as possible over a strongly connected graph, according to a mean-field model in the form of the discrete-time Kolmogorov forward equation. In the leader-based strategies, the leader determines its next action based on its observations of robot populations and shepherds the swarm over the graph by probabilistically repelling nearby robots. The scalability of this approach with the swarm size is demonstrated with leader control policies that are designed using two tabular Temporal-Difference learning algorithms, trained on a discretization of the swarm distribution. To improve the scalability of the approach with robot population and graph size, control policies for both leader-based and leaderless strategies are designed using an actor-critic deep RL method that is trained on the swarm distribution predicted by the mean-field model. In the leaderless strategy, the robots’ control policies depend only on their local measurements of nearby robot populations. The control approaches are validated for different graph and swarm sizes in numerical simulations, 3D robot simulations, and experiments on a multi-robot testbed.
ContributorsKakish, Zahi Mousa (Author) / Berman, Spring (Thesis advisor) / Yong, Sze Zheng (Committee member) / Marvi, Hamid (Committee member) / Pavlic, Theodore (Committee member) / Pratt, Stephen (Committee member) / Ben Amor, Hani (Committee member) / Arizona State University (Publisher)
Created2021