Simulations
Locomotion & Phototaxing
In locomotion and phototaxing, a particle system exhibits collective movement in both directed and undirected variants. When all particles have equal rates of activity, as in the simulation on the right, the system moves but doesn’t exhibit any directed drift. However, when some particles are less active than others, the system provably exhibits directed motion towards the less active members. This directed motion can be seen in the simulation on the left, where particles closer to the right/thick sides of the bounding hexagon are more active. The system then collectively moves towards the inactive members; i.e., away from the thicker sides.
Shortcut Bridging
In shortcut bridging, the particle system (black dots) starts on “land” (brown dots). Imitating the behavior of the army ant genus Eciton (right, image credit Reid et al.), the particles bridge over the gap to shorten the total distance between the two objects (red dots). This is similar to Eciton ant behavior in their foraging trails; however, shortening the travel distance requires larger and larger bridges, which takes more and more ants out of the workforce. Our algorithm provably balances this trade-off between wanting both a shorter path and a short bridge, using only local, random decisions by each particle about where to move next.
Compression
In compression, the particle system seeks to gather as tightly as possible. In real 3D-space, this would result in a sphere; on the triangular lattice the optimally compressed shape is a hexagon. Unlike in the other algorithms, there are no particle states which are used for coordination. Instead, particles use biased random decisions to move into locations which maximize the number of neighboring particles, resulting in a compressed system.
Universal Coating
In universal coating, the particle system seeks to coat the surface an arbitrarily shaped object as evenly as possible, using multiple layers if applicable. When the object’s surface is longer than the number of particles, this achieves a result similar to infinite object coating (see below). In the following demo, the object is a closed, regular hexagon (black particles). The first phase of this algorithm is complaint-based coating, which coats the first layer (this occurs very quickly in the demo, but can be seen by pausing at 0:01 and moving the slider). Red particles are super-roots, which move forward when they receive complaints from their followers. Yellow particles are awaiting the election of a leader, and those on the object’s surface participate in a node-based leader election primitive. The segment colors are the same as in the leader election algorithm (see below). The light grey particle is the elected leader. White particles are followers, which follow their parents to the surface of the coating. Dark grey particles are roots, which move into the current coating layer and become retired when the coating reaches them. One retired particle per layer becomes the marker particle (grey), which denotes the start and end of its layer. This allows the system to locally determine when a layer is complete.
Hexagon Shape Formation
In hexagon shape formation, the particle system seeks to organize into a regular hexagon. (However, the final layer of the hexagon may be incomplete if the number of particles does not exactly equal the area of a regular hexagon). The green particle is the seed, which serves as the center of the hexagon. Blue particles are followers, which follow their parents until they reach the hexagon. Red particles are roots, which traverse the surface of the hexagon until they reach the next hexagon position. At this point, they become retired (black) and do not participate further in the algorithm.
Triangle Shape Formation
In triangle shape formation, the particle system seeks to organize into an equilateral triangle. (However, since the total number of particles may not be exactly equal to the area of an equilateral triangle, the last layer may be incomplete). In the following demo, the green particle is the seed, which aids the rest of the system in developing a sense of direction. Blue particles are followers, which follow their parents until they are adjacent to the triangle. Red particles are roots, which follow the surface of the triangle until they find the next finishing position. Black particles are retired, which have finished and do not participate further in the algorithm.
Leader Election
In leader election, the particle system seeks to elect a unique leader which also knows that it is the unique leader of the system. Since our particles can only see and communicate with their local neighbors, this is a highly non-trivial task. We leave the details of this algorithm to the corresponding paper. Red agents and segments are competing to have the longest segment. To aid in breaking ties, the gold agents and segments flip a coin and transfer their candidacy to the next agent if the coin comes up heads. A blue agent and its segment are performing solitude verification to determine if they are the only remaining candidate on their border. Once solitude is verified, the agent turns green. The inner-outer border test is performed next. If the agent determines it is on an inner border, it deletes its border and revokes candidacy; otherwise, the agent is on the outer border and declares itself the system leader (green border).
Line Formation
In line formation, the particle system seeks to organize into a straight line. The green particle is the seed, which serves a reference point for the start of the line. Blue particles are followers, which follow their parents until they reach some point adjacent to the line. Red particles are roots, which traverse the sides of the line until they reach one of the two ends. At this point, they become retired (black) and do not participate further in the algorithm.
Infinite Object Coating
In infinite object coating, the particle system seeks to spread itself over the surface of some long object. The idea of an object being “infinite” simply means the surface of the object is longer than the number of particles. Blue particles are followers, which follow their parents until they reach the object’s surface. Red particles are leaders, which traverse the length of the current coating until reaching the first uncoated position. At this point, they become retired (green) and do not participate further in the algorithm. The following demo includes several cases of narrow “tunnels” in the object’s surface, which the particles bridge over so that the coating remains one continuous path.