Research On Evolution And Computation With Cellular Automata

Natural evolution has"created"a multitude of systems in which the actions of simple, locally-interacting components give rise to coordinated global information processing. In this paper we use cellular automata to simulate the phenomena. It is evolved and computed on disperse time dimension by local rules. The whole complex system can be described through simple behaviors of local cells and their interaction.Firstly, we expound the principle of cellular automata which is an indispensable precondition for its research on evolution itself. Classifying the initial configuration of a 1-D and binary-state cellular automata as to whether it contains a majority of 0s or 1s– the so-called density-classification problem. Considering it, we prove two necessary conditions that cellular automata must satisfy in order to classify density perfectly. And we depict its property about 2-D cellular automata with periodic boundary conditions, according to variety curve of cells'states.Secondly, we use the cells'parallelism and locality of cellular interactions to simulate propagation of signal and function of logic gates, and achieve efficient computation power on synchronous 2-state, 5-neighbor or 6-state, 5-neighbor asynchronous cellular automata. Then we design variety rules and different configurations of the modules with functions to get the movement without structure change in complex cell space.Finally, the cellular automata model is set to a mobile robot and its environment. When the environment is completely known, the path is generated by repeatedly going through a series of cells and choosing the square with the lowest cost by heuristic algorithm. We also use the interactive and multi-layered cellular automata to get a shortest path which has orientation restrict and different costs. When the robot is in an environment that is partially known, a mixed algorithm including cellular automata and artificial potential field is introduced to the path planning approach temporary point to find the goal. The simulation shows that the mixed algorithm suits the environment entirely and the robot can search a path without collision.