Geometric Aspects of Robot Navigation: From Individual Robots to Massive Particle Swarms

Abstract

We describe a spectrum of challenges and results related to geometric aspects of robot navigation, advancing from centralized methods for difficult offline problems (such as the Art Gallery Problem), to online tasks for many robots (as in online exploration by a swarm of robots), locally managing the connectivity and shape of a large swarm (i.e., cohesive control), all the way to controlling massive swarms of particles by global forces.

1 Introduction

Ever since the first work on autonomous robots, algorithmic aspects of robot navigation have played an important role, with new theoretical insights making it possible to expand the practical possibilities, and new real-world challenges motivate algorithmic innovation. Particularly important roles in these developments were played by geometry and by the advances of distributed models and methods. In the following, we provide a number of highlights: The Art Gallery Problem described in Sect. 2 deals with localizing stationary viewpoints for mapping all of a given, known region. Section 3 describes how to explore and triangulate an unknown region by a swarm of simple robots with only weak sensor and navigation capabilities. Section 4 deals with the challenge of cohesive control, i.e., organizing a swarm of simple agents by local interaction, such that connectivity is maintained, even in the presence of external forces and agent failures. The final Sect. 5 describes how to control a massive swarm of particles by using uniform external forces.

2 Art Gallery Problems

2.1 Motivation

Consider a robot platform that can produce high-resolution, virtual environments, based on a limited number of laser scans. For mapping all of a given region in the presence of obstacles, we need to compute an optimal set of scan positions. This is closely related to one of the classic problems of computational geometry: The Art Gallery Problem (AGP) asks for illuminating or surveying all of a given polygonal region P from as few positions (“guards”) as possible.

2.2 Formal Aspects

Consider a given polygonal region P. For any point $g\in P$, the visibility region $\mathcal {V}(g)$ is the set of all positions $p\in P$ for which there is a straightline connection between G and p that lies completely in P. The Art Gallery Problem (AGP) asks for a minimum cardinality guard set $G\subset P$ that sees all of P, i.e., such that $\bigcup _{g\in G} \mathcal {V}(g) =P$. An important distinction arises from the possible positions of guards: a vertex guard must be placed at a vertex of P, while a point guard can be located anywhere in P.

2.3 Context

As first proven by Chvátal [15] and shown by Fisk [32] in a beautiful and concise proof, $\lfloor \frac{n}{3}\rfloor$ guards are sometimes necessary and always sufficient for guarding a simple polygon P with n vertices. See O’Rourke [64] for an early overview.

Algorithmically, the AGP is NP-hard, even for a simply connected polygonal region P [51]. Eidenbenz et al. [20] showed that for a region with holes, finding an optimal set of vertex guards is at least as hard as the problem Set Cover, so there is little hope of achieving a better approximation guarantee than $\varOmega (\log n)$. It seems unlikely that this gets any easier when allowing general point guards, as there is no known simple characterization of a discrete candidate set of guard locations. Furthermore, recent work by Abrahamsen et al. [1] proves that the AGP is complete for the existential theory of the reals, implying that it is unlikely to even belong to the class NP.

All this shows the difficulty of the AGP, but it does not rule out methods that combine structural insights with powerful mathematical tools to achieve provably optimal solutions for instances of interesting size.

Computing optimal solutions for general AGP instances is not only relevant from a theoretical point of view, but has also gained in practical importance in the context of modeling, mapping, and surveying complex environments, such as in the fields of architecture, robotics and medicine.

2.4 Application Scenario

One particular real-world platform giving rise to instances of the Art Gallery Problem is Irma3D (Intelligent Robot for Mapping Applications in 3D), an autonomous robot; see Fig. 1. Its main sensor is a Riegl VZ-400 laser scanner. A typical 3D laser scan needs 3 min, producing up to 20 million highly precise 3D measurements of the surrounding. A globally consistent scan matching is used to merge the 3D scans to a single scene [11]. Irma3D is built on a Volksbot RT-3 chassis; it uses the Xsens MTi IMU and odometry to sense its own position. See Fig. 2 for a real-world image (Top) and the schematic view with an optimal set of scan points (Bottom). The algorithmic challenge is to plan number and positioning of these scans.

Fig. 1.

IRMA3D in front of the town hall of Bremen, scanning the city square.

Fig. 2.

(Top) part of a real-life AGP instance with 15 holes and 332 vertices: a square in the city center of Bremen. (Bottom) a corresponding extracted polygonal region, with an optimal set of scan positions, shown as 15 black dots. The white holes correspond to obstacles formed by buildings in the square.

2.5 Algorithmic Insights

Independently, different groups (Braunschweig and Campinas) have combined methods from integer (IP) and linear programming (LP) with non-discrete geometry in order to obtain optimal solutions; first for the discrete case of vertex guards [17], but later also for general point guards [46, 73].

The algorithm in [73] computes lower and upper bounds for the AGP, based on computing finite set cover instances with the help of a state-of-the-art IP solver. To generate a lower bound, a finite set of witness candidates is chosen and a restricted AGP is solved, in which only the witnesses have to be covered. For this, it suffices to extract a finite set of potential guard positions from the visibility arrangement of the witness set to ensure optimality. Similarly, finite sets of potential witness positions for a given finite guard set can be extracted from the visibility arrangement of the guards. This allows it to compute upper and lower bounds for the optimal AGP value by solving discrete set cover instances. The algorithm in [73] iterates between generating tighter lower and upper bounds by refining the witness and guard candidate sets along the iterations. It stops when lower and upper bounds coincide. Although no proof of theoretical convergence is known (and the work by Abrahamsen et al. [1] strongly suggests that no such convergence can exist for all classes of instances), in tests, the approach is able to yield optimal solutions for a large variety of instance classes, even for polygons with up to a thousand vertices.

An approach presented in [46] considers a similar primal-dual scheme, but focuses on the linear relaxation of the primal guard cover with guard set G, from which a small subset has to be selected to cover all points from a witness set W: For each point $w\in W$, a guard in its visibility region $\mathcal {V}(w)$ must be chosen. Allowing fractional guards corresponds to admitting guard variables $0\le x_g\le 1$ for any guard $g\in G$. This yields the following linear program.

$$\begin{aligned} \text {min}&\sum _{g\in G} x_g \end{aligned}$$

(1)

$$\begin{aligned} \text {s.}\,\text {t.}&\sum _{g\in G\cap \mathcal {V}(w)} x_g \ge 1 \;\; \forall w\in W\end{aligned}$$

(2)

$$\begin{aligned}&0\le x_g\le 1 \quad \quad \quad \forall g\in G \end{aligned}$$

(3)

Its dual is the witness packing problem, in which the objective is to find as many independent witness positions $w\in W$ as possible, such that no two of them can be seen from the same guard position $g\in G$.

$$\begin{aligned} \text {max}&\sum _{w\in W} y_w \end{aligned}$$

(4)

$$\begin{aligned} \text {s.}\, \text {t.}&\sum _{g\in G\cap \mathcal {V}(w)} y_w \le 1 \; \forall g\in G\end{aligned}$$

(5)

$$\begin{aligned}&0\le y_w\le 1 \quad \quad \forall w\in W \end{aligned}$$

(6)

Because of strong duality of linear programming, considering these fractional guard and witness values leads to optimal primal and dual solutions with identical objective values. To eliminate fractional solutions, we can apply appropriate cutting planes derived from the set cover polytope, based on specific subsets $J_1\cap G$ and $J_2\cap G$.

$$\begin{aligned} \sum _{g \in J_2 \cap G} 2 x_g + \sum _{g \in J_1 \cap G} x_g \ge 2 \end{aligned}$$

(7)

As it turns out [24], only a small subset of these inequalities matter in the context of AGP instances. Together with a similar primal-dual iteration scheme such as the one in [73], we can find optimal integral solutions for a large range of benchmark instances, including the one shown in the scenario above; see Fig. 3 for a pair of primal and dual solutions.

Fig. 3.

A pair of primal and dual solutions to the fractional linear programming relaxation.

2.6 Extensions

There are various extensions and related questions. In the work described above, the robot has unlimited viewing distance, only the number of scans is to be minimized, and the given region is known in advance. We have also studied this problem for the case of limited viewing distance and an objective function that is a linear combination of the number of scans and distance traveled by the robot. See [29] and the cited related work. We have also studied the context of exploring an unknown region by a robot with discrete vision; see [31].

2.7 Acknowledgments

The content of this section is based on the abstract [10] and paraphrases the joint work with Dorit Borrmann, Pedro de Rezende, Cid de Souza, Stephan Friedrichs, Alexander Kröller, Andreas Nüchter and Christiane Schmidt contained in the papers [24, 46]. For a visualization, see the video that accompanies [10], to be found at the website http://www.computational-geometry.org/SoCG-videos/socg13video/#Borrmann-etal.

3 Online Exploration and Triangulation by a Swarm of Simple Robots

3.1 Motivation

Consider a swarm of inexpensive robots without explicit mapping capabilities in an unknown area. Each robot has a limited visibility range, but can move around to get a more complete picture of the environment. Once the region has been fully covered, the robots can also stay around so that we can get live updates. How can we organize this exploration and make sure that we can continue to observe all parts of the environment after they are discovered?

3.2 Formal Aspects

We are given a polygonal region P, and a point $z\in P$ on the boundary of P. In addition, we are given a supply of robots with limited (circular) communication range r; for ease of description, we normalize to $r = 1$. Within this range, perception of and communication with other robots is possible. In the Minimum Relay Triangulation Problem (MRTP), the goal is to compute a set R of robot positions within P (with $z\in R$ and $V\subseteq R$ for the vertex set V of P), such that there is a (unit) triangulation of P whose vertex set is exactly the set R and whose edges stay within P and have length at most 1. The objective is to minimize the number of robots. In the Maximum Area Triangulation Problem (MATP), the number of available robots is bounded by a number k; the goal is to determine a set R of at most k robot positions, with a unit triangulation covering a maximum possible area. For the online versions (OMRTP and OMATP), the polygon P is unknown. Each robot may move through the area, and has to decide on a new location for a triangulation vertex, while still being within reach of the previously placed relays. Once it has stopped, it becomes part of the static triangulation, allowing other relays to extend the exploration.

3.3 Context

In recent years, the field of robotics has seen two diverging trends. One has been to achieve progress by increasing the capabilities of individual robots, keeping the cost of state-of-the-art machines relatively high. An opposite direction has been to develop simpler and cheaper platforms, at the expense of reducing the capabilities per robot. The latter raises new challenges for developing new principles and algorithms, such as coordinating many robots with limited capabilities into a swarm that can carry out difficult tasks, such as exploration, surveillance, and guidance.

3.4 Application Scenario

A real-life example of an advanced, low-cost, swarm robot design with limited sensor capabilities is the r-one [61], shown in Fig. 4. Its estimated unit cost is about US $250. Measuring only 11 cm in diameter, it has a 32-bit ARM-based microcontroller, running at 50 MHz with no floating point unit. The local infrared (IR) communication system is used for inter-robot communication and localization. Each robot has eight IR transmitters and eight receivers. The transmitters broadcast in unison and emit a radially uniform energy pattern. The robot’s eight IR receivers are radially spaced to produce 16 distinct detection regions (shown in Fig. 4 (Right)). By monitoring the overlapping regions, the bearing of neighbors can be estimated to within ${\approx }\pi /8$. Thus, it has limited capabilities for measurement, which is intertwined with local communication. The IR receivers have a maximum bit rate of 1250 bits per second. Each robot transmits $(\varDelta +1)$ 4-byte messages during each round, one being a system announce message, the others containing the bearing measurements to that robot’s neighbors. The system supports a maximum of $\varDelta =10$. For more on experimental work on coordination and navigation of r-ones, see [61, 62].

Fig. 4.

(Left) the r-one for multi-robot research, designed by the MRSL group at Rice University. (Right) IR receiver detection regions. Each receiver detects an overlapping $68^\circ$, allowing to determine angles within about $22.5^\circ$.

The algorithmic challenge is to exploit the capabilities of a swarm to overcome the limitations of the individual robots, and achieve overall behavior with provable performance guarantees that are rooted in solid algorithmic theory.

3.5 Algorithmic Insights

The problems MRTP and MATP were introduced in [26]; the currently best results for the online versions OMRTP and OMATP were presented in [25, 68]. Both problems share their decision problem, which is known to be NP-hard. For the OMRTP, there is a lower bound of 6/5 on the competitive factor of any deterministic strategy, as well as a 3-competitive algorithm for general polygons. This strategy is shown in Fig. 5: We place robots at unit intervals along the boundary (green) and fill the interior with a regular triangular grid (blue). The space between the two is patched together using a third class (red). One can prove that the size of each of the three classes is bounded by the number of robots in an optimal solution. For polyominoes, algorithms with better competitive factors exist [30].

Fig. 5.

The 3-competitive strategy for the OMRTP, consisting of three sets of robots: green robots are placed along the boundary at vertices and at unit distance along edges; blue robots fill the interior by a grid; red robots complete the triangulation by connecting boundary interior robots. (Color figure online)

On the other hand, the OMATP does not admit a deterministic strategy with a constant competitive factor, if the polygon may have small corridors. If these can be excluded, greedy strategies perform well [30].

These strategies have been used on the real robots described above; see Fig. 6 for a snapshot.

Fig. 6.

A swarm of r-ones executing the online algorithm for the OMATP in the real world.

3.6 Extensions

Once a well-formed triangulation (with lower bounds on minimum edge length and minimum internal angle) is established, it can be employed for a number of different purposes. In [53], we show how the underlying connectivity graph of the robots forming the triangulation can be used for maintaining the corresponding dual graph (in which vertices correspond to triangles, and edges represent triangles sharing a common boundary), and how a minimum hop count in the unweighted dual graph achieves a constant stretch factor compared to the shortest geometric distances, i.e., manages to stay within a constant factor of the shortest achievable distance with global information; see Fig. 7.

Fig. 7.

Using a dual path for routing in a triangulated environment: a shortest path (shown in red) is approximated by a minimum-hop path (shown in yellow), achieving constant stretch. (Color figure online)

Another application of a triangulation is to use it for surveying the underlying region by additional, mobile robots, again based on the dual graph of the stationary triangulation. In [2, 54, 57], we discuss various aspects of local policies for patrolling the vertices of such a graph.

3.7 Acknowledgments

The content of this section is based on the abstract [28] and paraphrases the joint work with Aaron Becker, Tom Kamphans, Alexander Kröller, Seoung Kyou Lee, James McLurkin, Joe Mitchell, Christiane Schmidt, described in the papers [25, 52, 54]. For a visualization, see the video http://www.computational-geometry.org/SoCG-videos/socg13video/#Becker-etal that accompanies [28]. See the journal paper [54] for full technical details of the robotics side and its extensions.

4 Distributed Cohesive Control

4.1 Motivation

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. How can we achieve coordinated dynamic swarm behavior without centralized coordination? How can we employ each robot as much as possible, without depending on it if it fails? How can we balance overall flexibility and robustness to deal with the hostile environment?

The challenge is to develop local self-stabilizing mechanisms that allow the swarm to stay locally well connected (forcing swarm members to stay close to each other), even when it is being pulled apart by several distant and mobile sites (forcing swarm members to spread out).

Fig. 8.

A robust robot swarm emulating a Steiner tree between five diverging leader robots.

4.2 Formal Aspects

We consider a finite set of robots $\mathcal {R}$ with an externally controlled subset of leader robots $\mathcal {L}\subsetneq \mathcal {R}, |\mathcal {L}|\ll |\mathcal {R}|$. We want the remaining robots $\mathcal {R}\setminus \mathcal {L}$ to maintain a dynamic and robust network that keeps the swarm connected, even in the presence of random robot failures and arbitrary leader movements. Thus, the overall shape of the swarm should form a “thick” Steiner tree among the leaders with the robots $\mathcal {R}\setminus \mathcal {L}$ evenly distributed along the edges, as shown in Fig. 8.

Robots have the shape of circles; two of them are connected when within a maximum distance and with an unobstructed line of sight. Robots know the relative positions and orientations of their neighbors and can communicate asynchronously. Each robot has a unique ID; leader IDs are known by all others. Robot’s translations and rotations are limited in velocity and acceleration. Communication is possible by broadcasting to immediate neighbors.

The perception of all robots is local; however, due to the known position and orientation difference, each robot can transform vectors of its neighbors to its own coordinate system. We avoid multi-hop transformations to keep errors small.

4.3 Context

One of the earliest works on flocking is Reynold’s pioneering work [66]. In recent years, a considerable number of aspects and objectives have extended this perspective. We highlight only some of the ensuing papers, showing how they differ from our perspective.

A basic component of flocking is volumetric control, as it was presented by Spears [71]: Robots use local potential field controllers (with attractive and repulsive forces) for constructing a regular lattice with a corresponding base density [40, 63]. This does not necessarily preserve connectivity [3, 36, 71]. While the latter can be side-stepped by simply assuming that robots are always connected [70], we aim for connectivity as a requirement, which is vital in a fully distributed setting in which deterministic recovery from disconnectedness may be impossible.

Some of the ideas of Olfati-Saber [63] form the basis of our work; however, in that model, robots do utilize global information, e.g., the position of a guide robot in a shared coordinate frame [14, 49, 50, 63] or environmental potential [34]. Instead of the potentials, Cortes et al. [16] and Lindhé et al. [56] used Voronoi tessellation. This is based on a density function, requiring global information for covering a region. Overall, this differs from our objective of developing methods that are fully distributed, aiming for collective mechanisms for complex group behavior that go beyond relatively simple objectives [9], but also for systems that are robust against partial hardware failures [43].

The final property is cohesiveness of the overall swarm: all robots should maintain a unified state, such as desired distance or orientation; see [63] for a formal definition. As described in [60], detecting and maintaining a swarm boundary is of particular importance for maintaining swarm cohesiveness and connectedness. This is based on and related to work in the field of wireless sensor networks (WSNs), which has considered many geometric settings in which a large swarm of stationary nodes is faced with the task of achieving a large-scale overall goal, while the individual components can only operate locally, based on limited individual capabilities and information; refer to Fekete et al. [27, 47] for a detailed description. In addition to the work on swarm robotics described above, there is a large body of theoretical work on geometric swarm behavior; here we only mention Chazelle [13] for flocking behavior, and Fekete et al. [27, 47] for geometric algorithms for static sensor networks, including distributed boundary detection.

Beyond the involved properties and paradigm, the overall goal for the swarm can also be described as a distributed optimization problem: Maintain a generalized Steiner tree with limited edge lengths that connects a moving set of terminals. To the best of our knowledge, only Hamann and Wörn [35] have explicitly considered the construction of Steiner trees by a robot swarm. For static terminals, they start with an exploratory network; as soon as all terminals are connected, only best paths are kept and locally optimized.

Even in a centralized and static setting with full information, we must deal with a generalization of the well-known NP-hard problem of finding a good Steiner tree [33]; see the books by Hwang et al. [41] and Prömel and Steger [65] for further introduction. More specifically, we are faced with the relay placement problem: The input is a set of sensors and a number $r \ge 1$, the communication range of a relay. The objective is to place a minimum number of relays so that between every pair of sensors is connected by a path through sensors and/or relays. The best known theoretical performance bound for this NP-hard problem was given by Efrat et al. [19], who presented a 3.11-approximation algorithm; they also showed a worst-case lower bound of 3 for a large class of approximation algorithms. For a fixed number of available relays, this turns into our problem of maximizing the achievable networks size, with matching approximation factor.

4.4 Algorithmic Insights

A key insight is that achieving complex overall behavior can be based not only on local interaction that resembled physical forces, but also on principles of distributed algorithms that build more complex structures. To this end, we have developed a number of powerful local mechanisms for maintaining a dynamic swarm of robots with limited capabilities and information, in the presence of external forces and permanent node failures. These mechanisms consist of a set of local, self-stabilizing, continuous algorithms that together produce a generalization of a Euclidean Steiner tree, maintain a dynamic and robust network between leader robots. 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, adopting the directions of multiple leaders, while preserving a uniform thickness along the edges of the Steiner tree. 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.

We first sketch the base behavior of the robots, inducing an almost convex swarm shape. This is subsequently improved by leader forces, and stability improvement and thickness contraction.

4.4.1 Base Behavior

Our base behavior consists of three components that result in a swarm shape of a droplet. (i) The flocking algorithm of Olfati-Saber [63] considers regular distribution and movement consensus. The algorithm is a stateless equation based on potential fields and is proven to converge. It uses three rules: Attraction to neighbors, repulsion from too close neighbors, and adaption to the velocity of neighbors. We slightly modified the algorithm for better response to additional forces. (ii) An extended version of the boundary detection algorithm of McLurkin and Demaine [60], which determines if a robot lies on the boundary and also identifies small holes by using the average angle. (iii) The boundary tension of Lee and McLurkin [55], which straightens and minimizes the boundary of the swarm. This is done by simply pushing boundary robots to the middle of its two boundary neighbors.

Fig. 9.

A swarm configuration in which a purely physics-based mechanism lead to disconnection.

The base behavior without any other forces results in at most convex shapes before losing connectivity. Figure 9 shows a situation in which the swarm is about to lose connectivity. For stronger control and more variable shapes, leader forces are introduced.

4.4.2 Leader Forces

A single leader constitutes the simplest form of swarm control. In this case the swarm motion is determined by the leader’s velocity. With multiple (possibly antagonistic) leaders, the swarm is not just steered, but may be stretched to the limit until connectivity is lost. To this end, each robot needs to find an appropriate balance between the influence of different leaders. See top of Fig. 10 for an illustration. We therefore combine both methods by a smooth transition between velocity matching close to the leaders and leader pursuit when further away; see the bottom of Fig. 10.

Fig. 10.

(Top) A one-dimensional scenario with two leaders (red) moving in opposite directions. (Bottom) With increasing distance to the leader, the effect shifts from velocity matching to leader pursuit. (Color figure online)

4.4.3 Stability Improvement and Thickness

Near Steiner points, connections along concave swarm boundaries may be stretched by boundary forces. When the involved edges approach the upper bound for communication, connections may be disrupted, to the point where the swarm loses connectivity. By adding a thickness-dependent compression force, we reduce neighbor distances without influencing the Steiner-tree shape of the swarm; in effect, this works similar to compression stockings. Algorithmically, the involved mechanisms resemble methods that have been studied in the context of sensor networks, such as local methods for boundary detection and hop distance from the boundary. This gives rise to notions such as the hop circle of radius h with robot r as circle center: This is the set of all robots with a hop count ${\le } h$ to c; only robots with hop distance at least h may be on the boundary, so a hop circle of maximal radius around a given robot gives an indication of the local thickness in its neighborhood. (For an example, see Fig. 11.)

Fig. 11.

Thickness determination for a limb part of a swarm. The indicated triples of numbers at each node r correspond to (b(r) / t(r) / h(r)), where b(r) is the hop count from the boundary, t(r) is the local thickness, and h(r) is the circle center distance. A largest hop circle is marked in blue. (Color figure online)

This allows local approaches to keep track of and maintain local thickness and connectivity, even in the presence of external forces and robot failures. See our paper [48] for more technical details.

Fig. 12.

A comparison of strategies for the same example, for a swarm with $n=400$ and failure rate 0. As indicated, columns correspond to strategies Base, Leader, and All. Rows show the swarms at times $T=200$, $T=2000$, $T=3000$, $T=7600$, $T=12,000$, with 60 steps per simulated second. When a swarm is no longer shown, it has become disconnected right after the previous time step.

4.5 Extensions

There are numerous possible extensions, most notably for dealing with a cohesive swarm in the presence of obstacles. At this time, these are still under development.

4.6 Acknowledgments

The content of this section is based on the abstract [22] and paraphrases the joint work with Maximilian Ernestus, Michael Hemmer and Dominik Krupke contained in the paper [48] and the thesis [23] of Maximilian Ernestus and Dominik Krupke.

5 Controlling Swarms by Global Forces

5.1 Motivation

One of the exciting new directions of robotics is the design and development of micro- and nanorobot systems, with the goal of letting a huge population of robots perform complex operations in a complicated environment. Due to scaling issues, individual control of the involved robots becomes physically impossible: While energy storage capacity drops with the third power of robot size, medium resistance decreases much slower. A possible answer lies in applying a global, external force to all particles in the swarm. This is what many current micro- and nanorobot systems with many robots do: The whole swarm is steered and directed by an external force that acts as a common control signal. These common control signals include global magnetic or electric fields, chemical gradients, and turning a light source on and off.

Fig. 13.

(Top) State of the art in controlling small objects by force fields. (Bottom) A complex vascular network, forming a typical environment for the parallel navigation of small objects. This section investigates parallel navigation in discretized 2D environments. (Color figure online)

5.2 Formal Aspects

We consider a two-dimensional grid world, with some cells occupied and others free. Initially, the planar square grid is filled with some unit-square particles (each occupying a cell of the grid) and some fixed unit-square blocks. All particles are commanded in unison: a valid command is “Go Up” (u),“Go Right” (r),“Go Down” (d), or “Go Left” (l). All particles move in the commanded direction until they hit an obstacle or another particle. A representative command sequence is $\langle u,r,d,l,d,r,u,\ldots \rangle$. We call these global commands force-field moves. We assume that we can bound the minimum particle speed and that we can guarantee that all particles have moved to their maximum extent.

5.3 Application Scenario

Becker et al. [8] demonstrate how to apply a magnetic field to simultaneously move cells containing iron particles in a specific direction within a fabricated workspace; see Fig. 13a. Other recent examples include using the global magnetic field from an MRI to guide magneto-tactic bacteria through a vascular network to deliver payloads at specific locations [12], and using electromagnets to steer a magneto-tactic bacterium through a micro-fabricated maze [45]; however, this still involves only individual particles at a time, not the parallel motion of a whole, massive swarm. How can we manipulate the overall swarm with coarse global control, such that individual particles arrive at multiple different destinations in a (known) complex vascular network such as the one in Fig. 13b?

5.4 Context

The problem resembles the logic puzzle Tilt [72], and dexterity ball-in-a-maze puzzles such as Pigs in Clover and Labyrinth, which involve tilting a board to cause all mobile pieces to roll or slide in a desired direction. Problems of this type are also similar to sliding-block puzzles with fixed obstacles [18, 37,38,39], except that all particles receive the same control inputs, as in the Tilt puzzle. Another connection is to Randolph’s Ricochet Robots [21], a game that allows individual and independent control of the involved particles.

In the real world, driving ferromagnetic particles with a magnetic resonance imaging (MRI) scanner gives examples of this challenge, from nano- to micro-scales; see [74].

5.5 Algorithmic Insights

Clearly, having only one global signal that uniformly affects all robots at once poses a strong restriction on the ability of the swarm to perform complex operations. The only hope for breaking symmetry is to use interactions between the robot swarm and obstacles in the environment. The key challenge is to establish if interactions with obstacles are sufficient to perform complex operations, ideally by analyzing the complexity of possible logical operations.

It is important to note that there are two fundementally different classes of algorithmic problems, which we denote by External Computation and Internal Computation.

5.5.1 External Computation

Considering the particle swarm as input for a given algorithmic problem, we are faced with a number of questions that need to be resolved by a computing device “outside” of the particle system, such as the following.

• 1. Given a map of an environment, such as the vascular network shown in Fig. 13b, along with initial and goal positions for each particle, does there exist a sequence of inputs that will bring each particle to its goal position?

• 2. Given a map of an environment, such as the vascular network shown in Fig. 13b, along with initial and goal positions for each particle, what is the shortest sequence of moves that will bring each particle to its goal position?

• 3. Given initial and goal positions for each particle in a swarm, how can we design a set of obstacles and a sequence of moves, such that each particle reaches its goal position?

Deliberate use of existing stationary obstacles leads to a wide range of possible particle configurations. In our work [4,5,6, 69], we address all these issues. For the first two questions, we show that they may lead to computationally difficult situations. We also develop several positive results for the third question. The underlying idea is to construct artificial obstacles (such as walls) that allow arbitrary rearrangements of a given two-dimensional particle swarm.

Theorem 1

Given a specified goal location and an initial configuration of movable particles and fixed obstacles, it is NP-hard to decide if a move sequence exists that ends with some particle at the goal location.

The proof relies on a reduction from 3SAT. Suppose we are given n Boolean variables $x_1, x_2, \dots , x_n$, and m disjunctive clauses $C_j = U_j \vee V_j \vee W_j$, where each literal $U_j,V_j,W_j$ is of the form $x_i$ or $\lnot x_i$. We construct a problem instance that has a solution if and only if all clauses can be satisfied by a truth assignment to the variables. This instance is composed of variable gadgets for setting individual variables True or False, clause gadgets that construct the logical or of groupings of three variables, and a check gadget that constructs the logical and of all the clauses. A particle is only delivered to the goal location if the variables have been set in such a way that the formula evaluates to True. See Fig. 14 for an overview of the whole construction.

Fig. 14.

Combining twelve variable gadgets, four 3-input or gadgets, and a 4-input and gadget to realize the 3SAT expression $(\lnot x_1\vee \lnot x_3\vee x_4) \wedge (\lnot x_2\vee \lnot x_3\vee x_4) \wedge (\lnot x_1 \vee x_2\vee x_4) \wedge (x_1\vee \lnot x_2\vee x_3)$. (Color figure online)

On the positive side, we can show that for a given labeled arrangement of particles, arbitrary permutations can be achieved with appropriate sets of obstacles. To this end, we consider a 2D array of particles, as shown in Fig. 15. For an $a_r \times a_c$ matrix A and a $b_r \times b_c$ matrix B, of equal total size $N = a_r a_c = b_r b_c$, a matrix permutation assigns each element in A a unique position in B.

Fig. 15.

In this image for $N=15$, black cells are obstacles, white cells are free, and colored discs are individual particles. The world has been designed to permute the particles between ‘A’ into ‘B’ every four steps: $\langle u,r,d,\ell \rangle$. See the video at http://youtu.be/3tJdRrNShXM. Visually, the distinction between particles of the same color does not matter; however, the arrangement of obstacles induces a specific permutation of individual particles. (Color figure online)

Theorem 2

Let A and B be matrices with dimensions as above. Any matrix permutation that transforms A into B can be executed by a set of obstacles in just four moves. For N particles, the constructed arrangement of obstacles requires $(3N+1)^2$ space and $4N+1$ obstacles. If particles move with a speed of v, the required time for those four moves is 12N / v.

This can be employed to realize larger sets of permutations all at once, as shown in Fig. 16.

Fig. 16.

For any set of k fixed, but arbitrary permutations of N particles, we can construct a set of O(kN) obstacles, such that we can switch from a start arrangement into any of the k permutations using at most $O(\log k)$ force-field moves. Here $k=4$ and ‘A’ is transformed into ‘B’, ‘C’, ‘D’, or ‘E’ in eight moves: $\langle r,d,(r/\ell ),d,(r/\ell ),d,\ell ,u \rangle$.

The previous construction is efficient with respect to the number of required moves, at the expense of a possibly higher number of obstacles. By allowing a larger number of moves, we can limit the number of obstacles for achieving any permutation, as shown in Fig. 17.

Fig. 17.

Repeated application of two base permutations can generate any permutation, when used in a manner similar to Bubble Sort. The obstacles in (A) generate the base permutation $p=(1,2)$ in the clockwise direction $\langle u,r,d,\ell \rangle$ (B) and $q=(1,2,\ldots , N)$ in the counterclockwise direction $\langle r,u,\ell ,d \rangle$ (C).

Theorem 3

We can construct a set of O(N) obstacles such that any $a_r\times a_c$ arrangement of N particles can be rearranged into any other $a_r\times a_c$ arrangement $\pi$ of the same particles, using at most $O(N^2)$ force-field moves.

Proof

See Fig. 17. Use Theorem 2 to build two sets of obstacles, one each for p and q, such that p is realized by the sequence $\langle u,r,d,\ell \rangle$ (clockwise) and q is realized by $\langle r,u,\ell ,d \rangle$ (counterclockwise). Then we use the appropriate sequence for generating $\pi$ in $O(N^2)$ moves.

On the other hand, minimizing the number of moves for achieving a desired goal configuration for all particles turns out to be pspace-complete.

Theorem 4

Given an initial configuration of (labeled) movable particles and fixed obstacles, it is pspace-complete to compute a shortest sequence of force-field moves to achieve another (labeled) configuration.

The proof is largely based on a complexity result by Jerrum [42], who considered the following problem: Given a permutation group specified by a set of generators and a single target permutation $\pi$, which is a member of the group, what is the shortest expression for the target permutation in terms of the generator? This problem was shown to be Pspace-complete in [42], even when the generator set consists of only two permutations $\pi _1$ and $\pi _2$. Combining this with the idea of our construction of Theorem 3 yields the claimed result: Use two sets of obstacles for realizing $\pi _1$ by a sequence of four clockwise moves and $\pi _2$ by a sequence of four counterclockwise moves; then a shortest sequence of force-field moves for achieving a desired target permutation $\pi _3$ corresponds to a minimum generation of $\pi _3$ by $\pi _1$ and $\pi _2$.

5.5.2 Internal Computation

Considering the particle swarm as a complex system that can be reconfigured in various ways, we are faced with issues of the computational power of the swarm itself (as opposed to that of an external device), such as the following.

• 1. Can the complexity of particle interaction be exploited to model logical operations?

• 2. Are there limits to the computational power of the particle swarm?

• 3. How can we achieve computational universality with particle computation?

In [4, 5, 69], we give precise answers to all of these questions. In particular, we show that the logical operations and, nand, nor, and or can be implemented in our model using dual-rail logic. Using terminology from electrical engineering, we call these components that calculate logical operations gates. We establish a fundamental limitation for particle interactions: We cannot duplicate the output of a chain of gates without also duplicating the chain of gates. This means that a so-called fan-out gate cannot be generated. We resolve this missing component with the help of 2 $\times$ 1 particles, which can be used to create fan-out gates that produce multiple copies of the inputs without needing duplicate gates, as shown in Fig. 18 for a physical prototype. Using these fan-out gates, we provide rules for replicating arbitrary digital circuits, allowing us to establish the full range of computational universality as presented by complex digital circuits.

Fig. 18.

Gravity-fed hardware implementation of particle computation. The reconfigurable prototype is set up as a fan-out gate using a $2\times 1$ robot (white)

5.6 Extensions

There are numerous extensions to the basic framework of control by uniform global forces. In [58] we develop methods for mapping, foraging, and coverage with a particle swarm. In [59] we show how to collect a particle swarm. In [44] we show how to use uniform global forces in combination with appropriate obstacles to efficiently sort and classify polyomino shapes.

In combination with “sticky” particles that bind together when brought into contact, we can use the basic setup to build production lines for assembling given shapes; see our paper [7] for a basic algorithmic and complexity analysis, and [67] for more efficient methods that proceed in a hierarchical fashion.

5.7 Acknowledgments

The content of this section is based on the abstract [6] and paraphrases the joint work with Aaron Becker, Erik Demaine, Golnaz Habibi, Jarrett Lonsford, James McLurkin, Hahmed Mohtasham Shad, Rose Morris-Wright contained in the papers [4, 5, 69]. For an animated visualization, see the video at https://youtu.be/H6o9DTIfkn0.