Simulace aut ve městě

MASARYKOVA UNIVERZITA FAKULTA INFORMATIKY

Simulace aut ve městě BAKALÁŘSKÁ PRÁCE

Tomáš Chládek

Brno, podzim 2009

Prohlášení Prohlašuji, že tato bakalářská práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.

Vedoucí práce: RNDr. Vít Kovalčík, Ph.D.

II

Poděkování Děkuji vedoucímu práce za cenné rady a úpravu generátoru města ACG. Za poskytnutí modelů aut děkuji vedoucímu práce a Mgr. Tomášovi Pelikánovi. Dále bych chtěl poděkovat rodičům za jejich podporu při studiu.

III

Shrnutí První kapitola se zabývá základními rysy simulace a vlastnostmi podobných již existujících aplikací. V další kapitole popisuji hlavní komponenty systému VRECKO, které jsou použity v mém programu. Potom rozebírám jeho rozdělení na tři hlavní části. Čtvrtá kapitola zachycuje parametry silniční sítě a její převod do vhodnější podoby pro simulaci. V páté kapitole popisuji základní parametry aut a typy jejich cest. V další části rozebírám především zatáčení auta, povolení vjezdu do křižovatky a komplikovanější dopravní situace. Řízení auta vzhledem k jeho okolí popisuje sedmá kapitola. V předposledním oddíle uvádím, jakým způsobem probíhá vlastní pohyb aut. V závěru hodnotím dosažené výsledky a zabývám se možnými rozšířeními práce.

IV

Klíčová slova simulace aut, řízení aut, generování aut, VRECKO, doprava, silnice, křižovatka, graf silnic, ACG

V

Obsah 1. Úvod ......................................................................................................................................... 1 2. Systém VRECKO..................................................................................................................... 2 3. Rozvržení aplikace ................................................................................................................... 3 4. Silniční síť ................................................................................................................................ 5 4.1 Vstupní parametry silniční sítě ........................................................................................ 5 4.2 Úpravy silnic.................................................................................................................... 5 4.2.1 Typy hran a jejich atributy .................................................................................... 5 4.2.2 Typy křižovatek .................................................................................................... 8 4.2.3 Graf silnic ............................................................................................................. 9 4.2.4 Terminátor ............................................................................................................ 9 4.2.5 Slučování blízkých původních křižovatek do malých křižovatek ...................... 11 5. Auto ........................................................................................................................................ 13 5.1 Vytvoření cesty .............................................................................................................. 13 5.1.1 Nejkratší cesta ..................................................................................................... 13 5.1.2 Náhodná cesta ..................................................................................................... 14 6. Podíl RoadsState na řízení aut................................................................................................ 15 6.1 Modelování průjezdu auta malou křižovatkou .............................................................. 15 6.2 Řízení provozu na velké křižovatce ............................................................................... 18 6.2.1 Zamykání hran .................................................................................................... 18 6.2.2 Uváznutí.............................................................................................................. 19 6.2.3 Pravidlo pravé ruky............................................................................................. 20 6.2.4 Podmínky pro povolení průjezdu velkou křižovatkou ........................................ 20 6.2.5 Řešení konkrétních komplikovaných situací ...................................................... 21 6.3 Okolí auta na rovném úseku .......................................................................................... 22 7. CarControlUnit....................................................................................................................... 24 7.1 Zrychlování a brždění .................................................................................................... 24 7.2 Řízení směrových světel ................................................................................................ 25 7.3 Odstavení auta ............................................................................................................... 25 8. CarExecutionUnit................................................................................................................... 26 8.1 Proměnné parametry auta .............................................................................................. 26 8.2 Ovládací signály ............................................................................................................ 26 8.3 Aktualizace stavu auta ................................................................................................... 27 8.4 Rozměry auta ................................................................................................................. 27 9. Závěr ...................................................................................................................................... 28 Literatura .................................................................................................................................... 30 Příloha A: Obsah CD ................................................................................................................. 32 Příloha B: Parametry ability RoadsState v konfiguračním XML souboru ................................. 33 Příloha C: Zadávání jednotlivých aut ......................................................................................... 36 Příloha D: Výkonnostní testy ..................................................................................................... 40 Příloha E: Snímky ze simulace................................................................................................... 42

VI

1. Úvod Počítačová simulace prošla v posledních letech značným vývojem. Hojně se používá při trénování pilotů letadel, řidičů aut v autoškole, obchodníků v podnikání nebo vojáků před jejich misí. Má rozsáhlé využití i v medicíně. Lékaři se mohou například učit, jak provádět laparoskopii v umělém prostředí. Díky ní se mohou zjišťovat vlastnosti systémů bez jejich přímé komplikované realizace. Astrofyzikové tak mohou simulovat vznik galaxií i samotného vesmíru nebo si ověřit, zda se jeho rozpínání zrychluje. Simulace tak dovoluje snižovat náklady a zvyšovat bezpečnost. Velké uplatnění nachází také v počítačových hrách. Například Second life [1] simuluje skutečný život. Umožňuje lidem virtuálně pracovat a zároveň se bavit. Hry mají ale i své negativní stránky. Mohou podněcovat násilné chování a vyvolávat závislost. Ve své práci se zabývám simulací aut ve městě. Pár podobných projektů již vzniklo. Z těch komerčních mohu jmenovat například VISSIM [2], z volně dostupných je to pak SUMO [3], které je ale pouze ve 2D a nepočítá se u něj s předjížděním nebo nastavováním chování řidiče. Simulace mohou být rozlišeny na několik druhů podle jejich modelu dopravního toku, viz např. [4]. U makroskopických modelů je základní entitou dopravní tok. Nezajímají nás jednotlivá auta, ale shluky (proudy) vozidel. Mikroskopické modely berou v potaz chování řidiče a základní vlastnosti auta – zrychlení, zpomalení, nejvyšší a nejnižší možnou rychlost, rozměry a podobně. Submikroskopické modely navíc rozdělují vozidla na velké množství částí, u nichž jsou zadané další parametry auta. Jedná se například o rychlost otáčení motoru, způsob řazení řidiče, umístění přítlačného křídla, pružnost tlumičů, sklon světel, rozchod kol, typ pneumatik nebo vzdálenost mezi karoserií a vozovkou. Tyto modely jsou detailnější a simulace se tak více blíží skutečnosti. Na druhou stranu jsou výpočetně náročnější. Tím pádem je omezen maximální počet aut, která lze do simulace vložit při zachování její plynulosti. Větší výpočetní složitost může mít za důsledek také menší plochu, na které se vozidla pohybují. Simulace vypracovaná v rámci této práce má mikroskopický model dopravního toku. Program je napsán v jazyce C++ jako zásuvný modul do systému VRECKO [5], který je vyvíjen v Laboratoři interakce člověka s počítačem FI MU. Je primárně určený pro síť silnic, kterou vytváří generátor města ACG [6]. Lze ji však zadávat také ručně. Parametry aut a silnic jsou nastaveny přes XML [7]. Vozidla mohou být zadaná uživatelem samostatně nebo je lze nechat vygenerovat. Auto je po dojetí do cíle odstraněno ze simulace, aby nebránilo ostatním vozidlům v průjezdu. Systém podporuje rovné obousměrné a jednosměrné silnice s jedním pruhem v každém směru. Provoz na křižovatkách je řízen pravidlem pravé ruky. Auto se na křižovatce může otočit do protisměru. Celá aplikace je rozdělena na tři hlavní části: • řídící jednotku auta, která dostává informace o jeho okolí od jednotky stavu silnic a která na jejich základě dává rozkazy výkonné jednotce auta • výkonnou jednotku auta, jež vykonává vlastní pohyb • jednotku stavu silnic, která si pamatuje jejich geometrii a základní informace o autech Aplikaci lze využít v počítačových hrách, simulaci života ve městě nebo při hledání úzkých míst v síti silnic. Může také sloužit jako demonstrace systému VRECKO.

1

2. Systém VRECKO Systém VRECKO je určen k vytváření virtuálních světů. Je rozvržen do modulů, což umožňuje jeho snadnější rozšiřování. Hlavní komponentou virtuálního prostředí je World. Skládá se z těchto částí: Scene (obsahuje objekty umístěné ve scéně), DeviceManager (správce zařízení), EventDispatcher (zajišťuje komunikaci mezi částmi systému) a Scheduler (plánuje aktualizování entit). Entita EnvironmentObject reprezentuje objekt ve scéně. Jsou v ní uloženy jeho geometrický model, materiál, transformace (posunutí a natočení ve scéně), kolizní hierarchie a data uživatele. Chování takového objektu může být řízeno pomocí entity Ability, která má přímý přístup k jeho datům. V dalším textu používám termín abilita místo překladu „schopnost“ (nebo „vlastnost“). Abilita se nemusí nacházet pod nějakým objektem ve scéně, ale přímo pod ní. Všechny entity mají jednoduché rozhraní, které jim dovoluje dorozumívat se přes vstupní a výstupní porty. Hlavní typy komunikace jsou dva – událost (event) a žádost (request). Událost spouští na entitě s uvedeným vstupním portem metodu processEvent s požadovaným parametrem. Žádost se pak liší tím, že vyvolá metodu processRequest (opět s parametrem), která vrací ukazatel na void. Komunikace může probíhat přímo mezi dvěma entitami nebo přes prostředníka – EventDispatcher. Systém VRECKO nastavuje scénu a vstupní zařízení podle konfiguračních XML souborů, které jsou zadány na příkazové řádce programu. K vykreslování a členění virtuální scény do grafu využívá knihovnu OpenSceneGraph [8]. Je napsána v C++ a používá nízkoúrovňovou knihovnu OpenGL [9], takže je přenositelná na různé platformy (včetně MS Windows a Linux). Je poskytována s otevřeným zdrojovým kódem. Pro práci s daty ve formátu XML používá VRECKO knihovnu Xerces vyvíjenou firmou Apache Software Foundation [10]. Je opět volně dostupná. Pro více informací o systému VRECKO viz [5].

2

3. Rozvržení aplikace Program je rozdělen na tři hlavní ability – jednotku stavu silnic (RoadsState), řídící jednotku auta (CarControlUnit) a výkonnou jednotku auta (CarExecutionUnit). RoadsState je umístěna přímo pod scénou. Další ability jsou součástí auta ve scéně (entity EnvironmentObject), ve kterém jsou také uloženy geometrické modely částí vozidla. RoadsState si pamatuje rozmístění silnic a základní údaje o autech. Dostává dotazy na okolí vozidla od jeho řídící jednotky. Ta poskytnuté údaje vyhodnocuje a na jejich základě vysílá výkonné jednotce signály k zatočení kol, brždění a podobně. CarExecutionUnit také počítá změnu pozice a natočení vozidla v závislosti na jeho parametrech. Izolace výkonné jednotky umožňuje její snadnější modifikaci, takže se může později upravit, aby se auta více pohybovala podle fyzikálních zákonů. Oddělení CarControlUnit od RoadsState zase dovoluje implementaci různých typů chování vozidel (agresivní, normální, zpomalené). Tyto ability se mi však nepodařilo zcela separovat. RoadsState nevrací jednotce CarControlUnit pouze informace o okolí auta, ale také za ni v některých věcech rozhoduje o dalším pohybu vozidla. Například zjišťuje, zda má auto na křižovatce přednost, určuje optimální rychlost průjezdu křižovatkou a počítá, jaký by měl být úhel natočení kol v křižovatce. Řídící jednotka tak jakoby zasahuje do RoadsState. Toto řešení má ale i své výhody. Komunikace mezi těmito abilitami je jednodušší. RoadsState nemusí abilitě CarControlUnit předávat tolik informací o okolí auta (například že k další křižovatce přijíždí zprava vozidlo rychlostí 30 km ⋅ h -1 a je od ní vzdálené 50 m). Ze vstupního konfiguračního XML souboru se pro simulaci načítají zejména parametry: • ručně zadaných aut • generovaných aut • silniční sítě Životní cyklus programu lze rozdělit na dvě fáze: inicializační část a aktualizaci řídící jednotky auta. Inicializační část se skládá především z těchto akcí: • RoadsState načte silniční síť a převede ji do vhodné podoby pro simulaci • RoadsState vygeneruje vozidla (pokud si uživatel nějaká přeje vygenerovat) • vytvoří se ručně zadaná auta Aktualizace CarControlUnit (výpočet snímku vozidla) má přibližně tento průběh: • zjistí se čas uplynulý od posledního snímku, vyšle se pokyn k aktualizaci stavu auta abilitě CarExecutionUnit (která potom ve scéně pohne s vozidlem) • jednotka CarControlUnit se táže ability RoadsState, jak vypadá okolí auta (jako hlavní parametry jí předá dosavadní umístění vozidla a pozici jeho cíle)

3

•

•

CarControlUnit přijme odpověď (skládá se zejména z těchto parametrů: nové umístění auta, zda může vjet do křižovatky, optimální natočení kol v křižovatce, vzdálenost a rychlost dalšího vozidla) řídící jednotka rozhodne, zda by auto mělo natočit kola, zrychlovat nebo brzdit, a vyšle abilitě CarExecutionUnit signály k realizaci těchto úkonů

4

4. Silniční síť 4.1 Vstupní parametry silniční sítě Každá silnice zadaná ve vstupním XML souboru se skládá ze dvou křižovatek a čtyř krajních bodů. U všech těchto šesti prvků jsou zadané souřadnice. U křižovatek se nazývají středy křižovatek. Křižovatku, ze které silnice vychází, označuji fromJunction. Křižovatku, do které silnice směřuje, nazývám toJunction. K pochopení dalšího textu je třeba definovat strany silnice. Pravá strana je při pohledu shora vpravo od orientované úsečky dané středy křižovatek fromJunction a toJunction. Levá strana je pak vlevo od této úsečky. Body, které na ní leží, jsou na levé i na pravé straně. Krajní body silnice se rozlišují podle jejich umístění: • fromPointRight – krajní bod u křižovatky fromJunction na pravé straně silnice • toPointLeft – krajní bod u křižovatky toJunction na levé straně silnice • fromPointLeft – krajní bod u křižovatky fromJunction na levé straně silnice • toPointRight – krajní bod u křižovatky toJunction na pravé straně silnice Uvedené termíny ilustruje obrázek:

Obrázek: 4.1: Prvky silnice. U silnic je navíc na obou stranách zadán počet pruhů. Jestliže strana nemá žádné pruhy, je nesjízdná. Pokud jedna ze stran silnice nemá žádné pruhy, je tato silnice jednosměrná. Podrobněji popisuje parametry silnic ze vstupního souboru Příloha B.

4.2 Úpravy silnic Silniční síť se po načtení z XML souboru převádí do vhodnější podoby pro simulaci. Tyto úpravy jsou popsány v následujících podkapitolách.

4.2.1 Typy hran a jejich atributy Silnice se dělí vždy na dvě hrany (na její levou a pravou stranu). Pravá má kladný, levá záporný směr. Hrany mají své identifikátory (ID). Mohou obsahovat nula až pět pruhů.

5

Aplikace ovšem podporuje pouze žádný nebo jeden pruh. Při větším počtu pruhů se aplikace chová, jako kdyby hrana obsahovala pouze jeden pruh. Hrany mají celkem šest disjunktních typů. Jsou většinou normální. Výjimky tvoří tyto případy: • velmi krátká hrana – má alespoň jeden pruh a splňuje nejméně jednu z následujících podmínek: o je tak krátká, že by nepůsobilo přirozeně, kdyby auto nějakou její částí projíždělo rovně (viz obrázek 4.2) o pro komplementární hranu (na druhé straně silnice) platí předchozí podmínka • velmi krátká hrana bez pruhů • krátká hrana – hrana se považuje za krátkou, pokud není velmi krátká, má nejméně jeden pruh a splňuje alespoň jedno z tvrzení: o teoreticky existuje auto, které na ní nemůže zastavit, aniž by ohrozilo provoz na křižovatce před ním nebo za ním (viz obrázek 4.2) o hrana má komplementární krátkou hranu • normální nebo krátká hrana bez pruhů • terminátor – program ACG vynechává silnice na kraji města při vytváření jejich XML reprezentace; kolem středů některých křižovatek tak vznikají prázdná místa, která jsou zaplněna terminátory Krátkými hranami projíždějí auta vždy bez zastavování. Na velmi krátkých hranách vozidla vždy zatáčejí. Typy hran popisuje obrázek:

Obrázek 4.2: Typy hran.

6

Hlavní atributy hrany jsou: • fromJunction – křižovatka, ze které hrana vychází • toJunction – křižovatka, do které hrana vstupuje • fromPointRight – krajní bod u křižovatky fromJunction • toPointRight – krajní bod u křižovatky toJunction • length – délka hrany • In (pouze pro normální a krátké hrany) – bod, kde auto vstupuje do křižovatky a kde začíná zatáčet • Out (pouze pro normální a krátké hrany) – bod, ve kterém auto přestává zatáčet a ve kterém vyjíždí ze křižovatky • normal – normála hrany • stopBeforeJunc (pouze pro normální hrany) – bod mezi body Out a In, kde auto zastaví svým předním nárazníkem, jestliže se rozhodne zastavit před další křižovatkou • stopOrGoDecision (pouze pro normální hrany) – bod mezi body Out a In; když jej auto přejede svým předním nárazníkem, rozhodne se, jestli projede další křižovatkou hned, nebo bude brzdit k bodu stopBeforeJunc (aby dalo nějakému autu přednost) • widthTPR (pouze pro normální a krátké hrany) – šířka hrany u bodu toPointRight • widthFPR (pouze pro normální a krátké hrany) – šířka hrany u bodu fromPointRight Délka hrany je vzdálenost mezi aritmetickým průměrem středu křižovatky fromJunction a krajního bodu fromPointRight (dále ho budu pro jednoduchost nazývat fromMidPoint) a aritmetickým průměrem středu křižovatky toJunction a krajního bodu toPointRight (toMidPoint). Uvedené atributy ilustruje obrázek:

Obrázek 4.3: Atributy normální hrany. Bod In je vzdálenost mezi bodem toMidPoint a středem křižovatky toJunction od bodu

toMidPoint ve směru vektoru toMidPoint − fromMidPoint . Bod Out se nachází ve směru vektoru fromMidPoint − toMidPoint vzdálen od bodu fromMidPoint na délku mezi bodem fromMidPoint

a středem křižovatky fromJunction.

Oblast za nějakým bodem hrany je poloprostor daný tím bodem a vektorem Out − In . Obdobně oblast před bodem hrany je poloprostor daný tím bodem a vektorem In − Out . PDA označuje průměrnou délku auta, má 5 m. Bod stopOrGoDecision se nachází 2PDA před bodem In, pozice stopBeforeJunc je 0,5PDA před bodem In.

7

Na normálních a krátkých hranách jezdí auta rovně vždy z bodu Out do In. Prostor mezi těmito body označuji jako rovný úsek. Na rovném úseku normální hrany je pro vozidla zaznamenána rychlost a vzdálenost dalšího auta. Na tomto úseku by měla být vzdálenost mezi stojícím autem a bodem In nebo Out vždy alespoň 0,5PDA, aby nebyl ohrožen provoz na křižovatce před ním nebo za ním. Pokud je widthFPR či widthTPR menší než 1,05 · maximální šířka auta, nastaví se u hrany nulový počet pruhů. Maximální šířka auta je 3 m.

4.2.2 Typy křižovatek Rozlišuji celkem tři druhy křižovatek, které nejsou disjunktní (některé křižovatky mohou mít více druhů). Prvním typem jsou křižovatky původní (nebo také základní), které se načítají ze vstupního souboru. Některé z nich jsou u sebe tak blízko, že není vhodné je brát v úvahu samostatně. Proto se základní křižovatky, mezi kterými jsou velmi krátké hrany, slučují do malých křižovatek. Původní křižovatku, která není spojena s jinými do malé křižovatky, označuji také jako malou. Malé a původní křižovatky mají své identifikátory (ID). Pokud není řečeno jinak, mám dále v textu pod termínem křižovatka (bez přídavného jména) na mysli malou křižovatku. Do křižovatky auto vstupuje a začíná zatáčet u bodu In vstupní hrany. Vystupuje z ní a přestává měnit směr u bodu Out výstupní hrany. Prostor křižovatky je tedy vymezen body In a Out. Vozidla mění svůj směr pouze v křižovatkách a pro jednoduchost v nich nezastavují. U malých a původních křižovatek jsou zaznamenány identifikátory okolních hran s odkazy na následující a předcházející hrany (ve smyslu proti směru hodinových ručiček). Ty umožňují snadnější určení hrany, na které se auto nachází při průjezdu křižovatkou. Oblast křižovatky je vyznačena na obrázku:

Obrázek 4.4: Malá křižovatka.

8

Posledním typem křižovatek jsou velké křižovatky. Označují křižovatky propojené krátkými hranami. Křižovatka, která kolem sebe nemá žádnou krátkou hranu, je velká. Na rozdíl od předchozího druhu se velké křižovatky před vlastní simulací nijak nevypočítávají. Auta velkou křižovatku projíždí najednou, protože nezastavují na krátkých hranách a na křižovatkách. Touto křižovatkou může vozidlo projet, pokud dostane přednost od ostatních aut, která se do ní také chystají vjet a která mu kříží cestu. Příklad velké křižovatky je znázorněn na obrázku:

Obrázek 4.5: Velká křižovatka.

4.2.3 Graf silnic Z načtených silnic se vytváří ohodnocený orientovaný graf roads. Je implementován pomocí seznamu sousedů (adjacency-list representation). Protože je orientovaný, budu pro lepší srozumitelnost místo termínu soused používat termín následník. Pro podrobnější informace o této reprezentaci viz [11]. Uzly jsou identifikátory křižovatek. Hodnota hrany mezi dvěma uzly (křižovatkami) není vzdálenost mezi nimi, ale ID hrany, která je spojuje. Graf neobsahuje všechny, ale pouze normální a krátké hrany. Umožňuje rychlejší vyhledávání cesty pro vozidlo a jednodušší orientaci v cestě auta.

4.2.4 Terminátor Program ACG vynechává silnice na kraji města při jejich převodu do XML. Proto se u některých původních křižovatek objevují „zuby“ (prázdná místa). Aby se auto při průjezdu kolem středu křižovatky neocitlo mimo všechny hrany, vkládá se do těchto míst terminátor.

9

Příklad terminátoru u základní křižovatky se středem C je uveden na obrázku:

Obrázek 4.6: Terminátor. Prázdné místo je určeno páry samostatných krajních bodů (samostatných ve smyslu jejich výskytu u hran původní křižovatky), které jsou vedle sebe. První (fstSinglePolyPoint) se nachází vždy na vstupní hraně (fstInEdge). Druhý (sndSinglePolyPoint) přísluší vždy k výstupní hraně (sndOutEdge). Algoritmus nalezení prázdného místa u základní křižovatky má zhruba tento průběh: • procházejí se postupně všechny hrany křižovatky od vstupní po předcházející výstupní • jestliže se právě prošla výstupní hrana a krajní bod fromPointRight této hrany není shodný s krajním bodem toPointRight předchozí vstupní hrany, je nalezeno vykrojené místo Po svém objevení se prázdné místo zaplňuje terminátorem – dvěma hranami (fstTermEdge, sndTermEdge), jejichž body znázorňuje obrázek:

Obrázek 4.7: Atributy terminátoru. r r Nový červený bod newPoint je určen jako C + v . Vektor v se získá otočením vektoru C − fstSinglePolyPoint o poloviční úhel mezi tímto vektorem a vektorem C − sndSinglePolyPoint .

r Otáčí se kolem osy, která je průměrem normál hran fstInEdge a sndOutEdge. Nakonec se v normalizuje a vynásobí se aritmetickým průměrem vzdáleností mezi C a samostatnými krajními body.

10

Po svém vytvoření se nové hrany začlení u základní křižovatky mezi hrany fstInEdge a sndOutEdge. Terminátor nemusí vždy vypadat jako na obrázcích výše. Může být také nekonvexní:

Obrázek 4.8: Nekonvexní terminátor.

4.2.5 Slučování blízkých původních křižovatek do malých křižovatek Křižovatky se skládají z jedné nebo více původních křižovatek, jež jsou propojené velmi krátkými hranami. Proces slučování základních křižovatek popisuje pseudokód: • pro každou velmi krátkou hranu e o nechť je from ID křižovatky, do které se zatím sloučila základní křižovatka fromJunction hrany e (pokud se nesloučila, je to ID té křižovatky samotné) o nechť je to ID křižovatky, do které se zatím sloučila základní křižovatka toJunction hrany e (pokud se nesloučila, je to ID té křižovatky samotné) o vytvoří se nová křižovatka o její střed je váženým průměrem středů křižovatek from a to (váhami jsou počty původních křižovatek, které obsahují) o nechť je f komplementární hrana ke hraně e (na opačné straně silnice) o k nové křižovatce se přidají hrany od křižovatky to o přidají se k ní také hrany od křižovatky from ale bez hran e a f o předchozí hrana hrany e u nové křižovatky se nastaví na předchozí hranu hrany e u křižovatky from o následující hrana hrany f u nové křižovatky je následující hranou hrany f u křižovatky from o roads se změní tak, aby:
hrany, které směřovaly do křižovatky from nebo to, vedly do nové křižovatky
hrany, které směřovaly z křižovatky from nebo to, vedly z nové křižovatky o u původních křižovatek, ze kterých se skládají křižovatky from a to, se nastaví ID křižovatky, jejíž jsou součástí, na ID nové křižovatky o nová křižovatka se skládá z tolika základních křižovatek, z kolika se skládají křižovatky from a to dohromady o jestliže křižovatka from nebo to není původní, odstraní se

11

o

jestliže je hrana f velmi krátká, nebude se již procházet jako hrana e

Změny odkazů na předcházející a následující hrany při slučování křižovatek from a to jsou znázorněny na obrázku:

Obrázek 4.9: Změny odkazů na následující a předcházející hrany při slučování křižovatek.

12

5. Auto Každé auto má své parametry – zejména počáteční a konečnou pozici (start, cíl) a rozměry. Počáteční pozice se nachází na počáteční a konečná na konečné normální hraně. Vozidla mohou být nastavována buď ručně, nebo je lze nechat vygenerovat. V prvním případě se parametry zadávají u každého auta zvlášť (viz Příloha C), ve druhém se vytvářejí automaticky pomocí generátoru náhodných čísel (viz Příloha B). Všechna auta se do simulace vkládají na jejím začátku (nelze je tedy vkládat až v jejím průběhu). Generovaná vozidla jsou vytvořena před ručně zadanými auty.

5.1 Vytvoření cesty Cestu vozidla v programu představuje posloupnost křižovatek:

Obrázek 5.1: Cesta auta. U ručně zadaných aut se nachází vždy nejkratší cesta ze startu do cíle. Cesty generovaných vozidel mohou být také nejkratší. U nich lze ovšem navíc vytvořit náhodné cesty, které nemusejí být vždy nejkratší. V tomto případě se určuje konečná pozice až po nalezení cesty. Proto tento typ cesty není vhodný pro ručně zadaná auta, u kterých se vytváří cesta až po určení startu a cíle uživatelem.

5.1.1 Nejkratší cesta Nejkratší cestu z počáteční pozice do konečné pozice vozidla nalézá Dijkstrův algoritmus [12], který je upraven v těchto bodech: • do grafu silnic (roads) jsou přidány dva nové uzly pro start a cíl (z prvního vede hrana do následující křižovatky; do druhého pak vede hrana z křižovatky před konečnou pozicí) • hrany mezi uzly (křižovatkami) jsou ohodnoceny jejich délkami (jejich hodnotami tedy nejsou jejich identifikátory, jak by se mohlo zdát z grafu roads) • cyklus končí, když je určena nejkratší cesta ze startu do cíle (tj. když je uzel pro cíl vložen do množiny S, která obsahuje uzly, do nichž již jsou z uzlu pro start nalezeny nejkratší cesty), nebo když nemůže být nalezen další uzel, který by se mohl vložit do množiny S (cesta z počáteční do konečné pozice neexistuje)

( )

Složitost tohoto algoritmu je Θ n 2 , kde n znázorňuje počet všech křižovatek v grafu silnic.

13

5.1.2 Náhodná cesta Náhodná cesta vzniká z počáteční hrany. Má náhodnou délku, která je v tomto kontextu udána počtem hran mezi jejími křižovatkami. Maximálně ovšem může obsahovat 30 hran. Algoritmus pro její nalezení má tento průběh: • určí se délka cesty • do prázdné cesty je vložena křižovatka na začátku a na konci počáteční hrany • další křižovatky se postupně vybírají náhodně z následníků poslední křižovatky umístěné na konec cesty, dokud nemá potřebnou délku nebo počet těchto následníků není nulový; aby se auta co nejméně otáčela do protisměru, výběr se dále omezuje: o pokud počet zmíněných následníků je větší než jedna a patří k nim předposlední křižovatka v cestě, je zvolena jakákoliv jiná křižovatka než předposlední • pokud je poslední hrana v cestě krátká, ubírají se z ní křižovatky, dokud mezi jejími posledními dvěma křižovatkami není normální hrana Složitost tohoto algoritmu je Θ (n ) , kde n představuje počet křižovatek v cestě vozidla. Tento typ cesty je tedy vhodnější pro větší počet generovaných aut než předchozí typ.

14

6. Podíl RoadsState na řízení aut 6.1 Modelování průjezdu auta malou křižovatkou Průjezd auta křižovatkou v rovině xz (z bodu In vstupní do bodu Out výstupní hrany) je modelován Hermitovskými kubikami [13]. Pro jejich popis je třeba definovat další parametry: Nechť C je střed křižovatky. Úhel α představuje úhel otočení vektoru C − In (v xz) do vektoru C − Out (v xz) podle osy y. Jestliže je α nejvýše (2/3)π, zatáčí auto v křižovatce podle jedné kubiky. V opačném případě dráhu průjezdu tvoří dvě kubiky, jež odděluje bod předělu –

borderPoint. Ten je určen jako C + vec ⋅ r (v xz). Vektor vec vzniká otočením C − In (v xz) o α/2 podle osy y a následným převodem na jednotkový vektor. Konstanta r je aritmetický průměr polovin šířek vstupní a výstupní hrany. Vektor předělu borderVec se získá otočením vec o π/2 podle osy y. Pro větší rychlost vlastní simulace (po jejím načtení) se bod předělu a jeho vektor vypočítávají už v inicializační části. Hermitovská kubika je dána počátečním bodem P1, koncovým bodem P4, počátečním tečným vektorem R1 a koncovým tečným vektorem R4. V případě modelování průjezdu pouze podle jedné kubiky mají tento význam: • P1 – bod In • P4 – bod Out •

R1 – vektor vstupní hrany (vektor hrany je v tomto kontextu vektor Out − In )

•

R4 – vektor výstupní hrany

Obrázek 6.1: Průjezd auta křižovatkou podle jedné kubiky.

15

Pokud se dráha průjezdu skládá ze dvou kubik, parametry první z nich jsou nastaveny takto: • P1 – bod In • P4 – bod borderPoint • R1 – vektor vstupní hrany • R4 – vektor borderVec Parametry u druhé kubiky mají tento význam: • P1 – bod borderPoint • P4 – bod Out • R1 – vektor borderVec • R4 – vektor výstupní hrany Uvedené kubiky jsou znázorněny na obrázku:

Obrázek 6.2: Průjezd auta křižovatkou podle dvou kubik. Souřadnice y parametrů kubik P1, P4, R1 a R4 se na závěr vždy nastavují na 0. R1 a R4 jsou navíc ještě převedeny na jednotkový vektor a vynásobeny vzdáleností P1P4 a konstantou 1,5 (testováním se zjistilo, že tak mají kubiky nejhladší a nejpřirozenější průběh).

16

Parametrické vyjádření Hermitovské kubiky je (převzato z [13]):

(

Q (t ) = t 3 t 2

1   P1   2 −2 1     − 3 3 − 2 − 1  P4  t 1 , t ∈ [0,1] 0 0 1 0   R1      1 0 0 0   R4  

)

Její derivaci lze pak snadno odvodit:

(

Q' (t ) = 3t 2

1   P1   2 −2 1     − 3 3 − 2 − 1  P4  2t 1 0  , t ∈ [0,1] 0 0 1 0   R1      1 0 0 0   R4  

)

Jestliže se nachází auto uvnitř křižovatky, posílá abilita RoadsState úhel natočení kol δ jednotce CarControlUnit. Je vypočítán jako cβ, kde β je úhel mezi směrem auta a Q’(t), přičemž parametr t je přibližně určen jako BP1 / P1P4 , B představuje střed podstavy kvádru, který obklopuje auto (vždy v xz). Q’(t) určuje směr (v xz), jaký by vozidlo mělo mít v příštím snímku. Převodní koeficient c závisí na ujeté vzdálenosti v příštím snímku. Jelikož není ještě známa, aproximuje se jako ujetá vzdálenost v posledním snímku auta – s. Čím menší je tato vzdálenost, tím musí být výsledný úhel natočení kol δ větší, jelikož má pak auto menší manévrovací prostor. Koeficient c je tedy 3,0/s (konstanta 3,0 byla experimentálně zjištěna). Tento koeficient by měl záviset také na rozměrech auta, pro jednoduchost je ale neberu v úvahu. Při přechodu mezi dvěma kubikami nabývá úhel β vysokých hodnot. Aby se auto neotáčelo o celý tento úhel, zmenšuji koeficient c. To vede k setrvačnému rozložení velkého úhlu δ do více snímků. Tímto způsobem se mi ovšem nepodařilo úplně odstranit prudké změny směru vozidla. Hlavně při zatáčení auta do protisměru se stává, že sebou občas trochu trhne. Vozidlo vstupuje do křižovatky, když přejede svým bodem B bod In a vystupuje z ní, když tímto bodem přejede bod Out. RoadsState kontroluje, zda auto v křižovatce překročilo hranici hrany. Pokud k tomu došlo, nastavuje přes jednotku CarExecutionUnit normálu vozidla podle normály nové hrany. Jestliže auto opouští křižovatku, RoadsState také sděluje řídící jednotce auta optimální rychlost průjezdu příští křižovatkou. Závisí nepřímo úměrně na úhlu natočení směru auta (v xz) po přejetí celé křižovatky – úhlu γ . Se vzdáleností l mezi body In a Out je pak úměrná přímo. Definuje ji vzorec m − 2γ + l / 8 , přičemž shora ji omezuje m, kde m značí maximální rychlost průjezdu křižovatkou (je nastavena na 7,5 m ⋅ s −1 ; měla by však být vždy alespoň 6 m ⋅ s −1 , protože γ se může zdola blížit k π).

17

6.2 Řízení provozu na velké křižovatce 6.2.1 Zamykání hran Hrany k zamčení se oproti klasickým hranám liší v těchto bodech: • normální vstupní hranu do malé nebo velké křižovatky tvoří pouze část za bodem In, obdobně normální výstupní hranu z malé či velké křižovatky představuje část před bodem Out • krátká hrana je rozdělena na dvě hrany u bodu Out • pokud není řečeno jinak, jsou hrany mezi pro auto vstupní a výstupní hranou do/z malé křižovatky brány jako jedna sloučená hrana, která se skládá z dílčích hran Pokud se ve spojitosti s hranou budu zmiňovat o jejím zamykání, odemykání a podobně, bude tato hrana hranou k zamčení. Pokud auto přejelo bod stopOrGoDecision normální hrany, která není poslední v jeho cestě, RoadsState zjišťuje, zda má povolení k průjezdu velkou křižovatkou. Jestliže ho nemá, dělá to opět v dalším snímku. Pokud ovšem auto může jet, jsou zamčeny vstupní a výstupní hrana do/z velké křižovatky a hrany mezi nimi (přes které v ní pojede). Při zamčení se zvyšuje počet zamčení hrany, při odemykání se snižuje. Hrana se stává odemčenou, když je po jejím odemykání počet zamčení 0. Zamčení sloučené hrany se realizuje zamčením jejích dílčích hran. Tato hrana se považuje za odemčenou, jestliže jsou všechny její dílčí hrany odemčené. Hrany mohou být vícenásobně zamčeny, když vozidlo jede přes cyklus krátkých hran na velké křižovatce:

Obrázek 6.3: Vícenásobné zamčení hran. Pokud dojde ve velké křižovatce k přechodu auta přes hranu k zamčení, je odemykána předchozí hrana. Jestliže vozidlo u bodu Out výstupní hrany opouští velkou křižovatku, je tato hrana také odemykána (a vždy odemčena).

18

6.2.2 Uváznutí Rozlišuji dva druhy uváznutí aut – řešitelné a neřešitelné. Ve druhém případě si auta vzájemně blokují místa na začátcích výstupních hran, například takto:

Obrázek 6.4: Neřešitelné uváznutí. Taková auta nesmějí zůstat stát do konce simulace. Pokud čekají před bodem stopBeforeJunc příliš dlouho, jsou dočasně odstavena na kraj silnice jejich řídícími jednotkami. Toto uváznutí by se tedy mělo spíše nazývat neřešitelné normální cestou, pro jednoduchost to ale zkracuji pouze na neřešitelné uváznutí. Řešitelné uváznutí (dále pouze uváznutí) aut uvažuji vždy pouze lokálně na malé křižovatce. Ve výjimečných situacích se tak stává, že vozidlo nedává přednost jinému, i když by teoreticky mělo (viz obrázek 6.7 v podkapitole 6.2.5 Řešení konkrétních komplikovaných situací). Aby se tyto případy odstranily, mohl bych rozpoznávat uváznutí na velkých křižovatkách. To by ovšem bylo výpočetně náročnější. K odblokování uvázlých aut na křižovatce dochází tak, že všechna začnou mít přednost. Řešení uváznutí ilustruje obrázek:

Obrázek 6.5: Uváznutí na křižovatce. Na křižovatce k vzniká uváznutí, pokud platí: • všechny vstupní a výstupní hrany jsou odemčené • na žádné vstupní normální hraně není auto, které je na ní poslední a nestojí • pro žádnou krátkou vstupní hranu neexistuje vozidlo, které přes ní pojede ve své příští velké křižovatce, nestojí, je na normální hraně poslední a nachází se blízko další křižovatky (tak, že auta u křižovatky k zvažují, zda mu dají přednost) • na začátky všech výstupních normálních hran se vejde vozidlo s maximální délkou (2PDA) • v posledním snímku nedošlo na křižovatce k odemčení hrany (pokud se na křižovatce nebo v její těsné blízkosti něco děje, není zablokována)

19

6.2.3 Pravidlo pravé ruky Auto má na křižovatce přednost před ostatními vozidly podle pravidla pravé ruky (dále PPR), pokud: • pro všechny její normální a krátké vstupní hrany, přes které auto chce jet a se kterými svírá hrana, přes kterou chce vjet do křižovatky, úhel menší než (3/4)π, platí: o pro normální hranu: poslední auto je od křižovatky tak daleko, že mu toto vozidlo ještě nemusí dávat přednost o pro krátkou hranu: neexistuje žádné auto, které přes ní pojede ve své příští velké křižovatce, je poslední na normální hraně a nachází se tak blízko další křižovatky, že mu toto vozidlo musí dát přednost • vozidlo stojí na hraně jako poslední a na křižovatce jsou řešitelně uvázlá auta Následující obrázek popisuje, jak je PPR použito v konkrétní situaci:

Obrázek 6.6: Pravidlo pravé ruky. V některých případech nemusí být na první pohled jasné, které auto má přednost podle PPR (viz obrázek 6.8 v podkapitole 6.2.5 Řešení konkrétních komplikovaných situací).

6.2.4 Podmínky pro povolení průjezdu velkou křižovatkou Kritéria pro povolení vjezdu auta do velké křižovatky jsou následující: • auto je na hraně poslední • vstupní a výstupní hrana do/z velké křižovatky a hrany mezi nimi (přes které v ní chce jet) jsou odemčené • auto má přednost podle PPR před ostatními vozidly na všech malých křižovatkách, přes které chce jet ve velké křižovatce • na začátku uvedené výstupní hrany je pro vozidlo dostatek místa • jestliže má auto na některé z výše zmíněných malých křižovatek povolení jet podle PPR pouze díky uváznutí, musí být navíc na výstupní hraně dost místa i pro vozidlo s maximální délkou • pokud může auto přes některou z uvedených malých křižovatek jet jenom kvůli uváznutí, nesmí být na nich v posledním snímku odemčena hrana

20

Poslední dvě podmínky spolu se dvěma posledními kritérii pro vznik uváznutí zajišťují, že auta, která mohou jet bez uváznutí, mají většinou přednost před vozidly, která mohou jet jenom s ním. Výjimečnou situaci, kdy tomu tak není, popisuje obrázek 6.7 v další podkapitole. Tento systém povolování vjezdu do velké křižovatky vede k tomu, že vozidlo ví občas dopředu, kudy nějaké auto pojede, ačkoliv mu to nesděluje pomocí směrových světel. To může působit nepřirozeně. Stává se to, když vozidlo jede přes krátké hrany (viz obrázek 6.9 v další podkapitole) nebo když směrová světla nemohou rozlišit směr přesně (viz obrázek 6.10 v další podkapitole). Pokud se velká křižovatka skládá ze dvou a více krátkých hran, nemusí být někdy na první pohled patrné, proč auto dostalo povolení k průjezdu. Takové případy se ale ve městě generovaném programem ACG neobjevují příliš často a ještě méně se stávají ve skutečnosti. Obtížně by se hledal jiný systém povolování průjezdu velkou křižovatkou založený na PPR, který by byl v těchto situacích čitelnější.

6.2.5 Řešení konkrétních komplikovaných situací

Obrázek 6.7: Porušení PPR v důsledku lokálního rozpoznávání uváznutí.

Obrázek 6.8: Sporný výklad PPR.

21

Obrázek 6.9: Jasnovidnost aut u velké křižovatky složené z krátkých hran.

Obrázek 6.10: Telepatie aut u malé křižovatky.

6.3 Okolí auta na rovném úseku Jestliže je vozidlo na hraně mezi body Out a In, řídí se podle těchto parametrů: • vzdálenost k jednomu z následujících bodů: o pro normální hranu: bod stopBeforeJunc o pro konečnou hranu: cíl auta o pro krátkou hranu: bod In • směr zatočení vozidla na příští křižovatce (nabývá tří hodnot: doleva, doprava a rovně; slouží k obsluze směrových světel; RoadsState ho posílá řídící jednotce pouze, když auto opouští křižovatku)

22

• •

1

pro normální hranu: rychlost a vzdálenost dalšího auta (při nízkém FPS1 se stává, že je tato vzdálenost záporná – auta do sebe vrážejí) pro normální hranu, která není konečná: zda může vjet vozidlo do příští velké křižovatky

Frames Per Second

23

7. CarControlUnit Jestliže je auto v křižovatce, CarControlUnit přeposílá úhel zatočení kol od RoadsState výkonné jednotce.

7.1 Zrychlování a brždění Vozidlo za normálních okolností akceleruje vždy polovinou maximálního zrychlení auta (pro každé vozidlo může být jiné). Maximální zrychlení bude použito u budoucího rozšíření aplikace – například u předjíždění. Auta brzdí vždy průměrným zpomalením –3 m ⋅ s −1 , aby se nestávalo, že by do vozidla nabouralo auto s horšími brzdami. Větší zpomalení (menší, pokud jde o hodnotu) se využije při řešení krizových situací v pozdějším rozšíření práce. Řídící jednotka auta na rovném úseku určuje, zda by vozidlo mělo brzdit, aby dosáhlo v dalším bodě X rychlost vx. Následující tabulka popisuje druhy bodů X, odpovídající rychlosti vx a stavy auta, ve kterých se zjišťuje potřeba brzdit před bodem X: bod X

Rychlost vx (v m ⋅ s −1 )

Stav auta

bod stopBeforeJunc

0

cíl auta

0

bod In

optimální rychlost průjezdu další křižovatkou rychlost dalšího auta

auto je na normální hraně (před bodem stopBeforeJunc) a nemá povolení k průjezdu další velkou křižovatkou vozidlo se nachází na konečné hraně před cílem auto je na krátké hraně (před bodem In)

bod nacházející se 0,5PDA před zadním nárazníkem dalšího auta2

vozidlo se nachází na normální hraně

Tabulka 7.1: Typy bodů X. Z implementačních důvodů je referenčním bodem auta pro bod In a cil bod B a pro ostatní body přední nárazník. Pokud se nachází vozidlo před bodem X ve vzdálenosti nejvýše sm, brzdí (CarControlUnit vyšle abilitě CarExecutionUnit signál k brždění), v opačném případě zrychluje. Výpočet sm závisí na aktuální rychlosti auta v, rychlosti vx a na zpomalení a (zpomalení v důsledku brždění, ke kterému je připočteno zrychlení způsobené sklonem vozovky). Pokud je v menší než vx, nabývá sm zápornou hodnotu (vozidlo zrychluje). V opačném případě je aproximována rychlost, kterou pojede auto na úseku před bodem X dlouhém sm, jako (v + v x ) / 2 2

Minimální vzdálenost mezi vozidly na rovném úseku je vždy zhruba 0,5PDA.

24

(v příštím snímku tomu už ovšem může být jinak v důsledku posunutí bodu X). Hodnota sm je odvozena ze základních vzorců s = v t a v = a t :

sm =

v x2 − v 2 2a

Když vozidlo přejede bod stopOrGoDecision na normální hraně, rozhoduje se řídící jednotka, zda vjede do další velké křižovatky. Jestliže dostala od RoadsState povolení ke vstupu, pokračuje auto dál v jízdě. V opačném případě zpomaluje k bodu stopBeforeJunc. Pokud je vozidlo v křižovatce nebo na normální hraně za bodem stopOrGoDecision a má povolení k průjezdu další velkou křižovatkou, snaží se udržovat si optimální rychlost průjezdu křižovatkou. To znamená, že když ji výrazně překročí, zpomaluje. Když má značně menší rychlost, zrychluje.

7.2 Řízení směrových světel Jestliže se auto blíží k další křižovatce, zapnou se přes výkonnou jednotku směrová světla podle směru zatočení, které auto na této křižovatce bude mít. Při výjezdu z křižovatky se vypnou.

7.3 Odstavení auta Jestliže vozidlo čeká před bodem stopBeforeJunc příliš dlouho (déle než minutu), vzniklo nejspíš neřešitelné uváznutí. CarControlUnit pak vysílá výkonné jednotce pokyn k odsunutí auta ke kraji silnice a informuje o tom RoadsState, aby byl umožněn průjezd dalších vozidel na hraně. Pokud je auto první odsunuté na hraně, CarControlUnit se v určitém časovém intervalu (23 s) ptá jednotky stavu silnic, zda je pro vozidlo na hraně místo. Pokud dostává kladnou odpověď, dává rozkaz výkonné jednotce k posunutí auta zpátky do vozovky. K neřešitelnému uváznutí dochází často v oblastech, do které vedou hrany, ale žádné z ní nevychází. Pokud takovým místem projíždí hodně aut, trvá poměrně dlouho, než se všechna dostanou do cíle.

25

8. CarExecutionUnit 8.1 Proměnné parametry auta Každé auto má zejména tyto proměnné parametry (mění se v každém snímku): • rychlost v • rychlost v minulém snímku vp • zrychlení a, které by mělo vozidlo na rovné vozovce • směr d (jednotlivé složky označuji dx, dy, dz) • normála n (složky označuji nx, ny, nz) • čas t΄, který uplynul od minulého snímku • úhel natočení kol (do stran) δ • geometrický střed auta P • spodní pozice B (střed podstavy kvádru, který obklopuje auto) Některé z uvedených parametrů popisuje obrázek:

Obrázek 8.1: Hlavní proměnné parametry vozidla.

8.2 Ovládací signály CarExecutionUnit dostává pokyny od řídící jednotky především k: • nastavení zrychlení a • změně úhlu δ • přepnutí směrových světel do určitého stavu • zastavení (zatáhnutí ruční brzdy) • aktualizaci stavu auta • odsunutí vozidla na kraj silnice Výkonná jednotka také přijímá od RoadsState signály ke změně normály podle sklonu vozovky.

26

8.3 Aktualizace stavu auta Nejprve se vypočítá nová rychlost auta v: v = v p + a − ed y t '

(

)

Výraz edy představuje přírůstek, resp. úbytek zrychlení způsobený sklonem vozovky. Převodní konstanta e je 3,0. Byla experimentálně zjištěna. Měla by záviset na několika parametrech – hlavně na váze vozidla (těžší auta by ji měla mít větší). Pro jednoduchost je zanedbávám. Rychlost v je dále omezena maximální a minimální rychlostí auta (pro každé vozidlo jsou jiné, viz Příloha C). Směr auta se otočí kolem normály o úhel δu/3,0 (u je vzdálenost ujetá v předposledním snímku; viz koeficient c v podkapitole 6.1 Modelování průjezdu auta malou křižovatkou). Zjistí se dráha uražená v posledním snímku s: v + vp s= t′ 2 Je přičtena ve směru auta k pozicím B a P. Úhel δ se při přechodu mezi kubikami a při vjezdu a výjezdu do/z křižovatky prudce mění a může nabývat velkých hodnot (hlavně při zatáčení auta do protisměru). Na změně směru auta to ovšem není tolik vidět, jelikož se otáčí o pouhý zlomek úhlu δ. Aby zobrazované natočení předních kol působilo přirozeně, neotáčí se kolem osy y (v lokálním souřadnicovém systému kola) o úhel δ, ale o úhel ε. Od úhlu δ se liší tím, že je na něj aplikována setrvačnost (závisí na úhlech ε v minulých snímcích) a že jeho extrémní hodnoty jsou omezeny. U generovaných aut je |ε| vždy menší než 0,7. U ručně zadaných vozidel nastavuje tento limit uživatel. Kola se otáčí také kolem osy z (v lokálním souřadnicovém systému kola) o úhel, jenž závisí na ujeté vzdálenosti s a poloměru kola. Pro jednoduchost se předpokládá, že všechna kola auta mají stejný poloměr. Pokud je zapnuté nějaké směrové světlo, periodicky se po uplynutí určité doby (0,5 s) rozsvěcuje a zhasíná. Přední světla svítí neustále. Brzdová světla se rozsvítí, když auto začne brzdit a zhasnou, když přestane brzdit.

8.4 Rozměry auta Rozměry se skládají z výšky, délky a šířky. Maximální délka auta je nastavena na 10 m (2PDA). Delší vozidla aplikace nepodporuje, taková vozidla by už zřejmě musela mít kloub a při průjezdu zatáčkou se zlamovat. Maximální šířka auta je nastavena na 3 m. Mohla by se nastavit i větší, ovšem pak by mnoho normálních a krátkých hran začalo být příliš úzkých pro taková vozidla a byly by klasifikovány jako nesjízdné (typ hrany by se změnil na normální nebo krátkou hranu bez pruhů). Ostatní parametry auta popisuje Příloha C.

27

9. Závěr Výsledkem této práce je zásuvný modul do systému VRECKO pro simulaci dopravy ve městě. Jako u každé simulace, tak i v tomto případě výsledek úplně neodpovídá a ani nemůže odpovídat realitě. Simulace je napodobování skutečného procesu. Při provozování mé aplikace tak dochází k určitým odchylkám od reality. Auta mohou v některých výjimečných okamžicích (hlavně při otáčení do protisměru) nepřirozeně prudce zatočit. Tento problém by mělo být možné odstranit omezením pohybů vozidel pouze na ty, které jsou v souladu s fyzikálními zákony. K této úpravě by se mohla použít knihovna PhysX [14], kterou podporuje systém VRECKO. Řidiči vozidel vědí vždy dopředu, kudy jedou ostatní, a proto se občas může zdát, že jednají zbrkle, bez rozvahy. Lokální rozpoznávání uváznutí výjimečně způsobuje porušení PPR. Tato chyba ovšem není natolik závažná, aby ji bylo nutné složitě řešit. Ve skutečnosti je provoz na křižovatkách řízen podle PPR pouze v okrajových případech. Pokud by se do aplikace přidaly semafory a rozlišení silnic na hlavní a vedlejší, stávala by se tato závada ještě méně. Program je napsán modulárně pouze do určité míry. Hlavní tři ability (CarExecutionUnit, CarControlUnit a RoadsState) jsou propojeny více, než jsem zprvu plánoval. Jednotka stavu silnic vykonává řadu činností, které v počátečním rozvržení aplikace měla dělat CarControlUnit. Komunikace mezi nimi je tím pádem jednodušší – ovšem na úkor jejich rozšiřitelnosti. Hůře se například bude implementovat chování řidičů u řídící jednotky. Na druhé straně je například povolení vjezdu do velké křižovatky řešeno tak obecně, že by nemělo být větším problémem nahradit PPR jiným systémem dávání přednosti na malé křižovatce. Na práci mi nejvíce času zabral návrh i následná implementace modelování průjezdu auta křižovatkou. Vozidla v počáteční fázi vývoje měnila prudce svůj směr v každém snímku nebo byla při výjezdu z křižovatky blíže k levému či pravému okraji hrany. Při testování aplikace jsem také často nacházel porušení PPR, které jsem musel stále složitěji opravovat. Musím však konstatovat, že po překonání počátečních nezdarů se mi podařilo vytvořit plně funkční simulaci aut, která má vedle zmíněných odchylek od reality také velké množství pozitivních aspektů. Program ve výkonnostních testech dosáhl relativně dobrých výsledků i při velkém počtu generovaných vozidel (viz Příloha D). Kód je přehledně komentován. Aplikace je napsána robustně, takže vozidla do sebe nenarážejí a nezůstávají vzájemně zablokována do konce simulace ani v extrémních případech. Vždy dojedou do cíle. V jedné z prvních verzí programu byla auta reprezentována kvádry různých barev. Na konci vývoje aplikace se mi však podařilo vytvořit jednoduchý, ale účelný systém rozdělení modelů aut na jednotlivé části. Pomocí něho se zobrazuje otáčení kol a signalizace změny směru směrovými světly. Ta pomáhá při kontrole, zda auta projíždějí přes velkou křižovatku ve správném pořadí. Po vzoru modelů vozidel, které se nachází v aktuální verzi aplikace, lze snadno vytvořit další a používat je v simulaci (viz Příloha C). Uživatel může u ručně zadaných aut ve vstupním XML souboru nastavovat velké množství parametrů. Jednoduchý formát silniční sítě zajišťuje její snadnou ruční úpravu i úplnou náhradu sítí vytvořenou generátorem města ACG (viz Příloha B).

28

Simulaci lze rozšířit mnoha způsoby. V první řadě by bylo vhodné do výkonné jednotky přidat podporu PhysX. Auta by na hranách mohla jezdit po více než jednom pruhu. Provoz by už poté nemohl být řízen pouze pomocí PPR, takže by se musely přidat také semafory nebo rozlišení silnic na hlavní a vedlejší. Dále by bylo možné definovat tvar hrany složitější křivkou, aby nemusely být všechny silnice rovné. Předjíždění aut a s tím spojené variabilní chování řidičů (agresivní, normální, zpomalené) by také tuto simulaci značně zpestřily a přiblížily více realitě. Další, méně důležité modifikace, o které by se aplikace mohla obohatit, jsou např. přechody pro chodce, parkovací místa pro auta či zastávky autobusů.

29

Literatura [1] Linden Lab. What is Second Life? [online]. [2009] [cit. 2009-12-13]. Dostupný z WWW: . [2]

PTV AG. VISSIM [online]. c2009 [cit. 2009-12-13]. Dostupný .

z

WWW:

[3] KRAJZEWICZ, Daniel, BEHRISCH, Michael. SUMO - Simulation of Urban MObility User Documentation [online]. [2009] [cit. 2009-12-13]. Dostupný z WWW: . [4] KRAJZEWICZ, Daniel, BEHRISCH, Michael. SUMO - Simulation of Urban MObility User Documentation [online]. [2009] [cit. 2009-12-13]. s. 5. Dostupný z WWW: . [5] KOVALČÍK, Vít, FLASAR, Jan, SOCHOR, Jiří. Extensible Approach to the Virtual Worlds Editing. In Afrigraph 2007 Proceedings. Grahamstown (South Africa) : ACM, 2007. s. 31-37. Dostupný z WWW: . [6] PUNČOCHÁŘ, Jaromír. Automatické generování městské zástavby. Brno, 2006. 35 s. Fakulta informatiky. Masarykova univerzity. Vedoucí bakalářské práce Mgr. Vít Kovalčík. [7] W3C. Extensible Markup Language (XML) [online]. c1996-2003 [cit. 2009-12-13]. Dostupný z WWW: . [8] OpenSceneGraph : Introduction [online]. 2007 [cit. 2009-12-13]. Dostupný z WWW: . [9] Khronos Group. OpenGL Overview [online]. c1997-2009 [cit. 2009-12-13]. Dostupný z WWW: . [10] The Apache Xerces Project [online]. c1999-2009 [cit. 2009-12-13]. Dostupný z WWW: . [11] CORMEN, Thomas, et al. Introduction to Algorithms. 2nd edition. Cambridge (Massachusetts) : The MIT Press, 2001. s. 528. [12] CORMEN, Thomas, et al. Introduction to Algorithms. 2nd edition. Cambridge (Massachusetts) : The MIT Press, 2001. s. 595-596.

30

[13] ŽÁRA, Jiří, et al. Moderní počítačová grafika. 2. přepracované a rozšířené vyd. Brno : Computer Press, 2004. s. 184-185. [14] NVIDIA PhysX SDK Features [online]. [2009] [cit. 2009-12-13]. Dostupný z WWW: .

31

Příloha A

Obsah CD CD obsahuje: • bc-text – adresář s textem bakalářské práce ve formátu doc a pdf •

src – adresář se zdrojovými soubory modulu podporujícího simulaci aut

•

bin – adresář se zkompilovanou verzí systému VRECKO včetně tohoto modulu

•

ACG – adresář s generátorem města ACG

•

install – adresář s instalačními programy aplikací, které potřebuje ke svému běhu aplikace ACG

V adresáři bin se nachází dávka carsim.bat, která spustí simulaci s předpřipraveným konfiguračním souborem carsim_testing_world.xml. Pro zahájení aplikace s jiným nastavením, lze spustit v témže adresáři vreckoApp.exe file_path, kde file_path je cesta k souboru s požadovanou konfigurací.

32

Příloha B

Parametry ability RoadsState v konfiguračním XML souboru Zápis ability RoadsState ve vstupním XML souboru může vypadat tímto způsobem (viz také carsim_testing_world.xml ve složce bin ): RoadsState CarSim <Parameters> data/CarSim 0 1 0 <Junction id="1" x="0.0" y="0.0" z="0.0"/> <Junction id="2" x="50" y="0.0" z="0.0"/>

Element určuje složku s daty aplikace (modely částí aut, textura silnice, vygenerované město).

Síť silnic Síť silnic je zadána v elementu v elementu <Parameters>. Je tvořena třemi prvky: původními křižovatkami (element <Junction>), krajními body silnic (element ) a vlastními silnicemi (element ). V atributech základní křižovatky je uvedeno její ID a souřadnice jejího středu. Krajní body obsahují také své ID a souřadnice a dále ID původní křižovatky, u které se nacházejí (atribut junction).

33

Silnice je specifikována těmito parametry: • ID (atribut id) •

ID křižovatky, ze které vychází (atribut fromJunction)

•

ID křižovatky, do které směřuje (atribut toJunction)

•

ID krajního bodu u křižovatky fromJunction na pravé straně silnice (atribut fromPointRight)

•

ID krajního bodu u křižovatky toJunction na levé straně silnice (atribut toPointLeft)

•

ID krajního bodu u křižovatky fromJunction na levé straně silnice (atribut fromPointLeft)

•

ID krajního bodu u křižovatky toJunction na pravé straně silnice (atribut toPointRight)

•

počet pruhů na pravé straně silnice (atribut numLanesForward)

•

počet pruhů na levé straně silnice (atribut numLanesBack)

Na pořadí elementů <Junction>, , a jejich atributů nezáleží. Silniční síť ve výše uvedeném zápisu ability RoadsState se skládá z jedné silnice s jedním pruhem v obou směrech, která je dlouhá 50 m a široká 7 m. Tento formát výstupu má program ACG (vytvořený také v Laboratoři interakce člověka s počítačem), který je obvykle použit pro generování silnic. V souboru carsim_testing_world.xml se nachází ukázková silniční síť vygenerovaného města o poloměru 1000 m. Následujícím postupem lze programem ACG vytvořit jinou síť a vložit ji do nového vstupního XML souboru: • ACG je napsán v jazyku Python, proto je potřeba mít nainstalován jeho interpret (instalátor python-2.4.4.msi se nachází v adresáři install) a modul ctypes (standardní instalace Pythonu ho od verze 2.5 obsahuje v sobě, instalátor tohoto modulu ctypes-1.0.2.win32-py2.4.exe se také nachází v adresáři install) •

v adresáři ACG se spustí program acg.py –y –r radius –d out_dir_path, kde radius je číslo určující poloměr města v metrech a out_dir_path představuje cestu k adresáři, kde se uloží výstupní soubory (potřeba budou soubory acg_parcels.xml a terrain.obj)

•

zkopírováním souboru carsim_testing_world.xml se vytvoří nový vstupní soubor

•

nahradí se v něm obsah elementu obsahem elementu uvnitř elementu <SubBlock type="RoadSystem"> v souboru acg_parcels.xml

•

v elementu uvnitř popisu objektu ve scéně (element <EnvironmentObject>) s ID 50 se uvede cesta k souboru terrain.obj, který obsahuje model terénu města

34

Generování aut Element v parametrech (element <Parameters>) obsahuje informace o náhodně generovaných autech. Jejich počet udává dceřinný element . Jeho následník pak určuje, zda mají být jejich cesty nejkratší (hodnota 1 nebo true je pro nejkratší, 0 nebo false pak pro náhodné cesty). Přibližně každé třetí auto je nákladní (IVECO TRAKKER AD 340T41), zbylá vozidla jsou osobní (BMW 645 CI).

Vykreslování silnic Načtenou silniční síť lze zobrazit zadáním hodnoty 1 (true) v elementu v parametrech. U generovaného města tomu tak ovšem většinou není, jelikož polygony silnic jsou již součástí zobrazovaného modelu terénu města (terrain.obj).

35

Příloha C

Zadávání jednotlivých aut Auto s konkrétními parametry se přidává do simulace vložením elementu <EnvironmentObject> pod element <Scene> v konfiguračním XML souboru. Následuje ukázkový zápis takového elementu: <EnvironmentObject> 17 bmwLP CarControlUnit CarSim <Parameters> <StartRoad>150 <StopRoad>160 <StartDirection>0 <StopDirection>1 <StartOffset>50 <StopOffset>50 CarExecutionUnit CarSim <Parameters> 1.416 4.839 <Width>2.036 <MaxSpeed>14.0 <MinSpeed>-5.0 <MaxAcc>6.0 <MinAcc>-8.0 <MaxDispWheelAngle>1.0 <WheelRadius>0.36449554 bmwLP/bmwLPwithoutWheels.3DS bmwLP/bmwLPwheel.3DS bmwLP/bmwLPwheel.3DS bmwLP/bmwLPfrontLights.3DS

36

bmwLP/bmwLPbrakeLights.3DS bmwLP/bmwLPleftBlinker.3DS bmwLP/bmwLPrightBlinker.3DS <WheelsPosition> 1.474 -0.343 -0.788 -1.324 -0.343 -0.788

Element obsahuje ID auta, které je pro něj v simulaci unikátní. Další element určuje název vozidla. Následující element představuje abilitu CarControlUnit. V dceřiném elementu <Parameters> je uložena počáteční a konečná pozice auta. Element <StartRoad> má hodnotu ID silnice, kde se nachází start auta. Element <StartDirection> určuje hranu té silnice. Hodnota 1 (true) označuje hranu s kladným a 0 (false) se záporným směrem. Přesná pozice na hraně mezi body Out a In je určena relativně v procentech (vůči vzdálenosti těchto bodů). Obsahuje ji element <StartOffset>. Podobný účel mají elementy <StopRoad>, <StopDirection> a <StopOffset> pro cíl. Obě tyto pozice ovšem nemohou být úplně libovolné. Vztahují se na ně další omezení, která již počítají s vkládáním vozidel do simulace v jejím průběhu3: • počáteční a konečná hrana musí být normální • auto musí být v cíli a na startu před bodem stopBeforeJunc a zároveň za bodem, který se nachází za bodem Out ve vzdálenosti 0,5PDA • mezi počáteční a konečnou pozicí musí existovat cesta • na startu musí být vzdálenost k dalšímu vozidlu za ním alespoň 0,5PDA • podobně je tomu na startu s předcházejícím autem, které ale může být již rozjeté; aby se nestřetlo s novým vozidlem, musí být vzdálenost mezi nimi nejméně 0,5PDA + 0,5PDA · rychlost předcházejícího auta • jestliže je počáteční hrana u malé křižovatky, ze které vychází, zamčená, musí být vozidlo od bodu Out hrany vzdálené minimálně 4,5PDA (na hranu může vjíždět auto, které si uvědomí přítomnost dalšího nového vozidla na hraně až, když je u bodu Out) Jestliže auto nesplňuje nějakou z výše uvedených podmínek, není vloženo do simulace.

3

Všechna auta jsou zatím vkládána na začátku simulace, proto některá omezení zůstávají nevyužita.

37

Uvnitř dalšího elementu se nachází parametry pro abilitu CarExecutionUnit. Jedná se o: • rozměry – element •

maximální a minimální rychlost – elementy a

• •

maximální a minimální zrychlení – elementy a maximální úhel zobrazovaného natočení předních kol kolem osy y (v lokálním souřadnicovém systému kola) – element <MaxDispWheelAngle> (hodnota je v radiánech) poloměr kol – element <WheelRadius>

• •

cesty k souborům popisujícím geometrii auta – element , jsou relativní vůči adresáři uvedeném v elementu (viz Příloha B), dceřiné elementy určují jednotlivé části auta: o auto bez kol – element o přední levé kolo – element o zadní levá kola – elementy , kde i označuje řadu kol směrem k zádní části auta, i ≥ 1 (modely levých kol jsou použity i pro pravá kola) o přední světla – element o brzdová světla – element o levé směrové světlo – element o pravé směrové světlo – element

•

umístění levých kol – element <WheelsPosition> (pozice pravých kol se odvozují od levých), dceřiné elementy obsahují: o pozici předního levého kola (element ) o pozice zadních levých kol (elementy , kde i označuje řadu kol směrem k zadní části auta, i ≥ 1)

Na tyto parametry se vztahují omezení: • hodnota elementu musí být v intervalu [0,1; 10] m •

hodnota elementu musí být v intervalu [0,1; 2PDA] m

•

hodnota elementu musí být v intervalu [0,1; maximální šířka auta ] m

•

hodnota elementu musí být v intervalu [1, 50] m ⋅ s −1

•

hodnota elementu musí být v intervalu [–20, –1] m ⋅ s −1

•

hodnota

•

hodnota elementu musí být v intervalu

elementu musí být v intervalu [1, 30] m ⋅ s −2

[-25, 2 ⋅ průměrné zpomalení auta ] m ⋅ s −2 •

hodnota elementu <MaxDispWheelAngle> musí být v intervalu [0, π/2]

•

hodnota elementu <WheelRadius> musí být v intervalu [0,1; 2] m

38

Ve složce bin/data/CarSim jsou umístěny modely dvou aut. První, nákladní vozidlo IVECO TRAKKER AD 340T41, vytvořil Mgr. Tomáš Pelikán. Nachází se v adresáři iveco. Druhé, osobní auto BMW 645 CI, mi poskytl vedoucí práce. Je v adresáři bmwLP. Po vzoru těchto aut lze snadno udělat další a používat je v simulaci.

39

Příloha D

Výkonnostní testy Testy byly provedeny na počítači s procesorem Athlon XP 2700+, operační pamětí o velikosti 2 GB a s grafickou kartou GeForce 7600GS. Silniční síť byla generována programem ACG. Při měření byla kamera umístěna v bodě [0,1200,0] (v metrech). Město s nejmenším poloměrem bylo v záběru celé, u větších měst byl vidět pouze jeho střed. Průměrný počet snímku za vteřinu (FPS) v 1. minutě byl měřen programem FRAPS. Poloměr města

Počet aut k vygenerování

300 300 300 300 300 300 600 600 600 600 600 600 1000 1000 1000 1000 1000 1000 1500 1500 1500 1500 1500 1500 1500 1500

1 100 204* 1 100 150* 1 550 1107* 1 550 1145* 1 1250 2663* 1 1250 2485* 1 1250 2500 5166* 1 1250 2500 6105*

Průměrný počet aktualizací jednotky CarControlUnit 1. generovaného auta za sekundu v 1. minutě Ano 1.185 503.276 Ano 1.244 100.560 Ano 1.333 52.868 Ne 1.235 502.121 Ne 1.284 94.425 Ne 1.219 68.906 Ano 2.265 499.496 Ano 7.894 24.406 Ano 13.671 10.983 Ne 2.257 500.057 Ne 2.514 27.669 Ne 2.945 11.264 Ano 9.041 529.073 Ano 60.144 15.434 Ano 119.541 7.547 Ne 9.040 528.358 Ne 9.917 16.986 Ne 11.168 8.447 Ano 24.924 496.865 Ano 180.299 16.325 Ano 330.546 8.771 Ano 682.383 4.528** Ne 25.075 459.547 Ne 25.911 17.730 Ne 26.127 9.400 Ne 33.175 –*** Tabulka D.1: Výkonnostní testy.

Cesty aut jsou nejkratší

Čas k načtení simulace (v sekundách)

Průměrný FPS v 1. minutě 500.350 99.983 52.700 501.600 94.217 68.967 492.050 23.983 10.750 492.700 27.500 11.250 522.417 15.383 7.483 523.633 16.867 8.533 490.400 16.083 8.750 4.500 450.867 17.517 9.067

* Počet aut, při kterém dochází k zaplnění silnic ve městě. Při generování aut s náhodnými cestami dochází k zaplnění silnic, když se 20krát za sebou nepodařilo vybrat správnou počáteční pozici. V případě nejkratších cest jsou silnice zaplněné, jestliže se 34krát za sebou nenalezl vhodný start, cíl a nejkratší cesta mezi nimi.

40

** Jelikož se aktualizace auta prováděla méně často, vozidla do sebe začala zezadu mírně narážet. *** Simulace se asi po 16 s zasekla. Když byla auta detailně zobrazena, tedy když byla kamera ve výšce asi 100 m nad rovinou xz, jevila se simulace plynulá, pokud v ní bylo nejvýše zhruba 800 vozidel. Jestliže se pozorovatel díval z bodu, ve kterém byla kamera umístěna pro testy, byla simulace plynulá ještě při počtu asi 3000 aut.

41

Příloha E

Snímky ze simulace

Obrázek E.1: Malé křižovatky propojené normálními hranami.

Obrázek E.2: Pohled seshora na silniční síť města o poloměru 1000 m.

42