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 decentralized pervasive systems that consist of billions of components (nodes, sensors, etc.) distributed in our everyday environments. This chapter focuses on the emergent properties of CAs induced by external perturbations toward controlling decentralized pervasive systems. We assumed a minimum task in which a CA has to change its global state drastically after every occurrence of a perturbation period. In the perturbation period, each cell state is modified by using an external rule with a small probability. By conducting evolutionary searches for rules of CAs, we obtained interesting behaviors of CAs in which their global state cyclically transited among different stable states in either ascending or descending order. The self-organizing behaviors are due to the clusters of cell states that dynamically grow through occurrences of perturbation periods. These results imply that we can dynamically control the global behaviors of decentralized systems by states of randomly selected components only.
TopIntroduction
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 comparison of space-time diagrams of configurations and some of 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.