1 Search Results for "Kedia, Hridesh"

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.14

Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems

Authors: Hridesh Kedia, Shunhao Oh, and Dana Randall

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract

We present local distributed, stochastic algorithms for alignment in self-organizing particle systems (SOPS) on two-dimensional lattices, where particles occupy unique sites on the lattice, and particles can make spatial moves to neighboring sites if they are unoccupied. Such models are abstractions of programmable matter, composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational capabilities. We consider oriented particle systems, where particles are assigned a vector pointing in one of q directions, and each particle can compute the angle between its direction and the direction of any neighboring particle, although without knowledge of global orientation with respect to a fixed underlying coordinate system. Particles move stochastically, with each particle able to either modify its direction or make a local spatial move along a lattice edge during a move. We consider two settings: (a) where particle configurations must remain simply connected at all times and (b) where spatial moves are unconstrained and configurations can disconnect. Our algorithms are inspired by the Potts model and its planar oriented variant known as the planar Potts model or clock model from statistical physics. We prove that for any q ≥ 2, by adjusting a single parameter, these self-organizing particle systems can be made to collectively align along a single dominant direction (analogous to a solid or ordered state) or remain non-aligned, in which case the fraction of particles oriented along any direction is nearly equal (analogous to a gaseous or disordered state). In the connected SOPS setting, we allow for two distinct parameters, one controlling the ferromagnetic attraction between neighboring particles (regardless of orientation) and the other controlling the preference of neighboring particles to align. We show that with appropriate settings of the input parameters, we can achieve compression and expansion, controlling how tightly gathered the particles are, as well as alignment or nonalignment, producing a single dominant orientation or not. While alignment is known for the Potts and clock models at sufficiently low temperatures, our proof in the SOPS setting are significantly more challenging because the particles make spatial moves, not all sites are occupied, and the total number of particles is fixed.

Cite as

Hridesh Kedia, Shunhao Oh, and Dana Randall. Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kedia_et_al:LIPIcs.APPROX/RANDOM.2022.14,
  author =	{Kedia, Hridesh and Oh, Shunhao and Randall, Dana},
  title =	{{Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.14},
  URN =		{urn:nbn:de:0030-drops-171367},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.14},
  annote =	{Keywords: Self-organizing particle systems, alignment, Markov chains, active matter}
}

Refine by Author
1 Kedia, Hridesh
1 Oh, Shunhao
1 Randall, Dana

Refine by Classification
1 Mathematics of computing → Stochastic processes
1 Theory of computation → Random walks and Markov chains
1 Theory of computation → Self-organization

Refine by Keyword
1 Markov chains
1 Self-organizing particle systems
1 active matter
1 alignment

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Kedia, Hridesh"

Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems

Abstract

Cite as

Thanks for your feedback!

Could not send message