Catalyzed  by  the  emergence  of  modern  computers,  cellular  automata (CAs)  became  a  full-fledged  research domain  in  the eighties  of the previous  century. The  relevant  literature is of a dichotomous nature in the sense that studies  either focus on  the spatio-temporal dynamics that is evolved by CAs, while others merely use the CA paradigm  to  build  a  model  for  a  given  biological,  natural  or  physical  process.  It  goes  without saying that a profound  understanding  of  CA  dynamics  is  a  prerequisite  for building realistic, identifiable CA-based models, though this is not straightforward due the fact that a CA is discrete in all its senses. 

In  an  attempt  to  quantify  CA  behaviour  in  a  meaningful  and reproducible way, several so-called behavioural measures  have  been  proposed  during  the  last  two  decades.  Here,  we  show  how  Lyapunov exponents and Boolean  derivatives can be used to get a complete picture of CA dynamics in the sense that they not only make it possible  to  unravel  the  nature  of  a  given  CA,  but also allow for assessing the effect of changing model design parameters  on  the  CA  behavior.  Finally,  we  introduce  the  so-called  Lyapunov  profile  of  a CA, which may be understood  as  the counterpart of the Lyapunov spectrum of a smooth dynamical system. These profiles capture the spreading  properties  of  a  set  of  defects,  as  well  as  the  exponential accumulation rates of defects within this set. 

In a second part,  we  focus  on 1D CAs and the space-time diagrams they evolve. We present a novel approach to the  automated  classification  of  1D  CAs   according  to  Wolfram's  classification  scheme  by  relying  on  texture features  grasping  the  diagrams' nature,  followed  by  nearest  neighbor  classification.   Finally,  we consider the identification   of  1D  CAs  in  the  context  of  spatially and/or temporally  incomplete  space-time  diagrams.   We formulate  the  identification  problem as  an  optimization  problem  and present a genetic algorithm variant with individuals   of   variable   length,   corresponding   to   different  neighborhood  radii.  Connections   between   the dynamical properties of CAs and the performance of the algorithm are explored.

Department of Mathematics and Statistics

University of Guelph

Talk title: Cognitive Agents Learning to Cross a Cellular Automaton Based Highway

Research  in  swarm  robotics  has  shown  that,  for carrying  out  some  tasks  (e.g.,  target or source search, task allocation,  exploration,  mapping,  cooperative  transportation,  unmanned aerial vehicle (UAV)  controlling,  post-disaster  relief),  it  may  be  more  efficient,  reliable  and  economical   to  employ  a  large  number  (hundreds or thousands) of very simple robots than to employ a small number  of  sophisticated ones. For the development of swarms  of autonomous robots,  which  may  require  them  to learn  how  to  accomplish some tasks in unknown dynamically  changing  environments,  it  is  important  to  study the process of learning through observation and repetition.

Since individual robots in a swarm are usually architecturally minimal with limited computational capabilities, it is important that, in a swarm of robots, the implemented learning algorithms are not computationally demanding. In the microscopic  modeling  of  swarm of robots, individual robots may be identified as cognitive agents capable of  performing  cognitive  acts;  i.e.  a  sequence  of the following activities: (1) “Perceiving” information in both the environment  and  that  which  is  provided  by  other agents (2) “Reasoning” about this information using existing knowledge; (3)   “Judging”  the  obtained information using existing knowledge; (4) “Responding” to other cognitive agents  or  to   the  external   environment, as  it  may   be  required;  (5)  “Learning”;  i.e.  changing (and  hopefully augmenting) the existing knowledge if the newly acquired information allows it.

In  this  talk  a  simple example of  a minimal cognitive agent that could be used as  a  virtual experimental platform to   explore  agent  ability   to  learn  will  be identified and discussed. We will discuss the model of cognitive agents learning  to  cross  a  CA  based  highway. As the emphasis is on minimal storage and logical primitives, the formal methods of computational intelligence and established algorithms such as reinforcement learning algorithms are not used in this example. Instead, inspired by “biomimicry”, simple learning algorithm based on an “observational social learning” principle, i.e. each agent learns from observing the outcomes of the behaviours of other agents, is designed  and  its  performance  is  investigated.  We  discuss  the  effects of the agents’ different decision-making cognitive processes, the effects of the agents’ knowledge base  accumulation  through observation and repetition and the effects of other model parameters on the agents’ success of learning to cross a CA based highway.

Modern control theory emerged in the late 50’s and since then successfully addressed many theoretical and application problems related with the online observation and control of finite dimensional dynamical systems. Later on, from the late 60’s, some system theorist (mainly applied mathematicians) were getting involved in the analysis and control of spatially distributed dynamical systems, also termed as distributed parameters or infinite dimensional systems, whose dynamics is usually described with sets state partial differential equations. From then, many problems were solved, especially those related to classical control problems for linear distributed parameter systems. However very challenging questions arise specifically for spatially distributed systems.

In this talk we will review briefly the traditional settings for distributed parameters control systems and some important questions related to the control and observation of these systems. Then we will present some control problems related to the spatial distribution of these systems for which cellular automata like approaches could be relevant.