Lattice gas automaton

Lattice gas automata (LGCA), or lattice gas cellular automata, are a type of cellular automaton used to simulate fluid flows, pioneered by Hardy–Pomeau–de Pazzis and Frisch–Hasslacher–Pomeau. They were the precursor to the lattice Boltzmann methods. From lattice gas automata, it is possible to derive the macroscopic Navier–Stokes equations.^[1] Interest in lattice gas automaton methods levelled off in the early 1990s, as the interest in the lattice Boltzmann started to rise.^[2] However, an LGCA variant, termed BIO-LGCA, is still widely used^[3] to model collective migration in biology.

Basic principles

As a cellular automaton, these models comprise a lattice, where the sites on the lattice can take a certain number of different states. In lattice gas, the various states are particles with certain velocities. Evolution of the simulation is done in discrete time steps. After each time step, the state at a given site can be determined by the state of the site itself and neighboring sites, before the time step.

The state at each site is purely boolean. At a given site, there either is or is not a particle moving in each direction.

At each time step, two processes are carried out, propagation and collision.^[4]

In the propagation step, each particle will move to a neighboring site determined by the velocity that particle had. Barring any collisions, a particle with an upwards velocity will after the time step maintain that velocity, but be moved to the neighboring site above the original site. The so-called exclusion principle prevents two or more particles from travelling on the same link in the same direction.

In the collision step, collision rules are used to determine what happens if multiple particles reach the same site. These collision rules are required to maintain mass conservation, and conserve the total momentum; the block cellular automaton model can be used to achieve these conservation laws.^[5] Note that the exclusion principle does not prevent two particles from travelling on the same link in opposite directions; when this happens, the two particles pass each other without colliding.

Early attempts with a square lattice

In papers published in 1973 and 1976, Jean Hardy, Yves Pomeau and Olivier de Pazzis introduced the first lattice Boltzmann model, which is called the HPP model after the authors. HPP model is a two-dimensional model of fluid particle interactions. In this model, the lattice is square, and the particles travel independently at a unit speed to the discrete time. The particles can move to any of the four sites whose cells share a common edge. Particles cannot move diagonally.

If two particles collide head-on, for example a particle moving to the left meets a particle moving to the right, the outcome will be two particles leaving the site at right angles to the direction they came in.^[6]

The HPP model lacked rotational invariance, which made the model highly anisotropic. This means for example, that the vortices produced by the HPP model are square-shaped.^[7]

Hexagonal grids

The hexagonal grid model was first introduced in 1986, in a paper by Uriel Frisch, Brosl Hasslacher and Pomeau, and this has become known as the FHP model after its inventors. The model has six or seven velocities, depending on which variation is used. In any case, six of the velocities represent movement to each of the neighboring sites. In some models (called FHP-II and FHP-III), a seventh velocity representing particles "at rest" is introduced. The "at rest" particles do not propagate to neighboring sites, but they are capable of colliding with other particles. The FHP-III model allows all possible collisions that conserve density and momentum.^[8] Increasing the number of collisions raises the Reynolds number, so the FHP-II and FHP-III models can simulate less viscous flows than the six-speed FHP-I model.^[9]

The simple update rule of FHP model proceeds in two stages, chosen to conserve particle number and momentum. The first is collision handling. The collision rules in the FHP model are not deterministic, some input situations produce two possible outcomes, and when this happens, one of them is picked at random. Since random number generation is not possible through completely computational means, a pseudorandom process is usually chosen.^[10]

After the collision step a particle on a link is taken to be leaving the site. If a site has two particles approaching head-on, they scatter. A random choice is made between the two possible outgoing directions that conserve momentum.

The hexagonal grid does not suffer as large anisotropy troubles as those that plague the HPP square grid model, a fortunate fact that is not entirely obvious, and that prompted Frisch to remark that "the symmetry gods are benevolent".^[11]

Three dimensions

For a three-dimensional grid, the only regular polytope that fills the whole space is the cube, while the only regular polytopes with a sufficiently large symmetry group are the dodecahedron and icosahedron (without the second constraint the model will suffer the same drawbacks as the HPP model). To make a model that tackles three dimensions therefore requires an increase in the number of dimensions, such as in the 1986 model by D'Humières, Lallemand and Frisch, which employed a face-centered hypercube model.^[12]

Obtaining macroscopic quantities

The density at a site can be found by counting the number of particles at each site. If the particles are multiplied with the unit velocity before being summed, one can obtain the momentum at the site.^[13]

However, calculating density, momentum, and velocity for individual sites is subject to a large amount of noise, and in practice, one would average over a larger region to obtain more reasonable results. Ensemble averaging is often used to reduce the statistical noise further.^[14]

Advantages and disadvantages

The main assets held by the lattice gas model are that the boolean states mean there will be exact computing without any round-off error due to floating-point precision, and that the cellular automata system makes it possible to run lattice gas automaton simulations with parallel computing.^[15]

Disadvantages of the lattice gas method include the lack of Galilean invariance, and statistical noise.^[16] Another problem is the difficulty in expanding the model to handle three dimensional problems, requiring the use of more dimensions to maintain a sufficiently symmetric grid to tackle such issues.^[12]

As a model in biology

Lattice-gas cellular automata have been adapted and are still widely used for modeling collective migration in biology. Due to the active nature of biological agents, as well as the viscuous environments cells live in, momentum conservation is not required. Furthermore, agents may die or reproduce, so mass conservation may also be absent. During the collision step, particles reorient stochastically following a Boltzmann distribution, simulating local interaction between individuals.

Notes

^ Succi, section 2.3 describes the process
^ Succi, section 2.6
^ Deutsch, Andreas; Nava-Sedeño, Josué Manik; Syga, Simon; Hatzikirou, Haralampos (2021-06-15). "BIO-LGCA: A cellular automaton modelling class for analysing collective cell migration". PLOS Computational Biology. 17 (6): e1009066. Bibcode:2021PLSCB..17E9066D. doi:10.1371/journal.pcbi.1009066. PMC 8232544. PMID 34129639.
^ Buick, section 3.4
^ Wolfram, Stephen (2002), A New Kind of Science, Wolfram Media, pp. 459–464, ISBN 1-57955-008-8.
^ Buick, section 3.2.1
^ Succi, footnote p. 22
^ Buick, section 3.2.2
^ Wolf-Gladrow 3.2.6, figure 3.2.3
^ Wolf-Gladrow 3.2.1
^ Succi, footnote p. 23
^ ^a ^b Wolf-Gladrow, sections 3.4 - 3.5
^ Buick, section 3.5.1
^ Buick, section 3.8
^ Succi, section 2.4
^ Succi, section 2.5

References

Sauro Succi (2001). The Lattice Boltzmann Equation, for fluid dynamics and beyond. Oxford Science Publications. ISBN 0-19-850398-9. (Chapter 2 is about lattice gas Cellular Automata)
James Maxwell Buick (1997). Lattice Boltzmann Methods in Interfacial Wave Modelling. PhD Thesis, University of Edinburgh. (Chapter 3 is about the lattice gas model.) (archive.org) 2008-11-13
Dieter A. Wolf-Gladrow (2000). Lattice-Gas Cellular Automata and Lattice Boltzmann Models. Springer. ISBN 3-540-66973-6.

External links

(in French) Master thesis (2000) – Details on programming and optimising the simulation of the FHP LGA
(in Polish and English) Master thesis (2010) - Implementation of FHP model in Nvidia CUDA technology.

[1] Succi, section 2.3 describes the process

[2] Succi, section 2.6

[3] Deutsch, Andreas; Nava-Sedeño, Josué Manik; Syga, Simon; Hatzikirou, Haralampos (2021-06-15). "BIO-LGCA: A cellular automaton modelling class for analysing collective cell migration". PLOS Computational Biology. 17 (6): e1009066. Bibcode:2021PLSCB..17E9066D. doi:10.1371/journal.pcbi.1009066. PMC 8232544. PMID 34129639.

[4] Buick, section 3.4

[5] Wolfram, Stephen (2002), A New Kind of Science, Wolfram Media, pp. 459–464, ISBN 1-57955-008-8.

[6] Buick, section 3.2.1

[7] Succi, footnote p. 22

[8] Buick, section 3.2.2

[9] Wolf-Gladrow 3.2.6, figure 3.2.3

[10] Wolf-Gladrow 3.2.1

[11] Succi, footnote p. 23

[WG_3D-12] Wolf-Gladrow, sections 3.4 - 3.5

[13] Buick, section 3.5.1

[14] Buick, section 3.8

[15] Succi, section 2.4

[16] Succi, section 2.5

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]