A 1D CELLULAR AUTOMATON THAT MOVES PARTICLES UNTIL REGULAR SPATIAL PLACEMENT
Abstract
We consider a finite cellular automaton with particles where each site can host at most one particle. Starting from an arbitrary initial configuration, our goal is to move the particles between neighbor sites until the distance to the nearest particle is minimized globally. Such a configuration corresponds in fact to a regular placement. This problem is a cellular automata equivalent of load-balancing in parallel computing, where each task is a particle and each processor a connected set of sites. We present a cellular automata rule that solves this problem in the 1D case, and is convergent, i.e. once the regular placement is achieved, the configuration does not change anymore. The rule is inspired from the Lloyd algorithm, computing a centroidal Voronoi tessellation. The dynamic of the rule is described at a higher level, using self-explanatory space-time diagrams. They exhibit signals acting as quantity of movement carrying the energy of system. Each signal bounces or pass through particles, causing their movement, until it eventually reaches the border and vanishes. When signals have all vanished, particles are regularly placed.
References
- Mathematical and Computer Modelling 23(16), 51 (1996). Crossref, ISI, Google Scholar
- ACM Comput. Surv. 23(3), 345 (1991), DOI: 10.1145/116873.116880. Crossref, ISI, Google Scholar
-
B. Chopard and M. Droz , Cellular Automata Modeling of Physical Systems ( Cambridge University Press , 1998 ) . Crossref, Google Scholar - SIAM Rev. 41(4), 637 (1999), DOI: 10.1137/S0036144599352836. Crossref, ISI, Google Scholar
- Physica D (2008). Google Scholar
-
F. Gruau , Blob computing , Computing Frontiers 2004 ACM SIGMicro ( 2004 ) . Google Scholar - Multi-Agent and Grid Systems 3(4), 105 (2007). Crossref, Google Scholar
- Parallel Comput. 28(10), 1477 (2002), DOI: 10.1016/S0167-8191(02)00151-5. Crossref, ISI, Google Scholar
- IEEE Transactions on Information Theory 28, 129 (1982), DOI: 10.1109/TIT.1982.1056489. Crossref, ISI, Google Scholar
J. B. MacQueen , Some methods for classification and analysis of multivariate observations, Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability1, eds.L. M. L. Cam and J. Neyman (University of California Press, 1967) pp. 281–297. Google Scholar- L. Maignan. Uniformisation de la reépartition spatiale d'un ensemble de points par diagramme de voronoi: Implémentation sur automate cellulaire, 2007 . Google Scholar
-
L. Maignan and F. Gruau , Integer gradient for cellular automata: principle and examples , Spatial Computing Workshop at IEEE SASO 2008 ( 2008 ) . Google Scholar - IEEE Transactions on Information Theory 28(2), 137 (1982), DOI: 10.1109/TIT.1982.1056492. Crossref, ISI, Google Scholar
- S. Poduri and G. Sukhatme. Constrained coverage for mobile sensor networks, 2004 . Google Scholar
-
T. Toffoli and N. Margolus , Cellular Automata Machines, A New Environment for Modeling ( The MIT Press , Reading, Massachusetts , 1987 ) . Crossref, Google Scholar - Mathematical and Computer Modelling 26(8), 71 (1997), DOI: 10.1016/S0895-7177(97)00145-3. Crossref, ISI, Google Scholar


