# American Institute of Mathematical Sciences

March  2019, 14(1): 1-22. doi: 10.3934/nhm.2019001

## Controlled cellular automata

 2565 Mc Carthy Mall, Department of Mathematics, University of Hawaii at Manoa, Honolulu, 96822, USA

Received  July 2018 Published  January 2019

Fund Project: The second author is partially supported by the Simons Foundation, award # 359510

Cellular Automata have been successfully used to model evolution of complex systems based on simples rules. In this paper we introduce controlled cellular automata to depict the dynamics of systems with controls that can affect their evolution. Using theory from discrete control systems, we derive results for the control of cellular automata in specific cases. The paper is mostly oriented toward two applications: fire spreading; morphogenesis and tumor growth. In both cases, we illustrate the impact of a control on the evolution of the system. For the fire, the control is assumed to be either firelines or firebreaks to prevent spreading or dumping of water, fire retardant and chemicals (foam) on the fire to neutralize it. In the case of cellular growth, the control describes mechanisms used to regulate growth factors and morphogenic events based on the existence of extracellular matrix structures called fractones. The hypothesis is that fractone distribution may coordinate the timing and location of neural cell proliferation, thereby guiding morphogenesis, at several stages of early brain development.

Citation: Achilles Beros, Monique Chyba, Oleksandr Markovichenko. Controlled cellular automata. Networks & Heterogeneous Media, 2019, 14 (1) : 1-22. doi: 10.3934/nhm.2019001
##### References:

show all references

##### References:
Left: Configuration $s^0$ (classical checkerboard). Right: Configuration $s^1$ (alternate checkerboard)
Let $s^0$ be the configuration with value 0.5 in each cell of the grid. Then we have: $d(s^0, s^1) = d(s^0, s^2) = d(s^0, s^3)<d(s^0, s^4)$
In all the figures, red represents positive values and blue represents negative values. The uncontrolled simulation at 4 different timesteps: (a) 0, (b) 5, (c) 20 and (d) 100. The average value at the four timesteps: (a) 0.010, (b) 0.0079, (c) 0.0041 and (d) 0.00014
The pictures show a controlled simulation at the following timesteps: (a) 0, (b) 5, (c) 20, (d) 39, (e) 40, (f) 50, (g) 75, (h) 100 and (i) 150. The control switches on at 20, off at 40, back on at 50 and finally off again at 100. Notice that while the control is off, the sign is constant and the magnitude diminishes at a slow exponential rate. When the control is on, the sign alternates with each timestep and the magnitude increases at a slow exponential rate
The average is negative for the odd numbered timesteps for which the control is active. For reference, the distance from the controlled simulation at timestep 150 to a grid of zeros is 632.06
Top row using the Von Neumann neighborhood. Timesteps: (a) 1, (b) 50 and (c) 100. Bottom row using the Moore neighborhood. Timesteps: (a) 1, (b) 25 and (c) 50. Note that the Moore neighborhood promotes much faster evolution. For both $\alpha_1 = 0.1$, $\alpha_2 = 0.2$ and $\alpha_3 = 0.3$
Top row: $\alpha_1 = 0.05$, $\alpha_2 = 0.1$ and $\alpha_3 = 0.15$. Bottom row: $\alpha_1 = 0.15$, $\alpha_2 = 0.3$ and $\alpha_3 = 0.05$. For both, the three times steps are 1, 50 and 100
Timesteps: (a) 1, (b) 125, (c) 175, (d) 200, (e) 210 and (f) 250. The fire is diverted by the obstacles
Timesteps: (a) 1, (b) 20, (c) 30, (d) 38, (e) 45 and (f) 100. The fire is diverted by the obstacles
Timesteps: (a) 1, (b) 20, (c) 25, (d) 35, (e) 50 and (f) 100. The fire is diverted by the obstacles
Timesteps: (a) 1, (b) 15, (c) 50 and (d) 100. A simple, uncontrolled cell growth using the Von Neumann neighborhood
Timesteps: (a) 1, (b) 5, (c) 10, (d) 30, (e) 60 and (f) 100. An uncontrolled cell growth using a neighborhood consisting of the three grid units directly above the central unit and the three side-by-side units in the row three rows below the central unit
Timesteps: (a) 0, (b) 30, (c) 60 and (d) 100. The interaction between growth of normal cells and tumor cells. The competition between the cell masses plays out at the boundary between the cell masses. The normal cells are in red, the probability of a tumor cell developing is in blue
Timesteps: (a) 1, (b) 5, (c) 15, (d) 30, (e) 60 and (f) 100. Fractones are placed along three horizontal lines. One is above the initial cell and consists of fractones that stop cell growth; they are arranged in blocks. One is in line with the initial cell (across the middle of the simulation) and greatly increases cell growth. The final line is below the intial cell and also stops cell growth. The placement of the fractones is clearly visible in (f)
Eigenvalues corresponding to Example 4 and $m = 5$
 $a$ $a\pm \sqrt{ed}$ $a\pm \sqrt{3ed}$ $a+\sqrt{bc}$ $a + \sqrt{bc+de\pm 2\sqrt{bcde}}$ $a + \sqrt{bc+3de\pm2\sqrt{3bcde}}$ $a-\sqrt{bc}$ $a - \sqrt{bc+de\pm 2\sqrt{bcde}}$ $a - \sqrt{bc+3de\pm 2\sqrt{3bcde}}$ $a+\sqrt{3bc}$ $a+\sqrt{3bc+3de\pm 6\sqrt{bcde}}$ $a+\sqrt{3bc+3de+2\sqrt{3bcde}}$ $a-\sqrt{3bc}$ $a-\sqrt{3bc+3de\pm 6\sqrt{bcde}}$ $a-\sqrt{3bc+3de+2\sqrt{3bcde}}$
 $a$ $a\pm \sqrt{ed}$ $a\pm \sqrt{3ed}$ $a+\sqrt{bc}$ $a + \sqrt{bc+de\pm 2\sqrt{bcde}}$ $a + \sqrt{bc+3de\pm2\sqrt{3bcde}}$ $a-\sqrt{bc}$ $a - \sqrt{bc+de\pm 2\sqrt{bcde}}$ $a - \sqrt{bc+3de\pm 2\sqrt{3bcde}}$ $a+\sqrt{3bc}$ $a+\sqrt{3bc+3de\pm 6\sqrt{bcde}}$ $a+\sqrt{3bc+3de+2\sqrt{3bcde}}$ $a-\sqrt{3bc}$ $a-\sqrt{3bc+3de\pm 6\sqrt{bcde}}$ $a-\sqrt{3bc+3de+2\sqrt{3bcde}}$
 [1] Achilles Beros, Monique Chyba, Kari Noe. Co-evolving cellular automata for morphogenesis. Discrete & Continuous Dynamical Systems - B, 2019, 24 (5) : 2053-2071. doi: 10.3934/dcdsb.2019084 [2] Xinxin Tan, Shujuan Li, Sisi Liu, Zhiwei Zhao, Lisa Huang, Jiatai Gang. Dynamic simulation of a SEIQR-V epidemic model based on cellular automata. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 327-337. doi: 10.3934/naco.2015.5.327 [3] T.K. Subrahmonian Moothathu. Homogeneity of surjective cellular automata. Discrete & Continuous Dynamical Systems - A, 2005, 13 (1) : 195-202. doi: 10.3934/dcds.2005.13.195 [4] Marcus Pivato. Invariant measures for bipermutative cellular automata. Discrete & Continuous Dynamical Systems - A, 2005, 12 (4) : 723-736. doi: 10.3934/dcds.2005.12.723 [5] Ana I. Muñoz, José Ignacio Tello. Mathematical analysis and numerical simulation of a model of morphogenesis. Mathematical Biosciences & Engineering, 2011, 8 (4) : 1035-1059. doi: 10.3934/mbe.2011.8.1035 [6] Bernard Host, Alejandro Maass, Servet Martínez. Uniform Bernoulli measure in dynamics of permutative cellular automata with algebraic local rules. Discrete & Continuous Dynamical Systems - A, 2003, 9 (6) : 1423-1446. doi: 10.3934/dcds.2003.9.1423 [7] Marcelo Sobottka. Right-permutative cellular automata on topological Markov chains. Discrete & Continuous Dynamical Systems - A, 2008, 20 (4) : 1095-1109. doi: 10.3934/dcds.2008.20.1095 [8] Aleksandar Zatezalo, Dušan M. Stipanović. Control of dynamical systems with discrete and uncertain observations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4665-4681. doi: 10.3934/dcds.2015.35.4665 [9] Qiying Hu, Wuyi Yue. Optimal control for resource allocation in discrete event systems. Journal of Industrial & Management Optimization, 2006, 2 (1) : 63-80. doi: 10.3934/jimo.2006.2.63 [10] Qiying Hu, Wuyi Yue. Optimal control for discrete event systems with arbitrary control pattern. Discrete & Continuous Dynamical Systems - B, 2006, 6 (3) : 535-558. doi: 10.3934/dcdsb.2006.6.535 [11] Akinori Awazu. Input-dependent wave propagations in asymmetric cellular automata: Possible behaviors of feed-forward loop in biological reaction network. Mathematical Biosciences & Engineering, 2008, 5 (3) : 419-427. doi: 10.3934/mbe.2008.5.419 [12] Galina Kurina, Sahlar Meherrem. Decomposition of discrete linear-quadratic optimal control problems for switching systems. Conference Publications, 2015, 2015 (special) : 764-774. doi: 10.3934/proc.2015.0764 [13] Anthony M. Bloch, Peter E. Crouch, Nikolaj Nordkvist. Continuous and discrete embedded optimal control problems and their application to the analysis of Clebsch optimal control problems and mechanical systems. Journal of Geometric Mechanics, 2013, 5 (1) : 1-38. doi: 10.3934/jgm.2013.5.1 [14] Byungik Kahng, Miguel Mendes. The characterization of maximal invariant sets of non-linear discrete-time control dynamical systems. Conference Publications, 2013, 2013 (special) : 393-406. doi: 10.3934/proc.2013.2013.393 [15] Hongyan Yan, Yun Sun, Yuanguo Zhu. A linear-quadratic control problem of uncertain discrete-time switched systems. Journal of Industrial & Management Optimization, 2017, 13 (1) : 267-282. doi: 10.3934/jimo.2016016 [16] Chuandong Li, Fali Ma, Tingwen Huang. 2-D analysis based iterative learning control for linear discrete-time systems with time delay. Journal of Industrial & Management Optimization, 2011, 7 (1) : 175-181. doi: 10.3934/jimo.2011.7.175 [17] Elena K. Kostousova. On control synthesis for uncertain dynamical discrete-time systems through polyhedral techniques. Conference Publications, 2015, 2015 (special) : 723-732. doi: 10.3934/proc.2015.0723 [18] Qiying Hu, Chen Xu, Wuyi Yue. A unified model for state feedback of discrete event systems II: Control synthesis problems. Journal of Industrial & Management Optimization, 2008, 4 (4) : 713-726. doi: 10.3934/jimo.2008.4.713 [19] Yuefen Chen, Yuanguo Zhu. Indefinite LQ optimal control with process state inequality constraints for discrete-time uncertain systems. Journal of Industrial & Management Optimization, 2018, 14 (3) : 913-930. doi: 10.3934/jimo.2017082 [20] Elena K. Kostousova. On polyhedral control synthesis for dynamical discrete-time systems under uncertainties and state constraints. Discrete & Continuous Dynamical Systems - A, 2018, 38 (12) : 6149-6162. doi: 10.3934/dcds.2018153

2018 Impact Factor: 0.871