Cellular automata for the observation of complex systems

Overview & Synopsis

In this thesis, we propose to study the observability of cellular automata (CA), i.e. how we can efficiently reconstruct the state of a CA from a limited number of measurements. To do so, we draw our inspiration from the notion of observability in classical control theory. This notion guarantees that the state of a system can be perfectly reconstructed from the measurements.In order to apply results in classical control theory to CA, we adopt the CA definition of El Yacoubi (2008) and use it to define the notions of measurements and sensor networks for CA. Utilising these definitions we then develop the concepts of observability, reconstructibility, and adaptability in the context of cellular automata.Subsequently, we define analytical criteria to verify these three notions for specific families of CA. We start with additive and affine CA for which we transpose the rank condition developed by Kalman and adapt it to provide similar conditions for reconstructibility and adaptability. Next, we focus on non-linear CA. We optimise observability and reconstructibility criteria for Boolean networks. We also propose a method for decentralising the observability analysis which may be applied to check observability and reconstructibility for very large CA.We propose then another observation method with a totally different approach based on synchronisation. It avoids the computational complexity issues encountered using previous methods. In particular, in the case of small initial error, we propose an improved synchronisation method that drastically increases observation performance.We conclude the thesis by illustrating the developed methods on three examples. We apply reconstructibility and synchronisation methods to a forest fire propagation model. We compare the observation performance of both methods. Then, we use reconstructibility and decentralised reconstructibility on a road traffic model. Finally, we use the observability of additive CA to reconstruct a sequence of numbers produced by a CA-based random number generator.