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

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.

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.