Identifiability of cellular automata and related spatio-temporal paradigms
Dr. ir. Jan Baetens
Cellular Automata (CAs) form an interesting class of dynamical systems. Whereas partial differential equations are prototypical examples of the continuous modelling paradigm (as state, time and space are continuous), CAs are to be situated at the extreme end of the discrete modelling paradigm (as state, time and space are discrete). In essence, the discrete state of the discrete spatial entities evolves in discrete time steps according to some local transition rule based on the notion of a neighborhood. Their simplicity and the increased availability of spatio-temporal observations at various spatial scales are but two of the factors explaining their increased popularity in different areas of science.
Unfortunately, the identification of a CA from data is far from simple and largely understudied. Pinpointing the local transition rule such that the model meets certain criteria or shows a satisfactory fit to the observed data is still difficult. To that end, in a cooperation between KERMIT and the Polish Academy of Sciences (carried out by PhD student Witold Bolt), a set of methods and algorithms are being developed in order to tackle such identification problems. The current approach is based on the use of evolutionary algorithms.
The main goal of this new project is to determine the conditions under which (partially observed) CAs are identifiable, understood as the full recovery of the rule in question. The problem should be studied in different contexts including: stochastic CAs, noisy observations, spatial and/or temporal gaps in observations, CAs with multiple (ordered) states, etc. The output expected is theoretical as well as practical.