Cellular Automata

This paper presents our first version of Protein modeling Cellular Automata Machine (PCAM). The peptide chain of amino acid backbone of a protein having n number of amino acids is designed with an 8n cell uniform CA employing one of the 64 three neighborhood CA (3NCA) rules. Each amino acid of a protein chain is modeled by a group of eight CA cells. Variation of the interaction pattern of a protein backbone under different physical conditions is modeled with different sixty-four 3NCA rules. Another set of twenty 8-bit patterns are next designed to encode the molecular structure of side chains of twenty amino acids. The eight CA cells representing an amino acid in the chain is initialized with the 8 bit pattern of its side-chain. A set of features extracted from evolution of PCAM are mapped to real life experimental results. The PCAM model is validated from cancer immunotherapy experimental results for MAb-PD-L1 interaction on multiple MAbs (Monoclonal Antibodies) with the protein PD-L1 associated in human immunity.

Increasing experimental evidence suggests that the behaviour of multi-cellular systems, such as tissues and organs, might be largely driven by the complex interplay occurring among metabolic networks. Computational approaches are required to unravel this complexity. However, they currently deal with either the simulation of the spatial dynamics of cell populations or with the simulation of metabolism of individual cells. In order to integrate the modeling of these two key biological processes, we here introduce FBCA (Flux Balance Cellular Automata) a new multi-scale modeling framework that combines a cellular automaton representation of the (higher-level) spatial/morphological dynamics of multi-cellular systems, i.e., the Cellular Potts Model, with a model of the (lower-level) metabolic activity of individual cells, as modeled via Flux Balance Analysis. The representation via cellular automata allows to identify and analyze complex emergent properties and patterns of real-world multi-cellular systems, in a variety of distinct experimental settings. We here present preliminary tests on a simplified model of intestinal crypt, in which cell populations with distinct metabolic properties compete for space and nutrients. The results may allow to cast a new light on the mechanisms linking metabolic properties to clonal dynamics in tissues.

Modern biological paradigms of invasion in tumour cells cannot be fully explained or described by existing modelling techniques. We present a novel cellular automata model which represents both the nucleus of a cell and its membrane, allowing one to capture the interaction of a cell with its environment, as well as selected theorems for the efficient computation of solutions to such systems. We use this technique to simulate cell-cell binding, single-cellular micro track invasion, and co-injection of MITF $$^{\text {HIGH}}$$ (proliferative) and MITF $$^{\text {LOW}}$$ (invasive) tumour cells into heterogeneous environments. Results shed new light on emergent phenomena of cellular elongation, filopodial protrusion, and the co-invasion of the local stroma by classically non-invasive cells. We also provide a new modelling framework in which the cellular automaton exhibits non-local interaction within its context.

Existing computer models of cancer focus mostly on disease progression rather than its remission/recurrence caused by anti-cancer therapy. Herein, we present a discrete model of tumor evolution in 3D, based on the Particle Automata Model (PAM) that allows for following the spatio-temporal dynamics of a small neoplasm (millimeters in diameter) under treatment. We confront the 3D model with its simplified 0D version. We demonstrate that the spatial factors such as the vascularization density, absent in the structureless 0D cancer models, can critically influence the results of treatment. We discuss briefly the role of computer simulations in personalized anti-cancer therapy.

In this paper we propose a new approach to evaluate electrical performances and temperature field for standard photovoltaic (PV) panels. The model is based on two-component cellular automata (CA) that describe the dynamics and behavior of a solar cell. The first component represents the evolution and distribution of the temperature in PV panels and the second consists of the electrical output characteristics of the solar cells. The coupling of these two-components allows us to simulate numerically the operation mode of solar cells according to four defined states: direct mode, inverse mode, hot spot mode and failure mode in order to compute the generated electrical power. This model is adapted to the case of uniform and non-uniform irradiation. Some simulations and experimental results illustrate our approach.

Cellular Automata (CA) models have been applied to different fields of knowledge, from cryptography, arts, to the modelling and simulation of complex systems. In the latter area, however, sometimes the ability to properly represent complex interacting but distinct dynamics taking place within a given area is limited by the need of calibrating models in which the number of necessary parameters grows. Hidden costs related to the identification of specific values or plausible ranges for parameters can become overwhelming.Here we model the assembly process of plant communities after fire. The number of elements of plant communities (plants of different species) and processes involved (seed dispersal, plant recruitment, competence, etc.) require a high degree of parameterization because all those processes have great relevance on the evolution of the system, for instance during post-fire recovery.The fire, aside negative effects, releases a number of resources (space, nutrients, ...) making them easily available for plants, which promptly use those resources so they are no longer available to other plants after a period of time which usually ranges from months to years. In the meantime, the plasticity of species in relation to fire and environment and the interactions among species determine the direction of changes to occur.In this work we present a novel approach to the assembly of plant communities after fire using CA. In particular we gather the preliminary results of their application and give a feasible way to optimize the parameterization of the model.

A hybrid model, combining a Cellular Automaton (CA) and a multi-agent system, was proposed to mimic the computation abilities of the plasmodium of Physarum polycephalum. This model was implemented on software, as well as, on hardware, namely on a Field Programmable Gate Array (FPGA). The specific ability of the P. polycephalum simulated here is given in brief, also bringing attention to the approximation of a Kolmogorov-Uspensky machine (KUM), an alternative to the Turing machine. KUM represent data and program by a labeled indirected graphs and a computation is performed by adding/removing nodes/edges. The proposed model implementation is taking full advantage of the inherent parallel nature of automaton networks, and CA, as a result of the mapping of the local rule to a digital circuit. Consequently, the acceleration of the computation for the hardware implementation, compared to the software, is as high as 6 orders of magnitude.

Cellular Automata based approach to modelling of the corrosion and passivation of metals in electrolytes is presented. We simulate the growth of the passive layer using an asynchronous CA, implemented for parallel processing on a GPU. In the present version of our model, the studied system is under galvanostatic control. The electric potential is adjusted to fix the current flow to a prescribed value. In the electrochemical experiments, this leads to potential oscillations for certain values of the current. This is related to the fact that for certain range of potentials our system displays a negative differential resistivity. We manage to obtain potential oscillations in our simulations. To our knowledge this is the first time that this peculiar feature of passivating system is reproduced by a computer simulation.

In this paper we present a method for motion detection and characterization using Cellular Automata. The original approach employs results of the application of the Sobel operator to individual frames, that are translated to CA configurations that are processed with the aim of detecting and characterizing moving entities to support collision avoidance from the perspective of the viewer. The paper formally describes the adopted approach as well as its experimentation videos representing plausible situations.

Individual-based modelling is an increasingly popular framework for modelling biological systems. Many of these models represent space as a lattice, imposing unrealistic limitations on the movement of the modelled individuals. We adapt existing models of three competing species by using a lattice-free approach, thereby improving the realism of the spatial dynamics. We retrieve the same qualitative dynamics as the lattice-based approach. However, by facilitating a higher spatial heterogeneity and allowing for small spatial refuges to form and persist, the maintenance of coexistence is promoted. This corresponds well with experimental results.

We consider a problem of lifetime optimization in Wireless Sensor Networks. The purpose of the system is to find a global activity schedule maximizing the lifetime of the Wireless Sensor Network while monitoring some area with a given measure of Quality of Service. The main idea of the proposed approach is to convert the problem of a global optimization into a problem of self-organization of a distributed multi-agent system, where agents take part in a game and search a solution in the form of a Nash equilibrium. We propose two game-theoretic models related to the problem of the lifetime optimization in Wireless Sensor Network and apply deterministic $$\epsilon $$ -Learning Automata as players in the games. We present results of an experimental study showing the ability of reaching optimal solutions in the course of Learning Automata self-organization by local interactions in an iterated game.

Given a 2d Cellular Automaton (CA) with mobile agents controlled by a finite state automaton (algorithm). Initially the field is colored white and agents are randomly placed. They have the task to color the whole field into black in shortest time. The objective is to find algorithms that (1) can form the black–pattern, (2) keep it stable and then (3) change into a global state where all agents stop their activity. Four levels of stability are distinguished, depending on the grade of inactivity after having formed the pattern. For systems with up to four agents we found such algorithms by applying genetic algorithms (GA) and manual post fine tuning. Performances and simulations of these algorithms are presented.

In our paper we use the, recently proposed, model for simulating the process of disease spreading in the environment defined by the Cellular Automaton. The main effort goes to the analysis of the influence of cell size on the epidemic curves and other characteristics related to the studied process. We take into account some real data concerning the occupation in the city of Łódź, which has about 700000 inhabitants. The results show that by marshaling the parameters of simulation we can obtain explicitly different results. This comment applies to a lot of features like: the shape of epidemic curve, the total number of diseased or the amount of ill in particular areas/cells.

This work investigates a coordination model based on a two-dimensional cellular automata applied to a team of surveillance robots. The synergy among the robots emerges from the indirect communication performed by repulsive pheromone interactions. Five strategies are evaluated for the decision-making related to the next-cell selection: three stochastic (pure, elitist and inertial), one random and one deterministic. The performance of the team performing surveillance are evaluated in respect to two aspects: the number of task cycles (visiting all the rooms) completed in a fixed interval of time and the homogeneity of the environment coverage. Experimental results corroborate the importance of the cooperative pheromone and shows that the decision-making strategies have different inherent skills that can be explored for distinct situations.

A model of agent-based simulation of communicating vehicles is presented to study the information spreading in a vehicular ad hoc network (VANET). The agents are moving along the fastest paths between their starting points and their destinations on real urban topo-logy. During the motion, they can exchange information by short-range wireless communication. The goal is to analyze the statistical properties of the information spreading in the system, e.g. the time evolution of the average awareness or the age distribution of information owned by separate vehicles.

The rates of cognitive agents’ correct and incorrect crossing decisions, correct and incorrect waiting decisions in learning to cross cellular automaton based highway are studied. The effects of presence of risk takers and risk avoiders on these rates are investigated for agents using observational social learning strategies. One of these strategies is based on the assessment of agents crossing decisions, and another one is based on the assessment of agents crossing and waiting decisions. Also, the effects of transfer of agents’ knowledge base built in one traffic environment to the agents in another one on the rates of agents’ various decisions are investigated.

The Hermes project [1] demonstrated the usefulness of on site predictive simulations of probable evacuation scenarios for security personnel. However, the hardware needed was prohibitively expensive [2]. For use in crowd management, the software has to run on available computers. The CA methods, which are fast enough, have well known problems with treating corners and turns. The present paper shows how a standard CA method can be modified to produce a realistic movement of people around bends and obstacles by changing the standard floor field. This can be done adaptively allowing for the momentary situation using simple predictions for the immediate future. The approach has one or two tuning parameter that have an obvious meaning and can therefore be set correctly by people not familiar with the inner process of a CA simulation. With this, a high end laptop can simulate more than 100 000 persons faster than real time, which should be enough for most occasions. It is intended to integrate the method into the tool JuPedSim [23].

The problem of analysis of traffic jams performed by the Cellular Automata oriented techniques is widely studied since the beginning of 90th and the seminal paper of Nagel and Schreckenberg. The typical approach is based on the one to one relation between the sizes of cell and the particular vehicle. We propose to take into account the smaller size of cells what makes possible to consider more densely distributed values of typical features of vehicles like velocity or acceleration. On the other hand, the decrease of cell size can lead to the model which is very similar to the continuous one. We think that our approach does not exceed the limits sensible for CA.

In the article the influence of corners on the path on discrete-continuous pedestrian dynamics model have been discussed. Angles from classic 90 $$^\circ $$ case study to “Z”-shaped geometry were considered. “Z”-shaped geometry is peculiar for modern shopping and entertainment centers, when we consider way from the stadium to outer perimeter.

The paper presents a model of a two-way one-lane road with loading/unloading bays. The developed model is based on the theory of cellular automata. The model reflects the real behaviour of drivers described in the literature and observed in reality. A micro-simulator was developed to present the measurement results. The model was compared with the one-way two-lane road with loading/unloading bays model described in the literature.

Cellular automaton (CA) models of traffic flow are typically constructed to reproduce macroscopic features of traffic flow. Here, a few thoughts based on real car-following data are presented that show how to construct a discrete time/discrete space microscopic model of traffic flow. The question whether this can still be called a CA-model is left to the reader.

Probabilistic Cellular Automata are extended stochastic systems, widely used for modelling phenomena in many disciplines. The possibility of controlling their behaviour is therefore an important topic. We shall present here an approach to the problem of controlling such systems by acting only on the boundary of a target region.

We study the regional master-slave synchronization of a one dimensional probabilistic cellular automaton with two absorbing states. The master acts on the boundary of an interval, the region, of a fixed size. For some values of the parameters, this is enough to achieve synchronization in the region. For other values, we extend the regional synchronization to include a fraction of sites inside the region of interest. We present four different ways of doing this and show which is the most effective one, in terms of the fraction of sites inside the region and the time needed for synchronization.

A large number of cellular automata have been given as a transition table constructed by hand. The methodology of “cellular fields” propose to give them by their modular design principles instead, and to generate the transition table in last step, as it is the case for high-level programming language source code and their binary executable file. In this paper, we check whether this generated tables can be optimized to be as small a their counterpart constructed by hand. This is done in the particular case of a cellular automaton solving the Firing Squad Synchronization Problem using cellular fields. We study the internal structure of this solution and study their reductions in the same vein as deterministic finite automata minimization. We also compare this solution with the 8-states solution of Noguchi and devise another notion of optimization.

The firing squad synchronization problem (FSSP, for short) on cellular automata has been studied extensively for more than fifty years, and a rich variety of FSSP algorithms has been proposed. Here we study the classical FSSP on a model of fault-tolerant cellular automata that might have possibly some defective cells and present the first state-efficient implementations of fault-tolerant FSSP algorithms for one-dimensional (1D) and two-dimensional (2D) arrays. It is shown that, under some constraints on the distribution and length of defective cells, any 1D cellular array of length n with p defective cell segments can be synchronized in $$2n-2+p$$ steps and the algorithm is realized on a 1D cellular automaton with 164 states and 4792 transition rules. In addition, we give a smaller implementation for the 2D FSSP that can synchronize any 2D rectangular array of size $$ m \times n$$ , including O(mn) rectangle-shaped isolated defective zones, exactly in $$2(m+n)-4$$ steps on a cellular automaton with only 6 states and 939 transition rules.

An n-cell maximal length cellular automaton (CA) is a binary CA which is having a cycle of length $$2^n-1$$ . These CAs are linear and have been used in different applications, such as pseudo random number generation, VLSI design & test, cryptosystem etc. For some applications, however, it could be good if we can use non-linear maximal length CAs. In this paper, we arrange an experiment for the search of non-linear maximal length CAs. By experimentation, we have seen that there exists non-linear maximal length CAs.

We introduce an algebraic approach for the analysis and composition of finite, discrete-time dynamical systems based on the category-theoretical operations of product and sum (coproduct). This allows us to define a semiring structure over the set of dynamical systems (modulo isomorphism) and, consequently, to express many decomposition problems in terms of polynomial equations. We prove that these equations are, in general, algorithmically unsolvable, but we identify a solvable subclass. Finally, we describe an implementation of the semiring operations for the case of finite cellular automata.

Cellular Automata (CA) are both a parallel computational paradigm and an archetype for modelling complex systems, that evolve on the basis of local interactions. CA can embody different numeral representations and perform related basic arithmetical operations. However, conventional numeral representations are thought as intrinsically sequential in such operations, which implies that CA parallelism is underexploited when CA evolution mimics the sequentiality of calculation, while some redundant numeral representations could exalt the CA parallelism in a space/time trade-off, where the time complexity of some operations is constant on input length. The problem then arises when the result of an operation must be utilized in the conventional representation since, usually, the migration toward an advantageous redundant numeric representation is costless, but the inverse one implies necessarily a cost that cancels the benefits in terms of computation time. This paper explores the properties of the conventional binary positional representation embodied in a CA together with the addition operation and the corresponding ones of a redundant binary positional representation, the rules and time cost for the passage from conventional numeral system to redundant one and vice versa. The results permit to individuate the CA computation context, when redundancy could be exploited advantageously. It regards cases where a longest sequence of additions (or operations based on addition, e.g., fast Fourier transforms) has to be performed in well-defined short times as for the automatic control of mobile devices.

Many physical problems cannot be easily formulated as quantum circuits, which are a successful universal model for quantum computation. Because of this, new models that are closer to the structure of physical systems must be developed. Discrete and continuous quantum walks have been proven to be a universal quantum computation model, but building quantum computing systems based on their structure is not straightforward. Although classical cellular automata are models of universal classical computation, this is not the case for their quantum counterpart, which is limited by the no-coning theorem and the no-go lemma. Here we combine quantum walks, which reproduce unitary evolution in space with quantum cellular automata, which reproduce unitary evolution in time, to form a new model of quantum computation. Our results show that such a model is possible.

Cellular automata (CAs) have played a significant role in studies of complex systems. Recently, a recursive estimation of neighbors algorithm that distinguishes the perception area of each cell from the CA rule neighborhood was introduced to extend CA. This framework makes it possible to construct non-uniform CA models composed of cells with different sizes of the perception area, which can be interpreted as an individual attribute of each cell. For example, focusing primarily on one-dimensional (1D) elementary CA, fractal CAs composed of self-similarly arranged cells have been proposed and their characteristics have been investigated. In this paper, 2D fractal CAs are defined and implemented for outer-totalistic CA rules. Fractal CAs derived from a linear rule inherit that rule’s features, including replicability and time reversibility, which indicate their applicability to various fields.

We study the computational capacity of self-verifying cellular automata with an emphasis on one-way information flow ( $$\text {SVOCA}$$ ). A self-verifying device is a nondeterministic device where each computation path can give one of the answers yes, no, or do not know. For every input word, at least one computation path must give either the answer yes or no, and the answers given must not be contradictory. Realtime $$\text {SVOCA}$$ are strictly more powerful than realtime deterministic one-way cellular automata. They can be sped-up from lineartime to realtime and are capable to simulate any lineartime computation of deterministic two-way CA. Closure and decidability properties are considered as well.

Cellular Automata (CA) are a self reproducing model widely accepted for their applications in pattern recognition, VLSI design, error correcting codes, cryptography etc. They have also been widely accepted as good random number generators. The pseudorandom properties of 3- and 4-neighbourhood CA have been studied and they show that the neighbourhood radii has an impact on pseudorandomness. This motivated us to perform the exploration of 5-neighbourhood 1-dimensional CA for better cryptographic properties. We construct a class of linear and nonlinear rules for 5-neighbourhood CA and also propose a new stream cipher design using 5-neighbourhood CA inspired from the Grain cipher.

Mutually Orthogonal Cellular Automata (MOCA) are sets of bipermutive CA which can be used to construct pairwise orthogonal Latin squares. In this work, we consider the inversion problem of pairs of configurations in MOCA. In particular, we design an algorithm based on coupled de Bruijn graphs which solves this problem for generic MOCA, without assuming any linearity on the underlying bipermutive rules. Next, we analyze the computational complexity of this algorithm, remarking that it runs in exponential time with respect to the diameter of the CA rule, but that it can be straightforwardly parallelized to yield a linear time complexity. As a cryptographic application of this algorithm, we finally show how to design a (2, n) threshold Secret Sharing Scheme (SSS) based on MOCA where any combination of two players can reconstruct the secret by applying our inversion algorithm.

We study a cellullar automata inspired asynchronous model of computation that models core features of the structure and functioning of living cells. We describe cell repair rules that ensure that the structure and the computation performed by a group of cells withstands occasional faults that may occur.We observe that some self-organizing healing strategies of cells do admit that, under certain conditions, cells do exhibit massive proliferation of cells.

Alesia is a two-player zero-sum game which is quite similar to the rock-paper-scissors game: the two players simultaneously move and do not know what the opponent plays at a given round. The simultaneity of the moves implies that there is no deterministic good strategy in this game, otherwise one would anticipate the moves of the opponent and easily win the game. We explore how to build a family of one-dimensional stochastic cellular automata to play this game. The rules are built in an iterative way by progressively increasing the complexity of the transitions. We show the possibility to construct a family of rules with interesting results, including a good performance when confronted to the Nash-equilibrium strategy.

The asynchronous dynamics associated with a Boolean network $$f:\{0,1\}^n\rightarrow \{0,1\}^n$$ is a finite deterministic automaton considered in many applications. The set of states is $$\{0,1\}^n$$ , the alphabet is [n], and the action of letter i on a state x consists in either switching the ith component if $$f_i(x)\ne x_i$$ or doing nothing otherwise. This action is extended to words in the natural way. We then say that a word w fixes f if, for all states x, the result of the action of w on x is a fixed point of f. A whole family of networks is fixable if its members are all fixed by the same word, and the fixing length of the family is the minimum length of such a word. In this paper, which is building closely on [2] where these notions have been introduced, we are interested in families of Boolean networks with relatively small fixing lengths. Firstly, we prove that fixing length of the family of networks with acyclic asynchronous graphs is $$\varTheta (n 2^n)$$ . Secondly, it is known that the fixing length of the whole family of monotone networks is $$O(n^3)$$ . We then exhibit two families of monotone networks with fixing length $$\varTheta (n)$$ and $$\varTheta (n^2)$$ respectively, namely monotone networks with tree interaction graphs and conjunctive networks with symmetric interaction graphs.

In this paper we study the family of two-state Totalistic Freezing Cellular Automata (FTCA) defined over the triangular grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only of the sum of its active neighbors. We study the family of FTCA in the context of asynchronous updating schemes (calling them FTACA), meaning that at each time-step only one cell is updated. The sequence of updated sites is called a sequential updating schemes. Given configuration, we say that a site is stable if it remains in the same state over any sequential updating scheme.In this context, we consider the Asynchronous Stability problem, consisting in decide whether there is a sequential updating scheme such that an inactive cell becomes active. We show that in this family the problem is NC, i.e. it can be solved by fast-parallel algorithms.

We investigate the dependence of steady-state properties of Schelling’s segregation model on the agents’ activation order. Our basic formalism is the Pollicott-Weiss version of Schelling’s segregation model. Our main result modifies this baseline scenario by incorporating contagion in the decision to move: (pairs of) agents are connected by a second, agent influence network. Pair activation is specified by a random walk on this network.The considered schedulers choose the next pair nonadaptively. We can complement this result by an example of adaptive scheduler (even one that is quite fair) that is able to preclude maximal segregation. Thus scheduler nonadaptiveness seems to be required for the validity of the original result under arbitrary asynchronous scheduling. The analysis (and our result) are part of an adversarial scheduling approach we are advocating to evolutionary games and social simulations.

Cellular Automata (CA) have a long history being employed as pseudo-random number generators (PRNG), especially for cryptographic applications such as keystream generation in stream ciphers. Initially starting from the study of rule 30 of elementary CA, multiple rules where the objects of investigation and were shown to be able to pass most of the rigorous statistical tests used to assess the quality of PRNG. In all cases, the CA employed where of the classical, synchronous kind. This assumes a global clock regulating all CA updates which can be a weakness if an attacker is able to tamper it. Here we study how much asynchrony is necessary to make a CA-based PRNG ineffective. We have found that elementary CA are subdivided into three class: (1) there is a “state transition” where, after a certain level of asynchrony, the CA loses the ability to generate strong random sequences, (2) the randomness of the sequences increases with a limited level of asynchrony, or (3) CA normally unable to be used as PRNG exhibit a much stronger ability to generate random sequences when asynchrony is introduced.

This paper presents an analysis how different acceleration policies to reach the maximum speed of the road, considered as a heterogeneity unobserved in usual measurements, influence the probability of occurrence of Dangerous Situations (DS) that can lead to accidents between vehicles. For this, a modified version of the NaSch model is proposed. The probability Density Function (PDF) Beta is used to describe these distinct behaviors. The effect of these policies on the traffic dynamics was also analyzed. A new metric is presented so that we can analyze results where real deceleration rates data are used to evaluate accident probability.

In the paper we present a model using Cellular Automata dedicated for competitive evacuation. Floor field models of pedestrian dynamics are the starting point. We have observed that during competitive evacuation, the dynamics of particular pedestrians is similar to the dynamics of particles in granular flow when viscosity is taken into account. In order to address this issue we have prepared real experiments and have proposed and implemented a Cellular Automata model using an idea of viscosity.

Computer simulation for the study of pedestrian dynamics is an active and lively area in which contributions from different disciplines still produce advancements on the state of the art. Discrete modelling of pedestrian dynamics represents a more computationally efficient approach than the continuous one, despite the potential loss of precision in the reproduced trajectories or modelling artefacts. To overcome these issues and reducing the intrinsic effects of employing a discrete environment, several works have been proposed focusing on distinct objectives within this framework. This paper proposes a general approach to reproduce smooth and rounded trajectories of pedestrians in presence of bends and corners, by means of a so-called angular floor field. The proposed algorithm works with arbitrary settings and it is tested on benchmark situations to evaluate its effects from both a quantitative and qualitative perspective.

This study presents a simple Cellular Automata model which allows to estimate the combined effect of crowd control and information provision on pedestrian dynamics. We assume the case of a closed loop consisting of two lanes connected in only two points where pedestrians are allowed to move from the inner to the outer loop and in the opposite direction. Both lanes are virtually divided by a wall which does not allow to visually inspect the other side except on the locations connecting them. To investigate the effect of information provision we assume that a given number of pedestrians have information on the speed in both lanes. In addition, we assume that lane changing locations are guarded by security staff which can give orders to the crowd on which lane to choose. However, only a given number of pedestrians are compliant and will obey to the orders. Initial settings for the simulation have been set so that free flow in both lanes is obtained only when the number of lane changes is limited and density is equal in both inner and outer loops. Results show that crowd control strategy, compliance ratio and information provision have a clear impact on the overall group speed. The combined analysis of all variables showed that efficient information provision is the most reliable method to ensure an adequate speed (and flow) even when crowd control fails or when compliance is low.

Cellular Automata simulations of crowd dynamics can support the design of transportation facilities in terms of efficiency, comfort and safety. The development of realistic CA models requires the acquisition of empirical evidences about human individual and collective behavior. The paper reports the results of controlled experiments of personal space in static and dynamic situations: the area surrounding human body, linked to crowding due to spatial intrusion/restriction. We propose a discrete representation of personal space through discrete potentials and an innovative crowding estimation method (i.e. Cumulative Mean Crowding). Simulation results are focused on the parametric evaluation of pedestrians’ psychological stress reaction to density.

This study presents the principles of an application that is designed to facilitate customized evacuation from indoor spaces. The proposed approach combines in-doors detection using existing wireless networks based on trilateration technique and proper evacuation estimation based on cellular automata (CA). An efficient application has been developed that can be installed in smartphones under Android operation system and technically fulfills the scopes of the aforementioned evacuation model. More specifically, it offers the user the option to view her/his location at any time and to find the closest possible route to an exit in case of an emergency. The efficiency of the application to provide reliable guidance towards an exit is also evaluated. Preliminary results are reasonably encouraging; provided that the application is properly customized then a reliable, real-time evacuation guidance could be realized.

The Biham-Middleton-Levine (BML) traffic model is a simple two-dimensional discrete Cellular Automaton (CA) that has been used to study self-organization and phase transitions in traffic flows. From the computational point of view, the BML model exhibits the usual features of discrete CA, where the new state of each cell is computed according to simple rules involving its current state and that of the immediate neighbors. In this paper we evaluate the impact of various optimizations for speeding up CA computations on shared-memory parallel architectures using the BML model as a case study. In particular, we analyze parallel implementations of the BML automaton for multicore CPUs and GPUs. Experimental evaluation provides quantitative measures of the payoff of different optimization techniques. Contrary to popular claims of “double-digit speedups” of GPU versus CPU implementations, our findings show that the performance gap between CPU and GPU implementations of the BML traffic model can be greatly reduced by clever exploitation of all available CPU features.

Organizational models and holonic multiagent systems are growing as a powerful tool for modeling and developing large-scale complex system. The main issue in deploying holonic multiagent systems is the building of the holonic model called holarchy. This paper presents a novel top down approach based on graph theory in order to build recursively the initial holarchy of road traffic. Moreover, multilevel indicators based on standard deviation is proposed to evaluate the consistency of the holonification process.