In this paper, we present deformable configuration control - a fully distributed algorithm that allows multiple robots to deform their configuration to avoid various shapes of obstacles while maintaining connectivity. Robots contacted with an obstacle first estimate the width of an obstacle by sharing bumped status of individual robots, and choose an appropriate obstacle avoidance scenarios between obstacle detouring and bouncing off a wall. Second, for both scenarios, robots switch their motion model to a parent following motion to avoid the obstacle. Finally, robots keep sensing the maximum tree angle to estimate whether they are completely escaped from the obstacle, and return to flock formation motion model. We provide theoretical analysis about maintaining connectivity while robots are avoiding an obstacle. Simulation results show a group of 36 robots successfully avoid three different kinds of obstacles including 1) a small bar, 2) a narrow corridor, and 3) a large wall while maintaining connectivity.

This paper presents four distributed motion controllers to enable a group of robots to collectively transport an object towards a guide robot. These controllers include: rotation around a pivot robot, rotation in-place around an estimated centroid of the object, translation, and a combined motion of rotation and translation in which each manipulating robot follows a trochoid path. Three of these controllers require an estimate of the centroid of the object, to use as the axis of rotation. Assuming the object is surrounded by manipulator robots, we approximate the centroid of the object by measuring the centroid of the manipulating robots. Our algorithms and controllers are fully distributed and robust to changes in network topology, robot population, and sensor error. We tested all of the algorithms in real-world environments with 9 robots, and show that the error of the centroid estimation is low, and that all four controllers produce reliable motion of the object.

We describe the National Museum of Mathematics's Robot Swarm exhibit and our approach for achieving a reliable system for collision avoidance. The Robot Swarm exhibit allows visitors to program behaviors and interact with a “swarm” of small robots. The exhibit supports extended unattended run times, continuous interaction with the public and the demonstration of evocative group behaviors. The exhibit software includes a robust collision avoidance scheme that prevents collisions between robots and collisions between robots and static obstructions in the exhibit space. This system was achieved by building on the Optimal Reciprocal Collision Avoidance (ORCA) algorithm in a novel implementation: the Extended Velocity Obstacle validation system. This paper presents: 1) A collision avoidance algorithm that robustly and efficiently avoids collisions between many robots and static obstacles. 2) A unique hybrid ORCA collision avoidance approach that utilizes global state knowledge without subverting the behavioral independence of each robot. 3) A unique position filtering system which is tailored to an error model in which positions reads can be treated as “ground-truth” and a noise model that is highly discontinuous and non-linear. We present experiments and experimental data that demonstrate the efficacy of our approach.

We present and analyze methods for patrolling and surveillance in an environment with a distributed swarm of robots with limited capabilities. Our approach is based on a distributed triangulation of the work space, in which a set of p stationary sensors provides coverage control; in addition, there are r mobile robots that can move between the sensors. Building on our prior work on structured exploration of unknown spaces with multi-robot systems, we can make use of a triangulation that is constructed in a distributed fashion and guarantees good local navigation properties, even when sensors and robots have very limited capabilities.

We consider the problem of organizing a scattered group of n robots in two-dimensional space. The communication graph of the swarm is connected, but there is no central authority for organizing it. We want to arrange them into a sorted and equally-spaced array between the robots with lowest and highest label, while maintaining a connected communication network. In this paper, we describe a distributed method to accomplish these goals, without using central control, while also keeping time, travel distance and communication cost at a minimum. We proceed in a number of stages (leader election, initial path construction, subtree contraction, geometric straightening, and distributed sorting), none of which requires a central authority, but still accomplishes best possible parallelization. The overall arraying is performed in O(n) time, O(n2) individual messages, and O(n) travel distance per robot. Implementation of the sorting and navigation use communication messages of fixed size, and are a practical solution for large populations of low-cost robots.

Micro- and nanorobots are often controlled by global input signals, such as an electromagnetic or gravitational field. These fields move each robot maximally until it hits a stationary obstacle or another stationary robot. This paper investigates 2D motion-planning complexity for large swarms of simple mobile robots (such as bacteria, sensors, or smart building material). In previous work we proved it is NP-hard to decide whether a given initial configuration can be transformed into a desired target configuration; in this paper we prove a stronger result: the problem of finding an optimal control sequence is PSPACE-complete. On the positive side, we show we can build useful systems by designing obstacles. We present a reconfigurable hardware platform and demonstrate how to form arbitrary permutations and build a compact absolute encoder. We then take the same platform and use dual-rail logic to build a universal logic gate that concurrently evaluates AND, NAND, NOR and OR operations. Using many of these gates and appropriate interconnects we can evaluate any logical expression.

Micro- and nanorobotics have the potential to revolutionize many applications including targeted material delivery, assembly, and surgery. The same properties that promise breakthrough solutions - small size and large populations - present unique challenges to generating controlled motion. We want to use large swarms of robots to perform manipulation tasks; unfortunately, human-swarm interaction studies as conducted today are limited in sample size, are difficult to reproduce, and are prone to hardware failures. We present an alternative. This paper examines the perils, pitfalls, and possibilities we discovered by launching SwarmControl.net, an online game where players steer swarms of up to 500 robots to complete manipulation challenges. We record statistics from thousands of players, and use the game to explore aspects of large-population robot control. We present the game framework as a new, open-source tool for large-scale user experiments. Our results have potential applications in human control of micro- and nanorobots, supply insight for automatic controllers, and provide a template for large online robotic research experiments.

This paper presents a distributed approach for exploring and triangulating an unknown region using a multirobot system. The resulting triangulation is a physical data structure that is a: compact representation of the workspace, contains distributed knowledge of each triangle, builds the dual graph of the triangulation, and supports reads and writes of auxiliary data. Our algorithm builds a triangulation in a closed two-dimensional Euclidean environment, starting from a single location. It provides coverage with a breadth-first search pattern and completeness guarantees. We show that the computational and communication requirements to build and maintain the triangulation and its dual graph are small. We then present a physical navigation algorithm that uses the dual graph, and show that the resulting path lengths are within a constant factor of the shortest-path Euclidean distance. Finally, we validate our theoretical results with experiments on triangulating a region with a system of low-cost robots. Analysis of the resulting triangulation shows that most of the triangles are of high quality, and cover a large area. Implementation of the triangulation, dual graph, and navigation all use communication messages of fixed size, and are a practical solution for large populations of low-cost robots.

Positioning a group of robots at the center of their geodesic Voronoi cells minimizes the worst-case response time for any robot to arrive at an exogenous event in the workspace. We construct these cells in a distributed fashion, building on our prior work on triangulating unknown spaces with multi-robot systems. This produces a physical data structure - a set of triangles formed by the positions of the robots that can be used to perform coverage control. This paper presents: 1) A discrete approximation of the geodesic Voronoi cell using the multi-robot triangulation. We call this a topological Voronoi cell, and show that it can be computed efficiently in a distributed fashion and with theoretical guarantees compared to continuous version. 2) A local motion controller to guide navigating robots to the centroid of their topological Voronoi cell. This controller uses bounded communications with a fixed constant, but can produce local extrema that trap navigating robots away from the optimal position. 3) An enhanced local controller using navigation agents to help guide the navigating robot to the optimal position in its Voronoi cell. It also uses bounded communications, but with a constant that can be tuned to trade communications bandwidth for increased accuracy. 4) Hardware experiments that compute the topological Voronoi cell on a group of 14 robots, simulation results that demonstrate local extrema, and the effectiveness of the virtual navigation agents, and simulation results comparing the performance of the patrolling algorithm using and not using topological Voronoi cells.

In this paper, we present flocking with cohesive configuration control - motion controllers that allow multiple robots to move through the environment as a coherent group while maintaining connectivity and density invariants. We start with a flocking controller from the literature. First, we produce a boundary force on robots that are on the internal and external boundaries of the configuration. This removes concave regions of the boundary, producing a convex configuration with uniform density. Second, we solve interstitial lattice errors caused by robots clumping too close together by moving them towards the boundary with a clump remover algorithm. Finally, we determine when a configuration is on the verge of disconnecting by identifying local articulation points; regions where the removal of a single robot will change the local topology. When one is detected, we switch modes to a clustering algorithm that draws robots to the vulnerable region. The combination of these algorithms produces a cohesive configuration controller. We verify our resulting controller with simulations from random initial conditions and selected extreme cases. Simulation results show the controller successfully forms a configuration with natural resting density in twelve of trials and maintains connectivity in twelve trials. We also provide real-world experiments to show that proposed algorithms work under low-resolution sensor platforms.

Multi-robot manipulation allows for scalable environmental interaction, which is critical for multi-robot systems to have an impact on our world. A successful manipulation model requires cost-effective robots, robust hardware, and proper system feedback and control. This paper details key sensing and manipulator capabilities of the r-one robot. The r-one robot is an advanced, open source, low-cost platform for multi-robot manipulation and sensing that meets all of these requirements. The parts cost is around $250 per robot. The r-one has a rich sensor suite, including a flexible IR communication/localization/obstacle detection system, high-precision quadrature encoders, gyroscope, accelerometer, integrated bump sensor, and light sensors. Two years of working with these robots inspired the development of an external manipulator that gives the robots the ability to interact with their environment. This paper presents an overview of the r-one, the r-one manipulator, and basic manipulation experiments to illustrate the efficacy our design. The advanced design, low cost, and small size can support university research with large populations of robots and multi-robot curriculum in computer science, electrical engineering, and mechanical engineering. We conclude with remarks on the future implementation of the manipulators and expected work to follow.

No abstract available.

Roboticists, biologists, and chemists are now producing large populations of simple robots, but controlling large populations of robots with limited capabilities is difficult, due to communication and onboard-computation constraints. Direct human control of large populations seems even more challenging. In this paper we investigate control of mobile robots that move in a 2D workspace using three different system models. We focus on a model that uses broadcast control inputs specified in the global reference frame. In an obstacle-free workspace this system model is uncontrollable because it has only two controllable degrees of freedom - all robots receive the same inputs and move uniformly. We prove that adding a single obstacle can make the system controllable, for any number of robots. We provide a position control algorithm, and demonstrate through extensive testing with human subjects that many manipulation tasks can be reliably completed, even by novice users, under this system model, with performance benefits compared to the alternate models. We compare the sensing, computation, communication, time, and bandwidth costs for all three system models. Results are validated with extensive simulations and hardware experiments using over 100 robots.

In this paper we investigate controlling many nonholonomic unicycles that each receive exactly the same inputs. The robots are almost homogeneous, but each robot has a unique parameter that scales its turning rate. Previous work showed that such a collection of robots can be approximately steered to arbitrary Cartesian positions, but not to arbitrary heading angles in a global reference frame. We extend this work by proving we can always steer such a collection of robots exactly to arbitrary range and bearing locations relative to targets in R2in a finite number of steps. We also provide existence proofs for controlling the final heading angles of many robots. This work addresses a fundamental challenge in micro-and nanorobotics with possible applications in targeted therapy, sensing, and actuation. Scale hardware experiments validate the control policy. All code is provided online.

We describe a proof-of-concept design for a low-cost two-degree-of-freedom robotic arm that incorporates series elastic actuators (SEAs) with force sensing. The cost effectiveness of the design will enable the construction of compliant manipulators for multi-robot systems with large populations. The arm assembly attaches to a commercially available mobile robot chassis to perform multi-robot coordination. In this work, we present the design of a robot arm and data from experiments to characterize the accuracy and resolution of the force sensing. We describe a force-following manipulation experiment using two robots. The experiment measures strain on a rigid bar between two robots. The data shows the feasibility of using SEAs for force sensing to reduce the strain in the bar. This is the first step towards a distributed force controller for multi-robot object coordination with large numbers of robots.

Agreement algorithms allow individual agents in a population to estimate a global quantity by sharing information. A common example is computing the global mean of a sensor measurement from each agent. We present a practical agreement algorithm, input-based consensus (IBC), that produces bounded error and recovery in the face of significant communications failures in a stochastic distributed system. We compare our algorithm to linear average consensus (LAC), which produces an exact result under ideal conditions, but is not robust to message loss. For both algorithms, we measure performance with respect to a varying percentage of dropped messages. The algorithms are examined analytically, simulated using the Stochastic Simulation Algorithm, and demonstrated experimentally on a testbed of 20 robots. In all cases, the IBC algorithm produced reasonable values, even when tested with up to 90% message loss.

We describe a distributed boundary detection algorithm suitable for use on multi-robot systems with dynamic network topologies. We assume that each robot has access to its local network geometry, which is the combination of a robot's network connectivity and the positions of its neighbors measured relative to itself. Our algorithm uses this information to classify robots as boundary or interior in one communications round, which is fast enough for rapidly changing networks. We use the local boundary classifications to create a robust boundary subgraph, and to determine if the boundary is an interior void or the exterior boundary. A proof of the key property of the boundary detection algorithm is provided, and all the algorithms are extensively tested on a swarm of 25-35 robots in rapidly changing network topologies.

This demonstration showcases distributed algorithms for configuration control in multi-robot systems. These algorithms include examples of gradient communication, clustering and dispersion, group motion, and network characterization. The algorithms are demonstrated on a swarm of 15 mobile robots.