2D P Colonies and Modelling of Liquid Flow Over the Earth's Surface

2D P Colonies and Modelling of Liquid Flow Over the Earth’s Surface Ludˇek Cienciala, Lucie Ciencialov´a, and Miroslav Langer Institute of Computer Science and Research Institute of the IT4Innovations Centre of Excellence, Silesian University in Opava, Czech Republic {ludek.cienciala, lucie.ciencialova, miroslav.langer}@fpf.slu.cz Summary. We continue the investigation of 2D P colonies introduced in [1], a class of abstract computing devices composed of independent agents, acting and evolving in a shared 2D environment where the agents are located. Agents have limited information about the contents of the environment where they can move in four directions. 1 Introduction P colonies were introduced in the paper [5] as formal models of computing devices belonging to membrane systems and similar to formal grammars called colonies. This model is inspired by the structure and the behaviour of communities of living organisms in a shared environment. The independent organisms living in a P colony are called agents. Each agent is represented by several objects embedded in a membrane. The number of objects inside each agent is the same and constant during computation. The environment is agents’ communication channel and storage place for objects. At any moment all agents “know” about all the objects in the environment and they can access any object immediately. More information about P colonies the reader can find in [4, 2]. P colonies are one of the types of P systems. They were introduced in 2000 in [6] by Gheorghe P˘aun as a formal model inspired by the structure and the behaviour of cells. With each agent a set of programs is associated. The program, which determines the activity of an agent, is very simple and depends on the contents of agents and on types and number of objects placed in the environment. An agent can change the contents of the environment through programs and it can affect the behaviour of other agents through the environment. This influence between agents is the key factor in the functioning of the P colony. At any moment each object inside every agent is affected by the execution of the program. For more information about P systems see [8, 7] or [11]. 52 L. Cienciala, L. Ciencialov´a, M. Langer In addition 2D P colony has the environment in a form of a 2D grid of square cells. The agents are located in this grid and their view is limited to the cells that immediately surround them. Based on the contents of these cells, the agents decide their future locations. Behaviour of each agent is based on its set of programs. The programs are formed from two rules of type rewriting, communication and movement. By using the rewriting rule one object within the agent is changed (evolved) to another object. When the communication rule is applied one object from the environment is consumed by the agent and one object from content of the agent is placed to the environment. The last type of rules is the movement rule. The condition for the movement of an agent is to find specific objects in specific locations in the environment. This is specified by a matrix with elements - objects. The agent is looking for at most one object in every surrounding cell. If the condition is fulfilled then the agent moves one cell up, down, left or right. The program can contain one movement rule at most. To achieve the greatest simplicity in agent behaviour, we set another condition. If the agent moves, it cannot communicate with the environment. So if the program contains a movement rule, then the second rule is the rewriting rule. Although the colony is a theoretical computing model through 2D, it is a suitable tool for modelling the behaviour of natural multi-agent systems - colonies of bacteria or ants, spreading substances in homogeneous and inhomogeneous medium. In this paper we present hydrological modelling flow of liquid over the Earth’s surface using 2D P colonies. Based on the entered data - the slope surface, a source of fluid and quantity - we simulate the fluid distribution in the environment. The first part of the paper is devoted to 2D P colonies. The rest is organised as follows: The issue of the flow of liquid over the surface, problem solution - maps preparation, definition of the agent, process simulation, comparison with cellular automaton and future expansion. 2 Definitions Throughout the paper we assume that the reader is familiar with the basics of the formal language theory. We use NRE to denote the family of the recursively enumerable sets of natural numbers. Let Σbe the alphabet. Let Σ∗be the set of all words over Σ(including the empty word ε). We denote the length of the word w∈Σ∗by |w|and the number of occurrences of the symbol a∈Σin wby |w|a. A multiset of objects Mis a pair M= (V, f), where Vis an arbitrary (not necessarily finite) set of objects and fis a mapping f:V→N;fassigns to each object in Vits multiplicity in M. The set of all multisets with the set of objects Vis denoted by V◦. The set V0is called the support of Mand is denoted by supp(M) if for all x∈V0f(x)6= 0 holds. The cardinality of M, denoted by 2D P Colonies 53 |M|, is defined by |M|=Pa∈Vf(a). Each multiset of objects Mwith the set of objects V0={a1,...an}can be represented as a string wover alphabet V0, where |w|ai=f(ai); 1 ≤i≤n. Obviously, all words obtained from wby permuting the letters represent the same multiset M. The εrepresents the empty multiset. 3 2D P colonies We briefly summarize the notion of 2D P colonies. A P colony consists of agents and an environment. Both the agents and the environment contain objects. With each agent a set of programs is associated. There are three types of rules in the programs. The first rule type, called the evolution rule, is of the form a→b. It means that the object ainside the agent is rewritten (evolved) to the object b. The second rule type, called the communication rule, is of the form c↔d. When the communication rule is performed, the object cinside the agent and the object doutside the agent swap their places. Thus, after the execution of the rule, the object d appears inside the agent and the object cis placed outside the agent. The third rule type, called the motion rule, is of the form matrix 3×3→move direction. Based on the contents of the neighbouring cells, an agent can move one step to the left, right, up or down. A program can contain maximum one motion rule. When there is a motion rule inside a program, there cannot be a communication rule inside the same program. Definition 1. The 2D P colony is a construct Π= (A, e, Env, B1, . . . , Bk, f), k ≥1, where •Ais an alphabet of the colony, its elements are called objects, •e∈Ais the basic environmental object of the colony, •Env is a pair (m×n, wE), where m×n, m, n ∈Nis the size of the environment and wEis the initial contents of environment, it is a matrix of size m×nof multisets of objects over A− {e}. •Bi,1≤i≤k, are agents, each agent is a construct Bi= (Oi, Pi,[o, p]) , 0≤o≤m, 0≤p≤n, where –Oiis a multiset over A, it determines the initial state (contents) of the agent, |Oi|= 2, –Pi={pi,1, . . . , pi,li}, l ≥1,1≤i≤kis a finite set of programs, where each program contains exactly 2rules, which are in one of the following forms each: ·a→b, called the evolution rule, ·c↔d, called the communication rule, ·[aq,r]→s, 0≤q, r ≤2, s ∈ {⇐,⇒,⇑,⇓}, called the motion rule; •f∈Ais the final object of the colony. The configuration of the 2D P colony is given by the state of the environment - matrix of type m×nwith multisets of objects over A− {e}as its elements, and 54 L. Cienciala, L. Ciencialov´a, M. Langer by the state of all agents - pairs of objects from alphabet Aand the coordinates of the agents. An initial configuration is given by the definition of the 2D P colony. The computational step consists of three parts. The first part lies in determining the applicable set of programs according to the actual configuration of the P colony. There are programs belonging to all agents in this set of programs. In the second part we have to choose one program corresponding to each agent from the set of applicable programs. There is no collision between the communication rules belonging to different programs. The third part is the execution of the chosen programs. A change of the configuration is triggered by the execution of programs and it involves changing the state of the environment, contents and placement of the agents. The computation is nondeterministic and maximally parallel. The computation ends by halting when no agent has an applicable program. The result of the computation is the number of copies of the final object placed in the environment at the end of the computation. Another way to determine the result of the computation is to take into account not only the number of objects but also their location. The result could then be a grayscale image, a character string or a number that is dependent on both the number and pposition of the objects (for example, g=Pn−1 j=0 Pm−1 i=0 f(i, j)· ni, where f(i, j) is the number of copies of object fin the [i, j]-cell). The reason for the introduction of 2D P colonies is not the study of their computational power but monitoring their behaviour during the computation. We can define certain measures to assess the dynamics of the computation: •the number of moves of agents •the number of visited cells (or not visited cells) •the number of copies of a certain object in the home cell or throughout the environment. These measures can be observed both for the individual steps of the computation and the computation as a whole. 4 The issue of the flow of liquid over the surface The issue of the flow of liquid over the Earth’s surface is studied by experts from two areas - hydrology and geoinformatics. Both of these disciplines work closely together on the issue of the so-called “surface runoff”. Surface runoff is the water flow that occurs when the soil is infiltrated to full capacity and excess water from rain, meltwater, or other sources flows over the land. Surface runoff can be generated in four reasons: infiltration excess overland flow, saturation excess overland flow, antecedent soil moisture, subsurface return flow. Infiltration excess overland flow occurs when the rate of rainfall on a surface exceeds the rate at which water can infiltrate the ground, and any depression 2D P Colonies 55 storage has already been filled. When the soil is saturated and the depression storage filled, and rain continues to fall, the rainfall will immediately produce surface runoff - saturation excess overland flow. Soil retains a degree of moisture after a rainfall. This residual water moisture (antecedent soil moisture) affects the soil’s infiltration capacity. During the next rainfall event, the infiltration capacity will cause the soil to be saturated at a different rate. The higher the level of antecedent soil moisture, the more quickly the soil becomes saturated. Once the soil is saturated, runoff occurs. After water infiltrates the soil on an up-slope portion of a hill, the water may flow laterally through the soil, and exfiltrate (flow out of the soil) closer to a channel. This is called subsurface return flow or throughflow. We can say that generation surface runoff depends on type of soil, temperature, humidity and rainfall. The task of our model is to determine which way the flow would run and which areas could be affected by flash floods. 5 Problem solution We divide solution of the problem into two parts - (1) preparation of maps (2D P colony’s environment) and (2) definition of agents. We assume that the soil is already saturated thus the main factor of overland flow is the slope of the field. 5.1 Preparation of maps Map data is obtained from the geographic information system (GIS) and processing system ArcGIS. We use the map data for the Czech Republic called the digital model of the terrain in scale 1: 25 000 (DM´ U25). Raster graphics images are probably the most appropriate format for modelling real-world phenomena in the field of GIS. To process this format, many tools were created and can be used for performing various analyses. A raster image is composed of a regular network of cells, usually in a square shape, to which values of displayed properties can be assigned independently. More information about GIS and image processing the reader can find in [3] and about geosimulation in [10]. The first step to simulate the flow of liquid over relief was the determination of its runoff from individual pixels (cells). Gradient with respect to an adjacent cell is defined as the ratio of the height difference to the horizontal distance. Gradient is positive due to the lower neighbours, or negative due to higher and zero in relation to the neighbours of the same height. Lowest neighbour is neighbour with the largest positive gradient. Basic classification algorithms to calculate the runoff: •Single flow direction (SFD) - each pixel of the liquid flows in one direction only (toward neighbour in the direction of the largest gradient). Each pixel belongs to only one basin. 56 L. Cienciala, L. Ciencialov´a, M. Langer •Multiple flow direction (MFD) - fluid can flow out of each pixel in multiple directions, maximum of eight. In the case of MFD a unit volume flow is fairly distributed among all lower neighbours. The MFD may include the pixel to multiple basins. There is implemented a tool for calculating the flow direction in ArcGIS software, called simply Flow direction. Flow Direction tool works as a simple flow direction (SFD). After its execution integer raster file is created that specifies the flow direction for each cell. Every cell can reach value ranging from 1 to 255. Eight basic directions of the flow are represented by the numbers 1,2,4,8,16, 32,64 and 128 (see Table 1). Other directions are generated as sums of values of the basic directions. 32 64 128 16 - ↑ % ← → . ↓ & 1 8 4 2 Table 1. The numbers of eight basic directions When creating the model, we used the test data to propose group of programs. The final visualization is based on data from DM´ U 25. What we obtain from ArcGIS is a raster file with natural number in each cell corresponding to the runoff from this cell. Because 2D P colony works with discrete symbols and not with numbers, it needed to transcode numbers to symbols. A coding table is shown on Table 2 direction → ← ↑ ↓ & . % - symbol a E i m q u y 2 Table 2. The coding table The first processed map is map without drainless area and its size is 20 ×12 and it is shown on the Table 3. Transcoded symbols are shown on the Table 4. 5.2 Definition of the agent Agents in 2D P colonies have capacity 2. It follows that the agent contains two objects, and each program is composed by two rules. 2D P Colonies 57 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0-↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑% 1←%%%%%%%%%%%%%%%%%%→ 2←%%%%%%%%%%%%%%%%%%→ 3←%%%%%%%%%%%%%%%%%%→ 4←%%%%%%%%%%%%%%%%%%→ 5←→%%%%%%%%%%%%%%%%% → 6← ↓ ↓ %%%%%%%%%%%%%%%%→ 7← ↓ ↓ ↓ ↓ ↓ & % % % % % %%%%%%%→ 8← ↓ ↓ ↓ ↓ ↓ ↓ & & & % % %%%%%%%→ 9←↓↓↓↓↓↓↓↓&&&→%%%%%%→ 10 ←↓↓↓↓↓↓↓↓↓↓↓&&%%%%%→ 11 ←↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓& Altitude (meters above sea level) 1320 1330 1340 1350 1360 1370 1380 1390 Table 3. Processed map 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 2 iiiiiiiiiiiiiiiiiiy 1Eyyyyyyyyyyyyyyyyyya 2Eyyyyyyyyyyyyyyyyyya 3Eyyyyyyyyyyyyyyyyyya 4Eyyyyyyyyyyyyyyyyyya 5Eayyyyyyyyyyyyyyyyya 6Emmyyyyyyyyyyyyyyyya 7E m m m m m q y y y y y y y y y y y y a 8E m m m m m m q q q y y y y y y y y y a 9E m m m m m m m m q q q a y y y y y y a 10 E m m m m m m m m m m m q q y y y y y a 11 Emmmmmmmmmmmmmmmmmm t Table 4. Transcoded symbols Each of the objects carries the information about the state of the agent. The first object has information about the activity of the agent. At this stage of the simulation it is the information that the agent “flows” down the terrain or it is still inactive (belonging to the rainfall that have not fall). The second object stores information about the previous direction of flow. This information can further modify the way of the agent as inertia. Objects and their association to the flow directions are given in the following table. direction → ← ↑ ↓ & . % - symbol 9 8 6 7 D D U U symbol L K H I I I H H 58 L. Cienciala, L. Ciencialov´a, M. Langer The inertia of crossing directions is modified because of longer distance between the centres of the cells. The first subset of programs with priority 0 is defined for the first step of computation. The initial configuration of each “working” agent is Xe. (1) *  ∗ ∗ ∗ ∗a∗ ∗ ∗ ∗  → ⇒;e→9+; (2) *  ∗∗∗ ∗E∗ ∗∗∗ → ⇐;e→8+; (3) *  ∗∗∗ ∗i∗ ∗∗∗ → ⇑;e→6+; (4) *  ∗∗∗ ∗m∗ ∗∗∗ → ⇓;e→7+; (5) *  ∗∗∗ ∗q∗ ∗∗∗ → ⇒;e→D+; (6) *  ∗∗∗ ∗u∗ ∗∗∗ → ⇐;e→D+; (7) *  ∗∗∗ ∗y∗ ∗∗∗ → ⇒;e→U+; (8) *  ∗∗∗ ∗2∗ ∗∗∗ → ⇐;e→U+; In the case of programs (5) and (6) (resp. (7) and (8)) it is neccessary to take one step down (resp. up). (9) *  ∗∗∗ ∗∗∗ ∗∗∗ → ⇓;D→I+; (10) *  ∗∗∗ ∗∗∗ ∗∗∗ → ⇑;U→H+; While agents apply programs with priority 1 (9) and (10), agents, that do not move in a cross direction, must stand. Therefore, they use a program composed of two rewriting rules. The programs have priority 2. (11) hX→X; 6 →Hi; (12) hX→X; 7 →Ii; (13) hX→X; 8 →Ki; (14) hX→X; 9 →Li; The following programs with priority 0 are used to guide the agent in the next steps, the agent may hold information about the movement in the previous step. (15) *  ∗ ∗ ∗ ∗a∗ ∗ ∗ ∗  → ⇒;H→9+; (16) *  ∗∗∗ ∗E∗ ∗∗∗ → ⇐;H→8+; (17) *  ∗∗∗ ∗i∗ ∗∗∗ → ⇑;H→U+; (18) *  ∗∗∗ ∗m∗ ∗∗∗ → ⇓;H→7+; (19) *  ∗∗∗ ∗q∗ ∗∗∗ → ⇒;H→D+; (20) *  ∗∗∗ ∗u∗ ∗∗∗ → ⇐;H→D+; (21) *  ∗∗∗ ∗y∗ ∗∗∗ → ⇒;H→U+; (22) *  ∗∗∗ ∗2∗ ∗∗∗ → ⇐;H→U+; 2D P Colonies 59 (23) *  ∗ ∗ ∗ ∗a∗ ∗ ∗ ∗  → ⇒;I→9+; (24) *  ∗∗∗ ∗E∗ ∗∗∗ → ⇐;I→8+; (25) *  ∗∗∗ ∗i∗ ∗∗∗ → ⇑;I→6+; (26) *  ∗∗∗ ∗m∗ ∗∗∗ → ⇓;I→7+; (27) *  ∗∗∗ ∗q∗ ∗∗∗ → ⇒;I→D+; (28) *  ∗∗∗ ∗u∗ ∗∗∗ → ⇐;I→D+; (29) *  ∗∗∗ ∗y∗ ∗∗∗ → ⇒;I→U+; (30) *  ∗∗∗ ∗2∗ ∗∗∗ → ⇐;I→U+; (31) *  ∗ ∗ ∗ ∗a∗ ∗ ∗ ∗  → ⇒;J→9+; (32) *  ∗∗∗ ∗E∗ ∗∗∗ → ⇐;J→L+; (33) *  ∗∗∗ ∗i∗ ∗∗∗ → ⇑;J→6+; (34) *  ∗∗∗ ∗m∗ ∗∗∗ → ⇓;J→7+; (35) *  ∗∗∗ ∗q∗ ∗∗∗ → ⇒;J→7+; (36) *  ∗∗∗ ∗u∗ ∗∗∗ → ⇐;J→D+; (37) *  ∗∗∗ ∗y∗ ∗∗∗ → ⇒;J→6+; (38) *  ∗∗∗ ∗2∗ ∗∗∗ → ⇐;J→U+; (39) *  ∗ ∗ ∗ ∗a∗ ∗ ∗ ∗  → ⇒;K→N+; (40) *  ∗∗∗ ∗E∗ ∗∗∗ → ⇐;K→8+; (41) *  ∗∗∗ ∗i∗ ∗∗∗ → ⇑;K→6+; (42) *  ∗∗∗ ∗m∗ ∗∗∗ → ⇓;K→7+; (43) *  ∗∗∗ ∗q∗ ∗∗∗ → ⇒;K→D+; (44) *  ∗∗∗ ∗u∗ ∗∗∗ → ⇐;K→7+; (45) *  ∗∗∗ ∗y∗ ∗∗∗ → ⇒;K→U+; (46) *  ∗∗∗ ∗2∗ ∗∗∗ → ⇐;K→6+; We need one more program for “resetting” inertia. This is for the case when the slope of the terrain changes extremely. (47) hX→X;N→ei; If we run the obtained 2D P colony in the simulator, agents, which represent a unit volume of water, will begin to move around the environment. The number of agents located in one cell at one moment corresponds to the amount of water that at once flowed through the territory in one unit of time.