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

2D P Colonies and Modelling o Liquid Flow O e he Ea h’s Su ace Ludˇek Cienciala, Lucie Ciencialo ´a, and Mi osla Lange Ins i u e o Compu e Science and Resea ch Ins i u e o he IT4Inno a ions Cen e o Excellence, Silesian Uni e si y in Opa a, Czech Republic {ludek.cienciala, lucie.ciencialo a, mi osla .lange }@ p .slu.cz Summa y. We con inue he in es iga ion o 2D P colonies in oduced in [1], a class o abs ac compu ing de ices composed o independen agen s, ac ing and e ol ing in a sha ed 2D en i onmen whe e he agen s a e loca ed. Agen s ha e limi ed in o ma ion abou he con en s o he en i onmen whe e hey can mo e in ou di ec ions. 1 In oduc ion P colonies we e in oduced in he pape [5] as o mal models o compu ing de ices belonging o memb ane sys ems and simila o o mal g amma s called colonies. This model is inspi ed by he s uc u e and he beha iou o communi ies o li ing o ganisms in a sha ed en i onmen . The independen o ganisms li ing in a P colony a e called agen s. Each agen is ep esen ed by se e al objec s embedded in a mem- b ane. The numbe o objec s inside each agen is he same and cons an du ing compu a ion. The en i onmen is agen s’ communica ion channel and s o age place o objec s. A any momen all agen s “know” abou all he objec s in he en i- onmen and hey can access any objec immedia ely. Mo e in o ma ion abou P colonies he eade can ind in [4, 2]. P colonies a e one o he ypes o P sys- ems. They we e in oduced in 2000 in [6] by Gheo ghe P˘aun as a o mal model inspi ed by he s uc u e and he beha iou o cells. Wi h each agen a se o p og ams is associa ed. The p og am, which de e - mines he ac i i y o an agen , is e y simple and depends on he con en s o agen s and on ypes and numbe o objec s placed in he en i onmen . An agen can change he con en s o he en i onmen h ough p og ams and i can a ec he be- ha iou o o he agen s h ough he en i onmen . This in luence be ween agen s is he key ac o in he unc ioning o he P colony. A any momen each objec inside e e y agen is a ec ed by he execu ion o he p og am. Fo mo e in o ma ion abou P sys ems see [8, 7] o [11]. 52 L. Cienciala, L. Ciencialo ´a, M. Lange In addi ion 2D P colony has he en i onmen in a o m o a 2D g id o squa e cells. The agen s a e loca ed in his g id and hei iew is limi ed o he cells ha immedia ely su ound hem. Based on he con en s o hese cells, he agen s decide hei u u e loca ions. Beha iou o each agen is based on i s se o p og ams. The p og ams a e o med om wo ules o ype ew i ing, communica ion and mo emen . By using he ew i ing ule one objec wi hin he agen is changed (e ol ed) o ano he objec . When he communica ion ule is applied one objec om he en i onmen is consumed by he agen and one objec om con en o he agen is placed o he en i onmen . The las ype o ules is he mo emen ule. The condi ion o he mo emen o an agen is o ind speci ic objec s in speci ic loca ions in he en i onmen . This is speci ied by a ma ix wi h elemen s - objec s. The agen is looking o a mos one objec in e e y su ounding cell. I he condi ion is ul illed hen he agen mo es one cell up, down, le o igh . The p og am can con ain one mo emen ule a mos . To achie e he g ea es simplici y in agen beha iou , we se ano he condi ion. I he agen mo es, i canno communica e wi h he en i onmen . So i he p og am con ains a mo emen ule, hen he second ule is he ew i ing ule. Al hough he colony is a heo e ical compu ing model h ough 2D, i is a sui - able ool o modelling he beha iou o na u al mul i-agen sys ems - colonies o bac e ia o an s, sp eading subs ances in homogeneous and inhomogeneous medium. In his pape we p esen hyd ological modelling low o liquid o e he Ea h’s su ace using 2D P colonies. Based on he en e ed da a - he slope su ace, a sou ce o luid and quan i y - we simula e he luid dis ibu ion in he en i onmen . The i s pa o he pape is de o ed o 2D P colonies. The es is o ganised as ollows: The issue o he low o liquid o e he su ace, p oblem solu ion - maps p epa a ion, de ini ion o he agen , p ocess simula ion, compa ison wi h cellula au oma on and u u e expansion. 2 De ini ions Th oughou he pape we assume ha he eade is amilia wi h he basics o he o mal language heo y. We use NRE o deno e he amily o he ecu si ely enume able se s o na u al numbe s. Le Σbe he alphabe . Le Σ∗be he se o all wo ds o e Σ(includ- ing he emp y wo d ε). We deno e he leng h o he wo d w∈Σ∗by |w|and he numbe o occu ences o he symbol a∈Σin wby |w|a. A mul ise o objec s Mis a pai M= (V, ), whe e Vis an a bi a y (no necessa ily ini e) se o objec s and is a mapping :V→N; assigns o each objec in Vi s mul iplici y in M. The se o all mul ise s wi h he se o objec s Vis deno ed by V◦. The se V0is called he suppo o Mand is deno ed by supp(M) i o all x∈V0 (x)6= 0 holds. The ca dinali y o M, deno ed by 2D P Colonies 53 |M|, is de ined by |M|=Pa∈V (a). Each mul ise o objec s Mwi h he se o objec s V0={a1,...an}can be ep esen ed as a s ing wo e alphabe V0, whe e |w|ai= (ai); 1 ≤i≤n. Ob iously, all wo ds ob ained om wby pe mu ing he le e s ep esen he same mul ise M. The ε ep esen s he emp y mul ise . 3 2D P colonies We b ie ly summa ize he no ion o 2D P colonies. A P colony consis s o agen s and an en i onmen . Bo h he agen s and he en i onmen con ain objec s. Wi h each agen a se o p og ams is associa ed. The e a e h ee ypes o ules in he p og ams. The i s ule ype, called he e olu ion ule, is o he o m a→b. I means ha he objec ainside he agen is ew i en (e ol ed) o he objec b. The second ule ype, called he communica ion ule, is o he o m c↔d. When he commu- nica ion ule is pe o med, he objec cinside he agen and he objec dou side he agen swap hei places. Thus, a e he execu ion o he ule, he objec d appea s inside he agen and he objec cis placed ou side he agen . The hi d ule ype, called he mo ion ule, is o he o m ma ix 3×3→mo e di ec ion. Based on he con en s o he neighbou ing cells, an agen can mo e one s ep o he le , igh , up o down. A p og am can con ain maximum one mo ion ule. When he e is a mo ion ule inside a p og am, he e canno be a communica ion ule inside he same p og am. De ini ion 1. The 2D P colony is a cons uc Π= (A, e, En , B1, . . . , Bk, ), k ≥1, whe e •Ais an alphabe o he colony, i s elemen s a e called objec s, •e∈Ais he basic en i onmen al objec o he colony, •En is a pai (m×n, wE), whe e m×n, m, n ∈Nis he size o he en i onmen and wEis he ini ial con en s o en i onmen , i is a ma ix o size m×no mul ise s o objec s o e A− {e}. •Bi,1≤i≤k, a e agen s, each agen is a cons uc Bi= (Oi, Pi,[o, p]) , 0≤o≤m, 0≤p≤n, whe e –Oiis a mul ise o e A, i de e mines he ini ial s a e (con en s) o he agen , |Oi|= 2, –Pi={pi,1, . . . , pi,li}, l ≥1,1≤i≤kis a ini e se o p og ams, whe e each p og am con ains exac ly 2 ules, which a e in one o he ollowing o ms each: ·a→b, called he e olu ion ule, ·c↔d, called he communica ion ule, ·[aq, ]→s, 0≤q, ≤2, s ∈ {⇐,⇒,⇑,⇓}, called he mo ion ule; • ∈Ais he inal objec o he colony. The con igu a ion o he 2D P colony is gi en by he s a e o he en i onmen - ma ix o ype m×nwi h mul ise s o objec s o e A− {e}as i s elemen s, and 54 L. Cienciala, L. Ciencialo ´a, M. Lange by he s a e o all agen s - pai s o objec s om alphabe Aand he coo dina es o he agen s. An ini ial con igu a ion is gi en by he de ini ion o he 2D P colony. The compu a ional s ep consis s o h ee pa s. The i s pa lies in de e min- ing he applicable se o p og ams acco ding o he ac ual con igu a ion o he P colony. The e a e p og ams belonging o all agen s in his se o p og ams. In he second pa we ha e o choose one p og am co esponding o each agen om he se o applicable p og ams. The e is no collision be ween he communica ion ules belonging o di e en p og ams. The hi d pa is he execu ion o he chosen p og ams. A change o he con igu a ion is igge ed by he execu ion o p og ams and i in ol es changing he s a e o he en i onmen , con en s and placemen o he agen s. The compu a ion is nonde e minis ic and maximally pa allel. The compu a ion ends by hal ing when no agen has an applicable p og am. The esul o he compu a ion is he numbe o copies o he inal objec placed in he en i onmen a he end o he compu a ion. Ano he way o de e mine he esul o he compu a ion is o ake in o accoun no only he numbe o objec s bu also hei loca ion. The esul could hen be a g ayscale image, a cha ac e s ing o a numbe ha is dependen on bo h he numbe and pposi ion o he objec s ( o example, g=Pn−1 j=0 Pm−1 i=0 (i, j)· ni, whe e (i, j) is he numbe o copies o objec in he [i, j]-cell). The eason o he in oduc ion o 2D P colonies is no he s udy o hei compu a ional powe bu moni o ing hei beha iou du ing he compu a ion. We can de ine ce ain measu es o assess he dynamics o he compu a ion: • he numbe o mo es o agen s • he numbe o isi ed cells (o no isi ed cells) • he numbe o copies o a ce ain objec in he home cell o h oughou he en- i onmen . These measu es can be obse ed bo h o he indi idual s eps o he compu a ion and he compu a ion as a whole. 4 The issue o he low o liquid o e he su ace The issue o he low o liquid o e he Ea h’s su ace is s udied by expe s om wo a eas - hyd ology and geoin o ma ics. Bo h o hese disciplines wo k closely oge he on he issue o he so-called “su ace uno ”. Su ace uno is he wa e low ha occu s when he soil is in il a ed o ull capaci y and excess wa e om ain, mel wa e , o o he sou ces lows o e he land. Su ace uno can be gene a ed in ou easons: in il a ion excess o e land low, sa u a ion excess o e land low, an eceden soil mois u e, subsu ace e u n low. In il a ion excess o e land low occu s when he a e o ain all on a su - ace exceeds he a e a which wa e can in il a e he g ound, and any dep ession 2D P Colonies 55 s o age has al eady been illed. When he soil is sa u a ed and he dep ession s o - age illed, and ain con inues o all, he ain all will immedia ely p oduce su ace uno - sa u a ion excess o e land low. Soil e ains a deg ee o mois u e a e a ain all. This esidual wa e mois u e (an eceden soil mois u e) a ec s he soil’s in il a ion capaci y. Du ing he nex ain all e en , he in il a ion capaci y will cause he soil o be sa u a ed a a di e en a e. The highe he le el o an eceden soil mois u e, he mo e quickly he soil becomes sa u a ed. Once he soil is sa u- a ed, uno occu s. A e wa e in il a es he soil on an up-slope po ion o a hill, he wa e may low la e ally h ough he soil, and ex il a e ( low ou o he soil) close o a channel. This is called subsu ace e u n low o h ough low. We can say ha gene a ion su ace uno depends on ype o soil, empe a u e, humidi y and ain all. The ask o ou model is o de e mine which way he low would un and which a eas could be a ec ed by lash loods. 5 P oblem solu ion We di ide solu ion o he p oblem in o wo pa s - (1) p epa a ion o maps (2D P colony’s en i onmen ) and (2) de ini ion o agen s. We assume ha he soil is al eady sa u a ed hus he main ac o o o e land low is he slope o he ield. 5.1 P epa a ion o maps Map da a is ob ained om he geog aphic in o ma ion sys em (GIS) and p ocessing sys em A cGIS. We use he map da a o he Czech Republic called he digi al model o he e ain in scale 1: 25 000 (DM´ U25). Ras e g aphics images a e p obably he mos app op ia e o ma o modelling eal-wo ld phenomena in he ield o GIS. To p ocess his o ma , many ools we e c ea ed and can be used o pe o ming a ious analyses. A as e image is composed o a egula ne wo k o cells, usually in a squa e shape, o which alues o displayed p ope ies can be assigned independen ly. Mo e in o ma ion abou GIS and image p ocessing he eade can ind in [3] and abou geosimula ion in [10]. The i s s ep o simula e he low o liquid o e elie was he de e mina ion o i s uno om indi idual pixels (cells). G adien wi h espec o an adjacen cell is de ined as he a io o he heigh di e ence o he ho izon al dis ance. G adien is posi i e due o he lowe neighbou s, o nega i e due o highe and ze o in ela ion o he neighbou s o he same heigh . Lowes neighbou is neighbou wi h he la ges posi i e g adien . Basic classi ica ion algo i hms o calcula e he uno : •Single low di ec ion (SFD) - each pixel o he liquid lows in one di ec ion only ( owa d neighbou in he di ec ion o he la ges g adien ). Each pixel belongs o only one basin. 56 L. Cienciala, L. Ciencialo ´a, M. Lange •Mul iple low di ec ion (MFD) - luid can low ou o each pixel in mul iple di ec ions, maximum o eigh . In he case o MFD a uni olume low is ai ly dis ibu ed among all lowe neighbou s. The MFD may include he pixel o mul iple basins. The e is implemen ed a ool o calcula ing he low di ec ion in A cGIS so - wa e, called simply Flow di ec ion. Flow Di ec ion ool wo ks as a simple low di ec ion (SFD). A e i s execu ion in ege as e ile is c ea ed ha speci ies he low di ec ion o each cell. E e y cell can each alue anging om 1 o 255. Eigh basic di ec ions o he low a e ep esen ed by he numbe s 1,2,4,8,16, 32,64 and 128 (see Table 1). O he di ec ions a e gene a ed as sums o alues o he basic di ec ions. 32 64 128 16 - ↑ % ← → . ↓ & 1 8 4 2 Table 1. The numbe s o eigh basic di ec ions When c ea ing he model, we used he es da a o p opose g oup o p og ams. The inal isualiza ion is based on da a om DM´ U 25. Wha we ob ain om A cGIS is a as e ile wi h na u al numbe in each cell co esponding o he uno om his cell. Because 2D P colony wo ks wi h disc e e symbols and no wi h numbe s, i needed o anscode numbe s o symbols. A coding able is shown on Table 2 di ec ion → ← ↑ ↓ & . % - symbol a E i m q u y 2 Table 2. The coding able The i s p ocessed map is map wi hou d ainless a ea and i s size is 20 ×12 and i is shown on he Table 3. T anscoded symbols a e shown on he Table 4. 5.2 De ini ion o he agen Agen s in 2D P colonies ha e capaci y 2. I ollows ha he agen con ains wo objec s, and each p og am is composed by wo ules. 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 ←↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓& Al i ude (me e s abo e sea le el) 1320 1330 1340 1350 1360 1370 1380 1390 Table 3. P ocessed 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 Table 4. T anscoded symbols Each o he objec s ca ies he in o ma ion abou he s a e o he agen . The i s objec has in o ma ion abou he ac i i y o he agen . A his s age o he simula ion i is he in o ma ion ha he agen “ lows” down he e ain o i is s ill inac i e (belonging o he ain all ha ha e no all). The second ob- jec s o es in o ma ion abou he p e ious di ec ion o low. This in o ma ion can u he modi y he way o he agen as ine ia. Objec s and hei associa ion o he low di ec ions a e gi en in he ollowing able. di ec ion → ← ↑ ↓ & . % - symbol 9 8 6 7 D D U U symbol L K H I I I H H 58 L. Cienciala, L. Ciencialo ´a, M. Lange The ine ia o c ossing di ec ions is modi ied because o longe dis ance be ween he cen es o he cells. The i s subse o p og ams wi h p io i y 0 is de ined o he i s s ep o compu a ion. The ini ial con igu a ion o each “wo king” agen 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 he case o p og ams (5) and (6) ( esp. (7) and (8)) i is neccessa y o ake one s ep down ( esp. up). (9) *  ∗∗∗ ∗∗∗ ∗∗∗ → ⇓;D→I+; (10) *  ∗∗∗ ∗∗∗ ∗∗∗ → ⇑;U→H+; While agen s apply p og ams wi h p io i y 1 (9) and (10), agen s, ha do no mo e in a c oss di ec ion, mus s and. The e o e, hey use a p og am composed o wo ew i ing ules. The p og ams ha e p io i y 2. (11) hX→X; 6 →Hi; (12) hX→X; 7 →Ii; (13) hX→X; 8 →Ki; (14) hX→X; 9 →Li; The ollowing p og ams wi h p io i y 0 a e used o guide he agen in he nex s eps, he agen may hold in o ma ion abou he mo emen in he p e ious s ep. (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 mo e p og am o “ ese ing” ine ia. This is o he case when he slope o he e ain changes ex emely. (47) hX→X;N→ei; I we un he ob ained 2D P colony in he simula o , agen s, which ep esen a uni olume o wa e , will begin o mo e a ound he en i onmen . The numbe o agen s loca ed in one cell a one momen co esponds o he amoun o wa e ha a once lowed h ough he e i o y in one uni o ime.