markov-chains

We extend the stochastic approach to self-organizing particle systems used in compression to shortcut bridging, in which particles self-assemble bridges over gaps that balance a tradeoff between bridge length and cost. This work is inspired by the bridging behavior of Eciton army ants, and demonstrates how local interactions can guide a system to globally optimal configurations.

We extend the stochastic approach to heterogeneous self-organizing particle systems made up of particles of different color classes. We show that by biasing random particle movements based on the number of same-color neighbors, these systems can collectively separate or integrate.

In this talk, I present a deep dive of our stochastic algorithm for shortcut bridging based on the bridging behavior of Eciton army ants.

We extend the stochastic approach to self-organizing particle systems used in compression to shortcut bridging, in which particles self-assemble bridges over gaps that balance a tradeoff between bridge length and cost. This work is inspired by the bridging behavior of Eciton army ants, and demonstrates how local interactions can guide a system to globally optimal configurations.

In this talk, I present algorithms for compression and shortcut bridging designed using the stochastic approach to self-organizing particle systems.

We introduce the stochastic approach to self-organizing particle systems in which we use a Markov chain to describe how the system evolves over time as particles move randomly. We show that by biasing particle moves towards positions where they have more neighbors, the system converges to compressed states; we also show that when this bias is not strong enough, the system converges to expanded states.

This undergraduate honors thesis treats the problem of compression in self-organizing particle systems, where the goal is to gather particles as tightly together as possible. Three algorithms are proposed and compared with rigorous proofs and simulations.

In this undergraduate thesis defense, I give three algorithms for compression in the amoebot model: local compression, hole elimination, and $\alpha$-compression. Formal analysis and simulations are presented.