key: cord-0044023-awm13fjn
authors: Fekete, Sándor P.
title: Coordinating Swarms of Objects at Extreme Dimensions
date: 2020-04-30
journal: Combinatorial Algorithms
DOI: 10.1007/978-3-030-48966-3_1
sha: 2618faac695904151a73587fe13b2429c11f260a
doc_id: 44023
cord_uid: awm13fjn

We describe a variety of algorithmic challenges arising from coordination and reconfiguration of swarms of potentially many objects, ranging in size from minuscule particles all the way to far-away satellite swarms. Particular results include methods for coordinating the motion of vehicles in traffic in order to avoid inefficient stop-and-go congestions; using uniform global forces for controlling particle swarms; online triangulation and structured exploration; cohesive control for swarms of robots with only local communication; coordinated motion planning for efficiently reconfiguring an arrangement of robots; and constructing and reconfiguring large-scale structures by finite automata. All presented work is based on collaborations with a variety of authors, who are named in the respective sections of this overview.

Problems of coordinating and reconfiguring arrangements of objects pose important questions at various dimensions, ranging from tiny particles all the way to far-away satellite swarms. Ironically, systems at these very small and very large distances share a fundamental property: It becomes difficult to use "external" computation, in which a powerful central computing device is provided with input about the system, and output is fed back into the system. Instead, it becomes important to consider "internal" computation, in which algorithms and execution remain within the system itself, even if that comes at the expense of processing power.

In this overview we provide a number of different contexts that require dealing with computation, communication and coordination of swarms of robots at extreme dimensions. These dimensions may correspond to extremely small or large sizes or extremely large numbers; both give rise to a wide range of algorithmic challenges. This overview provides pointers to more detailed contexts and references, and gives credit to the numerous collaborators and their contributions.

How can we coordinate the motion of many autonomous vehicles, such that the overall traffic flow is smooth and efficient? (Fig. 1) . We describe a distributed and self-regulated approach for the selforganization of a large system of many self-driven, mobile objects, i.e., cars in traffic. Based on methods for mobile ad-hoc networks using short-distance communication between vehicles, and ideas from distributed algorithms, we consider reactions to specific traffic structures (e.g., traffic jams). Building on models from traffic physics, we are able to develop strategies that significantly improve the flow of congested traffic. Results include fuel savings up to 40% for cars in stop-and-go traffic; we present a number of simulation results illustrating the efficacy of the underlying mechanisms (Fig. 2) . The results of this section summarize joint work with Sebastian Ebers, Stefan Fischer, Horst Hellbrück, Björn Hendriks, Christopher Tessars, and Axel Wegener. See [13, 16, 19] for further details.

How can we rearrange a potentially large swarm of particles that do not have their own energy supply? (Fig. 3) .

.025 mm 0.5 mm 65 mm 0.5 mm We consider algorithmic control of a large swarm of mobile particles, such as robots, sensors, or building material. The objective is to achieve arbitrary reconfiguration, even if the particles are too small to carry their own energy supply. Instead, they are moved around with the help of external forces, such as a magnetic field or gravity. Upon actuation, each object is pushed in the same direction until it collides with an obstruction. This concept can be used for a wide range of applications in which particles follow a uniform global signal. In an open workspace, this system model is of limited use, because all particles receive the same inputs and move uniformly. Thus, a crucial challenge for achieving any desired target configuration is breaking global symmetry in a controlled fashion.

We provide two different methods for this objective. The first is to add a maze of obstacles to the environment, which can make the system drastically more complex but also more useful. We provide a variety 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 (Fig. 4) . The second approach uses the interplay between static friction with a boundary and the external force to achieve arbitrary reconfiguration. As we demonstrate, it is possible to determine a precise theoretical characterization of the critical coefficient of friction that is sufficient for rearranging two particles in triangles, convex polygons, and regular polygons. We also illustrate a method for reconfiguring multiple particles in rectangular workspaces, and deriving practical algorithms for these rearrangements.

The results of this section highlight a broad spectrum of joint work with Victor Baez, Aaron Becker, Erik Demaine, Golnaz Habibi, Li Huang, Phillip Keldenich, Linda Kleist, Dominik Krupke, Jarrett Lonsford, Arun Mahadev, Sheryl Manzoor, James McLurkin, Rose Morris-Wright, Hamed Mohtasham Shad, Christian Rieck, Christian Scheffer, and Arne Schmidt; see [3, 4, [6] [7] [8] 10, 20, 23, 24, 26, 27] for further details. The shown video [2] is available at https://www. ibr.cs.tu-bs.de/users/fekete/Videos/SoCG/2020/Friction SoCG.mp4; an earlier video with further theoretical results [5] can be found at https://www.ibr.cs.tubs.de/users/fekete/Videos/SoCG/2015/TiltforCompGeom100mb.mp4.

How can we allow a swarm of relatively simple robots to cooperate in exploring an unknown environment? (Figs. 5 and 6 ).

We consider a fundamental framework for organizing exploration, coverage, and surveillance by a swarm of robots with limited individual capabilities, based on triangulating an unknown environment with a multi-robot system. Locally, an individual triangle is easy for a single robot to manage and covers a small area; globally, the topology of the triangulation approximately captures the geometry of the entire environment. Combined, a multi-robot system can explore, map, navigate, and patrol. Algorithms can store information in triangles that the robots can read and write as they run their algorithms. This creates a physical data structure (PDS) that is both robust and versatile. We study distributed approaches to triangulating an unknown, two-dimensional Euclidean space using a multi-robot network. The resulting PDS is a compact representation of the workspace, contains distributed knowledge of each triangle, encodes the dual graph of the triangulation, and supports reads and writes of auxiliary data. The ability to store and process this auxiliary information enables the simple robots to solve complex problems. This leads to distributed algorithms for dual-graph navigation, patrolling, construction of a topological Voronoi tessellation, and location of the geodesic centers in non-convex regions, making it possible to provide theoretical performance guarantees for the quality of constructed triangulation and the connectivity of a dual graph in the triangulation. In addition, the path lengths of the physical navigation are within a constant factor of the shortest-path Euclidean distance. These theoretical results were also practically validated with simulations and experiments with dozens of robots.

The results of this section summarize joint work with Aaron Becker, Tom Kamphans, Alexander Kröller, Seoung Kyou Lee, James McLurkin, Joe Mitchell, and Christiane Schmidt. See our papers [17, 22] for further details; the shown video [18] is available at https://www.ibr.cs.tu-bs.de/users/fekete/ Videos/SoCG/2013/MATP-Video.mov.

How can we enable a swarm of simple robots to maintain connectivity, even if it is being pulled apart by external forces? (Fig. 7) . Consider a swarm of robots that needs to remain connected. There is no central control and no knowledge of the overall environment. This environment is hostile: The swarm is being pulled apart by external forces, stretching it into a number of different directions, so it is in danger of breaking up. Individual robots are weak, with limited sensing, limited communication, and limited connectivity; even worse, each robot's expected lifetime is limited by random, permanent failures, which may destroy connectedness and functioning of the swarm as a whole. The objective is to achieve coordinated dynamic swarm behavior without centralized coordination, employing each robot as much as possible, without depending on it if it fails, and balancing overall flexibility and robustness to deal with the hostile environment.

We propose a set of local continuous algorithms that together produce a generalization of a Euclidean Steiner tree. At any stage, the resulting overall shape achieves a good compromise between local thickness, global connectivity, and flexibility to further continuous motion of the terminals. The resulting swarm behavior scales well, is robust against node failures, and performs close to the best known approximation bound for a corresponding centralized static optimization problem.

The results of this section summarize joint work with Dominik Krupke, Maximilian Ernestus, and Michael Hemmer. See our paper [21] for further details.

How can we coordinate the collision-free motion of many robots, vehicles, aircraft, or people, such that each one reaches its destination as quickly as possible? (Fig. 8) . We develop constant-factor approximation algorithms for minimizing the execution time of a coordinated parallel motion plan for a relatively dense swarm of homogeneous robots in the absence of obstacles. In our first model, each robot has a specified start and destination on the square grid, and in each round of coordinated parallel motion, every robot can move to any adjacent position that is either empty or simultaneously being vacated by another robot. In this model, our algorithm achieves a constant stretch factor : If every robot starts at a distance of at most d from its destination, then the total duration of the overall schedule is O(d), which is optimal up to constant factors. Our result holds for distinguished robots (each robot has a specific destination), identical (unlabeled) robots, and most generally, classes of different robot types (where each destination specifies a required type of robot). We also show that finding the optimal coordinated parallel motion plan is NP-hard, justifying approximation algorithms.

In our second model, each robot is a unit-radius disk in the plane, and robots can translate continuously in parallel subject to not intersecting, i.e., having disk centers at L 2 -distance at least 2. We prove the same resultconstant-factor approximation algorithm to minimizing execution time via constant stretch factor-when the pairwise L ∞ -distance between disk centers is at least 2 √ 2 = 2.8284 . . .. On the other hand, for N densely packed disks at distance at most 2 + δ for a sufficiently small δ > 0, we prove that a stretch factor of Ω(N 1/4 ) is sometimes necessary (when densely packed), while a stretch factor of O(N 1/2 ) is always possible.

The results of this section summarize joint work with Aaron Becker, Erik Demaine, Phillip Keldenich, Lilian Li, and Henk Meijer. See our paper [12] for further details; the shown video [9] is available at https://www.ibr.cs.tu-bs.de/ users/fekete/Videos/SoCG/2018/CoordinatedMotionPlanning.mp4.

How can we use simple robots to construct large-scale structures, such as space stations? (Fig. 9 ).

20% 40% 60% 80% 100% Fig. 9 . Snapshots from building a bounding box for a Z-shaped polyomino using 2D simulator, 3D simulator, and staged hardware robots, synchronized so all are shown at steps {0, 24, 48, 72, 96, 120}.

We consider recognition and reconfiguration of lattice-based cellular structures by very simple robots with only basic functionality. The underlying motivation is the construction and modification of space facilities of enormous dimensions, where the combination of new materials with extremely simple robots promises structures of previously unthinkable size and flexibility. We present algorithmic methods that are able to detect and reconfigure arbitrary polyominoes, based on finite-state robots, while also preserving connectivity of a structure during reconfiguration. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.

The results of this section summarize joint work with Amira Abdel-Rahman, Aaron Becker, Daniel Biediger, Kenny Cheung, Neil Gershenfeld, Sabrina Hugo, Ben Jenett, Phillip Keldenich, Eike Niehs, Christian Rieck, Arne Schmidt, Christian Scheffer, and Michael Yannuzzi. See our papers [15, 25] for further details; the shown video [1] is available at https://www.ibr.cs.tu-bs.de/users/fekete/ Videos/SoCG/2020/SpaceAnts SoCG.mp4.

Many of the presented topics are still subject to ongoing work; see the recent survey article [14] for more details on context, content and technical details, as well as additional references for some of the described topics. We are confident that more progress on a wide range of related problems is imminent.

Space ants: constructing and reconfiguring large-scale structures with finite automata. In: Symposium on Computational Geometry (SoCG)

Coordinated particle relocation with global signals and local friction

Reconfiguring massive particle swarms with limited, global control

Particle computation: designing worlds to control robot swarms with only global signals

Tilt: the video. Designing worlds to control robot swarms with only global signals

Particle computation: device fan-out and binary memory

Particle computation: complexity, algorithms, and logic

Targeted drug delivery: algorithmic methods for collecting a swarm of particles with uniform, external forces

Coordinated motion planning: the video

Tilt assembly: algorithms for micro-factories that build objects with uniform external forces

Feedback control of many magnetized Tetrahymena pyriformis cells by exploiting phase inhomogeneity

Coordinated motion planning: reconfiguring a swarm of labeled robots with bounded stretch

Verfahren und Vorrichtung zur Ermittlung einer Fahrstrategie

Geometric aspects of robot navigation: from individual robots to massive particle swarms

Cadbots: algorithmic aspects of manipulating programmable matter with finite automata

(eds) Organic Computing -A Paradigm Shift for Complex Systems

Exploring and triangulating a region by a swarm of robots

Triangulating unknown environments using robot swarms

Empowered by wireless communication: distributed methods for self-organizing traffic collectives

On designing 2D discrete workspaces to sort or classify polynminoes

Distributed cohesive control for robot swarms: maintaining good connectivity in the presence of exterior forces

Structured triangulation in multi-robot systems: coverage, patrolling, voronoi partitions, and geodesic centers

Mapping, foraging, and coverage with a particle swarm controlled by uniform inputs

Collecting a swarm in a 2D environment using shared, global inputs

Recognition and reconfiguration of lattice-based cellular structures by simple robots

Efficient parallel self-assembly under uniform control inputs

Coordinated particle relocation using finite static friction with boundary walls