Grafowy automat komórkowy o zmiennych sąsiedztwach relacyjnych komórek - założenia dla implementacji w FPGA

• Autorzy: Hołowiński G. , Małecki K.

Warianty tytułu

EN

Graph Cellular Automaton with Dynamic Relation Based Neighborhoods of Cells - Introduction for FPGA Implementation

• Języki publikacji: PL

Abstrakty

PL

Artykuł prezentuje nowy automat komórkowy r-sdgCA, który pozwala na modelowanie procesów zachodzących w układach o zmiennej w czasie liczbie obiektów i relacjach pomiędzy nimi. To nowe podejście pozwala na modelowanie zjawisk zachodzących w sieciach komputerowych, modelach ruchu pojazdów i interakcjach między nimi, serwisach społecznościowych, itp. Artykuł przedstawia definicję r-sdgCA i nową, charakterystyczną dla niego własność - dynamiczne sąsiedztwo relacyjne oraz omawia założenia do implementacji r-sdgCA w FPGA.

EN

Applications of cellular automata (CA) to modelling allow recognizing of complex systems with simple mechanisms [1, 2]. Use of regular, constant in time, grid of cells is the limitations of CA. It causes the set of neighbours is constant. There were provided results of researches that somehow allow omitting this limitation - for example structurally dynamic CA [3,4], CA with irregular neighbourhood or graph related neighbourhood [5, 6, 7]. In this paper there is proposed a new cellular automaton called r-sdgCA. Its unique feature is a reconfigurable structure of active cells in the grid and dynamic relation-based neighbourhoods of cells. The reconfigurable G graph - that can reconfigure its sets of vertices and directed weighted edges - is used to define the dynamic relation based neighbourhoods of cells in r-sdgCA and corresponding dynamic structure of active and inactive cells in the grid. Figure 2 shows example of objects and corresponding relations mapping to cells of r-sdgCA. The second part of paper focuses on possible areas of implementation of this new automaton and some basic assumptions about implementation or r-sdgCA in FPGA. Functional steps of process modelling using r-sdgCA and general scheme of r-sdgCA is shown at Fig. 3. The proposed r-sdgCA can be used to modelling processes in systems of dynamic number of objects (and relations among them). This new approach help understanding of wide range of processes that work both in real life and artificial systems.

Słowa kluczowe

PL

automat komórkowy; niehomogeniczny automat komórkowy; sąsiedztwo relacyjne dynamiczne; modelowanie systemów złożonych

EN

cellular automation; cellular automata; dynamic relationship; modeling of complex systems

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 8
• Strony: 861--863
• Opis fizyczny: Bibliogr. 9 poz., rys., schem., wzor

Twórcy

autor

Hołowiński G.

autor

Małecki K.

• Akademia Morska w Szczecinie, Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, ul. Wały Chrobrego 1/2, 70-500 Szczecin,

Bibliografia

• [1] Wolfram S.: A New Kind of Science. Wolfram Media, Champaign, 2002.
• [2] Culik K., Hurd L. P., Yu S.: Computation theoretic aspects of cellular automata. Physica D, 45, 1990, pp. 357-378.
• [3] Ilachinsky A., Halpern P.: Structurally Dynamic Cellular Automata. Complex Systems, 1, 1987, pp. 503-527.
• [4] Alonso-Sanz R.: A Structurally Dynamic Cellular Automaton with Memory in the Triangular Tessellation. Complex Systems, 17, 2007, pp. 1-15.
• [5] Cornforth D., Green D. G., Newth D., Kirley M.: Do Artificial Ants March in Step? Ordered Asynchronous Processes and Modularity. Biological Systems, In Standish, Bedau, Abbass, Proceedings of the Eighth International Conference on Artificial Life, Sydney, 2002, pp. 28-32.
• [6] Couclelis H.: From cellular automata to urban models: new principles for model development and implementation. Environment and Planning B: Planning and Design 24, 1997, pp. 165-174.
• [7] O’Sullivan D.: Graph-cellular automata: a generalised discrete urban and regional model. Environment and Planning B: Planning and Design, volume 28, 2001, pp. 687-705.
• [8] Takeyama M., Couclelis H.: Map dynamics: integrating cellular automata and GIS through Geo-Algebra. International Journal of Geographical Information Science 11, 1997, pp. 73-91.
• [9] Takeyama M.: Building spatial models within GIS through geo-algebra. Transactions in GIS 2, 1997, pp. 245-256.