Emergent behaviour

From EngageWiki

Introduction

Air transportation systems are facing the challenge to innovate air and ground infrastructures and air traffic management protocols to meet the levels of projected passenger volume and quality of services expected in future years. The most critical aspect of this challenge is how to overcome the problem of airspace capacity limitation by ensuring high levels of efficiency together with the highest standards of security.

General objective

In recent years there has been a growing awareness that the air transportation system cannot be planned, optimized, monitored and investigated by focusing separately on the different modules building up the system, see Holmes (2004). In fact, although the majority of the interactions among air traffic actors are interactions relatively localized in space and time, the complex interconnections present among all the actors of this socio-technical system make the air transportation system a "system-of-systems" structured as a layered collection of interacting networks, see for example DeLaurentis et al. (2006). For example, Holmes (2004) has identified four main layers of networks of the air transportation system described as (i) a physical layer (with airports as nodes and airways as links), (ii) a transportation layer (with aircrafts as nodes linked by air traffic control radar), (iii) an operational layer (with a network of pilots, crew, controllers, etc. linked by a VHF communication system) and (iv) an application layer (with people, goods and travel planners setting the needs of air capacity for the short and medium term time period).

In each of these network layers the interconnection of a plurality of heterogeneous socio-technical actors produces emergent phenomena impacting multiple spatial regions on multiple time scales. The position paper needs therefore to focus on the investigation and modelling of emergent processes observed in the current setting of air traffic management and on the future scenarios of it (planned and/or simulated). A key concept in the description of emergent properties of complex systems is the concept of phase transition. Phase transitions occur in physical, biological and social systems both in the presence and in the absence of tuning parameters. A paradigmatic example of phase transition is provided by the phenomenon of percolation that was originally introduced in simple geometrical lattices and therefore used in the modelling of many real systems. Specific scales both in space and in time cannot typically describe statistical properties of emerging behaviours. For this reason, their functional profile is often a power-law profile.

In summary, the complexity of the interconnections and of the procedures present in the air traffic management systems and of their future developments implies that emergent phenomena are natural in this system. These emergent phenomena need to be investigated to assess the degree of efficiency, robustness and resilience of the system at a global scale.

Definitions

We will therefore illustrate hereafter a few emergent phenomena observed in a socio-technical complex system like the ATM one. Before going further, it is however useful to set up a glossary of terms specifically used in the ATM context. Networks and power-laws were defined earlier, in Section 0.2.1.

Phase Transition: the original concept of “phase transition” refers to the fact that a thermodynamic system can change its state of matter. In the complex systems context, “phase transition” refers to the fact that a complex systems made of many elementary elements locally interacting, under certain conditions may present a collective state (called phase of the system). The properties of this state are controlled by a variable named “order parameter”. It also said that the system shows criticality, meaning that there exists a “critical point” that marks the passage from a disordered state in which the local interactions are predominant to the collective state. A fingerprint of criticality is the presence of power-law behaviour in variables describing the system.

Percolation: the original concept of “percolation” concerns the movement and filtering of fluids through porous materials. In the complex systems context, “percolation” refers to the fact that given two neighbouring sites, a link between them is present with probability [math]p[/math] and its absence is observed with probability [math](1-p)[/math]. Percolation is relevant in the study of the spreading of information over a network.

Scope

In this chapter we will focus mainly on a specific mechanism of emergent behaviour, namely phase transitions with a special emphasis on jamming transitions and percolation phase transitions, because we believe they might play an important role in ATM modelling. Moreover phase transitions are probably the most important example of emergent behaviour in Statistical Physics. We also discuss power laws, which are functional relations between variables of a complex system that are observed frequently around phase transition. It is important to stress, however, that a power law relation is not sufficient to claim that the system is at a critical state. In fact, it has been repeatedly shown that there are many mechanisms, which are able to display power law behaviour. Therefore the section on power laws focuses on a characteristic, which is ubiquitous in complex systems but not necessarily always overlapping with critical phenomena.

For the topics mentioned above, we will present some case studies reported in the existing literature. These include jamming transitions in air traffic, percolation of congestions in sectors, and the relevance of power law distributions in describing the hub and spoke airport network. This list is clearly very partial and not exhaustive. We present also some possible future challenges for the application of the concept of emergence to ATM. We only marginally cover self-organized criticality, which is a form of critical behaviour not driven by an external parameter. In particular, we do not describe self-organization mechanisms creating formation of patterns. This emergent behaviour is observed when an ordered spatial or spatio-temporal pattern emerges as the result of self-organization in systems out of equilibrium. This type of emergent phenomena has been observed in developmental biology, chemical reaction, growth of bacterial colonies, etc..

We also briefly consider emergent phenomena induced by the interaction of agents in an agent-based model of a complex system. In many socio-economic systems the interaction of individuals that pursue their own sheer interest might lead to collective phenomena that are not expected by looking at the individuals alone. The paradigmatic example is the concept of “Invisible hand” by Adam Smith. More recent examples include systems where agents have bounded rationality.

Finally we are not considering noise-induced phenomena, which is a class of emergent behaviour that is receiving growing attention in the recent years. Typically random fluctuations are considered a source of disorder in complex systems. In noise induced phenomena, the interaction between noise and nonlinear dynamics may lead to the emergence of a number of ordered behaviours (in time and space) that would not exist in the absence of noise.

Research lines

The analysis of the research theme ‘Emergen behaviour’ is divided into three research lines; they are the following:

  • Phase transitions;
  • Percolation in non-homogenous media;
  • Power laws in ATM complex systems.

Phase transitions

Problem statement

The concept of phase transition and criticality (Stanley (1971), Binney et al. (1992)) is probably the most important one when a physically oriented modelling of emergent behaviour is accomplished. In the simplest setting, a model (often a highly stylized toy model such as the Ising model (Huang (1987)) of many elementary elements interacting locally, presents a collective state (called phase of the system), whose properties are controlled by the temperature (or another thermodynamic variable) of the system and are characterized by a variable named order parameter. By changing the temperature of the system (or any variable that can play its role in complex systems) the system presents an abrupt transition between different phases of the system (e.g. a transition from a paramagnetic to a ferromagnetic phase). The nature of the phase of the system cannot be related to the microscopic nature of the basic element composing the system (a two state up or down variable in the Ising model). Different phases are separated by a critical state. The physical properties of the system near the critical state can belong to universality classes characterized by the nature of the order parameter of the system, Binney et al. (1992).

Statistical physics has also developed the concept of self-organized criticality (see Bak et al. (1987)). This is a concept showing that a critical state is not only encountered when a system switches between two distinct macroscopic phases but that criticality can also be observed for complex systems that naturally converge to a critical state without an external tuning.

A different type of transition is the jamming transition. In some materials, such as granular materials, it is observed that by increasing the density the material becomes rigid. This type of transition has similarity with the glass-liquid transition, which is observed when an amorphous material transforms itself from a hard and brittle state into a rubber-like state. Technically speaking it is still debated whether jamming transition is a phase transition, even if recent results seem to suggest a positive answer to this question (Biroli (2007), Key et al. (2007)), pointing out the difference with other phase transitions, such as the formation of a crystal. In a jamming transition at fixed temperature, the increase of the density limit the possibility that a particle explore the phase space, and the matter behaves as a solid. If one increases the temperature, the system might be able to un-jam. Therefore in jamming transitions there is a critical density, which signals the transition. This critical density depends on the details of the considered system. For example, the shape of the constituents or the nature (attracting versus repulsive) of the interaction between them plays an important role.

Literature review

The literature on phase transitions is so vast that it is quite difficult to summarize it here. Moreover it is probably more relevant in this case to review some application of phase transitions to systems that are or might be close to ATM systems and therefore that might be relevant as future research challenges (see also below).

For the purpose of this position paper an important example of applications of emergent behaviours associated with phase transition is the case of traffic jams. As it is well known, in a car jam the average velocity of cars on a road may drop sharply when the density of cars is increased. Therefore this system is analogous to the flow of grain in a pipe. When the density increases the velocity decreases and the flow can stop. The interaction between the grains represents the interaction between cars that need to stay at a certain distance from the next one. Several authors have shown how to build stylized (or toy) models of car flowing in a street and that traffic jams arise in a way similar to a (statistical mechanics) jamming transition.

One of the first and most popular of such models is the Nagel-Schreckenberg model (Nagel et al. (1992), Eisenblatter et al. (1998); for a review of the argument, see Helbing, (2001)). The model describes a flow of cars in a freeway and shows how traffic jams can arise as an emergent collective phenomenon due to the interaction between cars. In the model the road is divided into cells aligned in a single row, i.e. it describes a single lane where no passing is allowed and moreover periodic boundary conditions are often imposed. Each cell describes the space available for a car and at each time it can be in two states, either empty (no car) or filled (one car). Each car has a velocity that ranges from zero to a predefined maximum. Time is also discretized and therefore the model can be thought of as a cellular automaton. There are several variants of the model, but each of them prescribes a set of rules sequentially followed by the cars. For example, each car tries to increase their velocity (if no car in front avoid that) and sometimes randomness is added to the model. The main feature of the model is highlighted by considering the relation between the average car velocity and the density of cars (for a given set of parameters, such as the maximum velocity or the randomization parameter). Numerical simulations show that for small density the average velocity is high and equal to the maximum velocity in the deterministic case. Then there is a critical car density where one observes a discontinuity in the slope (i.e. the derivative) due to the sudden appearance of traffic jams. Then as the density increases further the average velocity decreases until it reaches zero when the road is 100% occupied. An example of this type of behaviour is shown in Figure 2.1.

When the density is smaller than a threshold (in this case, 0.2) the average car velocity is maximum, indicating that the system is in the flowing state. After the transition, the average velocity decreases to zero when the density of cars is increased.

The effect of randomization is to reduce the average velocity in the low-density phase, but it also lowers the critical density at which traffic jams appear. Moreover randomization rounds off an otherwise sharp transition from free flow to jam state. Note that the model gives a clear example of an emergent phenomenon in traffic systems. In fact traffic congestions can emerge without external influences, such as accidents or bottlenecks, but they emerge just because of crowding on the road.

Another example of phase transitions that can be relevant for ATM is the set of critical phenomena observed when modelling agent-based models. In fact, analytical (when feasible) and numerical investigations of an agent-based model can highlight the presence of an order parameter describing different phases of the system. A paradigmatic example of an agent based model describing agents' decisions in a framework of inductive reasoning of economic agents, extensively investigated both analytically and numerically, is the so-called El Farol bar problem (Arthur (1994)) and the corresponding formalized version of the minority game (Challet et al. (1997), Challet et al. (2005)). For a review on the statistical mechanics approach to socio-economic systems with heterogeneous agents the interested reader can consult De Martino et al. (2006).

The modelling of emergent behaviour in biological and social sciences has pointed out the importance of the hierarchical structure of complex systems. In the classic setting of this concept H.A. Simon stated that a hierarchic system is "a system that is composed of interrelated subsystems, each of the latter being, in turn, hierarchic in structure until we reach some lowest level of elementary subsystem" (Simon (1962)). The presence of a hierarchical organization with different levels makes it natural to observe that intrinsically different scientific descriptions are needed in the modelling of different levels of the system. Anderson pointed out this concept by stating "the behaviour of large and complex aggregates of elementary particles, it turns out, is not to be understood in terms of a simple extrapolation of the properties of a few particles. Instead, at each level of complexity entirely new properties appear, and the understanding of the new behaviours requires research which I think is as fundamental in its nature as any other" (Anderson (1972)). In other words, at different hierarchical levels, emergent properties set up and they might need a scientific explanation, which cannot be given in terms of the scientific laws describing the constituent parts of the lower hierarchical level. When the hierarchy of the system is of self-similar nature the concepts of scaling and fractal geometry naturally apply. Scaling (Kadanoff (1990), Stanley (1999)) is a concept that has originated in different areas of mathematics and physical sciences. It is observed in: (i) the absence of a specific scale for some variables of a system, which is at a critical state; (ii) the allometric laws (West et al. (1997)) observed between variables characterizing a system. Deviation from isometric scaling is often due to dimensional constraint as it is observed, for example, in turbulence; (iii) the relationships among observables which are functions of random variables (for example linear sum, maximum or minimum value, etc.) and their number.

Research challenges

Identification of phase transitions and emergence of collective phenomena in ATM.

As in many complex systems, it is important to identify which are the possible phase transitions that can emerge in a model of air traffic management. In fact, the microscopic interaction of many heterogeneous elements can give rise to unexpected emergent phenomena, even in the absence of an external driving event (a large strike or the volcanic ashes). As an example, preliminarily explored in the paper reviewed in the Case Study #1, is the emergence of air traffic jams. The current structure of airspace, with airways and navigation points, and the bottlenecks represented by airports, suggests the possibility that an increasing density of traffic, joined with the significant amount of randomness, can push the system close to a transition similar to a jamming transition.

Another important challenge arises when one considers the ATM system as a socio-technical system. In these cases agent based modelling is a natural tool to investigate the emergence of collective emergent phenomena from the interaction of individuals. As mentioned above, it is not uncommon to observe phase transitions in these models, and phases represent different possible collective states of the system.

The expected rapid increase of traffic in the European and worldwide airspace will challenge the current structure of the system. It is important therefore to know which increase in the air traffic density is sustainable by the system before a significant increase in jams is observed. Clearly jams in a rigidly controlled system, such as air traffic, means an increase in delays frequency, which, in the current structure of indirect connectivity, means in turn significant problems for the passengers. In a SESAR scenario, the topology of routes will completely change and this might have a significant effect on the critical density where the emergent phenomenon of jamming could appear. Carefully empirically calibrated models could help in answering these questions.

A better understanding of the behaviour of air traffic when the density of traffic is increased will clearly have a significant impact on the planning of the future scenario for air traffic management.

Besides amplification of delays frequency, one should also ask what increase is possible in the rate of safety events and accidents and the scaling of their frequency with aircraft density.

All these questions might be tackled by having a better understanding of the different phases in which the system can be found.

Percolation in non-homogenous media

Problem statement

What is percolation? Percolation is a random process exhibiting a phase transition. In the simplest setting percolation is investigated in simple geometrical systems such as regular lattices covering a 2D surface. Even in the simplest setting there are different variants of the percolation problem. Specifically, one speaks about bond percolation when a link between two neighbouring sites is present with probability [math]p[/math] and its absence is observed with probability [math](1-p)[/math]. In this variant all sites are present in the system and links between any pair of them may or may not be present. In the other variant of site percolation the links of the lattice are always present between two occupied sites, but each site is occupied with probability [math]p[/math] and empty with probability [math](1-p)[/math].

In spite of the simplicity of the setting the problem of obtaining the percolation probability, i.e. the probability that there is a continuous path from an arbitrary selected site of the system to infinity, is not an easy task. The percolation probability switches from 0 to 1 (the probability observed at the two extreme cases of empty lattice and fully-connected lattice respectively). Theoretical considerations and numerical simulations show that the percolation probability changes abruptly around a specific value [math]p_c[/math] called critical probability. Exact solutions have been obtained in a few cases as, for example, the case of 2D bond percolation in a square lattice and bond and site percolation in a triangular lattice and the case of bond percolation for d-dimensional lattices with [math]d\geq19[/math] or with [math]d\gt 6[/math] when additional hypothesis on the insertion of links between any two sites within a finite distance is assumed. An exact solution is also known for the case of Cayley tree (also known as Bethe lattice). In the large majority of cases the abrupt increase of the percolation probability at [math]p\approx p_c[/math] is investigated by approximate methods and/or with numerical simulations. The abrupt transition of the percolation probability between two distinct macroscopic states observed for [math]p\lt p_c[/math] and [math]p\gt p_c[/math] together with the presence of many functions characterizing the system, which are showing power-law behaviour when [math]p\approx p_c[/math], are signatures of universal behaviour characterizing systems at a critical state or undergoing a phase transition.

The percolation approach has been extended to disordered systems. Examples are studies describing electric transport in a random media and invasion percolation, i.e. the problem of one fluid invading a porous medium proceeding along a path at least resistance. Percolation has been also investigated in statistical and geometrical fractals. Recently the concept of percolation has been used in the modelling of network properties. In fact, in the investigation of networks describing, for example, internet, social networks, and the power grid, the resilience of these networks to either random or targeted deletion of network nodes has been empirically investigated and theoretically modelled by using concepts and tools of percolation theory on graphs characterized by both Poisson degree distribution and scale free distribution at their vertices.

Percolation is also a key concept in the study of the spreading of epidemics on a network.

Literature review

Percolation (Stauffer et al. (1994)) is today a key concept in complexity theory, statistical physics and in the mathematical description of random media. The first example of mathematical modelling of percolation theory was originally provided by Broadbent and Hammersley (Broadbent (1957)). However, before this mathematical formalization Flory and Stockmayer used percolation concepts in the modelling of the polymerization process that leads to gelation. In their studies, they developed a description of percolation on the Bethe lattice (or Cayley tree) ((Flory (1941), Stockmayer (1943)).

Harry Kesten (Kesten (1980)) obtained the first exact value of the critical probability [math]p_c[/math] for the 2D bond percolation in a square lattice ([math]p_c=1/2[/math]). Exact estimations of the critical probability [math]p_c[/math] are known only for other few cases of bond and site percolation in a triangular lattice and bond percolation for a honeycomb lattice (Kesten (1982)). However, Scullard (Scullard (2006)) and Scullard and Ziff (Scullard et al. (2006)) proved in 2006 that this exact knowledge can be used to obtain exact values of the critical probability of other 2D lattices obtained performing some nonlinear mappings on the triangular lattice.

Percolation theory has also been used in the modelling of random media since Flory's pioneering work. An area of wide applications of the percolation concept to random media is the area of transport of charged carriers. Scott Kirkpatrick (Kirkpatrick (1973)) investigated first the normalized conductance of random resistor networks. Other applications focus on disordered systems, fractals (Havlin et al. (1987)), statistical topography, turbulent diffusion, and heterogeneous media (Isichenko (1992)).

Under standard percolation, criticality is reached at the critical probability. However, there is a variant of percolation that automatically finds the critical points of the system. This variant of the percolation was named invasion percolation (Wilkinson et al. (1983)) and was originally proposed to describe the process of one fluid displacing another from a porous medium under the action of capillary forces. However, the same concept has been applied to many kinds of invasion process proceeding along paths of least resistance. Percolation concepts are also successfully used in the study of epidemics (Grassberger (1983), Cardy et al. (1985)).

The concept of percolation is also fruitfully used in network theory (Cohen et al. (2000), Callaway et al. (2000)) especially for the evaluation of the resilience of networks of different topology. Another research area widely using percolation concepts is the one investigating epidemics problems in social systems and in complex networks (Moore et al. (2000), PastorSatorras et al. (2000)).

Percolation concepts have also been used in the modelling of socio-technical systems. A percolation model was also developed to show how the sales of a new product might penetrate the consumer market (Goldenberg et al. (2000)). Another application concerns the model of innovation. Innovations in social systems occur highly clustered in time rather than if they were purely randomly generated in time. Technological change is often modelled in the economic literature as a process following technological trajectories. It has been proposed that these empirical observations be modelled considering a complex technology space whose dynamics is described in terms of percolation theory (Silverberg et al. (2005)). The technological space is searched randomly in local neighbourhoods. Within the proposed model, numerical simulations show that by increasing the diameter of search, the probability of becoming deadlocked declines and the mean rate of innovation increases. The distribution of innovation cluster sizes is highly skewed and may resemble a power-law distribution near the critical percolation probability.

It has been suggested that the modelling of air traffic control can benefit from the use of percolation concepts in the analysis and modelling of the spatio-temporal diffusion of congestion of sectors of the airspace (Conway2005, BenAmor et al. (2006)). Preliminary attempts show that percolation concepts can be fruitfully used in the analysis, modelling and simulation of the propagation of the saturation of capacity of neighbouring sectors triggered by en route modifications of the flight trajectories (Conway2005, BenAmor et al. (2006)). Moreover, percolation can be a guiding concept in the analysis of the network structure of future design for automated conflict detection of the next generation air transportation system. In fact percolation concepts are useful in the investigation and evaluation of the trade-offs of alternative concepts of collaborative operations, expected conflicts, communications requirements, and vulnerability of the transportation system to targeted attacks. Percolation concepts are indeed qualifying network architecture for air traffic control, enabling in-depth analysis and evaluation of the resulting system (Chen et al. (2011)).

Research challenges

Emergence of Percolation Phenomena in ATM.

The main research challenge to be first addressed in the area of emergence of a percolation phenomenon in ATM is whether percolation concepts can be fruitfully used in the analysis, modelling and numerical simulation of air traffic management time records and in the modelling of future scenario simulations performed with different procedures such as, for example, agent based modelling. Key research questions are: is the process controlled in statistical terms by a parameter describing the probability of congestion of each airspace/sector? is the topology of the airspaces/sectors interconnection relevant in the "percolation" of the congested status across wide regions of the airspace? is a centralized managing of the Air Traffic Control (ATC) more or less sensitive to "avalanches" of delays than a decentralized allocation of the flight trajectories?

En route delay propagation is a non-local problem. Delay originated in a specific airspace/sector can propagate quite far from the originating region. A basic design problem is to evaluate the sensitivity of the air traffic control system to the onset of an "avalanche" of delay as a function of the "avalanche" size. In other words the empirical and theoretical investigation of the scaling relations of the number of airspaces/sectors affected by congestions or closed will be highly informative about the degree of robustness and of resilience of the current and/or designed ATC system. This research challenge implies the solution of several research problems, which are state of the art problems in mathematics, computer science, network theory and statistical physics. In fact the study of percolation in time-dependent networks of arbitrary topology presents many unsolved problems.

Percolation makes the problem of en route delay non-local. The understanding of the spatio-temporal scaling relations of the delay avalanches observed in the global system of airspaces/sectors will provide theoretical instruments for the quantification of the degree of robustness and resilience of the air traffic control system.

Power laws in ATM complex systems

Problem statement

Power-laws were introduced in Section 0.2.1 and have been discussed at various points in this paper. Let us develop the discussion by illustrating the concept further with an example taken from Binney et al. (1992): let us consider [math]f_1=(x/L)^a[/math] and [math]f_2=e^{x/L}[/math]. Both functions involve a scale parameter [math]L[/math]. Let us consider the [math]f_2[/math] function in the interval [math]\left[ 1/2 L, 2L\right][/math]. The ratio between the largest to the smallest value in this interval is [math]r_2=e^{3/2}[/math]. When considering the [math]f_1[/math] function the ratio is [math]r_1=4^a[/math]. Let us now consider the interval [math]\left[ \frac{10}{2}L, 2\cdot10L\right][/math]. When considering the [math]f_2[/math] function the ratio between the largest to the smallest value in this interval is [math]r_2=e^{15}[/math]. When considering the [math]f_1[/math] function the ratio is [math]r_1=4^a[/math]. Let us now consider the interval [math]\left[ \frac{100}{2}L, 2\cdot100L\right][/math]. When considering the [math]f_2[/math] function the ratio between the largest to the smallest value in this interval is [math]r_2=e^{150}[/math]. When considering the [math]f_1[/math] function the ratio is [math]r_1=4^a[/math]. These results show that if we draw graphs of the [math]f_1[/math] function in any of the three intervals they can be superimposed by a simple change of variable. The same is not true for the [math]f_2[/math] function. In this sense a variable obeying a power-law looks the same no matter on what scale one probes it. We refer to such a property by saying that the variable is scale-free (as introduced in Section 0.2.1). The relevance of scale-free behaviour was popularized by Mandelbrot, in Mandelbrot (1977), where the word “fractals” was used to describe the non-differentiable patterns that satisfy power law scaling when the power-law exponent is not equal to an integer. Fractals have the property that, by using an appropriate magnifying glass, one sees the same behaviour across different scales.

Literature review

Statistical regularities expressed in terms of power-laws can be observed in many natural and social phenomena.

Relevant examples are the allometric relations between biological variables. For example the metabolic rates B of entire organisms scale like [math]M^{3/4}[/math] with respect to the mass M of the organism, the cross-sectional areas of mammalians scales again like [math]M^{3/4}[/math] , while the time of blood circulation scales like [math]M^{1/4}[/math] , see West et al. (1997) and West (1998). Other examples of power laws are given by the Zipf’s law. Originally observed in the context of natural language analysis, this law states that after ranking the different words, which are present in a certain text from the most to the least frequent, one observes that the most frequent word will occur approximately twice as often as the second most frequent word, three times as often as the third most frequent word, etc., i.e. the occurrence [math]N_k[/math] of the [math]k[/math]-th

This project has received funding from the SESAR Joint Undertaking under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 783287.