Lesz közlekedési dugó?
Mielőtt megvizsgáljuk, hogy hogyan lehet sejtautomatával modellezni a forgalmat, nézzük át röviden, hogy mik is a sejtautomaták. Egy végtelen négyzetrács minden négyzetében élhet egy sejt. Egy sejt állapota véges sok értéket vehet fel, a legegyszerűbb esetben \(\{1,0\}\). A sejtek állapota lépésenként változik oly módon, hogy egy adott sejt állapota a következő lépésben önmaga és szomszédai állapotától függ. A szabályt, amely leírja, hogy egy sejt egy adott állapotból milyen állapotba kerül, átmenetfüggvénynek nevezzük.
Az elemi sejtautomata egy mindkét irányban végtelen vonalon (számegyenesen) játszódik. A vonal egyes pozícióit (egész számokat) celláknak nevezzük. Egy cella vagy üres, vagy egy élő sejt található benne. Gyakori ábrázolási mód, hogy az üres cellákat fehér, míg az élő sejtet tartalmazó cellákat fekete négyzetek jelölik, így egy kép rajzolható ki az aktuális állapotból.
A jellemző kezdeti állapot az, hogy csupán néhány élő sejt van. Ezután minden körben kiszámítunk egy új generációt, tehát azoknak a celláknak a helyét, ahol a lépés után élő sejtek lesznek. Három eset lehetséges: egy sejt életben maradhat a következő generációra, elpusztulhat, vagy új sejt születhet egy üres cellában (természetesen üres cella, üresen maradhat). A cella következő pillanatban való lakott vagy lakatlan állapotának megadásához annak bal oldali szomszédjának, saját állapotának és jobb oldali szomszédjának állapotát veszi számításba. Ha egy sejt elpusztul, akkor a cellát üresnek tekintjük.
A sejtek életciklusát és új sejtek születését sejtautomata szabályokkal fogjuk megadni. 256 féle ilyen szabályt vizsgálunk, mind más-más elemi sejtautomatát határoz meg. Az egyes sejt-generációkat jellemzően egymás alá rajzoljuk, így egy ábrán a szimuláció egész folyamatát megtekinthetjük.
A fentiek alapján az egymás fölé rajzolt generációknál egy új négyzet értékét a felette lévő három (balra egy, felette és jobbra egy) cella értéke alapján határozzuk meg. Minden cella két értéket vehet fel, és három cella határozza meg az új generációs négyzet értékét, így összesen \(2^3=8\) féle állapotot definiálunk. Nézzünk egy példát.
A nyolc féle állapot kimeneti értékét tetszőlegesen definiálhatjuk, így összesen \(2^8=256\) szabályrendszert tudunk felállítani az elemi sejtautomaták esetén. (A fenti a \(71=01000111_2\)-es szabály, amely a fehér=0 és fekete=1, kettes számrendszerben felírt számból származik.)
Most már el tudjuk készíteni egy adott sejtautomata állapot következő generációs képét, a hozzá tartozó szabály szerint. A fenti 71-es szabállyal megvizsgálunk egy véletlenszerűen összeállított kezdő állapotot és annak képét. (A széleken szereplő értékeket úgy kell kiszámítani, hogy a másik oldalról egy mezőt hozzáveszünk oldalról, mintha össze lenne ragasztva egy gyűrűvé a sor.) Az alábbi ábrán, például az új generáció \(1.\) elemét úgy kapjuk meg, hogy az előző generáció \(10-1-2\) helyen szereplő értékeit tekintjük eredeti állapotnak. A következőkben gyakran \(1,0\) értékeket fogunk használni a fekete-fehér jelölés helyett, illetve egy-egy sort összesítve kettes számrendszerbeli számként írjuk fel az egyes sejtek állapotának megfelelően.
Tekintsünk egy példát. Az új generáció első elemét, amelyet a második sorban sárgával jelöltünk, a felette lévő sorból a szintén sárgával jelölt sejtek, határozzák meg. A fenti \(71\)-es szabályrendszer \(3.\) eleme alapján fehér lesz az eredmény. Az \(5.\) fekete elemet a bordóval keretezett elemekből tudjuk meghatározni, a szabályrendszer \(6.\) tagja alapján. Rend és káosz
A bevezetőben megismertük az elemi sejtautomaták működési elvét és láthattuk, hogy miért éppen \(256\) szabályrendszert használunk. A 256 szabály négy csoportba osztható, aszerint, hogy tetszőleges kiinduló állapotból hogyan viselkedik több generáció után.
- uniform – lényegében tetszőleges kiinduló állapotból, kevés lépés után homogén végállapotba kerül a rendszer. Minden véletlenszerűség eltűnik.
- oszcilláló – lényegében tetszőleges kezdőállapot, néhány lépés után stabilizálódik, vagy oszcilláló mintává válik. A kezdetei véletlenszerű mintákból némelyek eltűnnek, azonban néhány megmarad. A kezdeti értékek lokális módosítása lokális hatással van a teljes mintázat tekintetében.
- véletlen – lényegében tetszőleges kezdőállapot véletlenszerű vagy kaotikus mintázatot vesz fel. Bármilyen stabil minta hamar eltűnik a környező véletlenszerű “zajban”. A kezdeti értékek lokális módosítása hamar átterjed a teljes mintázatra, korlátok nélkül.
- komplex – lényegében tetszőleges kezdőállapot olyan mintázatot hoz létre, amely komplex módon viselkedik és kerül kapcsolatba a környezetével. A bonyolult struktúrák hosszan fennmaradnak, és esetenként a 2. csoportba tartozó oszcilláló viselkedésbe mennek át. A kezdeti értékek lokális módosítása átterjedhet a teljes mintázatra, korlátok nélkül.
A \(90\)-es szabály a Sierpinski-háromszöget (fraktált) eredményez, ha a kiinduló állapot egy olyan sor, amelynek a közepén egy fekete négyzet szerepel a többi pedig fehér.
A \(184\)-es szabályt az egysávos autópálya modellezésére is használják. Ha egy autó előtt ál egy másik, akkor megáll, ellenkező esetben továbbhalad.
Sejtautomatákkal modellezhetjük a többsávos autópálya forgalmát, olyan esetekben is, ha valamely sáv elfogy, és be kell sorolni az autóknak, különböző szabályok alapján. Ezek feldolgozása meghaladja jelen összefoglaló célját, azonban egy másik egyszerű, látványos modellt nézzünk meg. Egy négyzet vagy téglalap alakú véges négyzethálóra véletlenszerűen felveszünk valamennyi kék és ugyanannyi piros pontot. A piros pontok csak jobbra léphetnek, a kékek pedig csak lefelé, de csak akkor ha a lépés irányába se kék, se piros pont nincs a szomszédjában. Ha nem tud lépni, akkor várakozik mindaddig, amik ki nem ürül előtte a tér. A pontok a forgalomban rész vevő egy-egy autót szimbolizálnak. Az oldalt “kilépő” pontok a másik oldalon belépnek a következő körben, így a struktúra nem változik az eltűnő “autók” miatt. A közlekedési helyzetet egy \(200×200\)-as négyzethálón modelleztük, az autók különböző sűrűsége mellett. A modell meglehetősen egyszerű, egy valóságos helyzethez képest, ennek ellenére érdekes jelenséget figyelhetünk meg. Talán nem okoz meglepetést, hogy kevés autó esetén nincs közlekedési dugó, sok autó esetén pedig gyakori, esetleg teljesen leállhat a forgalom. A modell szerint mindkét esetben további érdekességeket tapasztalhatunk. Kevés autó esetén a piros és kék pontok átlós sávokba rendeződnek, és megfelelő sok lépés után már minden autó megállás nélkül tud mozogni. Sok autó esetében egy idő után olyan torlaszok alakulnak ki, amelyek nem oldódnak fel, és teljesen leáll a forgalom. Ezek az állapotok függetlenek a véletlenszerűen kialakított induló helyzettől. Ezt a modellt Biham-Middleton-Levine közlekedés modellnek nevezzük, megalkotóik után. Az eddigi kutatások csekély támpontot adnak, hogy mennyi legyen a sok vagy a kevés autó a kiinduló állapotban. Az általunk vizsgált sejtautomatábban \(34-36\%\)-os kezdő kitöltöttség esetén fordul a forgalom dinamikája. Megfigyelhetünk azonban egy további érdekességet is. Az előző határok környékén, a mi esetünkben \(35\%\)-nál kialakul egy átmeneti állapot, amikor periodikus mozgás alakul ki. A szabad mozgás mintájára átlós sávokba rendeződnek az autók, de kisebb-nagyobb dugók alakulnak ki. Fontos eleme ennek az állapotnak, hogy a dugók miden esetben maguktól feloldódnak és nem lesz teljes leállás. Az esetek jó részében sok iterációs lépés szükséges, így mozgásban csak egy teljes esetet vizsgálunk meg, a többinél csak a végső állapotot mutatjuk be (az átmeneti állapot esetén \(4000\) iterációs lépésből az utolsó \(500\)-at.
\(31\%\)-os telítettség mellett, \(1000\) iterációs lépés után már látszik a sávokba rendeződés, és a szabad mozgás (egyre ritkulnak az apró dugók).
Állandósult dugó
\(55\%\)-os telítettség esetén, viszonylag hamar, kb. 600 lépés után minden autó dugóba került és megszűnik a mozgás (a szimuláció \(601.\) képkockája).Átmeneti állapot
A legtöbb érdekességet hordozó átmeneti állapotot, esetünkben \(36\%\)-os telítettség mellett figyelhettük meg, amelyhez \(4000\) lépést modelleztünk (az utolsó \(500\) képkocka látható animálva). A Biham-Middleton-Levine modell egyszerű feltételezés alapul, amelyet még úgy is heréz általánosítani és gyakorlati alkalmazását tekinteni, ha egy nagyváros úthálózatán próbáljuk meg értelmezni. A modell alapfeltevései túl egyszerűek ahhoz, hogy gyakorlati problémára megoldást kínáljanak, azaz lesz dugó, ha sok az autó. A sejtautomata szabálya lényegében azt mondja, hogy csak egy lépésre gondolkodik előre, és megáll ha vannak előtte, függetlenül attól, hogy egyébként mennyire akadályozza a többieket. Ez nem csak ahhoz a kellemetlen helyzethez vezet nagy autó sűrűség esetén, hogy megáll a forgalom, hanem ahhoz is, hogy nem is lehet tovább indítani az adott szabályrendszerrel. Érdekes továbbfejlesztése lehet a modellnek, ha a mozgó részecskék több eseményt vesznek számításba, esetleg nagyobb távolságból is vesznek adatot, megtanulnak “udvariasan” viselkedni, vagy elsőbbséget adni. A modell mindenképpen továbbfejleszthető, ha a sejtautomata szabályrendszerébe olyanokat kódolunk, hogy pl. a piros autónak elsőbbsége van vagy ha találkoznak, és mindkettő megáll, akkor valamelyik visszalép egy mezőt, ha az üres, esetleg van mód manőverezésre, és megállás esetén a kijelölt iránytól eltérhetnek, és más irányba folytathatják útjukat, persze ha az szabad.A közlekedést mikroszintű szabályok alapján is megközelítetjük, amelyek szintén modellezhetők sejtautomatákkal. Vegyük példaként egy autópálya forgalmát (ezen nincsenek kereszteződések). Minden sávra egy-egy sejtautomatát vezethetünk be oly módon, ha az úttestet felosztjuk olyan elemi szakaszokra, amely adott szempont szerint elfogadható. A leginkább kézenfekvő, hogy legyen az osztásköz egy autó hossza. Ez valószínűleg nem hagy túl sok mozgásteret, ezért kibővíthetjük oly módon, hogy az osztások legyenek akkorák mint az átlagos követési távolság. Az egyes tartományok értékét az adja, hogy van-e benne autó, vagy nincs. Készítsünk most szabályrendszert a fenti struktúrához. Ha szabad az út valamely autó előtt, akkor nem változtat a sebességén. Ha az előtte haladó lassít, akkor ő is lassít. Lehetőség van olyan szabály megalkotására is, hogy mi történjen a lassítás után, például sávot válthat, ha nem jönnek mögötte a mellette lévő sávban. Ezzel már egy komplex modellt írtunk le, és a sejtautomaták segítségével arra is van mód, hogy közlekedési szituációkat modellezzünk. Lehet baleset, lezárt sáv miatti átsorolás, új sáv megnyílása.
Egy-egy út vagy úthálózat közlekedési sajátosságait figyelembe véve alkothatunk meg olyan szabályokat, amelyek többé kevésbé állandóak és eredményük a gyakorlatba is átültethetők. A Biham-Middleton-Levine modell alapján egy primitív következtetést vonhatunk le: ne engedjünk a forgalomba \(35\%\)-nál több autót, különben végérvényesen dugóba kerülnek. Ebből is látszik, hogy a modell finomítására, komplexebb szabályrendszerre van szükség. Egy körültekintően elemzett közlekedési helyzet, a jól megválasztott (sejtautomata) modellel olyan eredményeket is produkálhat, amely a végeláthatatlan várakozás helyett például az ajánlott sebességről tájékoztatja az autópályán haladókat, annak érdekében, hogy ne alakuljon ki álló kocsioszlop. Ez fontos célja lehet a forgalomszervezésnek, ugyanis az álló kocsioszlop nem csak kellemetlen a benne ülőknek, de az óvatlan vezetők számára balesetveszélyes is.