Implementation of cell clustering in cellular automata

[摘要] ENGLISH ABSTRACT: Cellular Automata (CA) have become a popular vehicle to study complex dynamicalbehaviour of systems. CA can be used to model a wide variety of physical,biological, chemical and other systems. Such systems typically consist of subpartsthat change their state independently, based on the state of their immediate surroundingsand some generally shared laws of change.When the CA approach was used to solve the LEGO construction problem, the bestsolution was found when using a variant of CA allowing for the clustering of cells.The LEGO construction problem concerns the optimal layout of a set of LEGObricks. The advantages found for using the CA method with clustering in this caseare the ease of implementation, the significantly smaller memory usage to previouslyimplemented methods, and its trivial extension to construct multicoloured LEGOsculptures which were previously too complex to construct.In our research we propose to explore the definitions of clustering in CA and investigatethe implementation and application of this method. We look at the antsorting method described by Lumer and Faieta, and compare the implementationof this algorithm using regular CA as well as the clustering variation. The antsorting model is a simple model, in which ants move randomly in space and pickup and deposit objects on the basis of local information.

[发布机构] Stellenbosch University