Prírodou inšpirované algoritmy

2D CA model

Väčšina modelov cestnej premávky je založených na 1D CA. V súčasnosti sa však môžeme stretnúť aj s implementáciou 2D CA na simuláciu dopravy. Tieto modely si nedávajú za cieľ modelovať príliš sofistikované správanie sa. Model ktorý je tu v krátkosti popísaný je jednoduchý model cestnej premávky, ktorý v sebe zahŕňa adaptívnu zmenu cesty. Rovnako ako v modely s jedným jazdným pruhom aj tu každá bunka môže obsahovať vozidlo alebo je neobsadená. Vozidlá majú prepojenú počiatočnú polohu s cieľovou polohou na mriežke a ich snahou je presunúť sa k cieľu. Počet vozidiel je konštantný. Akonáhle nejaké vozidlo dosiahne svoju cieľovú polohu, je vytvorené nové vozidlo s náhodným štartom a cieľom. K aktualizácii dochádza asynchrónne.

Model

Tento model je implementovaný ako 2D CA s štvorcovou mriežkou. Počet vozidiel je určený pevne v každom časovom okamihu. Jedna bunka môže byť obsadená max. jedným vozidlom a v jednom časovom kroku sa vozidlo môže pohnúť do jedného zo 4 smerov. Update CA nastáva asynchrónne - v každom časovom okamihu sa každé vozidlo aktualizuje bez náhrady.

Vytváranie vozidiel, ich deštrukcia a zachovanie

Automobily sú spojené s danými štartovacou a cieľovou bunkou. Vzniknú v počiatočnom bode a cestujú smerom k cieľovému bodu a tam “zomierajú“. Každé “mŕtve“ vozidlo je okamžite nahradené novým vozidlom a tak je vždy zachovaný počet vozidiel.

Štartovacie a cieľové pozície nových vozidiel sú generované náhodne. Cieľom je aby sa páry rovnomerne rozmiestnili po celej ploche. Ak sa už na nejakej pozícii nachádza vozidlo, tak sa vygeneruje nová dvojica bodov.

Pohyb vozidiel a adaptívny výber cesty

Vozidlá sa kedykoľvek je to možné presúvajú do ich cieľa a to tým spôsobom, že sa presunú na pozíciu, ktorá je k ich cieľu čo najbližšie. Dá sa povedať, že vozidlá používajú na presun krátkozraký prístup.

Ak máme voľné vozidlo, preskúmajú sa všetky neblokované okolité pozície. Pre každú z nich je následne vypočítaná vzdialenosť k cieľu toho ktorého vozidla. Pozícia s najmenšou vzdialenosťou od cieľa je potom určená za miesto kam sa vozidlo presunie v ďalšom časovom kroku. V prípade, že sú všetky pozície v okolí blokované, vozidlu musí stáť na mieste. Ako metrika na meranie vzdialenosti je použitá suma absolútnych vzdialenosti x a y.

Jednou z dôsledkov tohto mechanizmu pre výber cesty je, že vozidlo sa bude presúvať vždy ak v okolí existuje voľné miesto, dokonca aj vtedy ak to znamená, že sa od svojho cieľa bude vzdiaľovať ( v krátkodobom ponímaní ).

Existuje množstvo štatistík na ohodnotenie dynamiky a výkonnosti takéhoto dopravného systému, ktoré zahŕňajú aspekt širší - teda pohľad na systém ako taký rovnako nás však zaujíma aj výkonnosť jednotlivých vozidiel. Globálne nás teda v každom časovom kroku zaujímajú nasledujúce parametre:

• priemerná rýchlosť vozidiel
• počet vozidiel, ktoré dorazili do svojho cieľa
• počet blokovaných vozidiel ( tých, ktoré sa nemôžu hýbať )
• veľkosť najväčšieho zhluku vozidiel
• veľkosť najväčšej zápchy ( maximálny počet blokovaných vozidiel na jednom mieste)

Tiež, nás zaujímajú niektoré údaje v rámci väčšieho časového obdobia ako jeden krok, napr. počet zhlukov vozidiel a s tým súvisiace údaje:

• distribúcia veľkostí zhlukov
• pravdepodobnosť, že vozidlo bude v zhluku určitej veľkosti
• distribúcia veľkostí oblastí kde sú dopravné zápchy
• pravdepodobnosť, že vozidlo bude v zápche určitej veľkosti

Zhlukom je v tomto prípade myslená maximálne prepojená skupina vozidiel a zápchou je myslená maximálne prepojená skupina blokovaných vozidiel.

Prepojenosťou sa v tomto prípade myslí, byť priľahlý k niektorému zo štyroch najbližších susedov.

Vždy po ukončení cesty daným vozidlom sa realizujú tieto štatistiky:

• priemerná rýchlosť počas celej cesty
• zlomok minimálnej hodnoty času potrebného na prejdenie cesty zo štartovacej pozície do cieľa vzhľadom na aktuálny stav

Zároveň je ešte možné vypočítať čas spotrebovaný zápchami ( čas počas ktorého je vozidlo blokované ) a relatívny čas spotrebovaný zápchami ( čas spotrebovaný zápchami / čas potrebný na cestu zo štartu do cieľa )

Simulácia tohto modelu bola implementovaná v multi-agentovom systéme SWARM.Bližšie informácie o tomto systéme nájdete napríklad na tejto adrese

Typická konfigurácia vozidiel Šípky označujú smer odkiaľ vozidlo prišlo. Červené body označujú blokované vozidlá.