Article Preview
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 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.