Aaron T. Becker

Mariem Guitouni, Aaron T. Becker

Autonomous drone swarms deployed for surveillance, environmental monitoring, and infrastructure inspection must maintain reliable coverage of critical assets despite robot failures. This requires multicoverage: each asset must be observed by multiple robots for redundancy, with coverage requirements varying by asset importance. While recent work has solved the centralized problem optimally using integer programming, practical deployments face constraints that demand distributed solutions: robots operate with limited communication ranges, onboard computation restricts global planning, and partial system failures must not cause mission abort. We present a distributed multicoverage algorithm for robot swarms operating with local sensing, local communication, and no global coordination.

Daniel Biediger, Luben Popov, Aaron T. Becker

This paper investigates the pursuit-evasion problem of a defensive gun turret and one or more attacking drones. The turret must ``visit" each attacking drone once, as quickly as possible, to defeat the threat. This constitutes a Shortest Hamiltonian Path (SHP) through the drones. The investigation considers situations with increasing fidelity, starting with a 2D kinematic model and progressing to a 3D dynamic model. In 2D we determine the region from which one or more drones can always reach a turret, or the region close enough to it where they can evade the turret. This provides optimal starting angles for $n$ drones around a turret and the maximum starting radius for one and two drones. We show that safety regions also exist in 3D and provide a controller so that a drone in this region can evade the pan-tilt turret. Through simulations we explore the maximum range $n$ drones can start and still have at least one reach the turret, and analyze the effect of turret behavior and the drones' number, starting configuration, and behaviors.

Yitong Lu, Anuruddha Bhattacharjee, Daniel Biediger et al.

This paper examines a family of designs for magnetic cubes and counts how many configurations are possible for each design as a function of the number of modules. Magnetic modular cubes are cubes with magnets arranged on their faces. The magnets are positioned so that each face has either magnetic south or north pole outward. Moreover, we require that the net magnetic moment of the cube passes through the center of opposing faces. These magnetic arrangements enable coupling when cube faces with opposite polarity are brought in close proximity and enable moving the cubes by controlling the orientation of a global magnetic field. This paper investigates the 2D and 3D shapes that can be constructed by magnetic modular cubes, and describes all possible magnet arrangements that obey these rules. We select ten magnetic arrangements and assign a "colo"' to each of them for ease of visualization and reference. We provide a method to enumerate the number of unique polyominoes and polycubes that can be constructed from a given set of colored cubes. We use this method to enumerate all arrangements for up to 20 modules in 2D and 16 modules in 3D. We provide a motion planner for 2D assembly and through simulations compare which arrangements require fewer movements to generate and which arrangements are more common. Hardware demonstrations explore the self-assembly and disassembly of these modules in 2D and 3D.

Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete et al.

We investigate algorithmic control of a large swarm of mobile particles (such as robots, sensors, or building material) that move in a 2D workspace using a global input signal (such as gravity or a magnetic field). We show that a maze of obstacles to the environment can be used to create complex systems. We provide a wide range of results for a wide range of questions. These can be subdivided into external algorithmic problems, in which particle configurations serve as input for computations that are performed elsewhere, and internal logic problems, in which the particle configurations themselves are used for carrying out computations. For external algorithms, we give both negative and positive results. If we are given a set of stationary obstacles, we prove that it is NP-hard to decide whether a given initial configuration of unit-sized particles can be transformed into a desired target configuration. Moreover, we show that finding a control sequence of minimum length is PSPACE-complete. We also work on the inverse problem, providing constructive algorithms to design workspaces that efficiently implement arbitrary permutations between different configurations. For internal logic, we investigate how arbitrary computations can be implemented. We demonstrate how to encode 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. However, we establish that simulating the full range of complex interactions present in arbitrary digital circuits encounters a fundamental difficulty: a fan-out gate cannot be generated. We resolve this missing component with the help of 2x1 particles, which can create fan-out gates that produce multiple copies of the inputs. Using these gates we provide rules for replicating arbitrary digital circuits.

Shiva Shahrokhi, Lillian Lin, Chris Ertel et al.

Microrobotics has 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 for controlling motion. Robotic manipulation usually assumes intelligent agents, not particle systems manipulated by a global signal. To identify the key parameters for particle manipulation, we used a collection of online games where players steer swarms of up to 500 particles to complete manipulation challenges. We recorded statistics from over ten thousand players. Inspired by techniques where human operators performed well, we investigate controllers that use only the mean and variance of the swarm. We prove the mean position is controllable and provide conditions under which variance is controllable. We next derive automatic controllers for these and a hysteresis-based switching control to regulate the first two moments of the particle distribution. Finally, we employ these controllers as primitives for an object manipulation task and implement all controllers on 100 kilobots controlled by the direction of a global light source.

Arun V. Mahadev, Dominik Krupke, Jan-Marc Reinhardt et al.

This paper investigates efficient techniques to collect and concentrate an under-actuated particle swarm despite obstacles. Concentrating a swarm of particles is of critical importance in health-care for targeted drug delivery, where micro-scale particles must be steered to a goal location. Individual particles must be small in order to navigate through micro-vasculature, but decreasing size brings new challenges. Individual particles are too small to contain on-board power or computation and are instead controlled by a global input, such as an applied fluidic flow or electric field. To make progress, this paper considers a swarm of robots initialized in a grid world in which each position is either free-space or obstacle. This paper provides algorithms that collect all the robots to one position and compares these algorithms on the basis of efficiency and implementation time.

Shiva Shahrokhi, Arun Mahadev, Aaron T. Becker

Consider a swarm of particles controlled by global inputs. This paper presents algorithms for shaping such swarms in 2D using boundary walls. The range of configurations created by conforming a swarm to a boundary wall is limited. We describe the set of stable configurations of a swarm in two canonical workspaces, a circle and a square. To increase the diversity of configurations, we add boundary interaction to our model. We provide algorithms using friction with walls to place two robots at arbitrary locations in a rectangular workspace. Next, we extend this algorithm to place $n$ agents at desired locations. We conclude with efficient techniques to control the covariance of a swarm not possible without wall-friction. Simulations and hardware implementations with 100 robots validate these results. These methods may have particular relevance for current micro- and nano-robots controlled by global inputs.