{"id":1002,"date":"2024-03-28T10:47:10","date_gmt":"2024-03-28T17:47:10","guid":{"rendered":"https:\/\/labs.engineering.asu.edu\/sops\/?page_id=1002"},"modified":"2024-07-10T14:08:16","modified_gmt":"2024-07-10T21:08:16","slug":"simulations","status":"publish","type":"page","link":"https:\/\/labs.engineering.asu.edu\/sops\/simulations\/","title":{"rendered":"Simulations"},"content":{"rendered":"
<\/div>\"\"
\n\n\n\n

Simulations<\/h1>\n\n\n\n
<\/div>\n\n\n\n
<\/div>\n\n<\/div><\/div>\n\n\n
\n
\n

Locomotion & Phototaxing<\/h2>\n\n\n\n

In locomotion and phototaxing<\/a>, 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\u2019t 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.<\/p>\n<\/div>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n
\"\"<\/figure>\n<\/div>\n\n\n\n
\n
\"\"<\/figure>\n<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Shortcut Bridging<\/h2>\n\n\n\n

In shortcut bridging<\/a>, the particle system (black dots) starts on \u201cland\u201d (brown dots). Imitating the behavior of the army ant genus Eciton<\/em> (right, image credit Reid et al<\/a>.), the particles bridge over the gap to shorten the total distance between the two objects (red dots). This is similar to Eciton<\/em> 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.<\/p>\n<\/div>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n
\"\"<\/figure>\n<\/div>\n\n\n\n
<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Compression<\/h2>\n\n\n\n

In\u00a0compression<\/a>, 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.<\/p>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Universal Coating<\/h2>\n\n\n\n

In\u00a0universal coating<\/a>, the particle system seeks to coat the surface an arbitrarily shaped object as evenly as possible, using multiple layers if applicable. When the object\u2019s 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\u00a0super-roots<\/em>, which move forward when they receive complaints from their followers. Yellow particles are awaiting the election of a leader, and those on the object\u2019s 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\u00a0leader<\/em>. White particles are\u00a0followers<\/em>, which follow their parents to the surface of the coating. Dark grey particles are\u00a0roots<\/em>, which move into the current coating layer and become\u00a0retired<\/em>\u00a0when the coating reaches them. One retired particle per layer becomes the\u00a0marker<\/em>\u00a0particle (grey), which denotes the start and end of its layer. This allows the system to locally determine when a layer is complete.<\/p>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Hexagon Shape Formation<\/h2>\n\n\n\n

In\u00a0hexagon shape formation<\/a>, 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\u00a0seed<\/em>, which serves as the center of the hexagon. Blue particles are\u00a0followers<\/em>, which follow their parents until they reach the hexagon. Red particles are\u00a0roots<\/em>, which traverse the surface of the hexagon until they reach the next hexagon position. At this point, they become\u00a0retired<\/em>\u00a0(black) and do not participate further in the algorithm.<\/p>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Triangle Shape Formation<\/h2>\n\n\n\n

In\u00a0triangle shape formation<\/a>, 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\u00a0seed<\/em>, which aids the rest of the system in developing a sense of direction. Blue particles are\u00a0followers<\/em>, which follow their parents until they are adjacent to the triangle. Red particles are\u00a0roots<\/em>, which follow the surface of the triangle until they find the next finishing position. Black particles are\u00a0retired<\/em>, which have finished and do not participate further in the algorithm.<\/p>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Leader Election<\/h2>\n\n\n\n

In\u00a0leader election<\/a>, 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\u00a0paper<\/a>. 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).<\/p>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Line Formation<\/h2>\n\n\n\n

In\u00a0line formation<\/a>, the particle system seeks to organize into a straight line. The green particle is the\u00a0seed<\/em>, which serves a reference point for the start of the line. Blue particles are\u00a0followers<\/em>, which follow their parents until they reach some point adjacent to the line. Red particles are\u00a0roots<\/em>, which traverse the sides of the line until they reach one of the two ends. At this point, they become\u00a0retired<\/em>\u00a0(black) and do not participate further in the algorithm.<\/p>\n\n\n\n

<\/div>\n<\/div>\n\n\n\n
<\/div>\n\n\n\n
\n
\n

Infinite Object Coating<\/h2>\n\n\n\n

In\u00a0infinite object coating<\/a>, the particle system seeks to spread itself over the surface of some long object. The idea of an object being \u201cinfinite\u201d simply means the surface of the object is longer than the number of particles. Blue particles are\u00a0followers<\/em>, which follow their parents until they reach the object\u2019s surface. Red particles are\u00a0leaders<\/em>, which traverse the length of the current coating until reaching the first uncoated position. At this point, they become\u00a0retired<\/em>\u00a0(green) and do not participate further in the algorithm. The following demo includes several cases of narrow \u201ctunnels\u201d in the object\u2019s surface, which the particles bridge over so that the coating remains one continuous path.<\/p>\n\n\n\n