Evolutionary Search for Cellular Automata with Self-Organizing Properties toward Controlling Decentralized Pervasive Systems and Its Applications

Evolutionary Search for Cellular Automata with Self-Organizing Properties toward Controlling Decentralized Pervasive Systems and Its Applications

Yusuke Iwase (Internet Initiative Japan Inc. (IIJ), Tokyo, Japan), Reiji Suzuki (Nagoya University, Nagoya, Japan) and Takaya Arita (Nagoya University, Nagoya, Japan)
DOI: 10.4018/IJSBBT.2015010101
OnDemand PDF Download:
List Price: $37.50


Cellular Automata (CAs) have been investigated extensively as abstract models of the decentralized systems composed of autonomous entities characterized by local interactions. However, it is poorly understood how CAs can interact with their external environment, which would be useful for implementing pervasive systems that consist of billions of components (nodes, sensors, etc.). This paper focuses on the emergent properties of CAs induced by external perturbations toward controlling pervasive systems. The authors assumed a minimum task in which a CA has to change its global state drastically after every occurrence of a perturbation period. By conducting evolutionary searches for rules of CAs, they obtained interesting behaviors of CAs in which their global state cyclically transited among different stable states in either ascending or descending order. They analyze the emergent behavior in detail and also introduce applications of the evolved CA for controlling pervasive robots and an interactive art.
Article Preview


A cellular automaton (CA) is a discrete model consisting of a regular grid of finite automata called cells. The next state of each cell is completely decided by the current states of its neighbors including itself. CAs are well-suited for investigating the global behavior emerging from local interactions among component parts. A CA can be interpreted as an abstract model of multi-agent systems (MAS) if we regard each cell in a CA as an agent in a MAS, because the multiple autonomous agents in a MAS locally interact with each other in general, as shown as Figure 1. MAS can be constructed as a large-scale space by using CA and it is also easy to visualize. Therefore, there are several applications for MAS which make use of computational and emergent properties of CAs, including traffic simulations (Sakai, Nishinari & Iida, 2006), ecological modeling (Nagata, Morita, Yoshimura, Nitta & Tainaka, 2008), controlling decentralized pervasive systems (Mamei, Roli & Zambonelli, 2005).

Figure 1.

A cellular automaton (CA) as an abstract model of multi-agent systems (MAS)

There have been a number of studies on basic characteristic of CAs under the assumption of strong restrictions such as a regular arrangement of cells and synchronous update of the cell states.

It is well known that Wolfram suggested that elementary (one-dimensional two-state three-neighbor) CAs fall into four classes. In particular, he pointed out that CAs in class four exhibit complex behaviors, and some of them achieve computational universality (Wolfram, 2002).

On the one hand, there are studies on CAs with relaxed restrictions so as to investigate the behaviors of the decentralized systems in realistic situations from a variety of viewpoints. Ingerson & Buvel (1984) pointed out that the synchronous updating rule is unnatural if we regard them as abstractions of decentralized systems in a real world, and analyzed elementary CAs with asynchronous updating rules. They demonstrated that the global pattern of the asynchronous CA self-organized into a regular array, and argued that asynchronous CA might be useful for understanding self-organization in a real world.

Also, there are several discussions on the effects of influences on the system from outside such as boundary conditions and perturbations. Ninagawa, Yoneda & Hirose (1997) focused on influences of the differences, and compared the effects of the dissipative boundary conditions (in which each cell state is randomly decided at each step) on the global behaviors of CAs with those of the standard periodic boundary conditions. They showed that the CAs with the former condition can eliminate the size effects of the grid on the global behaviors which are prominent in CAs with the latter condition. Marr & Hütt (2006) showed that based on a comparison of space-time diagrams of configurations and some of the indices, the modifications of the neighboring structures on the regular grid can be functionally equivalent to the introduction of stochastic noises on the states of the cells in CAs that basically exhibit chaotic behaviors.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 5: 2 Issues (2017): Forthcoming, Available for Pre-Order
Volume 4: 2 Issues (2016): Forthcoming, Available for Pre-Order
Volume 3: 1 Issue (2015)
Volume 2: 4 Issues (2013)
Volume 1: 4 Issues (2012)
View Complete Journal Contents Listing