Prírodou inšpirované algoritmy

CA model s jedným jazdným pruhom

Tento CA model popísali Nagel a Schreckenburg a je určený na popis reálnej cestnej premávky.

Tento model predstavuje jeden jazdný pruh v ktorom sa vozidlá pohybujú jedným smerom.

Na reprezentáciu tohto modelu je postačujúci jednorozmerný CA. Tento sa skladá z n buniek, z ktorých každá môže byť prázdna, alebo môže obsahovať vozidlo. Vo väčšine prípadov sa považuje priestor obsadený jednou bunkou rovný 7,5 m čo približne zodpovedá priestoru potrebnému pre jedno vozidlo aj s potrebným voľným miestom pred a za vozidlom. Vozidlo môže dosahovať rýchlosti od 0 ( vozidlo stojí ), 1 až 6 ( vozidlo sa pohybuje danou rýchlosťou ). Rýchlosť je samozrejme možné premietnuť do reálnych hodnôt a potom napr. rýchlosť v=5 5 znamená, že vozidlo sa pohybuje rýchlosťou 5 buniek za jeden časový krok, alebo 37,5 m/s, alebo 135 km/h, alebo približne 85 míľ za hodinu. CA s týmito hodnotami dosahujú vierohodné výsledky s ohľadom na reálne správanie sa cestnej premávky.

V rámci spomenutej reprezentácie máme teda pole buniek pričom v každej bunke v ktorej sa nachádza vozidlo je uvedená jeho rýchlosť. Ďalšou z dôležitých vecí je zavedenie premennej gap, ktorá popisuje počet neobsadených miest pred vozidlom.

Jedná iterácia pozostáva z aplikácie troch po sebe nasledujúcich pravidiel, aplikovaných paralelne na všetky vozidlá.

Tri základné pravidlá:

• zrýchlenie vozidla ak je to možné IF (v < vmax) THEN v=v+1
• brzdenie vozidla aby nedošlo ku zrážke zozadu IF (v > gap) THEN v = gap
• stochastické správanie IF (v > gap) AND ( rand < pd ) THEN v = v-1

V treťom pravidle je zahrnutá aj pravdepodobnosť pd že vozidlo spomalí aj keď na to nemá žiaden dôvod a náhodná premennou rand. Pravidlá môžu byť modifikované pre jednotlivé vozidlá vzhľadom na ich preferované rýchlosti avšak v najjednoduchšom modeli sa používajú univerzálna max. rýchlosť a pravdepodobnosť spomaľovania pd. Na zmenu stavu v danom časovom okamihu je potrebné najprv určiť rýchlosti všetkých vozidiel, potom nasleduje presun vozidiel s pôvodnej polohy (stavu) do nasledujúcej polohy.

Problémom u takýchto modelov je, že vplyvom nemožnosti obiehania sa vytvárajú skupiny vozidiel ktoré musia nasledovať pomalé vozidlo vpredu. Modelovanie dvoj–rozmerných cestných sieti je možné spájaním týchto jednocestných modelov do väčších celkov. Križovatku je možné simulovať vytvorením kruhovej časti na ktorú nadväzujú ďalšie jazdné pruhy. Kruh je použitý preto, lebo je na ňom možné jednoducho a jasne definovať prioritu vozidiel na križovatke. Vozidlo nachádzajúce sa na kruhovom segmente má najväčšiu prioritu.

Biele a tmavo šedé jazdné pruhy označujú odchádzajúce ulice a svetlo sivou sú označené vstupné jazdné pruhy.

Taktiež môžeme uvažovať o prípade kedy kruhová časť obsahuje len štyri bunky a pripájajú sa na neho štyri vstupne a štyri výstupne jazdné pruhy (viď predchádzajúci obrázok). Rozhodnutie o tom či vozidlo zostane na kruhovej časti alebo križovatku opustí závisí na cieli projektu. Toto rozhodnutie môže prislúchať buď priamo vozidlu (vozidlo vyberá cestu), alebo konkrétnej bunke (rozhodnutie danej bunky ovplyvní vozidlo, ktoré sa na nej nachádza). Existujú teda dve stratégie.

Model 1: V tomto modeli, autá v kruhovej časti sa riadia nejakým všeobecným pravidlom, napr. pohnú sa len ak je bunka pred nimi voľná. Rozhodnutie opustiť križovatku prislúcha bunke a mení sa so zmenou stratégie: náhodný “kočovný“ pohyb je produkovaný v prípade, že je rozhodovacia značka update-ovaná v každom časovom kroku. Zmenou tejto rozhodovacej značky v pravidelných časových intervaloch získame situácia podobnú križovatke so svetelnou signalizáciou.

Model 2: V tomto modeli, je rozhodovanie priradené jednotlivým vozidlám akonáhle vstúpia na križovatku. Problém nastane ak sa všetky vozidlá rozhodnú v jednom okamihu, že križovatku opustia niektorým z východov. V tom prípade môžeme hovoriť o mŕtvom bode: všetci štyria vstúpia do križovatky naraz ( sever, juh, západ, východ ) a všetci sa chcú pohnúť na ploche križovatky, avšak neurobí to ani jeden pretože všetky pozície sú obsadené. Aby sa tomuto problému predišlo je v tomto modeli použité špeciálne pravidlo pre pohyb na križovatke – vozidlá na území križovatky sa musia stále pohybovať (čiže otáčať sa, alebo opustiť križovatku ).

Takýmto spôsobom teda môžeme simulovať dopravnú situáciu v mestách, na diaľnicach, apod.