Traficul Rutier

INTRODUCERE

Motivație

O dată cu dezvoltarea industrială a marilor orașe, a apărut în mod inevitabil problema congestionării traficului rutier. Statisticile [1] arată că, în anul 2010 numărul mașinilor din întreaga lume era de peste un miliard și este în continuă creștere. Una dintre soluțiile găsite pentru a remedia această problemă este utilizarea unor sisteme de control inteligente ale autovehiculelor. Un astfel de sistem poate asigura optimizarea consumului de combustibil, reducerea numărului de accidente și fluidizarea traficului rutier. Totuși, deși au fost realizate mai multe sisteme în acest scop, o soluție generală s-a dovedit a fi greu de găsit. Aceste sisteme se pot clasifica în trei mari categorii, și anume: de avertizare, semi-automate și automate. Sistemele de avertizare și semi-automate au fost dezvoltate deoarece realizarea unui sistem complet automat prezintă anumite riscuri, care pot fi reduse prin utilizarea unui supervizor. În această lucrare se propune realizarea unui simulator pentru dezvoltarea diferitelor sisteme de control automate și semi-automate a mașinilor.

Realizarea unui sistem capabil să simuleze traficul rutier este o sarcina foarte complexă, motiv pentru care simulatorul trebuie conceput în așa fel încât să poata fi dezvoltat pe parcurs. În mod special, se încearcă descrierea unui sistem în care o mașina ar putea circula în mod automat pe o anumită ruta prestabilită. Nu se impune în acest caz, ca mașina să fie capabilă să urmeze orice traseu, ci doar anumite trasee care au fost studiate și sunt considerate a fi sigure. În acest sens, se poate lua in considerare utilizarea unei benzi speciale pentru mașina autonoma. Conform cu B. van Arem [2], o astfel de soluție reduce riscurile producerii unui accident considerabil. Pentru a simplifica problema și mai mult, pe parcursul traseului se pot adăuga diferite sisteme care ar putea oferii informatii utile mașinii în timp real. Cele mai comune mașini autonome încearcă să strângă aceste informați prin intermediul unor tehnologii precum [3] :

Radare bazate pe folosirea undelor de frecvență scăzuta,

Radare bazate pe tehnologii laser (Lidar),

Senzori ultrasonici,

Senzori cu raze infraroșii,

Camere video.

Cu ajutorul unor astfel de tehnologii se pot identifica semnele de circulație, culoarea la semafor, oamenii de pe trecerea de pieton sau alte informații necesare pentru a putea controla un astfel de autovehicul. Totuși, în mediul real, un astfel de sistem este periculos, deoarece apar foarte multe variabile, iar cu cât numărul variabilelor este mai mare, cu atât crește riscul de apariție a situaților care nu au fost luate in considerare [22]. Majoritatea decizilor luate de către inteligența artificială a mașinii trebuie să fie similare cu decizile pe care un șofer real le-ar lua în aceeași situație. Totuși, există situații în care decizia umană nu este întotdeauna cea mai bună variantă. În acest sens se poate discuta despre capacitățiile superioare ale calculatoarelor și ale tehnologiilor care preiau informațiile din mediu exterior. Ca de exemplu, se pot monta mai multe camere video pe masină, care pot depășii cu mult capacitațile vizuale ale oamenilor. Astfel, unele pericole care nu pot fi detectate de către oameni, ar putea fi detectate cu ajutorul unor astfel de tehnologii. De asemenea se poate discuta și despre caracterul previzibil al șoferilor. Ray Fuller [4], propune un sistem bazat pe un arbore decizional, capabil sa prezică anumite decizii luate de către șoferi în diferite situații. Toate aceste situații vor fi identificate și se vor urma anumite protocoale pentru a lua deciziile corespunzătoare. Astfel, sistemul va încerca constant, să plaseze situația curentă într-un protocol cunoscut.

Această lucrarea propune o abordare puțin diferită prin care se încearcă să se i-a în considerare, atât funcționalitatea mașinii, cât și sistemul de drumuri, reducând astfel numărul variabilelor la minim. Soluția propusă, constă în maparea tuturol regulilor de circulație și a sistemului de drumuri într-o hartă digitală. Se presupune că mașina e echipată cu un sistem GPS capabil să transmita poziția mașinii cu o acuratețe de ordinul centimetrilor. Cu ajutorul acestor informații se poate renunța la identificarea regulilor de circulație, a semafoarelor, sau a trecerilor de pieton prin intermediul dispozitivelor prezentate mai sus. Fiecare semafor, va trimite starea sa în timp real, iar pozițile regulilor de circulatie vor fi cunoscute. În ideea de a creea un sistem cât mai sigur, se pot folosii doar treceri de pieton semaforizate sau semafoare cu buton. Câteva sisteme care pot ajuta în acest sens vor fi discutate în capitolele următoare. Astfel în cadrul simulatorului se vor testa doar condițiile logice, prin intermediul cărora se pot testa si gestiona diferite protocoale. Realizarea unui astfel de simulator asigură crearea structurii logice a inteligenței artificiale, fără a lua în considerare funcționalitatea diferitelor sisteme care sunt responsabile cu preluarea informaților din mediul exterior.

Scurtă descriere a sistemului

Pentru a putea testa scenarii cât mai realiste, e nevoie ca harta să se apropie cât mai mult de realitate. În acest sens a fost dezvoltată o aplicație, care procesează o imagine a unei hărti Google și o convertește într-o structură de date. O astfel de hartă poate fi obținută și prin alte modalități. Motivul pentru care a fost aleasă această opțiune, este dat de faptul ca harta poate fi editată prin simpla editare a imaginii. Astfel se pot studia și efectele modificării sistemului de drumuri. Din acea hartă, se poate apoi construi în mod automat traseul mașinii. Traseul mașinii va fi reprezentat de totalitatea punctelor care trec prin mijlocul benzii străzii. Astfel, mașina va fi comandată sa meargă din punct în punct cu o anumita viteză până ce ajunge la destinație.

De-a lungul acelei linii se vor plasa instrucțiuni de forma: ajungi la 30 km/h, oprește și verifică strada “x”, verifică semaforul “x” sau alte instrucțiuni asemănatoare. Mașina va încerca întotdeauna să atingă o anumită viteză și să se îndrepte spre un anumit punct. Aceasta va fi partea statică a simulatorului. În acest caz, mașina va merge asemănator cu un tren, fară a fi deranjată de mediul exterior. Partea dinamică, va fi reprezentată de factorii imprevizibili care pot apărea pe parcursul traseului. Dacă, de exemplu în fața mașinii autonome se află o mașina care se deplasează mai încet decât limita legală, atunci mașina va fi nevoită să încetinească. În acestă situație controlerul dinamic va prelua controlul mașinii și o va încetinii. De asemenea, pe parcursul traseului se pot plasa diferite obiecte statice sau dinamice pentru a testa reacțiile mașinii. Astfel, se pot testa diferite scenarii care pot apărea în realitate, fară a lua în considerare sistemele care sunt folosite la identificarea obiectelor.

Algoritmul care controlează mașina când aceasta virează a fost implementat într-un mod realist. Acest lucru poate ajuta în ideea în care sistemele de control ale mașinilor, pot fi testate în cadrul simulatorului, iar apoi pot fi ușor translatate în mediul real.

Clasificarea modeleleor de simulare a traficului rutier

Realizarea modelelor matematice pentru a simula diferite scenarii este constrânsa de capacitățile sistemului de calcul pe care va rula simularea. Această limitare poate duce uneori la nevoia de a renunța la anumite detalii, pentru a putea realiza simularea cu succes. Conform cu B.J.A de Graaf [5], modelele de simulare ale traficului rutier se pot clasifica în trei categorii, după nivelul de detaliu al simulării: microscopic, macroscopic, mesoscopic.

Modelul microscopic: este folosit pentru a studia comportamentul individual al fiecărei mașini în parte. În cadrul acestei simulări sunt luați în considerare parametrii care definesc caracteristicile individuale ale fiecărei mașini: accelerația, decelarația, viteza sau comportamentul șoferului.

Modelul macroscopic: acest model este folosit pentru a descrie traficul rutier la un nivel înalt, desconsiderând comportamentul individual al fiecărei mașini. Parametrii care sunt luați în considerare în acest caz sunt: debitul mașinilor, densitatea mașinilor, viteza medie sau accelerația medie.

Modelul mesoscopic: este folosit pentru a studia traficul rutier la un nivel mediu de detaliu. Modelul este descris de K. Li si P. Ioannou [6] ca fiind un model capabil să prezică densitatea și viteza medie la un nivel macroscopic, dar totuși să păstreze și unele caracteristici din modelul microscopic.  Unele modele mesoscopice sunt realizate pe baza analogiei între teoria gazelor și debitul mașinilor.

Pentru a simula și testa un vehicul autonom, este necesar să se folosească modelul microscopic. Acest model presupune folosirea unui sistem de calcul cu multe resurse la dispoziție, deoarece trebuie să fie capabil să reproducă un nivel de detaliu ridicat. Deși fiecare mașina trebuie tratată individual, nivelul de detaliu poate fi redus sau ridicat prin realizarea unor desene mai mult sau mai putin sofisticate. In figura 1.1 este prezentat un model de simulare realizat la nivel microscopic. Se poate observa că, în acest caz, modele realizate pentru reprezentarea mașinilor sunt destul de sofisticate. Pentru a crește eficienta sistemului, în locul acestor modele se pot desena simple figuri geometrice. Acest lucru este posibil, deoarece un model de simulare nu trebuie neaparat să ia în considerare partea estetică. Datele culese dintr-o astfel de simulare sunt relevante și dacă se folosesc modele mai puțin sofisticate.

Figura 1.1 Modelul microscopic de simulare

OBIECTIVE ȘI SPECIFICAȚII

Obiective

Principalele obiective ale sistemului sunt urmatoarele:

Obținerea unei hărți realiste în format digital.

Posibilitatea de a edita harta după ce aceasta a fost importată în simulator: elevarea și curbarea străzilor, modificarea regulilor de circulație, modificarea conexiunilor dintre străzi.

Posibilitatea de a vizualiza scenariul de oriunde din spațiul tridimensional și de la bordul oricărei masini.

Obținerea unui model matematic pentru controlul mașinii și posibilitatea de a configura parametrii acestuia, pentru a putea simula mai multe modele de mașini.

Crearea unei inteligențe artificiale pentru controlul mașinii capabilă să simuleze comportamentul unei mașini aflate în trafic.

Posibilitatea de a conecta în rețea mai multi utilizatori, în cadrul aceluiași scenariu.

Specificațile sistemului

Specificațiile structurale ale sistemului

Arhitectura sistemului se bazează pe utilizarea unui server care este folosit la centralizarea datelor. Această arhitectură este necesară dacă se dorește conectarea în rețea a mai multor utilizatori. Principala responsabilitate a serverului este centralizarea datelor și mai puțin oferirea resurselor, deoarece majoritatea calculelor se vor efectua pe stațiile individuale ale fiecărui utilizator. Din acest motiv, se poate spune că arhitectura tinde mai mult spre o arhitectură peer-to-peer. Totuși, este necesară folosirea unui server centralizat pentru a sincroniza transferul de date între utilizatori. Comunicarea între server și client se va realiza pe baza protocolului de comunicare TCP/IP(Protocol de control al transmisiei/Protocol Internet). În figura 2.1. este prezentată arhitectura sistemului.

Figura 2.1 Arhitectura sistemului

Specificațiile funcționale ale sistemului

Bază de date centralizată: Serverul conține unica bază de date a sistemului în care sunt păstrate următoarele componente: modelele de mașina, hărțile, scenarile și utilizatorii. Folosirea unei baze de date centralizată este necesară pentru a asigura sincronizarea întregului sistem. Daca un utilizator plasează ceva în baza de date, atunci toți utilizatorii vor avea acces la acea informație.

Distributivitate: Deoarece modelul pe care se bazeaza simularea este un modelul microscopic, fiecare mașina trebuie tratată individual. Acest lucru permite distribuirea calculelor pe mai multe fire de execuție sau chiar pe mai multe stații de lucru.

Scalabilitate: Această proprietate se manifestă atât la nivel hardware cât și la nivel software. La nivel hardware se manifestă datorită posibilității de a rula unele calcule pe mai multe stații de lucru, iar la nivel software este dată de posibilitatea de a adaugă componente noi în cadrul simulatorului. Acest lucru se poate realiza prin intermediul bazei de date centralizate. Pentru introducerea unei componente noi, nu trebuie decât să se introducă o nouă înregistrare în baza de date.

Drepturi de acces: În sistem vor exista mai multe tipuri de utilizatori: utilizatori finali si administratori. Administratorii se vor ocupa de: managementul utilizatorilor și a bazei de date, iar utilizatorii finali vor avea diferite drepturi în cadrul scenarilor: de a vizualiza, de a conduce mașina și de a configura scenariul.

Administrarea conturilor utilizatorilor: Administratorul este responsabil de adăugarea utilizatorilor în sistem. Fiecare utilizator va primii un nume și o parola care vor fi adăugate în baza de date. Pe langă aceasta în baza de date se vor mai salva și eventualele configurări ale fiecărui utilizator

Controlul mașinii: Controlul mașinii trebuie să se poata realiza de la tastatură, dar se poate folosii și un dispozitiv special, asemănător cu cel prezentat în figura 2.2. Dispozitivul trebuie să ofere doua informații: unghiul de rotire al volanului, și deplasarea pedalei de accelerație. Atașarea unui astfel de dispozitiv este opțională.

Comunicare eficientă: Timpul de răspuns între client și server trebuie să fie cât mai mic, în special în timpul rulării unui scenariu. La inițializarea unui scenariu se va trimite o cantitate mai mare de informații și este de așteptat ca procesarea să dureze mai mult. De altfel, acest lucru nu constituie o problema prea mare. O dată ce scenariul a fost inițializat, cantitatea de informații schimbată între clienți și server va scădea, deoarece se vor trimite doar informații de reactualizare.

Figura 2.2 Dispozitiv special de conducere a mașinii

Specificațile funcționale ale simulatorului

Funcționalitățile simulatorului se împart în trei categorii:

Editarea hărtii,

Editarea scenariului,

Rularea scenariului.

Editarea hărtii

VIZUALIZARE – caracterul (camera) se poate plimba liber prin tot spatiul 3D folosind săgețile și mouse-ul, asemanător unui joc de tip shooter, doar că deplasarea se poate realiza și în sus sau în jos.

ÎNCĂRCAREA HĂRTII – imaginea unei hărtii Google va fi procesată și încărcată în mediul tridimensional. Străziile vor fi încărcate în mod implicit, într-un plan bidimensional, la nivelul zero. Dacă se dorește încărcarea unei hărți tridimensionale, atunci se poate dezvolta un mecanism prin care să se încarce și o imagine alb-negru care să reprezinte înălțimile

EDITAREA HĂRTII– intersecțiile pot fi selectate prin specificarea numărului intersecției, iar străziile prin specificarea numărului a doua intersecții. După ce o stradă a fost selectată, se poate alege opțiunea de a selecta doar o porțiune din ea. Numărul de porțiuni în care va fi împărtita strada poate fi specificat. Cu cât numărul e mai mare cu atât porțiunea va fi mai mică. Prin folosirea săgețiilor se poate schimba selecția. Orice selecție din cadrul hărtii poate fi ștearsă: intersecție, stradă, porțiune de stradă. În același timp se poate alege să se conecteze doua puncte selectate, adăugându-se astfel o strada. Structura logică în care este păstrată harta va fi rearanjata automat.

ELEVAREA TERENULUI ȘI A STRĂZILOR – elevarea terenului nu este același lucru cu elevarea străzilor. Dacă o stradă este elevată, terenul nu e neaparat elevat. Dacă se alege această opțiune, atunci coordonatele fiecărui punct care alcătuiește acea selecție vor fi ridicate sau lăsate jos, paralel cu pământul. În mod similar orice stradă poate fi curbată. După ce o porțiune de stradă a fost selectată, aceasta se poate deplasa în fată/spate sau în stângă/dreapta.

ADĂUGAREA OBIECTELOR – modelele create pentru diferite obiecte precum: semne de circulație, semafoare sau obiecte decorative se pot adăuga prin selectarea unui punct de pe pământ sau prin precizarea unor coordonate. Obiectele pot fi rotite, mutate sau șterse.

Editarea scenariului

CONFIGURAREA MAȘINILOR – modelul mașinii a fost creat cu ajutorul aplicației Blender, dar se poate folosii oricare alt program atâta timp cât modelul poate fi exportat într-unul din următoarele formate:

3dm

.3ds

.blend

.bvh

.c4d

.dae

.fbx

Pentru cele patru roți ale mașinii trebuie create modele separate deoarece roțile din fața se vor roti independent de mașina pentru a putea vira. Lungimea, lătimea și înaltimea mașinii trebuie precizate. Aceste caracteristici sunt necesare pentru a putea detecta coliziunile și a putea configura sistemul de direcție. Fiecare mașina va avea un fișier de configurare în care se vor preciza următoarele caracteristici:

Adresa unde este localizat modelul mașinii

Adresa unde este localizat modelul roților

Curba de accelerație

Curba de decelerație

Unghiul maxim de virare

Coordonatele inițiale ale poziției mașinii

Viteza inițiala a mașinii

Lungime

Lățime

Inălțime

CONFIGURAREA TRASEULUI – traseul mașinii se va preciza în fișierul de configurare al fiecărei mașini. Traseul între două puncte poate fi generat și automat, dar dacă se dorește precizarea unui anumit traseu, atunci o astfel de soluție nu mai poate fi folosită. Pentru a configura un traseu se vor preciza toate intersecțiile prin care va trece mașina. Pe baza acestor informații se vor genera toate punctele care trec prin centrul benzii. Pentru simplitate se va considera doar cazul în care strada are o singură bandă pe sensul de mers. Aplicația poate fi îmbunătățită pentru a suporta mai multe benzi.Traseul poate fi ciclic, sau poate începe într-un punct și să se termine în altul. Un exmplu pentru configurarea unui astfel de traseu este prezentat mai jos:

Traseu: pozitie inițiala, intersecție1, intersecție2, intersecție3, intersecție4…

CONFIGURAREA INTSTRUCȚIUNILOR – instrucțiunile pot fi generate automat din semnele de circulație sau pot fi plasate în fișierul de configurare al mașinii. Fiecare mașina va avea un contor, care va măsura distanța pe care aceasta a parcurs-o. În fișierul de configurare al mașinii se poate preciza un nod de forma:

Instrucțiuni: dupa 30 de metri, instrucțiune1, dupa 150 de metri, instrucțiune2….

Prin aceasta modalitate se pot preciza instrucțiuni individuale pe care vrem să le dăm fiecărei mașini în parte. Această modalitate de configurare a instrucțiunilor este necesară deoarece, nu vrem întotdeauna ca o anumită mașină să respecte regulile clasice de circulație.

CONFIGURAREA ORARULUI – configurararea orarului fiecărei mașini se va realiza prin specificarea orei la care mașina trebuie să înceapă să execute instrucțiunile primite. Pentru configurarea orarului se pot realiza diferite mecanisme prin care se pot lua în considerare și alți parametrii.

Rularea scenariului

VIZUALIZAREA SCENARIULUI – Scenariul poate fi vizualizat de oriunde, prin utilizarea modului liber de vizualizare sau poate fi vizualizat de la bordul unei mașini. De asemenea, daca se dorește, se poate participa la scenariu prin preluarea controlului unei mașini. Dacă o mașina a fost selectată, atunci se poate alege opțiunea de a vizualiza traiectoria mașinii. Vizualizarea traiectoriei mașinii este o opțiune foarte utilă, deoarece se poate studia în detaliu modalitatea prin care inteligența artificială a mașinii funcționează. În acest sens pot fi dezvoltate ulterior mecanisme prin care se pot vizualiza și alți parametrii precum: viteza, accelerația sau alte mărimi care pot fi utile

REVIZUALIZAREA SCENARIULUI – prin folosirea unei astfel de opțiuni, utilizatorul poate vizualiza scenariul asemăntor unui film având cele patru opțiuni clasice:

Înainte/ înapoi

Repede înainte/ Repede înapoi

Start/pausă

Deplasarea cursorului în orice punct temporal

Opțiunea este utilă și în cazul în care performanțele calculatorului nu permit vizualizarea în timp real a scenariului. Această tehnică, se folosește destul de des în realizarea diferitelor simulări de un grad de complexitate ridicat. De altfel, calculatoare din ziua de astazi impun limitări mari în realizarea simulărilor realiste. Motiv pentru care de multe ori se renunță la detalii.

Specificațiile funcționale ale clientului

CONECTARE – prima operatie pe care orice utilizator trebuie să o facă este să se conecteze la sistem prin introducerea ip-ului și portul serverului.

LOGARE – după ce s-a conectat, clientul se poate loga în simulator prin introducerea numelui și a parolei. Pentru ca logarea să se realizeze cu succes, numele si parola trebuie validate de către server.

ALEGEREA/EDITAREA SCENARIULUI – o dată logat, administratorul pune la dispoziția utilizatorilor mai multe scenarii (simulări) în care aceștia pot intra. Dacă au drepturille necesare, utilizatorii pot alege să creeze un scenariu nou sau să editeze un scenariu existent.

DREPTURILE UTILIZATORILOR:

Dreptul de a vizualiza: utilizatorul nu are nici un drept, decât să privească scenariul. Acesta poate alege să privească de la bordul unei mașini sau să se deplaseze în modul liber.

Dreptul de a interacționa: utilizatorul are dreptul de a interacționa cu scenariul prin preluarea controlului unei mașini. Mașinile si configurările ei sunt puse la dispoziție prin intermediul bazei de date.

Dreptul de editare: utilizatorul are dreptul de a edita scenariul. Pentru a edita un scenariu, utilizatorul trebuie să configureze: harta, traseele și să aleagă modelele de mașini din simulare.

Specificațiile funcționale ale serverului

PORNIREA/OPRIREA SERVERULUI – O dată ce serverul a fost pornit, acesta va pune la dispozitie o adresă de ip și un port utilizatorilor, pentru ca aceștia să se poată conecta. Serverul poate fi folosit pentru a pune la dispozitia clienților diferite informații de care aceștia au nevoie pentru a rula scenarii: hărti, modele de mașina, sau chiar scenarii gata configurate. Dupa ce serverul a fost pornit și s-au conectat la el mai mulți utilizatori, aceștia se pot conecta în rețea în cadrul aceluiași scenariu

ADMINISTRAREA BAZEI DE DATE – înregistrările trebuie introduse în baza de date de către o persoana autorizată. Acest lucru este necesar, deoarece o persoana care nu are experienta cu această aplicație, poate introduce înregistrări care pot dăuna sistemului.

ADMINISTRAREA CONTURILOR UTILIZATORILOR – administratorul va creea și gestiona conturile utilizatorilor. Fiecare utilizator va primi drepturi, acest lucru fiind necesar pentru a putea asigura buna funcționare a aplicației.

STUDIU BIBLIOGRAFIC

Avantajele utilizării unui simulator

Conform cu Norbert Grunwald [7] avantajele oferite de utilizarea unui simulator pentru a dezvolta sisteme de control a roboților sunt următoarele:

Realizarea rapidă a prototipelor: ideile pot fi implementate cu ușurinta chiar dacă anumite piese hardware nu sunt accesibile. Se pot astfel dezvolta și testa diferite sisteme de control a roboților fără a lua în considerare partea hardware.

Testare separată: diferiți algoritmi care sunt folosiți pentru a controla robotul pot fi testați separat datorită flexibilității în realizarea scenarilor.

Repetabilitate: testele pot fi rulate rapid în nenumărate rânduri fără dificultăți prea mari. În mediul real repetabilitatea testelor poate devenii o problemă, deoarece realizarea unui scenariu este de cele mai multe ori o dificil de realizat.

Posibilitatea de a compara rezultatele testelor: rezultatele pot fi comparate într-o manieră obiectivă. Acest lucru nu este atât de ușor de realizat în lumea reală, deoarece pot intervenii și alte variabile care pot pune în discuție acuratețea rezultatelor. În unele cazuri, aceste variabile care nu au fost luate în considerare pot dăuna sistemului. Totuși, simulatorul nu este conceput pentru a prezice orice situație. Testele rulate în lumea reală pot ajuta la îmbunătățirea simulatorului. Astfel, variabilele care nu au fost luate în considerare, pot fi integrate ulterior în cadrul simulatorului.

Automatizare: testele pot fi rulate automat, chiar în timpul dezvoltării noilor algoritmi. Fiecare modificare a sistemului poate pune în pericol vechiul sistem. Un bun exemplu în acest sens este utilizarea unit-testelor. Testele sunt rulate automat cât de des posibil, pentru a verifica constant dacă noii algoritmi se integrează în sistem.

Vizualizare: parametrii sistemului sunt accesibili utilizatorului. Folosind acești parametrii se pot realiza cu ușurintă diferite sisteme grafice care pot ajuta în acest sens. Vizualizarea într-o simulare nu impune nici o constrângere, spre deosebire de mediul real, unde accesul la diferiți parametrii ai sistemului poate pune diverse probleme.

Siguranța: deseori, în mediul real pot apărea situații în care se poate pune în discuție siguranța utilizatorilor. În cadrul unei simulari aceste situații sunt excluse cu desăvârșire.

Costuri scăzute: piesele tehnologice și munca depusă pentru realizarea unui robot pot să aibă un cost ridicat. Un risc mare provine din faptul, că în lipsa realizării unei simulări, sistemul poate fi conceput greșit de la bun început. Prin folosirea unei simulări, acest risc scade considerabil. Astfel, un sistem de simulare se poate folosii cu succes și în scop educativ, nu doar pentru a dezvolta sistemelor de control al roboților

Realizarea oricărui sistem, presupune anumite riscuri. Pe baza celor prezentate mai sus, se poate spune că un simulator reduce o mare parte din aceste riscuri. Acest lucru este posibil deoarece sistemul poate fi testat și optimizat înainte de a fi implementat în mediul real. În unele cazuri, testarea si optimizarea sistemului ar fi imposibile fără ajutorul unui simulator, deoarece crearea condiților dorite nu este întodeauna atât de ușor de realizat. În cadrul simulatorului, orice parametru poate fi modificat cu ușurinta pentru a realiza orice scenariu. Astfel, se poate spune că utilizarea unui simulator pentru dezvoltarea sistemelor de control a roboților este o necesitate.

Aplicabiliatea simulatoarelor de trafic

În ultimii ani, simularea traficului rutier, s-a dovedit a fi o metodă din ce în ce mai eficientă pentru rezolvarea diferitelor probleme care apar în mod inevitabil o dată cu creșterea numărului de mașini. În continuare sunt prezentate câteva domenii, în care simularea traficului poate ajuta semnificativ:

Congestia si decongestia traficului: Amplasarea semafoarelor, sensurilor giratorii sau a altor semne de circulație poate avea un efect benefic în anumite circumstante, dar dacă intervin și alți factori, aceste componente pot dăuna grav circulației rutiere. Schimbarea vremii, este un bun exemplu în acest caz. Numărul mașinilor aflate în circulație poate crește sau descrește rapid o dată cu schimbarea condiților meteorologice. În zonele urbane traficul rutier poate scăpa ușor de sub control. Simulând astfel de scenarii, aceste probleme pot fi identificate și remediate înainte ca ele să apară.

Mijloacele de transport în comun: transportul în comun este o necesitate în orice oraș dezvoltat. Controlul unui astfel de sistem poate devenii o probleme majoră, deoarece în acest caz se impune un orar care trebuie respectat. Amplasarea diferitelor centre comerciale poate afecta ușor un asemenea sistem [8]. Un studiu făcut în acesta direcție poate ajuta în crearea unui sistem flexibil, care se poate adapta ușor oricărei situații.

Transportul de mărfuri: planificarea traseului între furnizori și beneficiari poate scădea semnificativ costurile și poate ajuta în reducerea timpului de livrare. Un studiu făcut de o companie poștala din America arată că, dacă traseul mașinii este planificat în așa fel încât să realizeze cât mai multe viraje la dreapta, se poate reduce consumul de combustibil semnificativ. Prin folosirea unei astfel de strategii se asigură și reducerea timpului de livrare, deoarece mașina nu mai trebuie să oprească pentru a da prioritate sau pentru a se asigura. O altă solutie inovativă a fost propusă de U. Franke [9], care descrie un sistem de transport al mărfurilor bazat pe utilizarea unui sistem de urmărire. Astfel, un camion condus de un șofer real, ar putea fi urmărit în mod automat de restul camioanelor. Prin utilizarea unui astfel de sistem forța de frecare dintre camione este redusă și astfel se reduce și consumul de combustibil.

Servicile mobile de urgență: deplasarea ambulanțelor, a mașinilor de pompieri sau a altor autospeciale trebuie să se realizeze într-un interval de timp cât mai scurt, oriunde este nevoie. Pornirea girofarului nu asigură întotdeauna efectul dorit, deoarece poate pune în pericol restul circulației. În acest scop au fost dezvoltate sisteme inteligente, prin care culorile semafoarelor se modifica în așa fel încât se crează o cale liberă pentru autospeciala respectiva. Realizarea unui astfel de sistem impune utilizarea unui simulator, deoarece pot apărea mulți factori imprevizibili.

Poluarea mediului inconjurător: datorită folosirii combustibilor fosili ca sursă principală de energie, poluarea a crescut considerabil în zonele urbane în ultimii ani. Totuși, eliminarea poluării nu este posibilă în momentul de față, dar se pot dezvolta diferite sisteme care pot ajuta la reducerea poluării. Simulări realizate în această direcție au arătat că poluarea poate fi redusă considerabil prin folosirea mașinilor semi-automate [10]. Mașinile semiautomate s-au dovedit a avea un succes deosebit datorită faptului că unele manevre pot fi efectuate prin folosirea unor algoritmi matematici de optimizare. O altă soluție pentru a remedia problema poluării este dirijarea traficului spre zone mai puțin populate. O astfel de măsura poate asigura atât reducerea poluarii cât și reducerea numărului de mașini din zonele supraaglumerate.

Siguranța traficului rutier: Numărul accidentelor rutiere este ingrijorator de mare în fiecare an. Accidentele sunt cauzate atât de neatenția șoferilor, cât și de amplasarea necorespunzătoare a diferitelor reguli de circulație. Au fost creeate în această directie diferite sisteme avertizare și de control a mașinii, care pot ajuta în reducerea numărului accidentelor. Folosirea unui simulator poate ajută în această situație la descoperirea zonelor de risc în infrastructura drumurilor.

Sisteme de control de avertizare si semi-automate

Evoluția tehnologiei din ultimiii ani a permis dezvoltarea unor sisteme de control a autovehiculelor care pot ajuta semnificativ la îmbunătățirea calitații traficului rutier. Dezvoltarea acestor sisteme a fost posibilă o dată cu creșterea puterii de calcul a calculatoare și în consecință micșorarea timpului de răspuns. În continuare sunt prezentate câteva sisteme promițătoare care au fost dezvoltate până în momentul de față.

Urmează liderul

Acest sistem mentine viteza mașinii constantă la o anumită valoare dacă aceasta nu are nici o alta mașină în fața ei. Dacă există o altă mașina în fata ei, atunci sistemul reglează viteza mașinii în așa fel încât să păstreze o distanță de siguranță cât mai mică față de vehiculul respectiv. Detectarea mașinilor se face cu ajutorul tehnologiei radar sau prin folosirea unor dispozitive wireless de comunicare. Conform cu C. Kreuzen [11], un astfel de sistem poate fi realizat fie prin folosirea unui regulator de tip PID, fie prin folosirea unui controler bazat pe modelul predictiv al mașinii. Regulatorul PID preia eroarea între distanța de referință și distanța actuală, iar pe baza unei funcții de transfer trimite o comandă mașinii pentru a regla viteza în așa fel incât să se apropie cât mai mult de distanța de referintă. Al doilea model e considerat o variantă mai avansată o regulatorului PID. Acesta preia datele inițiale după care încearcă să facă o predicție. Pe baza acestei predicții se trimite un semnal de comandă mașinii pentru a păstra distanța dorită. Testele rulate pentru cele două modele arată superioritatea controlorului bazat pe modelul predictiv al mașinii.

Prin folosirea unui astfel de sistem se asigură păstrarea distanței optime între mașini, scăzând astfel riscul producerii unui accident. Un alt avantaj care rezultă din micșorarea distanței dintre mașini, este dat de faptul că forța de frecare între autovehicul și aer scade. Cu cât mașinile sunt mai apropiate, cu atât consumul de combustibil va scădea. Micșorarea distanței între mașini fără ajutorul unui sistem specializat poate pune în pericol circulația rutieră.

Un alt sistem util care se poate realiza în scopul reducerii distanței între mașini este comandarea mai multor mașini să pornească în același timp. Un bun exemplu în acest sens, este pornirea mașinilor aflate în coloana la un semafor. În acest caz, un sistem centralizat ar putea comanda toate mașinile să pornească în același timp o dată ce culoarea semaforului este verde. Astfel s-ar anihila efectul de undă, care apare când mașinile pornesc una câte una din coloana. P.Fernandes si U. Nunes  [12], descriu un sistem în care autovehiculele pot fi organizate în grupuri, despărțite prin distanțte cât mai mici. Folosind astfel de grupuri, un asemenea de sistem ar fi mai ușor de realizat.

Cooperarea vehiculului cu infrastructura drumurilor

O altă abordare prin care se încearcă creșterea calității traficului rutier este plasarea unor dispozitive de comunicare și de analizare în infrastructura drumului. Cu ajutorul acestor dispozitive, mașina poate primii informații în timp real referitor la viteza legală pe acel segment de drum sau se pot strânge informații referitor la densitatea mașinilor și viteza cu care se circula. Aceste informații pot fi apoi centralizate și communicate altor autovehicule. Evolutia acestui sistem a fost posibilă, o dată cu evoluția tehnologiilor wireless de comunicare. Bobby J.W. Nijssen [13] descrie patru moduri de comunicare posibile într-un astfel de sistem:

Vehicul si vehicul (V2V)

Vehicul si infrastructură (V2I)

Infrastructură si vehicul (I2V)

Infrastructură si infrastructură (I2I)

Schimbul de informații prezentat mai sus poate fi folosit în principal ca mijloc de avertizare a șoferilor. Un bun exemplu în acest sens este avertizarea șoferilor în legătura cu un accident care s-a produs sau avertizarea șoferilor că au depașit viteza legală. Avertizarea șoferilor în legătură cu un accident care s-a produs este deosebit de importantă, deoarece semnalizarea unui accident nu este întotdeauna o modalitate eficientă de a proteja restul circulației. Preluarea controlului mașinii presupune totuși anumite riscuri, motiv pentru care o mașina care a depășit viteza legală nu poate fi încetinită într-un mod automat. Totuși se pot realiza în acest sens sisteme mai avansate de monitorizare care pot avea rol atât în a-l descuraja pe șofer să depașească viteza legală, cât și în a strânge informații statistice pentru a îmbunătății sistemele de drumuri.

Asistentă în păstrarea mașinii în interiorul benzii de circulație

Acest sistem este folosit pentru a păstra mașina pe traseul dorit. De fiecare dată când mașina depașește linia care delimitează banda de restul drumului, șoferul este avertizat printr-un semnal sonor. Un sistem mai avansat poate chiar să intervină pentru a modifica traiectoria mașinii în așa fel încât să păstreze mașina pe centrul benzii. Un astfel de sistem a fost conceput de către firma Honda. Totuși, sistemul creeat de Honda acționeaza doar în proporție de 80% pentru a schimba traiectoria mașinii, restul de 20% trebuie să fie realizat de către sofer[14]. Sisteme similare au fost create și de către alte firme, dar este dificil de spus care algoritm este cel mai bun având în vedere numărul mare de variabile care apare în aceasta situație.

Sistemul prezentat poate detecta devierea mașinii de la traseu prin identificarea linilor care marcheaza marginea benzii. Identificarea liniei se realizează cu ajutorul unor camere video montate pe mașina. Cunoscând coordonatele liniei se poate calcula apoi, la ce unghiu trebuie mașina să vireze pentru a rămâne pe centrul benzii. Sistemul este totuși destul de periculos datorită faptului ca identificarea linilor de pe străzi cu ajutorul unor camere video nu este o soluție sigură.

O solutie mai simplă, dar mai dificil de implementat, constă în amplasarea unor striații pe liniile care se doresc a fi semnalate. La contactul între roata mașinii și aceste striații se produce un sunet, care cel mai probabil va fi auzit de șofer. Acest sistem nu ofera posibilitatea de a ghida mașina în interiorul benzii, ci doar de a-l avertiza pe șofer. Totuși, preluarea controlului mașinii de către un controler, care redirecționează mașina în mod automat spre centrul benzii, poate pune în pericol restul traficului. Se pune problema în acest caz, dacă nu cumva șoferul chiar dorește să schimbe banda, iar controlerul dirijează mașina spre un accident. Astfel de situatii sunt foarte greu de identificat, motiv pentru care sistemul trebuie activat și dezactivat manual.

Monitorizarea locurilor de parcare

V. Tang [15] descrie în lucrarea sa un sistem de monitorizare a parcărilor prin plasarea unor senzori în fiecare loc de parcare. Cu ajutorul acestor senzori se poate identifica dacă un loc de parcare este liber sau ocupat. Aceste informatii sunt apoi centralizate într-o bază de date care poate fi accesată de către fiecare șofer. Cu ajutorul acestei baze de date se poate creea un sistem bazat pe rezervări. Informatia transmisa de către senzori, este inutilă în lipsa unui astfel de sistem, deoarece locul de parcare se poate ocupa în timp ce șoferul se indreaptă spre acesta.

Implementarea sistemului se poate realiza cu ușurință, o dată ce infrastructura sistemului de senzori a fost realizată. Acest lucru este posibil o dată cu apariția SmartPhone-urilor, care oferă utilizatorului posibilitatea de a se conecta la internet și de a folosii tehnologia GPS într-o manieră foarte accesibilă.

Astfel de tehnologii ar fi utile și pentru folosirea unui vehicul autonom. Dacă un autovehicul autonom care este programat să meargă pe un anumit traseu, nu găsește un loc de parcare liber, atunci acesta ar fi obligat să se învartă în cerc până ce locul de parcare s-ar elibera. Cu ajutorul sistemului prezentat această situație nu ar mai apărea.

Asistență în parcarea mașinii

Parcarea este de cele mai multe ori o problemă dificilă pentru șoferi, motiv pentru care s-a încercat dezvoltarea unor sisteme care pot parca mașina într-un mod automat. Un astfel de sistem reconstruiește spațiul 3D în care se află mașina, si generează o traiectorie care o va duce în locul de parcare dorit. Și aceste sisteme sunt folosite doar în asistarea soferului, volanul fiind controlat de către sistem doar într-o anumită proporție[20].

Deși sistemele prezentate sunt doar de avertizare sau semiautomate, se poate spune că cercetarea în domeniul vehiculelor inteligente s-a dovedit a fi un succes.

Semaforizare inteligentă

Scopul lucrării constă în descrierea unui sistem care poate ajuta la creșterea calității traficului rutier, în mod special din zonele urbane. Se propune în acest sens dezvoltarea unui sistem inteligent de semaforizare, care să se integreze în structura actuală a sistemelor de drumuri, dar să și ajute în dezvoltarea sistemului de control al unei mașini autonome. Testarea unui astfel de sistem se va face prin compararea timpului mediu pe care o mașina îl petrece în trafic. În acest caz, trebuie luat în considerare timpul mediu pe care îl parcurge fiecare mașină, deoarece nu este acceptabil ca unele mașini să parcurgă un anumit traseu într-un timp extrem de mic, în timp ce altele să parcurgă un alt traseu într-un timp extrem de ridicat.

Sistemele de semaforizare au apărut ca o necesitate, o dată cu creșterea mare a numărului de mașini din zonele urbane. Aceste sisteme pot ajuta uneori în fluidizarea traficului, dar alteori pot pune probleme mari dacă nu sunt luate în considerare toate variabilele. Oprirea și așteptarea la un semafor presupune un consum în plus de combustibil și în același timp blocheaza circulația pe traseul respectiv. Aceste probleme au dus la nevoia dezvoltării unui noi tip de semafoare, și anume semafoarele inteligente. Prin folosirea acestor semafoare se încearcă să se găsească niște algoritmi capabili să optimizeze traficul din marile orașe. Totuși, niște algoritmi pentru aceste semafoare sunt greu de implementat, deoarece traficul rutier este foarte imprevizibil. Reglarea sistemului pentru un anumit scenariu, poate fi dezastruoasă în alte situații. Alejandro L´opez Vidal [15], descrie în lucrarea sa doua metode principale de control a semafoarelor: active și pasive. Utilizarea metodelor pasive presupune schimbarea culorilor semaforului la intervale fixe de timp, în timp ce prin metodele active culorile semafoarelor se schimbă în functie de mai multi parametrii. În continuare sunt prezentate câteva modalitați prin care semafoarele pot fi folosite, pentru a dirija traficul într-un mod inteligent:

Semafoarele cu buton: acest tip de semafoare este folosit de regulă pe străziile principale pentru a menține fluiditatea traficului și a permite pietonilor să traverseze în siguranță strada. Algoritmul care controlează un astfel de semafor este relativ simplu de descris. Pietonul apasă un buton, iar după un anumit interval de timp culoarea semaforului pentru pietoni se va face verde, în timp ce pentru mașini se va face roșu. Pentru a nu pune în pericol circulația mașinilor pe artera respectivă, se poate stabili un anumit interval de timp în care semaforul își păstrează culoarea verde pentru mașini. Un astfel de mecanism este necesar pentru a nu permite pietonilor să abuzeze de acest sistem. Avantajele folosirii acestui tip de semafor constau în faptul că se poate controla ușor circulația pe artera respectivă prin setarea timpilor semaforului și în același timp pietonii pot trece în siguranța strada. Pietonii în acest caz sunt ușor dezavantajați, deoarece nu pot trece strada când doresc. Totuși fluidizarea traficului este prioritară pe o arteră principală și un astfel de sistem se poate dovedii de cele mai multe ori foarte util.

Crearea liniilor verzi: această metodă este folosită tot pe arterele principale, în încercarea de a reduce consumul de combustibil și de a fluidiza traficul. Algoritmul de control al unui astfel de sistem constă în aproximarea timpilor în care mașina ajunge de la un semafor la altul, și schimbarea culorii semaforului în verde în momentul în care mașina a ajuns la urmatorul semafor. Avantajul oferit de un astfel de algoritm este dat de faptul că mașina poate parcurge traseul fără să mai oprească deloc, chiar dacă este necesară așteptarea unui timp mai îndelugat la primul semafor. Astfel se poate asigura reducerea consumului de combustibil, deoarece mașinile vor efectua un număr mai mic de opriri.

Algoritmi dinamici de reglare: acești algoritmi se pot folosii în intersecțiile în care traficul este relativ scăzut, iar străzile care se intersectează au o prioritate aproximativ egală. Pentru a implementa un astfel de sistem e nevoie de utilizarea unor senzori care să contorizeze numărul de mașini care se află pe fiecare stradă în parte. Cu ajutorul acestor informații se pot lua în unele cazuri decizii mai inteligente care pot ajuta la fluidizarea traficului rutier. Un bun exemplu în acest sens este dat de faptul că dacă se poate spune cu certitudine că o mașina are cale liberă, atunci semaforul ar trebui să îi permită acesteia să treacă. Astfel de situații pot apărea la folosirea semafoarelor clasice, care își schimbă culorile la intervale fixe de timp. Această situație este totuși un caz particular care poate apărea mai rar în marile intersecții. Sistemul menționat, este de regula folosit împreună cu un anumit algoritm de control, care dirijeaza intersecția în așa fel încât timpii medii pe care fiecare mașina îi petrece la intersecția respectivă, scad considerabil. În Fig 3.1 [15], sunt ilustrate principalele mărimi care trebuie cunoscute pentru a putea controla traficul într-un mod inteligent. Distanța d reprezintă, distanța de unde mașinile încep să fie contorizate. Când numărătorul depașește un anumit prag, culoarea de la semafor se va schimba și numărătorul se va reseta. Culoarea va rămâne verde un interval de timp prestabilit. Dacă se afla mașini la o distanță mai mică decât distanța r, atunci semaforul nu își va schimba culoarea, deoarece șoferul nu mai are timp să reacționeze. Dacă se afla mșini oprite la distanța e, atunci semaforul va permite mașinilor de pe artera secundară să treacă, deoarece artera este blocată.

Figura 3.1 Semafoare inteligente

Controlul semafoarelor în timp real: orice algoritm poate avea defectele lui, care nu pot fi luate în considerare la dezvoltarea lor. Uneori algoritmii pot fi ulteriori îmbunătățiți, dar este recomandat ca orice sistem să aibă un sistem de rezervă. E necesar în acest caz să se poată prelua controlul semafoarelor de către o persoană umană, pentru a putea asigura consistența sistemului. În momentul de față soluționarea unor astfel de probleme, se face de regulă prin plasarea unor politiști de circulație în marile intersecții pentru a dirija traficul. Totuși, o astfel de soluție poate fi înlocuită prin realizarea unui sistem centralizat de control, de unde să se poată prelua controlul semafoarelor. Astfel, marile intersecții ar putea fi vizualizate prin intermediul unor camere video și controlate într-o manieră inteligentă de la distanță. Realizarea unui astfel de sistem poate ajuta și în dezvoltarea ulterioară a unor algoritmi care pot remedia situațiile întâlnite într-un mod automat. Un alt avantaj oferit de acest sistem, este dat de faptul că timpul de răspuns scade semnificativ, și astfel problemele pot fi identificate și rezolvate mult mai devreme. Sistemul prezentat nu este totuși o noutate și se folosește în principal pentru a putea controla și gestiona traficul de pe autostrăzi. Implementarea unor astfel de sisteme pentru a putea vizualiza traficul de pe autostrăzi are un rol foarte de important, deoarece mașinile circulă cu viteză foarte mare și un accident poate pune ușor în pericol restul circulației.

Simulatoare de trafic existente

VISSIM

VISSIM este un simulator de trafic realizat pe baza modelului microscopic și a fost dezvoltat pentru a putea simula în principal traficul din zonele urbane. Simulatorul a fost conceput în anul 1972 și în prezent este un lider pe piața mondiala. Principalul avantaj oferit de acest simulator este capacitatea sa de a simula mai multe tipuri de trafic:

autovehicule,

mijloace de transport în comun,

biciclete,

pietoni

trăsuri.

Principile matematice care stau la baza acestui simulator au fost descrise de către Rainer Wiedemann în anul 1974 la Universitatea Karlsruhe din Germania și se bazează pe modelul de urmărire a mașinii din față. Acest model este construit pe baza comportamentului psihologic al șoferului și i-a în considerare așa numitele puncte de acțiune pentru a controla mașina. Punctele de acțiune sunt situații identificate de către șofer în mod conștient sau inconștient pentru a lua diferite decizi [17]. Deși modelul care guvernează acest simulator sugerează un comportament determinist, rezultatele obținute în urma rulării diferitelor scenarii nu pot fi analizate decât prin folosirea unui model stocastic. Acest lucru rezultă din faptul că nu se pot stabilii niște condiții inițiale fixe, numărul vehiculelor și al pietonilor din simulare variază într-un mod aleator. Astfel rezultatele sunt analizate pe baza unor grafice în care sunt distribuite diferite date culese în urma rulării unui scenariu. Se poate observa, în acest caz diferența între modelul microscopic și cel macroscopic. În cazul modelului microscopic, rezultatele pot fi analizate pe baza unor funcții matematice cunoscute. Totuși modelul microscopic este mult mai apropiat de realitate și este recomandat să se folosească dacă se dorește obținerea unor informații precise.

Principala funcționalitate a algoritmului de control al mașinii constă în implementarea modelului de urmărire a mașinii din față. M Fellendorf și P Vortisch [18] prezintă patru principii de bază după care functionează acest model:

Conducerea liberă a mașinii: în acest caz mașina controlată nu are nici o altă mașină, sau un alt obstacol în fața ei. Șoferul va încerca să atingă o anumită viteză care este în mod normal limita de viteză maximă admisă și să o mentină. Se poate lua în acest caz în considerare comportamentul șoferului, care poate fi mai mult sau mai puțin agresiv. Un bun exemplu în acest sens este dat de faptul că persoanele de sex feminin conduc mai prudent decât persoanele de sex masculin.

Apropierea de mașina din fată: în acest caz șoferul coboară viteza mașinii până în momentul în care viteza sa este egală cu viteza mașinii din fața. Șoferul va încerca să mențină viteza constanta doar în momentul în care acesta consideră că se află la o distantă sigură față de mașina din fața. În realitate, nici un șofer nu poate să mențina viteza constantă, ci doar să oscileze în jurul vitezei dorite. Trebuie luat în acest caz în considerare faptul că viteza de reacție, și capacitățiile fiecărui șofer diferă în funcție de caracteristicile individuale ale fiecărei persoane. Configurările pentru un astfel de scenario pot fi mai complexe, dar rezultatele obținute se vor apropia mai mult de realitate.

Urmărirea: în momentul în care șoferul consideră că a ajuns la o distanță sigură față de mașina din fată, acesta va încerca să mentină viteza constantă fără să aplice o accelerare sau decelerare semnificativă mașinii.

Frânarea: încetinirea mașinii se poate realiza de la sine, datorită forței de frecare dintre roțile mașinii și pământ, sau se poate realiza prin apăsarea pedalei de frână. Frânarea se consideră a fi reducerea vitezi mașinii prin aplicarea unei rate de decelerare medii sau ridicate. Frânarea este necesară în momentul în care distanța de siguranță se modifică brusc: mașina din față frânează puternic, o altă mașină schimbă banda sau diferite obstacole apar într-un mod neasteptat.

În cazurile prezentate mai sus accelerația sau decelerația mașinii poate fi descrisă în funcție de variațiile vitezei sau variațiile diferitelor distanțe. Astfel se poate trece dintr-un mod în altul în funcție de anumite praguri care sunt depăsite. Un factor important care stă la baza acestui model de simulare este percepția șoferului. În acest sens trebuie luate în considerare abilitățile inidividuale ale fiecăre persoane de a percepe variații ale vitezei sau ale distanțelor.

O altă problemă tratată în cadrul acestui simulatorului este schimbarea benzii. Schimbarea benzii este o prolema dificilă, deoarece trebuie luați mulți factori în considerare. Și în acest caz algoritmul de control funcționeaza pe baza unui model care încearca să copieze comportamentul uman. Atâta timp cât șoferul este departe de următorul punct care îl forțează să schimbe banda, iar banda actuală îi oferă o cale mai ușoară de străbătut, mașina va rămâne pe banda actuală. În momentul în care șoferul este obligat totuși să schimbe banda, acesta va accepta că prin acțiunile sale poate să forțeze o altă mașina să încetinească. Valoarea decelerației acceptabile trebuie reglată la calibrarea sistemului. Cu cât șoferul este mai aproape de un punct critic în care va fi obligat să schimbe banda, acesta va devenii din ce în ce mai agresiv în dorința sa de a schimba banda. Astfel, șoferul care încearcă să schimbe banda va accepta o decelerare din ce în ce mai puternică a mașinii de pe banda secundară, pe măsură ce se apropie mai mult de un punct critic. Schimbarea benzii poate rezulta din condițile în care rulează traficul, așa cum au fost prezentate sau poate fi impusă. Pentru a evita un accident intenția șoferului de a schimba banda nu trebuie să depașească abilitățiile șoferului de pe banda secundară de a frâna. Se poate observa ca cele patru principii de bază a urmăririi mașinii din față prezentate mai sus includ și acest caz. Din acest motiv se poate spune ca modelul prezentat, poate ajuta la dezvoltarea ulterioară a simulatorului. Adăugarea noilor principii nu vor afecta vechiile principii, ci doar vor imbunătății performanțele simulatorului. Un alt factor important care trebuie menționat, este faptul că principile mașinilor nu se bazeaza pe o respectare strictă a regulilor de circulație, ci pe o încercare de a copia comportamentul uman.

Pentru a putea detecta coliziunile între mașini, modelele mașinilor vor fi încadrate într-un dreptunghi. În interiorul acelui dreptunghi se pot adăuga diverse modele de mașini care pot servi în scop estetic. Se pot alcătuii în acest sens modele destul de complexe, dar cu cât modelul e mai complex cu atât performanțele simulatorului vor fi mai slabe și astfel dimensiunile scenarilor se vor micșora. Pentru aproximarea distanțelor între vehicule și detectarea coliziunilor e de ajuns ca dimensiunile mașinilor să fie aproximate într-un dreptunghi sau cel mult într-un paralelipiped. De altfel, realizarea unui algoritm care să simuleze accidentele luând în considerare fiecare punct din care este alcătuită mașina, ar epuiza resursele sistemului de calcul. Rezultatele unui accident pot fi analizate de către utilizator fără a fi nevoie de o simulare foarte complexă.

Rutele pot fi specificate prin precizarea unor noduri sau a unor conectori. Totuși pentru o simulare cât mai realistă s-a ales implementarea unui algoritm care poate decide într-un mod dinamic schimbarea rutei. Astfel ruta poate fi schimbată, într-un mod automat, pe porțiuni mici, dacă pe ruta actuală este o densitate ridicată de mașini. Acest lucru asigură o distribuție mai realistă a mașinilor, dat fiind faptul că și în mediul real șoferii recurg uneori la astfel de metode pentru a ajunge mai repede la destinație.

Pentru a putea rula scenarii și pe sisteme de calul mai slabe, VISSIM oferă posibilitatea de a seta intervalele de reactualizare a scenei între 0.1 si 1 secundă. Cu cât aceste intervale sunt mai mari, cu atât sistemul de calcul va avea mai mult timp pentru a procesa noile poziții ale mașinilor. Totuși, setarea unui interval foarte mare, poate avea un efect dăunător în acest caz, având în vedere ca modelul de control al mașinilor se bazeaza pe reacțiile șoferilor. Setarea unui interval prea mare, poate avea ca efect imposibilitatea șoferului de a răspunde. În această situație se pot lua niște decizii de urgenta, pentru a păstra consistența sistemului. Aceste decizii nu fac parte din modelul descris până în momentul de față, dar sunt utile în păstrarea consistenței simulatorului.

Pentru construirea unei hărtii VISSIM oferă posibilitatea de a desena harta virtuală peste o imagine grafică. Acest lucru ajută, deoarece se pot construi scenarii mai apropiate de realitate. În figura 3.1 este prezentată o imagine de ansamblu a simulatorului, în timpul editării unui scenariu. Se poate observa faptul că scenariul este de o complexitate ridicată. Totuși, trebuie remarcat numărul mic al intersecților care formează acest scenariu. Simularea unui scenariu de anvergura mai mare, poate fi problematică, având în vedere că modelul de simulare este unul microscopic.

Figura 3.2 Editarea hărții în VISSIM

ANALIZĂ ȘI PROIECTARE

Analiza sistemului

Funcționalitățile sistemului, atât a clientului cât și a serverului, sunt prezentate în figura 4.1 prin folosirea unei diagrame a cazurilor de utilizare.

Figura 4.1 Diagrama cazurilor de utilizare

Diagrama menționată mai sus prezintă actorii sistemului: utilizatorul, administratorul și dispozitivul de conducere a mașinii care este optional. Rolul diagramei este de a descrie interacțiunea dintre utilizatori și componentele ale sistemului. Linia continuă reprezintă interacțiunea dintre utilizator si componentele principale ale sistemului, iar linia întreruptă reprezintă dependența între componentele principale și cele secundare. Prin relația de incluziune se înțelege faptul că dacă una dintre acțiuni se petrece, atunci și cealaltă trebuie neaparat să se petreacă, în timp ce prin relația de extindere se ințelege faptul că dacă una dintre acțiuni se petrece atunci cealaltă nu trebuie neaparat să se petreacă.

Pentru a se loga în sistem, utilizatorul va trebui mai intâi să se conecteze. O dată logat utilizatorul poate opta pentru una din cele două opțiuni principale: editarea scenariului sau participarea la scenariu. În acest moment se vor verifica drepturile utilizatorului pentru a primii acces doar la opțiunile care i-au fost asignate. Dacă utilizatorul dorește să conducă mașina, acesta poate folosii tastatura sau se poate folosii de dispozitivul special de conducere al mașinii.

Administratorul va pornii serverul, iar prin aceasta va pune la dispozitia utilizatorului o adresă IP și un port pentru a se putea conecta. După ce serverul a fost pornit, administratorul poate vizualiza toți utilizatorii și are dreptul de a-l deconecta pe oricare dintre ei. Deconectarea unui utilizator presupune logarea afară din sistem a acestuia. Administratorul este de asemenea responsabil cu introducerea înregistrărilor în baza de date. Aceste înregistrări pot fi introduse și la cererea clientului, dar trebuie validate de către administrator.

Arhitectura sistemului

Un sistem distribuit poate fi definit ca fiind o colecție de calculatoare care comunică între ele prin intermediul unei rețele pentru a efectua diferite sarcini. Totuși, deși sistemul presupune existența mai multor componente, acesta va fi privit de către utilizator ca fiind un sistem unitar. Conform cu George Colouris [19] principalele caracteristici ale unui sistem distribuit sunt:

Concurența: această caracteristică rezultă din proprietatea componentelor de a efectua sarcini în paralel. Din acest motiv, capacitatea unui sistem distribuit poate fi crescută, prin adăugarea unor componente noi. Design-ul unei astfel de arhitecturi este din acest punct de vedere foarte important. Arhitectura trebuie concepută în așa fel încât să poata fi adăugate componente noi fără a afecta funcționalitatea sistemului.

Lipsa unui ceas global: pentru a asigura buna funcționare a unui sistem distribuit acțiunile efectuate de către compenetele acestuia trebuie coordonate. Sincronizarea acțiunilor se poate realiza în cel mai simplu mod prin utilizarea unui ceas global. Totuși în unele situații e nevoie de o precizie ridicată, iar în acest caz sincronizarea nu se mai poate realiza prin această metodă. Acest lucru se datorează faptului că sincronizarea unui ceas global presupune o anumită marjă de eroare. În acest caz coordonarea acțiunilor se va realiza prin intermediul schimbului de mesaje. Astfel, un mesaj sau mai multe mesaje primite pot reprezenta o condiție pentru a putea efectua o anumită acțiune. De altfel diferite sisteme de sincronizare a ceasurilor globale sunt descrise tot prin intermediul schimbului de mesaje.

Căderea independentă a componentelor: căderea unei componente nu presupune neaparat căderea întregului sistem. Totuși, fiecare componentă are un rol mai mult sau mai puțin important. Din acest motiv, căderea diferitelor componente, va afecta sistemul într-un mod diferit. Pentru a remedia aceasta problema se pot folosi sisteme de rezervă care pot prelua sarcinile unei componente care a încetat să mai funcționeze.

Protocolul de comunicare între client și server

În figura 4.2 este prezentat protocolul de comunicare între client și server folosind o diagramă de secvente. Diagrama prezentată descrie funcționarea aplicatiei dacă se dorește conectarea în rețea a mai multor utilizatori.

Figura 4.2 Protocolul de comunicare

Clientul va trimite o cerere de conectare serverului prin specificarea adresei IP și a portului. Dupa ce serverul primește cererea, acesta va trimite o confirmare clientului. După ce conectarea s-a realizat cu succes, clientul va trece la faza de logare prin introducerea numelui și a parolei. Serverul va prelua acest mesaj și va căuta în baza de date numele, respectiv parola corespunzatoare pentru a putea valida sau invalida logarea. Dacă logarea s-a terminat cu succes, atunci clientul poate intra într-unul din scenariile active. După ce s-a realizat conexiunea la scenariu, serverul va trimite un mesaj inițial de configurare a scenariului. Acest mesaj va fi mai mare, deoarece conține informații referitoare la: mașinile care sunt în simulare, harta, obiectele și pozițiile lor. Clientul va prelua acest mesaj și va desena scenariul. Din acest punct, serverul va trimite mesaje mai scurte, doar de actualizare. Mesajele de actualizare vor conține informații referitoare la noile poziții ale mașinilor. Utilizatorii trebuie să trimită un mesaj periodic, la un interval scurt de timp, de ordinul milisecundelor, numit heart-beat (bătai de inima). Acest mesaj poate contine inputul utilizatorului sau poate să nu conțina nici o informatie nouă. Dacă acest mesaj nu este trimis se va presupune ca utilizatorul s-a deconectat de la sistem. Serverul poate trimite mesajul de reactualizare numai după ce a primit toate mesajele de heart-beat de la utilizatori.

Dupa ce serverul a primit mesajul care conține inputul tuturor utilizatorilor, acesta poate alege să proceseze el însăși calculele necesare pentru reactualizarea scenei sau poate trimite mai departe inputul celorlați utilizatori pentru a procesa utilizatorii scenariul. Se poate în acest caz alcătui un sistem în care prin intermediul serverului conectarea utilizatorilor să se realizeze direct. Acest lucru este necesar pentru ca mesajul să nu mai circule de la client la server și de la server la ceilalti clienti. În acest caz arhitectura devine peer-to-peer. Totuși ambele opțiuni au avantajele și dezavantaje lor. Dacă calculele au loc pe server, atunci dimensiunea mesajului de reactualizare a scenei va crește și astfel rețeaua va fi mai încărcată. În acelasi timp, dacă serverul trimite doar input-ul utilizatorului atunci dimensiunea mesajului va fi mai mica, dar procesarea se va realiza pe stațiile individuale ale fiecărui utilizator în parte.

Dacă serverul nu primește mesajul de heart-beat de la unul din utilizatori într-un anumit interval de timp numit time-out, atunci se va presupune că utilizatorul s-a deconectat. Deconectarea utilizatorului presupune eliminarea mașinii sale din simulator.

Principalele componente ale sistemului

Configurarea elementelor statice

Crearearea unui mediu 3D prin care se incearcă să se copieze realitatea este o sarcină dificilă, deoarece sunt foarte multe elemente care trebuie luate în considerare. Cu cât se dorește o apropiere mai mare de realitate, cu atât complexitatea crește mai puternic atât pentru programator cât și pentru sistemul de calcul. În figura 4.3 sunt prezentați principalii pași de configurare a mediului simulatorului, folosind o diagramă de componente.

Figura 4.3 Configurarea elementelor statice

Prima parte a acestei aplicatii constă în procesarea unei imagini a unei harti google și convertirea ei într-o structura de date. Cu ajutorul acelei structuri de date, harta se poate apoi redesena în spațiul tridiminesional. Desenarea hărtii se va face prin folosirea unor primitive grafice precum: triunghiuri, dreptunghi sau poligoane. În urma procesării imaginii, harta nu va putea fi încărcată decât într-un plan bidimensional. Dacă se dorește încărcarea harții în toate cele trei dimensiuni atunci se pot specifica și înălțimi. Înălțimea terenului se poate specifica printr-o hartă de culoare alb-negru, în care fiecare pixel ia valori între 0-255. Aceste valori reprezintă înălțimea terenului în ficecare punct. Trebuie făcut în acest caz diferențierea între teren și strazi. Dacă de exemplu se dorește elevarea unei străzi, atunci nu înseamnă neaparat că se dorește și elevarea terenului. Un mecanism util ar fi, ca în momentul în care se încarcă harta, aceasta să se plieze peste teren. Dacă harta este în mod implicit mai sus decât înălțimea terenului, atunci ambele componente vor fi încărcate la înălțimea lor naturală. După ce aceste componente au fost încărcate și desenate de către motorul grafic, utilizatorul poate alege să le editeze. Structurile de date corespunzatoare se vor modifica automat și la cererea utilizatorului vor fi salvate într-o baza de date.

Încărcarea hărții Google și a imaginii alb-negru pentru teren are rolul de a ajuta în configurarea unui scenariu mai rapid. Totuși, e bine ca utilizatorul să aiba posibilitate de editare a scenariului și în cadrul simulatorului, deoarece metodele folosite pot avea defecte nedorite de către utilizator.

O altă parte importantă în editarea unui scenariu tridimensional este încărcarea modelelor statice. Modele statice pot fi introduse pentru a simula diferite construcții din mediul real, și anume: stâlpi, blocuri, case, etc. Poziția acestor modele nu va fi schimbată pe tot parcursul scenariului. Modelele statice au rolul în a simula obturarea câmpului vizual al mașinii autonome, dar nu numai. Modelele statice pot creea un mediu mai apropiat de realitate utilizatorului care se poate identifica mai ușor cu scenariul.

Cu cât se dorește să se încarce mai multe modele, cu atât sistemul de calcul va fi mai încărcat. De asemenea trebuie avut grija la numărul vertex-urilor din care este alcătuit fiecare model și calitatea texturii sale. Modelele statice sunt totuși mai putin importante în simulare unui scenariu. Din acest motiv, dacă este nevoie să se ruleze un scenariu mai complex, iar sistemul de calcul nu e capabil să proceseze o cantitate mare de informatii, se poate opta pentru desenarea unor modele mai simple, cum ar fi primitive grafice. O altă metodaă pentru a imbunătății performantele simulatorului, este creearea modelelor alcătuite dintr-un număr mai mic de noduri. Dupa alegerea modelelor utlizatorul va seta poziția modelului și unghiurile de rotație. Aceste informații vor fi salvate în baza de date împreună cu nodurile din care este alcătuit modelul. De asemenea în baza de date se mai pot salva și imagini pentru textura folosită, coordonatele de mapare ale texturii sau alte informații legate de luminozitatea reflectată sau normalele folosite pentru a calcula reflexia luminii de pe model. Totuși aceste informații sunt mai puțin relevante în funcționalitatea simulatorului, având un scop pur estetic.

Controlul mașinii

Elevarea terenului și a străzilor nu e posibilă în momentul de față în cadrul simulatorului. Din acest motiv mașina nu funcționeaza decât în planul bidimensional. Totuși sistemul de control al mașinii este în așa fel conceput încât poate fi imbunătățit pentru a funcționa și în trei dimensiuni.

În figura 4.4 este prezentată o curbă de accelerație a unei mașini oarecare. Se poate observa că pe axa OY este ilustrată viteza, iar pe axa OX timpul. Aceasta curbă reprezintă accelerația maximă pe care mașina o poate atinge când are o anumită viteză. Cu o astfel de curbă va trebui configurat fiecare model de mașina în parte. Curba prezentată în imagine este o reprezentare grafica a unor date experimentale. În fișierul de configurare al mașinii, curba de accelerație va fi reprezentată printr-o înșiruire de numere de forma:

ACCELERAȚIE: v0:t0,v1:t1,v2:t2,v3:t3,v4:t4,v5:t5,v6:t6,v7:t7

Figura 4.4 Curba de acceleratie

În mod similar e nevoie de o curba de decelaratie. Aceste curbe sunt utile numai în situațile extreme, atunci când pedala de accelerație sau de frână e apăsată la maxim. Mașina va fi comandată prin setarea unei viteze la care aceasta trebuie să ajungă. Din curba de accelerație se poate determina dacă mașina poate atinge viteza respectivă sau nu. Dacă mașina nu poate atinge viteza respectivă, atunci va înerca să se apropie cât mai mult prin apăsarea pedalei de accelerație la maxim. Se poate menționa în acest caz, că sistemul prin care o mașinaă accelerează este un sistem neinerțial. Acest lucru presupune faptul că dacă pedala de accelerație este apăsată, iar apoi lăsată dintr-o dată mașina va păstra o viteza relativ constantă, în unele cazuri viteza poate chiar să scadă imediat după ce a fost luat piciorul de pe accelerație. Acest lucru este deosebit de important, deoarece sistemul prin care mașina se controlează pentru a ajunge la o anumită viteză nu este oscilant. Din acest motiv sistemul poate fi realizat într-un mod simplificat, fară a fi necesară folosirea unor regulatoare complicate.

In Fig 4.5 este prezentat sistemul de virare Ackerman. Sistemul a fost inventat de către Georg Lankesperger în anul 1817, dar a fost patentat de către agentul său Rudolph Ackermann în anul 1818, motiv pentru care sistemul îi poartă numele. Se poate observa în figură că traiectoria mașinii când aceasta vireaza formează un cerc. Sistemul Ackerman descrie un mecanism prin care roțile din fată trebuie rotite la unghiuri ușor diferite pentru a orienta toate roțile spre același centru de rotație. Dacă acest lucru nu este realizeazat atunci cel puțin una din roți va aluneca. Sistemul a fost propus prima dată pentru a fi folosit la trăsuri, iar apoi a fost folosit și la autovehicule.

Figura 4.5 Sistemul de virare Ackerman

O caracteristică imporantă a acestui mecanism este dată de lungimea mașinii. Se poate observa din geometria sistemului că dacă mașina este mai lungă, atunci cercul care formează traiectoria mașinii va crește mai lent, iar dacă lungimea mașinii este mai scurtă atunci acest cerc se va mării mai brusc o dată cu creșterea unghiului de virare. Din acest motiv, pentru a configura o mașina în simulator va fi nevoie să se precizeze lungimea mașinii și unghiul maxim de virare. Configurarea lățimii mașinii este mai putin importantă, deoarece unghiul la care trebuie rotite roțile pentru a fi direcționate spre același centru de rotatie, va devenii o consecința a stabilirii unghiului de virare.

Algoritmul care controleazeă sistemul de direcție al mașinii a fost conceput fără a lua în considerare proprietățile fizice ale mașinii și ale mediului înconjurator, dar poate fi imbunătățit pentru a lua în considerare și acești parametrii.

Inteligența artificială a mașinii

În capitolul anterior s-a discutat despre mecanismul de virare și de accelerare al mașinii. Aceste mecanisme sunt foarte importante, deoarece definesc principalele caracteristici ale unui autovehicul. După cum a fost prezentat, traiectoria masinii când aceasta virează formeaza un cerc. Cunoscând aceasta informație, se poate calcula unghiul la care mașina trebuie să își rotească roțile pentru a ajunge într-un anumit punct. În același timp se poate calcula și accelerația necesară ca mașină să ajungă în acel punct cu o anumită viteză. Se poate menționa în acest caz că nu mai are sens să se discute despre un mecanism de simulare al pedalei de accelerație. Astfel, se va presupune că se cunoaște cât de tare trebuie apăsată pedala de accelerație pentru ca mașina să accelereze cu o anumită accelerație dorită.

Din coordonatele străzilor se poate calcula centrul străzilor, iar apoi, în funcție de câte benzi are strada, se poate calcula centrul benzii. Controlerul mașini va încerca întotdeauna să ghideze mașina spre un anumit punct cu o anumită viteză. Astfel, se va calcula constant unghiul roților care va duce mașina la următorul punct și accelerația necesară pentru a atinge viteza dorită. Alături de punctele pe care mașina trebuie să le traverseze, se vor plasa din loc în loc instrucțiuni. În cadrul instrucțiunilor se poate preciza ce viteză trebuie mașina să atingă, ce zone trebuie verificate sau alte proceduri care trebuie urmate. În Fig.4.6. este ilustrată o schiță a codificării unui astfel de traseu.

Figura 4.6 Codificarea intstructiunilor

Algoritmul de control al mașinii va fi compus din două părti principale: o parte statică și o parte dinamică. Partea statică este cazul ideal, în care mașina poate să urmeze instrucțiunile primite fără să intre în conflict cu alte evenimente imprevizibile care pot apărea pe parcursul traseului. Mai precis, traiectoria unui obiect nu intră în conflict cu traiectoria mașinii. Obiectele vor avea ca principale caracteristici, o traiectorie, o dimensiune și un nume. Traiectoria și dimensiunea obiectului vor determina dacă mașina este pe un curs de coliziune cu obiectul. Un rol important îl are de asemenea și numele obiectului. Numele obiectului poate avea de altfel o influență în predicția traiectoriei. Un bun exemplu în acest sens este dat de faptul, că o mașina, sau o motocicletă va avea o traiectorie mai previzibila decât un pieton sau un animal. Traiectoria unei mașini, poate fi ușor determinată prin aplicarea legilor fizicii, în timp ce omul se deplasează mai mult sau mai puțin hazardic. Astfel, se pot configura diferite scenarii în care să se verifice abilitatea sistemului de a răspunde în diferite situații.

Evitarea coliziunilor se poate face în două moduri, fie prin stabilirea unei traiectorii noi a mașinii, fie prin ajustarea vitezei. Un bun exemplu în acest caz este dat de faptul că dacă mașina se află pe un curs de coliziune cu un animal, cel mai bun protocol care poate fi urmat este ca mașina să înceteze să accelereze. Această strategie este recomandată deoarece frânarea bruscă poate avea un efect imprevizibil asupra traiectoriei mașinii. De asemenea, evitarea unei coliziuni prin schimbarea traiectoriei poate pune în pericol viețile altor oameni, motiv pentru care nu este recomandat să se încerce această manevră. Totuși, în cazul în care masina este pe un curs de coliziune cu un om, poate avea sens să se discute diferite manevre de evitare a coliziunilor, dar și acestea trebuie efectuate doar dacă riscul este minim. De asemenea în cazul prezentat un protocol care poate fi urmat este de a clanxona. Totuși și acest protocol este discutabil, deoarece reacțiile omului când o mașina clanxonează pot deveni foarte imprezibile. Orice protocol aplicat de către inteligența artificială a mașinii trebuie să genereze un scenariu prin care orice posibil incident să nu poata fi considerat a fi din vina mașinii la sfârșitul manevrei. Totuși, un astfel de protocol nu implică faptul că mașina nu are voie să încalce regulile de circulație, ci doar că nu are voie să le încalce dacă prin aceasta produce un accident. Un astfel de protocol este foarte dificil de studiat și implementat, dar este necesar având în vedere faptul ca un astfel de sistem ar putea fi capabil să ia decizii mai bune decât decizile naturale ale oamenilor.

Detectarea coliziunilor poate devenii o problemă majoră, deoarece consumă foarte multe resurse. În mod normal pentru detectarea coliziunilor tehnica folosită este partiționarea recursivă a spațiului în patru bucăți și detectarea coliziunilor în fiecare sub-regiune. Regiunile vor fi reprezentate de forme dreptunghiulare sau paralelipipedice care împart spațiul bidimensional, respectiv pe cel tridimensional. Fiecare model va fi încadrat într-unul din cele două spații dacă se afla în totalitate într-o singură regiune, sau va fi plasat în ambele regiuni dacă se află la granița între două regiuni.

Această tehnica nu își are totuși rostul în cazul de fată, existând o solutie mult mai rapidă. Deoarece se cunoaște poziția fiecărei mașini, se poate identifica cu ușurintă strada pe care mașina se află. Fiecare mașina o dată ce intră pe o anumită stradă, va fi păstrată într-o mapă, cu cheia având strada respectivă, iar valoarea, lista de mașini care circulă pe acea strada. Astfel se pot detecta cu ușurință coliziunile între mașini, verificând doar acele mașini care se află pe o anumită stradă, și eventual străzile vecine. Totuși, acest algoritm poate fi implementat doar pentru mașinile controlate de inteligența artificială, deoarece se poate determina rapid strada pe care aceste mașini circula. În cazul în care mașinile sunt controlate de către un șofer real, acest algoritm va fi mai dificil de implementat, deoarece pozitiile mașinilor nu mai pot fi corelate atât de ușor de strada pe care acestea circulă. În acest caz este necesar să se aplice tehinca de detectare a coliziunilor prin partiționarea recursivă a spațiului în sub-regiuni. Algoritmii prezentați pot fi combinați pentru a obține rezultate optime. În figura 4.8. este prezentata arhitectura inteligenței artificiale prin intermediul unei diagramă logice.

Figura 4.7 Inteligența artificială a mașinii

În continuare se vor discuta cele mai importante funcții prezentate în diagrama logica a inteligenței artificiale:

Acordarea priorității

Această situație poate apărea în momentul în care trebuie să se respecte următoarele reguli de circulație:

Cedează trecerea

Stop

Acordarea prioriții de dreapta

Schimbarea benzii

În primele trei cazuri, acordarea priorității este mai ușor de realizat. O dată ce mașina va ajunge într-o intersecție, aceasta va identifica toate mașiniile care se află în proximitatea și va calcula dacă prin actiunile sale determină o alta mașina care are prioritate să folosească manevre de evitare a coliziunilor. Manevrele de evitare a coliziunilor surprind și faptul că o mașina e nevoită să încetinească. Astfel dacă mașina trebuie să acorde prioritate de dreapta, atunci mașina va verifica doar strada din dreapta, iar dacă trebuie se cedeze trecerea sau să oprească la stop atunci va verifica străzile din ambele directii. Realizarea unui algoritm automat care să genereze instrucțiunile pentru mașina este dificilă. Din acest motiv, instrucțiunile primite de mașina vor fi doar de forma verifică strada „x”. Semnele de circulație vor fi plasate fictiv pentru a putea vizualiza scenariul, sau pentru utilizatorii care doresc să conducă mașina. Pentru a ceda trecerea mașina va primi o instrucțiune în timp util, prin care aceasta va trebui să își reducă viteza în așa fel încat să poată opri în orice moment înainte de a intra în intersecție. În acest timp se poate verifica dacă intersecția este liberă sau nu, caz în care mașina va oprii și va continua procesarea într-un mod identic cu așteptarea la stop.

Un algoritm pentru schimbarea benzii de circulatie a fost descris în capitolul II, unde a fost prezentat simulatorul VISSIM. Algoritmul prezentat propunea soluții prin care sistemul trebuia calibrat pentru ca o mașină să poată schimba banda de circulație în conformitate cu regulile de circulație și cu psihologia oamenilor. Acest algoritm nu a fost implementat, dar se propune implementarea unui algoritm asemănator.

Pentru detectarea coliziunilor în acest caz, se propupne realizarea unui algoritm prin care mașinile de pe o anumită stradă să fie păstrate în ordinea lor naturală într-o listă ordonată. Astfel se poate implementa un algoritm de detectare al coliziunilor mult mai eficient decât algoritmii clasici, verificând doar coliziunile cu acele mașini care se află în proximitate.

Verificarea semaforului

Fiecare semafor va avea un id. Acest id va devenii o cheie într-o mapă, iar valoarea va fi semaforul. Când mașina ajunge la o intersecție semaforizată va primii o instrucțiune de forma: verifică semaforul „x”. Semaforul va fi extras din mapă, și se va verifica dacă este sau nu permis să se traverseze intersecția. Pentru a putea lua această decizie, controlerul mașinii trebuie sa cunoască, nu doar culoarea semaforului în momentul curent, ci și timpul rămas până la schimbarea culorii. Acest lucru este necesar, deoarece mașina poate ajunge în situația în care semaforul poate să își schimbe culoare într-un moment în care mașina nu mai are timp să reacționeze.

Apariția comportamentului imprevizibil

Mașina va primii constant poziția curentă a ei și pozițiile celorlalte mașini. Având aceste informații, se poate calcula dacă viitoarea poziție a mașinii va intra în conflict cu unul din obiectele din mediul exterior. Astfel, fiecare mașina va devenii un obiect pentru celelalte mașini. Un rol important în cadrul acestui algoritm îl au predicțiile. În principal, predicțiile vor rezulta din aplicarea legilor fizicii, iar pentru a fi cât mai consistente, trebuie să se ia în considerare un interval de timp cât mai mic. Acest lucru este foarte important, deoarece pe măsură ce timpul trece, poate apărea un comportament din ce în ce mai imprevizibil. Cu cât intervalul de timp e mai scurt, cu atât șansa ca predicția să fie mai buna crește. De asemenea, pentru a face predictii cât mai precise, se poate lua în considerare și comportamentul psihologic al oamenilor sau al animalelor. Acest comportament este totuși mai greu de prezis, dar poate avea un rol foarte imporant.

Ajustarea vitezei

După ce sa detectat o coliziune, primul lucru pe care mașina îl va încerca va fi să ajusteze viteza. Aceasta opțiune nu este totuși întotdeauna și cea mai buna decizie. Mașina trebuie mai întâi să se asigure că decizia de a încetinii nu va pune în pericol restul traficului. Un bun exemplu în acest sens, este apariția unui obstacol pe marginea unui drum principal. În acest caz modificarea traiectoriei este o decizie mai buna decât ar fi oprirea în mijlocul drumului. Acest caz este un bun exemplu în care mașina va fi obligată să încalce regulile de circulație pentru a lua cea mai buna decizie. Orice decizie se va lua, mașina trebuie mai întâi să se asigure că prin decizia respectiva nu va pune în pericol restul traficul. Dacă nu există o decizie posibilă care nu va pune în pericol restul circulației, atunci trebuie luată decizia prin care se vor provoca cele mai puține daune.

Modificarea traiectorii

Pentru a seta o traiectorie de evitare a coliziunii, trebuie calculată cea mai scurtă traiectorie prin care se poate evita coliziunea fără a intervenii și alte pericole. Trebuie luat în acest caz, în considerare, posibilitatea mașinii de a derapa sau posibilitatea de a ajunge în altă situație de pericol. O situație periculoasă este considerată a fi o situație prin care traiectoria masinii se poate intersecta cu traiectoria unui alt autovehicul. De menționat cazul prezentat anterior în care e mai bine sa eviți un obstacol care se află pe marginea drumului, chiar dacă făcând acest lucru e posibil ca mașina să calce linia continua. Se poate studia în acest caz viteza probabila a mașinilor pe un anumit segment de drum și câmpul vizual al mașinii autonome. Pe baza acestor informații se poate estima riscul apărut prin efectuarea manevrei respective. Acest calcul este de altfel realizat constant de către șoferi reali. Astfel, se poate realiza un model pe baza căruia mașina va putea evalua riscul impus de efectuarea unei manevre. Pentru executarea acestor de manevre nu se poate lua în calcul realizarea unui algoritm automat, motiv pentru care fiecare situatie va trebuie identificată și tratată în parte. S-a discutat în acest sens despre programarea unor rute prestabilite, care oferă posibilitatea realizarii unor astfel de algoritmi. Totusi, modificarea traiectoriei nu este o problema atât de simpla, motiv pentru care nu va fi discutata în detaliu in această lucrare

Diagrame UML

Diagramele UML (Limbaj Unificat de Modelare) sunt folosite pentru a descrie arhitectura unui sistem prin intermediul folosirii unui limbaj standardizat. Acest limbaj a fost creat de către Grupul de Management al Obiectelor (OMG) între anii 1944-1945, iar în ziua de astăzi sunt foarte folosite pentru a modela sistemele care au la baza programarea orientată pe obiect. Pentru a modela diferite sisteme și pentru a putea scoate în evidentă anumite caracteristici a fost necesară dezvoltarea mai multor tipuri de diagrame printre care se numără:

Diagrame de componente

Diagrame de activitate

Diagrame de secvente

Diagrame de clase

Diagrame de utilizare a cazurilor

Diagrame de comunicație

Se poate observa în lista prezentată mai sus, că unele dintre aceste diagrame au fost deja folosite: diagramele de componente, diagrame a cazurilor de utilizare și diagramele de activitate. În capitolul următor se va descrie arhitectura sistemului la un nivel mai ridicat de detaliu folosind diagramele de clase si de secvente.

Diagrame de clase

Diagramele de clase sunt folosite pentru a reprezenta clasele, atributele lor și relațiile dintre acestea într-un sistem care respectă principile programării orientate pe obiect. Acest tip de diagrame este foarte folositor deoarece descrie codul la un nivel de detaliu ridicat.

În figura 4.8 sunt prezentate principale clase ale simulatorului prin utilizarea unor astfel de diagrame. Diagrama este intenționată pentru a descrie doar arhitectura simulatorului, excluzându-se partea aplicației care procesează harta. Se pornește de la premisa că harta a fost deja procesată și încarcată în simulator. Astfel se vor descrie doar clasele care sunt folosite pentru partea de configurare și de rulare a unui scenariu.

Figura 4.8. Diagrama de clase

Prima clasă despre care se va discuta este clasa Map. Aceasta clasă a fost concepută pentru a stoca informațiile procesate de către prima aplicație. Clasa Map conține o matrice bidimensională, iar în interiorul fiecărei celule se găsește un obiect de tip Street. Matricea este folosită pentru a putea aplica diferiți algoritmi care sunt folosiți în cazul structurilor de tip graf. Astfel, în matrice se va găsi un obiect de tip Street, doar dacă există o conexiune de la un nod la celalat, iar dacă nu atunci obiectul va fi null.

Obiectul de tip stradă conține două liste pentru a păstra coordonatele pentru cele două margini ale străzii, iar în cele doua liste sunt păstrate obiecte de tip Punct. Obiectul de tip Punct păstrează în cazul de față două coordonate care reprezintă coordonatele x si y în planul bidimensional. Dacă se dorește îmbunătățirea aplicației se poate adăuga și o a treia coordonata, Z, pentru a putea seta și înălțimea. Pe lângă matricea care stocheaza coordonatele străzii, mai este nevoie de o listă care să păstreze coordonatele intersecților. Fiecare intersecție primește de la aplicația care procesează harta un număr, dar acesta poate fi setat de către utilizator, pentru a fi mai sugestiv, cu un nume. Acest lucru este valabil și pentru străzi. În momentul de fața o intersecție poate fi selectată prin precizarea unui număr, iar o stradă prin precizarea a două numere care reprezintă intersecțile de la cele doua capete ale străzii. De menționat în acest caz faptul că printr-o intersecție se înțelege nodul din care pornește o stradă. Astfel, orice stradă va fi legată de două intersecții, chiar dacă strada se termină într-o înfundatură.

Deși nu o fost ilustrat pe diagramă, clasa Punct este extinsă de către o altă clasă numită InstructiunePunct. Această clasă este necesară, deoarece pe măsura ce mașina va parcurge un anumit traseu, ea va merge din punct în punct. Se poate astfel verifica dacă punctul respectiv conține o instrucțiune sau nu. Dacă punctul conține o instrucțiune, atunci mașina va fi comandată pe baza procesării instrucțiunii respective, iar în caz contrar mașina va fi comandată pe baza procesării ultimei instrucțiuni primite. Pentru a extrage intstrucțiunea se va verifica mai intâi dacă obiectul respectiv este o instanță a clasei InstructiuniPunct sau este o instanța a clasei Punct. Acest mecanism a fost ales pentru a respecta principile programării orientate pe obiect.

Pe măsură ce mașina avansează, Controlerul Mașinii va calcula constat distanța până la următorul punct. Dacă distanța se marește, atunci se poate trage concluzia că mașina a depășit punctul respectiv și se va extrage următorul punct din lista în care este stocat traseul.

Principalul avantaj oferit de această arhitecură este dat de faptul că se pot adăugă un număr nelimitat de instrucțiuni fără a afecta vechile funcționalități ale simulatorului. Instrucțiunile vor fi păstratate în șiruri de caractere sub forma unor propoziții pentru a fi cât mai sugestive pentru utilizator. Informațiile numerice care sunt necesare pentru a efectua calculele, vor fi extrase de către controler prin parsarea șirului de caractere. Se poate alcătuii în acest sens un sistem de codificare, renunțând în totalitate la algoritmul de parsare pentru a micșora timpul de procesare.

Pe lângă coordonatele străzilor și a intersecțiilor clasa Hartă mai conține și o mapă de semafoare. Fiecare semafor, va primi la instanțiere intervalul de timp la care este redesenată scena, și cele doua intervale de timp pentru a schimba culorile la semafor. Intervalul de timp la care este redesenată scena este foarte important pentru a putea sincroniza diferitele componente ale simulatorului. Setarea unui interval mai mic de actualizarea a scenei, va avea ca efect rularea mai rapida a instrucțiunilor, și în consecință timpul va trece mai repede. În mod analog, setarea unui interval mai mare, va avea ca efect rularea mai lentă a scenei.

Pentru configurarea semafoarelor s-au ales doar două stări, deoarece s-a luat în considerare faptul că semafoarele moderne afișează și intervalul de timp rămas până la următoarea schimbare a culorii. Din acest motiv culoarea galbenă a semaforului nu își are rostul în cazul de față. În capitolele anterioare s-a discutat despre diferite mecanisme care pot fi folosite pentru a creea semafoare inteligente. Realizarea unor astfel de algoritmi este o sarcina foarte dificilă, motiv pentru care semaforul își va schimba starea doar la intervale fixe de timp. Fiecare semafor va avea un id și niște coordonate la care trebuie plasat. În acest sens se poate discuta despre posibilitatea de a modifica aplicația care procesează harta, în așa fel încât pe marginile străzii să fie plasați pixeli de o anumita culoare care să reprezinte semafoarele. Astfel la încărcarea hărții, coordonatele semafoarelor ar putea fi identificate într-un mod automat, dar trebuie setate intervalele pentru schimbarea starilor semaforului.

Traseul mașinii va fi format din toate punctele care alcătuiesc centrul benzii. În acest caz se consideră că strada are o singură bandă pe sensul de mers. Coordonatele pentru centrul benzii vor fi calculate din coordonatele strazii, prin impartirea succesiza la 2 a coordonatelor punctelor paralele care alcatuiesc marginile strazii. Dupa calculul acestor coordonate, instructiunile pot fi plasate manual sau automat daca se cunosc cu exactitate coordonatele fiecarui semafor.

Dupa realizarea configurarilor mentionate, controlerul, va prelua din lista traseului, primul punct la care trebuie să comande mașina să se deplaseze și apoi va extrage din acel punct o instrucțiune. De menționat în acest caz, că primul punct al traseului trebuie să conțină neaparat o instrucțiune, altfel masina nu poate fi comandata. Pentru a simplifica aplicația, se consideră doar cazul în care toate intersecțile sunt semaforizate. Nu a fost implementă logica pentru a putea simula respectarea altor reguli de circulatie. Astfel mașina va primi un traseu, care poate conține instructiuni de forma:

ajungi la viteza “x”,

verifica semaforul “x”

Cazul în care pot apărea obiecte pe traseu nu va fi luat în considerare în aceasta descriere, dar se va discuta încetinirea mașinii daca este o alta masina în fata care merge mai încet. Acest caz apare la întâlnirea unui semafor, deoarece mașina din fața va primi instrucțiunea de a încetinii mai devreme decât mașina din spate. În acest caz mașina aflată în spate va trebui să încetinească de la sine pentru a evita coliziunea, deoarece ea nu are nici o informație legată de semafor. Se pot astfel descrie principale functionalitați ale controlerului luând în considerare următoarele cazuri:

Controlerul citește o instrucțiune prin care trebuie să comande mașina să ajunga la o anumita viteză. Acesta va calcula dacă prin acțiunea respectiva riscă să se apropie de mașina din fată la o distanta mai mica decât distanța considerată a fi sigură. Dacă acest lucru se întâmplă, atunci controlerul va calcula viteza cu care trebuie să comande mașina pentru ca distanța să rămână în zona de siguranța. Mașina va prelua viteza comandată de către controler, și pe baza curbei de accelerație sau a decelerației va încerca să se apropie cât mai mult de viteza primită. De asemenea mașina va primii de la controler punctul spre care aceasta trebuie să se îndrepte și va calcula unghiul de virare care o va duce spre acel punct. Se presupune în acest caz că mașina poate modifca unghiul instantaneu pentru a ajunge exact la punctul dorit. După ce mașina a urmat instructiunea, aceasta va răspunde controlerului cu viteza la care a ajuns și cu noua poziție. Controlerul va calcula dacă distanța pe care mașina a parcurs-o a depașit punctul la care trebuie să ajungă sau nu. Acest lucru este necesar deoarece punctele vor fi plasate la o oarecare distanța între ele. Dacă mașina a trecut de punctul respectiv atunci controlerul va prelua urmatorul punct din lista și va repeta procesul.

Controlerul citește o instrucțiune prin care trebuie să verifice un semafor. Semaforul este preluat din mapa în care sunt ținute semafoarele și se verifică dacă culoarea semaforului este galbenă sau rosie. În acest caz mașina masina trebuie să oprească cât mai aproape de linia de intersectie, sau cât mai aproape de urmatoarea mașina. Astfel se va calcula punctul în care mașina trebuie să opreasca: lângă linia intersecției, sau în spatele altei mașini, și apoi se va comanda mașina să atingă viteza necesară pentru a putea realiza această manevră.

Se poate observă pe baza celor prezentate mai sus, că realizarea scheletului pentru o astfel de aplicație pare o sarcina destul de complexă, însă nu este atât de dificil de implementat. S-a discutat în acest capitol funcționarea mașinii desconsiderând toate cazurile în care pot apărea obiecte imprevizibile pe parcursul traseului și desconsiderând toate regulile de circulație, mai puțin semafoarele care sunt relativ ușor de implementat. Restul algoritmilor se pot realiza de asemenea pe baza arhitecturii prezentate. Totuși realizarea unui simulator pentru traficului rutier este o problema de o complexitate ridicata, motiv pentru care s-a ales doar discutarea celor mai de baza funcționalități.

Diagrama de secvențe

Diagramele de secvențe sunt un tip de diagrame prin care se ilustrează ordinea mesajelor schimbate între principalele componente ale sistemului. În cazul utilizării programării orientate pe obiect, diagramele de secvența sunt utile pentru a reprezenta interacțiunea între obiecte. Cu ajutorul acestor diagrame se pot identifica si rezolva eventualele probleme legate de sincronizare. Pentru a sugera atomicitatea relaților, se vor folosii sageți care converg spre același dreptunghi. În figura 4.9 este ilustrată comunicarea între funcția principală, controlerul mașinii și mașina.

Figura 4.9 Diagrama de secvențe

Diagrama menționată are rol în a descrie schimbul de mesaje efectuat pentru a putea dirija o mașina într-un scenariu. După cum se poate observa, clasa Main este sursa principală din care sunt create toate obiectele. În cazul de față, această clasa este folosită pentru a instanția un obiect de tip ControlerMașina, care apoi instanțiază un obiect de tip Masina. Relația între aceste obiecte este de unu la unu. Astfel, la instanțiere, fiecare controler va primii o singură mașina. Trebuie menționat, faptul că diagrama ilustrează doar crearea unei singure astfel de perechi. Totuși, clasa principală poate fi folosită teoretic, pentru a crea un număr nelimitat de astfel obiecte. Acest număr este limitat de performanțele sistemului de calcul.

Pentru a crea un obiect de tip mașina, trebuie cunoscută poziția inițiala a mașinii și traseul pe care trebuie sa îl urmeze. Traseul este necesar, pentru a putea poziționa mașina la un anumit unghiu pe stradă. După instanțierea celor doua obiecte, se poate pornii bucla principală de control a mașinii. Trebuie menționat, că în diagramă, s-a omis ilustrarea utilizatorului, care este responsabil cu setarea traseului și a instrucțiunilor.

Pentru a putea genera anumite instrucțiuni pentru mașina autonoma, e nevoie să se cunoască pozițiile celorlate mașini. Se poate observa din diagramă, că înainte de a ajusta viteza, controlerul cere funcției principale coordonatele celorlate mașini. Acest lucru reprezintă de altfel partea dinamica a controlerului. Cu aceste informații, controlerul va face calculele necesare și va comanda mașina să se îndrepte spre un anumit punct, cu o anumită viteză. Mașina va prelua aceste informații și va încerca să îndeplinească comenzile primite cât mai precis posibil. După efectuarea calculelor, mașina va răspunde cu noua poziție și viteză la care a ajuns. Aceste informații vor fi trimise atât controlerului cât și funcției principale pentru a putea redesena mașinile la noile poziții.

Se poate observa din diagramă posibilitatea utilizarii mai multor fire de executie pentru a comanda mai multe mașinii. Totuși, un lucru mai important de remarcat este faptul că aceste calcule pot fi efectuate și pe o stație separată. Acest lucru este posibil deoarece comunicarea între două calculatoare se poate realiza într-un timp îndeajuns de scurt încât să nu depășească timpul de redesenare a scenei. Pentru realizarea unui astfel de sistem este necesar să se transmita un mesaj celeilalte stații cu traseul și pozițiile mașinilor din proximitate. Aceasta poate apoi să calculeze noua poziție a mașinii într-un mod identic cu cel prezentat. Desigur, respectiva stație trebuie să aibă instalată aplicația, sau cel puțin un modul din aplicație care să ii permită executarea acestor calcule. Realizarea unei astfel de arhitecturi presupune anumite riscuri. Se poate pune in discuție faptul că stația nu va răspunde în timp util, sau că va înceta să funcționeze. Datorită complexității unei astfel de arhitecturi, asemenea riscuri apar în mod inevitabil. Rezolvarea acestor probleme se poate face prin realizarea unui sistem de siguranța care va trimite același calcul mai multor stații.

Mesajele trimise între doua stații vor avea dimensiuni foarte mici, având în vedere că nu este nevoie decât de transmiterea câtorva numere care reprezintă pozițile mașinilor. Se pot alcătuii în acest sens, niște mecanime prin care, mai multe stații să se subscrie stației principale pentru a prelua o parte din calcule. Un astfel de mecanism ar putea ajuta în creșterea considerabilă a dimensiunilor scenarilor.

IMPLEMENTARE

Procesarea hărtii

Primul obiectiv care trebuie îndeplinit constă în obținerea unei hărti realiste într-o oarecare structură de date pentru a putea fi importată în mediul tridimensional. Soluția aleasă pentru a rezolva această problemă a fost crearea unei aplicații care preia imaginea unei hărți Google, o procesează, și returnează coordonatele fiecărei străzi. Procesarea imaginilor poate fi o sarcină complexa pentru sistemul de calcul datorită numărului mare de pixeli din care sunt formate imaginele. Totuși, în cazul de față, e nevoie de o aplicație rapidă, capabilă să proceseze imaginea într-un timp relativ scurt. Din acest motiv, pentru dezvoltarea acestei aplicații, s-a ales limbajul de programare C++ împreună cu librăria OpenCV care e folosită la importarea imaginilor. Principalul avantaj oferit de limbajul de programare C++ constă în faptul că permite programatorului să manipuleze memoria la un nivel scăzut, având astfel posibilitatea de a dezvolta algoritmi mult mai eficienți decât prin folosirea unor limbaje de programare de nivel mai înalt.

Creearea acestei aplicații s-a dovedit a fi o sarcina mult mai dificila decât sa crezut inițial. Din această cauză au fost dezvoltate două versiuni ale aplicației, fiecare având avantajele și dezavantajele ei. Ideea de baza în ambele versiuni constă în folosirea unor drone care sunt folosite pentru a scana harta. Dronele sunt plasate pe străzile de la marginea imaginii, se deplasează de-a lungul lor, iar când ajung într-o intersecție se despart în mai multe drone și reiau procesul. Informațiile strânse la finalul acestui proces sunt folosite pentru a crea o structura de date în care sunt ținute coordonatele străzilor. Problema unui astfel de algoritm apare la procesarea intersecțiilor, deoarece e dificil de realizat un algoritm capabil sa identifice străzile care se ramifică din acea intersectie și care e linia care marchează finalul intersecției și începutul străzii.

În prima versiune a aplicației intersecțiile sunt procesate într-un mod automat, în timp ce în a doua versiune intersecțiile au fost colorate cu o anumită culoare prestabilită, la fel ca în figura 5.1. Având aceasta informație se poate realiza un algoritm mult mai simplu și mai precis. Principalul avantaj oferit de prima versiune este că nu mai e nevoie de munca manuală suplimentară pentru a edita imaginea, în timp ce dezavantajul constă în faptul că algoritmul e mult prea complex. Cu cât un algoritm e mai complex, cu atât crește timpul de procesare și riscul de apariție al erorilor. În același timp, prin folosirea unui astfel de algoritm nu se poate garanta faptul că liniile care delimitează intersecția de stradă sunt trasate corect. Acest lucru se datorează faptului că nici în realitate nu exista o organizare clară în acest sens. Liniile intersecțiilor sunt de obicei trasate într-o anumită marjă de eroare, de la caz la caz. Cel de-al doilea algoritm rezolva cu ușurință această problemă. Intersecția este clar delimitată de străzi, iar algoritmul este mult mai simplu. Astfel timpul de procesare și riscul de apariție al erorilor scade, dar apare munca manuală suplimentară care poate fi migăloasă și greoaie.

Având în vedere avantajele și dezavantajele menționate, se poate spune că ambele aplicații pot fi folositoare pentru a procesa o astfel de hartă. Totuși, pentru a putea testa simulatorul, s-a folosit prima aplicație. Motivul principal pentru care s-a ales această variantă este dat de faptul că intersecțiile sunt procesate cu o precizie mai mare. Acest lucru este important în momentul în care mașina trebuie să oprească la intersecții. Dacă s-ar fi folosit prima variantă a aplicației, ar fi fost nevoie de o setare manuală a acestor puncte. În figura 5.1 sunt prezentate două exemple ale unor imagini care sunt folosite pentru a fi procesate de către cele două aplicatii.

Figura 5.1 Imaginile harților înainte de procesare

Procesarea hărții – versiunea I

Imaginea este importată în mediul de programare sub forma unui obiect de tip Mat. În interiorul obiectului se găsește o matrice în care este codificată culoarea fiecărui pixel din imagine. Dimensiunile acestei matrici sunt egale cu dimensiunile imaginii și conține în fiecare celula trei numere care pot lua valori cuprinse între 0-255. Aceste numere reprezintă intensitatea culorilor rosu, verde și albastru a pixelilor din imagine. Străzile sunt colorate cu culoarea albă (R=255, G=255, B=255), iar restul imaginii trebuie să fie colorata în orice altă culoare diferita de alb.

Primul pas care trebuie realizat constă în identificarea străzilor de la marginea imaginii. Mai precis e nevoie de coordonatele punctelor de început pentru cele doua margini ale străzii. Pentru a obține aceasta informație matricea este parcursă în sensul acelor de ceasornic, verificând punctele care se afla la marginea imaginii. Pentru a identifica aceste puncte se caută un pixel de culoare albă, aflat lângă un pixel de orice altă culoare. După ce aceste puncte au fost identificate, ele sunt marcate pe imagine cu culoarea neagră. Marcarea punctelor scanate este necesară pentru a putea vizualiza procesarea hărții. Totodata, prin marcarea punctelor scanate, drona va putea identifica daca un punct a fost deja scanat. Dupa ce aceste puncte au fost identificate, se poate calcula centrul străzii cu ajutorul formulelor prezentate în relațiile (5.1), (5.2):

(relatia 5.1)

(relatia 5.2)

La coordonatele rezultate din formulele menționate se plasează o dronă. Rolul dronei e de a scana imaginea într-un mod cât mai natural, asemănător cu modul în care un om scanează împrejurimile. Astfel, drona va cerceta imaginea în interiorul unui cerc, cu centrul aflat la mijlocul străzii, iar raza cercului cu puțin mai mare decât lățimea străzii. Cercul este descris de ecuația parametrică a cercului prezentată mai jos (relațiile 5.3,5.4):

(relația 5.3)

(relația 5.4)

Unde, a si b reprezintă coordonatele centrului cercului în planul x-y, r reprezintă raza cercului, iar t unghiul vectorului de poziție care se rotește pentru a descrie cercul. Pentru a descrie o rotație completă, parametrul t i-a valori cuprinse în intervalul: [0, 2π). Pentru a descrie cercul algoritmic, acest parametru va crește constant cu un anumit pas: 0.01, de la 0 până la 2π. În același timp, raza va crește, de la 1 până la câmpul maxim vizual al dronei. După efectuarea calculelor valorile coordonatelor x si y vor fi cel mai probabil numere reale. Aceste numere vor fi transformate în numere naturale prin aproximare, pentru a putea fi plasate la coordonatele pixelilor din imagine. În Fig.5.2 e ilustrată procesarea imaginii descrisă până în acest punct.

Figura 5.2 Începutul procesării unei străzi

Drona va extinde cercul până când raza va ajune la dimensiunea câmpului maxim vizual al dronei, sau până va identifica un perete. Prin acest procedeu se verifică fiecare pixel din interiorul cercului. Drona conține două liste, care sunt folosite pentru a memora coordonatele pentru cele două margini ale străzii. În timpul unui ciclu de scanare drona stocheaza toți pixelii care reprezintă coordonatele marginilor străzii într-o listă temporară. După ce termină un ciclu de scanare, coordonatele pixelilor aflați în lista temporară, vor fi ordonați și plasați în cele două liste corespunzatoare marginilor străzii. La finalul acestui proces, drona va calcula următorul centru al străzii la care se va deplasa. Acest procedeu se repetă până în momentul în care se ajunge la o intersecție sau într-o înfundatură. Drona a ajuns într-o intersecție în momentul în care a detectat o a treia margine care nu poate fi legată de niciuna din cele două margini. Dacă drona nu a detectat nici un punct nou, atunci se poate spune ca s-a ajuns într-o infundatură. Algoritmul prezentat mai jos reprezintă funcția principală de control a dronei.

void Drone:: scanStreet(){

tempEdge = getTempEdge ();

if(tempEdge.size() == 0){

isAlive = false;

return;

}

addTempEdge(firstEdge);

addTempEdge(secondEdge);

if(tempEdge.size() != 0){

isAlive = false;

solveIntersection();

return;

}

}

Algoritmul prezentat este folosit de către dronă pentru a scana o strada până la întâlnirea unei intersectii. La finalul acestei scanări drona va procesa intersecția, și va memora coordonatele de început ale străzilor care se ramifică din intersecția respectivă. Aceste coordonate vor fi folosite pentru a inițializa dronele copii care vor continua procesul.

Primul pas este identificarea punctelor care alcătuiesc marginile străzii și plasarea lor într-o listă temporară. În lista temporară sunt păstrate toate punctele, care sunt identificate în timpul unui ciclu de scanare, ca fiind puncte ce reprezintă marginile străzii, dar nu sunt ordonatate. Pentru o optimizare a algoritmului, ordonarea se poate face în timpul scanării. Totuși algoritmul prezentat a fost mai usor de implementat deoarece pot apărea diferite probleme dacă se dorește ordonarea în timpul scanării.

La finalul unui ciclu de scanare, se verifică dacă lista este goala. Dacă această condiție este adevarată, atunci înseamnă că drona a ajuns într-o înfundatură și este marcată ca fiind moartă. Dacă nu este adevarată, atunci se încearcă mutarea punctelor din lista temporară în listele care conțin cele două margini ale străzii. Dacă în urma acestui proces lista temporară nu s-a golit, atunci înseamnă că există o a treia margine și se poate trage concluzia că drona a ajuns într-o intersecție. În acest caz drona este marcată ca fiind moartă și se va apela funcția de rezolvare a intersecției. Marcarea dronei ca fiind moartă, este necesară deoarece în bucla principală de control trebuie pornite doar dronele copii. De asemenea trebuie menționat faptul ca drona nu mai poate fi refolosită deoarece păstrează în memorie coordonatele unei strazi.

O dată ce a ajuns într-o intersecție, drona trebuie să identifice coordonatele de început a fiecărei străzi care se ramifică din acea intersecție. Aceste coordonate sunt necesare pentru a putea inițializa dronele-copii care vor continua procesul. Centrul dronei se poate afla în acest moment în două locații geometrice importante: la finalul străzii (înainte de intrarea în intersecție) sau în interiorul intersecției. În continuare sunt prezentati pașii care vor fi parcurși pentru a procesa intersecția:

Se identifică punctul din lista temporară care se află la distanța cea mai mica de centrul dronei. În lista temporara sunt stocate toate punctele care alcătuiesc marginile străzilor din intersecție. Astfel se va determina un punct care reprezintă un colț al intersecției

Se inițializează o lista nouă pentru o a treia margine, în care se plasează acest punct. Se mută toate punctele din lista temporară care se pot lega de acest punct. În acest moment s-a identificat o margine a unei străzi care iese din intersecție.

Se identifică punctul din lista temporară care se afla la distanța cea mai mica de punctul identificat anterior și se repetă procesul.

În acest moment s-au identificat două margini ale unei străzi care ies din intersecție. Procesul se repeta, pana când lista temporară se golește

Se construiesc drone noi care sunt inițializate cu coordonatele pentru strada găsita și cu numărul intersecției din care pornește. Drona părinte este marcată ca fiind moartă, și memorează numărul intersecției la care a ajuns. Dronele copii sunt marcate ca fiind vii, și vor fi repornite în bucla principală de control

Dupa ce dronele au terminat de procesat harta, se salvează într-un fișier numărul intersecției din care a pornit, numărul intersecției în care a ajuns, și coordonatele străzii pe care a parcurs-o. Acest fișier este apoi parsat de către simulator și se poate realiza matricea în care se păstrează structura logică a hărții. Inițial, matricea va avea o dimensiune de 1×1 și va conține un obiect de tip null. Pe măsura ce numărul intersecțiilor citite din fișier crește, matricea va fi mărită, și populată tot cu null, iar peste aceste valori vor fi introduse obiectele de tip stradă. În Fig.5.3 sunt prezentate rezultate experimentale obținute în timpul procesării unei astfel de hărți.

Figura 5.3 Procesarea hărții – versiunea I

Procesarea hărții – versiunea II

Realizarea primului algoritm pentru procesarea hărții s-a dovedit a fi o sarcina dificilă. Problemele au apărut la procesarea intersecțiilor, în momentul în care două drone încercau să proceseze aceeași intersecție în același timp. Rezolvarea acestei probleme, propunea soluții dificile, iar algoritmul devenea tot mai complex. În același timp, după cum se poate observa și din Fig 5.3, liniile trasate de către drone la procesarea intersecțiilor nu coincid cu realitatea. Un alt dezavantaj al primei aplicații este timpul de procesare. Procesarea unei hărți ca cele prezentate în Fig 5.3 durează mai mult de 60 de secunde. Aceste probleme au dus la nevoia de a găsii o nouă soluție. Soluția a constat în colorarea intersecțiilor cu o anumită culoare prestabilită (R=100, G=100, B=100). Astfel se rezolvă problema sincronizării dronelor, a preciziei cu care sunt trasate liniile intersecțiilor, și a timpului de procesare al hărții, care scade sub 3 secunde.

Algoritmul principal de control e similar cu algoritmul din prima aplicație și anume: se plasează drone pe o stradă de la marginea imaginii, iar dronele se răspândesc pe ramificațiile străzilor. Diferența apare la parcurgerea străzilor și procesarea intersecților. Deoarece se poate identifica cu ușurință intersecția, nu mai e nevoie ca drona să scaneze strada cu ajutorul unui cerc. O dată ce s-a identificat punctul de început al străzii, se verifică doar punctele din jurul acestui punct, până ce se găsește următorul punct care reprezintă o margine a străzii. Căutarea acestui punct se va realiza prin verificarea punctelor vecine. Spre deosebire de aplicația prezentată anterior, în cazul de fața trebuie să se verifice doar opt puncte. În versiunea precedentă era nevoie să se identifice toate punctele din interiorul unui cerc, numărul acestora fiind mult mai mare. Mai mult decât atât, era nevoie și de o aproximare pentru a putea plasa punctele corespunzator.

Astfel, drona se va deplasa de-a lungul marginilor străzilor până în momentul în care întâlnește un pixel de culoarea intersecție. Marginile străzilor vor fi memorate, iar apoi se poate procesa intersecția. Pentru a procesa intersecția se parcurg următorii pași:

Se identifică primul punct de la marginea intersecției prin verificarea condiției ca pixelul să fie de culoarea intersecției (R=100, G=100, B=100), iar lângă el să existe un pixel de culoare albă sau de orice altă culoare. Prin găsirea unui pixel de culoare albă se poate trage concluzia că se parcurge linia intersecției care se intersectează cu o stradă. Daca pixelul este de altă culoare atunci linia parcursă se află între două străzi ale intersecției.

Se caută următorul punct de la marginea intersecției prin verificarea condițiilor prezentate mai sus.

Cordonatele punctului de început sunt memorate. De fiecare dată când se găsește un nou punct, se verifică dacă acest punct nu coincide cu punctul de început al intersecției. Dacă această condiție este adevarată, atunci procesarea intersecției s-a încheiat

În figura 5.4 este prezentată imaginea din figura 5.1 după procesare. Se poate observa că una dintre intersecții a fost mărită, pentru a putea ilustra în detaliu modalitatea prin care a fost procesată intersecția.

Figura 5.4 Procesarea hartii versiunea II

Timpul de procesare a unei imagini ca cele prezentate în Fig.5.4 este sub 3 secunde. Însă pe măsură ce dimensiunea hărții se dublează timpii de procesare cresc exponential. O soluție la această problemă ar fi împărțirea unei hărti mari în imagini mai mici, iar apoi combinarea rezultatelor. Acest lucru ar asigura o creștere liniară a timpului de procesare. Însă și asa timpii de procesare sunt îndeajuns de mici încât să nu prezinte probleme mari.

În continuare este prezentat codul implementat pentru bucla principală de control a dronelor. Bucla e valabilă atât pentru prima, cât și pentru a doua aplicație. Codul a fost comentat, dar va fi și explicat în rândurile următoare.

Primul pas constă în identificarea străzilor de la marginea imaginii și plasarea unor drone pe acele străzi. Aplicația a fost în așa fel concepută încât se pot plasa drone pe toate străzile de la marginea imaginii. Totuși, deși acest mecanism functionează, aplicația nu a fost structurată pe mai multe fire de execuție. Folosirea mai multor fire de execuție ar putea îmbunătății performanțele aplicației, dar ar pune în pericol sincronizarea dronelor o dată ce au ajuns la intersecție. Din acest motiv pornirea mai multor drone va procesa harta în același timp ca și pornirea unei singure drone. Motivul pentru care acest lucru se întâmplă este un rezultat al faptului ca dronele proceseaza fiecare stradă secvențial. Aplicația poate fi îmbunătățită pentru a putea folosii mai multe fire de executie, dar acest lucru nu este recomandat, deoarece sincronizarea dronelor ar putea ridica probleme mai mari. Aceste probleme ar putea propune soluții care într-un final ar putea încetinii aplicația.

După ce dronele de la marginea străzii au fost inițializate, acestea sunt plasate într-o listă. Pe măsură ce lista este parcursă dronele sunt comandate să scaneze o stradă. După ce drona a terminat de scanat strada, aceasta va genera o listă de drone copii. Aceste drone vor fi plasate la finalul vectorului, iar procesul se repeta.

for(int i=0;i<mainDrones.size();++i){

//daca drona nu mai e in viata, inseamna ca a

//memorat deja o strada si se poate trece peste

if(!mainDrones [i]->alive){

continue;

}

//drona scaneaza strada; in aceasta functie drona va initializa si dronele copii

mainDrones [i]->scanStreet();

//daca sa ajuns la o infundatura, se incrementeaza contorul care numara //intersectiile si se marcheaza infundatura ca o intersectie

if(mainDrones [i]->reachedDeadEnd()){

mainDrones [i]->toIntersection = countingIntersections++;

continue;

}

//se verifica daca drona a ajunsa la o intersectie care a fost deja scanata

if(mainDrones [i]->reachedCheckedIntersection()){

mainDrones [i]->matched = true;

match(myDrones[i]);

continue;

}

//daca sa ajuns pana in acest punct inseamna ca drona are copii

//se incrementeaza contorul intersectiei

mainDrones [i]->toIntersection = countingIntersections++;

//se adauga copii dronei in lista principala

for(int j=0;j< mainDrones [i]->childDrones.size();++j){

mainDrones [i]->childDrones[j]->fromIntersect = mainDrones [i]->toIntersction;

mainDrones.push_back(mainDrones [i]->childDrones[j]);

}

}

Simulatorul

Pentru dezvolatarea simulatorului s-a optat pentru folosirea librăriei OpenGL în cadrul limbajului de programare C++. Librăria OpenGL definește un standar API (Application Programing Interface) de nivel mic, folosit pentru a desena primitive grafice în două sau trei dimensiuni. Cu ajutorul acestor primitive se pot dezvolta scene complexe tridimensionale. Nivelul scăzut al acestei librării îl obligă pe programator să realizeze algoritmi complecși, dar ii oferă acestuia o libertate mare în a crea și implementa noi algoritmi. Această libertate nu este oferită de către alte API-uri grafice de nivel mai înalt.

Desenarea scenei

Coordonatele străzilor au fost plasate de către aplicația prezentată în capitotul anterior într-un fișier .txt în următorul format:

Prima linie: numerele celor două intersecții care conecteaza strada

A doua linie: Coordonatele primei margini ale străzii: x11 y11 x12 y12 …

A treia linie: Coordonatele pentru cea de a doua margine a străzii: x21 y21 x22 y22 …

Aceste informații sunt preluate de către simulator, parsate și stocate în matricea menționată în capitolele anterioare

OpenGL permite desenarea unor primitive grafice precum: triunghiuri, linii sau poligoane. Aceste primitive sunt desenate prin precizarea coordonatelor fiecărui nod din care e alcătuită primitiva. În figura 5.5 sunt prezentate câteva moduri de desenare oferite de către API-ul OpenGL.

Figura 5.5 Moduri de desenare în OpenGL

Dupa cum se poate observa și din figură, cea mai buna solutie pentru desenarea străzilor este prin folosirea modului GL_QUAD_STRIP. O primă problema care apare la desenarea unei străzi, este faptul că lungimile celor două margini ale strazii pot să difere cu puțin. Ca de exemplu, o margine a străzii poate avea 500 de noduri, în timp ce cealaltă poate avea 503. Această problemă poate fi ușor remediată prin desenarea în modul GL_QUAD_STRIP până în momentul în care se ajune la numărul cel mai mic de noduri, iar apoi se poate desena în modul GL_TRIANGLE_FAN. Totuși, aceasta soluție este destul de complexă și lungimea diferită a celor două margini poate prezenta alte probleme mai târziu. Din acest motiv soluția aleasa este de a elimina câteva noduri din lista mai lungă. Nodurile se elimină la intervale cât mai mari pentru ca această transformare să nu fie sesizabilă. Cu ajutorul unui astfel de algoritm străzile pot fi desenate folosind doar modul GL_QUAD_STRIP.

O altă problemă care apare la desenarea străzilor este dată de faptul că străziile au un aspect pătrățos. Aspectul pătrățos rezultă din dimensiunile relativ mici ale imaginii. O soluție evidentă ar fi procesarea unei imagini mai mari de o rezoluție mai bună. Totuși această soluție nu este implementabilă, deoarece timpul de procesare al hărții crește puternic, putând duce chiar la căderea sistemului. O soluție mai eficienta constă în aplicarea unui filtru de netezire. Mai jos este prezentat un exemplu pentru realizarea unui astfel de filtru.

ys(1) = y(1)

ys(2) = (y(1)+y(2)+y(3))/3

ys(3) = (y(1)+y(2)+y(3)+y(4)+y(5))/5

ys(4) = (y(2)+y(3)+y(4)+y(5)+y(6))/5

Filtrul este inspirat din functia smooth a aplicației Matlab [21]. O astfel de funcție a fost implementată și în simulator. Timpul de procesare pentru o hartă ca cea prezentată în figura 5.1 este sub o secunda. În figura 5.5 sunt prezentate rezultate experimentale obținute în urma folosirii unui astfel de filtru.

a). Înainte de netezire b). După netezire

Figura 5.5 Aplicarea filtrului de netezire

După aplicarea filtrului de netezire se poate renunța la unele puncte din alcătuirea străzii. Ca de exemplu marginile străzilor pot fi parcurse cu un anumit pas. În exemplul prezentat pasul optim s-a identificat experimental ca fiind de trei. Dacă se trece de acest pas atunci calitatea imaginii scade vizibil. Această optimizare oferă posibilitatea de a încărca o hartă de trei ori mai mare.

După remedierea problemelor prezentate mai sus, harta poate fi desenată în întregime prin parcurgerea matricii în care sunt ținute străziile. Harta este încărcată la nivelul zero pe axa Z, într-un plan bidimensional. În fig 5.6 se poate observa că intersecțiile nu au fost desenate, în locul lor s-a ales să se plaseze numerele intersecțiilor. Aceste numere sunt atribuite aleatoriu de către aplicația care procesează harta, dar sunt utile în testarea aplicației. În acest sens a fost implementat un algoritm care preia două numere introduse de la tastatura și colorează strada ce leagă intersecțiile respective. Din acest punct e simplu de realizat un algoritm care e capabil să eleveze sau să curbeze străzile. Pentru a putea implementa aceasta funcționalitate, algoritmul trebuie îmbunătățit pentru a putea selectat doar anumite poțiuni din stradă. După ce o porțiune de strada a fost selectată deplasarea ei în sus-jos sau în stânga-dreapta se va realiza prin incrementarea, respectiv decrementarea coordonatelor pe una din cele trei axe. Modificarea coordonatelor poate fi realizată datorită modului în care au fost desenate străzile, și anume GL_QUAD_STRIP. Acest mod este folositor doarece deplasarea unui punct va avea ca efect rearanjarea automată a poligoanelor care construiesc străzile. În figura 5.6 sunt prezentate rezultatele obținute după încărcarea hărți.

Figura 5.6 Harta încarcată în simulator

Pentru a da un aspect mai placut, pe străzile desenate se poate încărca o textură. Textura se va încărca folosind tehnica de mapare prin specificarea coordonatelor UV. Această tehnica se folosește la lipirea unei imagini bidimensionale pe o suprafață tridimensională. În cazul de față suprafața este tot bidimensională. Coordonatele UV sunt coordonatele asociate imaginilor. Fiecare imagine e definită ca fiind construită pe baza a doi vectori perpendiculari de lungime 1. Astfel, lungimea și lățimea imaginii va fi scalată între 0 si 1. În cazul de față maparea se realizează destul de usor, deoarece străzile au fost desenate cu un anumit pas, si anume de trei. Tot ce trebuie facut este să se specifice din poligon în poligon coordonatele de început și de sfârșit a imaginii. În figura 5.7. este ilustrat procedeul prezentat.

Figura 5.7 Încărcarea texturii pe străzi

Funcțiile principale folosite pentru a putea realiza algoritmul prezentat sunt:

glTexCoord2f(float x, float y);

glVertex3f(float x, float y, float z);

Se poate observa ca funcția glVertex3f primește trei parametrii pentru a putea preciza toate cele trei coordonate ale unui punct în spațiu. Al treilea parametru este setat în cazul de față pe zero. Cu ajutorul acestei funcții se vor preciza coordonatele marginilor străzii, pentru a putea desena poligoanele care alcătuiesc o strada. Funcția glTexCoord2f, primește doar doi parametrii, necesari pentru a putea preciza coordonatele UV ale texturii. Parametrii trimiși funcției glTexCoord2f trebuie sa se încadreze între 0 si 1.

Încărcarea texturii la interscții este mai dificil de realizat, deoarece în acest caz nu mai sunt doar două margini paralele, intersecția fiind realizată dintr-un număr variabil de margini. De asemenea, nici aplicarea filtrului de netezire pe marginile intersecție nu este atât de ușor de realizat.

Aplicația care procesează imaginea hărții, returnează, pe lângă coordonatele străzii și coordonatele fiecărui punct din care sunt alcătuite intersecțiile. Pentru a putea desena intersecțiile, acestea vor fi privite ca un poligon. Aplicarea filtrului de netezire nu se poate face direct pe linia intersecției. Acest lucru nu este posibil, deoarece linile dintre străzi nu ar mai fi curbate în modul dorit. Pentru a aplica filtrul de netezire într-un mod corect, trebuie identificate marginile intersecției aflate între două străzi. Acest lucru se realizează prin identificarea punctelor aflate la distanța cea mai mica de finalul străzii. Pe acele margini se poate aplica filtrul de netezire pentru a obține efectele prezentate în Fig 5.8..

Încărcarea texturii este de asemenea dificil de realizat, deoarece fiecare punct care alcătuiește intersecția este încărcat la coordonatele sale în planul hărții. Trebuie în acest caz realizată o translație în punctul 0, iar apoi poligonul trebuie scalat între 0 si 1. Pentru a realiza acest lucru, trebuie identificate punctele intersecției aflate la distanța cea mai mică pe axa X, respectiv Y. Distanța respectivă va fi scăzuta din fiecare punct care alcătuiește acea intersecție. Astfel se va realiza translația în punctul 0. Pentru a realiza scalarea intersecției între 0 si 1, fiecare punct va fi împărțit la punctul cel mai departe de punctul de origine. Acest lucru este necesar pentru a preciza coordonatele UV ale imaginii și a încărca textura peste poligonul care formează intersecția. În figura 5.8 sunt prezentate rezultatele obținute în urma aplicării algoritmilor prezentați mai sus.

Figura 5.8 Încărcarea texturii la intersecții

Timpii de procesare al acestor algoritmi sunt destul de ridicati, deoarece trebuie parcurs un număr relativ mare de noduri. Totuși acest algoritm este folosit doar la încărcarea hărții, neavând un impact în timpul rulării unui scenariu.

Aplicarea filtrului de netezire pe marginile intersecției, este realizată în scop estetic. Intesecția poate fi desenată și la unghiuri drepte. Aceste opțiuni sunt la alegerea utilizatorului.

Controlul mașinii

Mașina va fi ghidată dupa principiul sistemului de virare Ackerman. Acest sistem a fost descris în capitolul anterior și nu va mai fi descris. Modelul matematic pentru un astfel de sistem este foarte complex, motiv pentru care va fi descrisă o variantă simplificată. Acest model funcționează doar în spațiul bidimensional și nu i-a în considerare legile fizice: forța de frecare sau accelerația gravitațională. Algoritmul poate fi imbunătățit în acest sens. Varianta simplificată a sistemului de control al mașinii e ilustrată în Fig 5.8. Se poate observa că mașina este schițată sub forma unui vector. Pentru a simplifica desenul, pe figură nu a mai fost desenată direcția vectorilor. În ciuda faptului că mașina este ilustrată sub forma unui vector de lățime zero, modelul funcționează corect. Astfel pentru a calcula traiectoria mașinii se va considera că mașina are doar o roată în spate și una în față. Peste acest vector al mașinii, se poate plasa apoi un model real. Traiectoria ilustrată în figură, este traiectoria pe care o face punctul aflat pe centrul axei roților din spate a mașinii când aceasta virează. După ce aceasta traiectorie se cunoaște, restul traiectorilor se vor forma într-un mod natural. Un rol important în realizarea acestui model îl are roata ilustrată în figură. Aceasta roata este fictivă, și este plasata pe centrul axei roților din fată. Deși traiectoriile fiecărei roți se vor forma într-un mod natural, unghiul de rotire al roților din fața trebuie calculat separat. Problema care se pune constă în găsirea coordonatelor de început a vectorului mașinii (spatele masinii) și unghiul vectorului, în funcție de unghiul de virare și lungimea mașinii. Unghiul de virare se consideră unghiul roții fictive de pe centrul axei din față.

Figura 5.9 Modelul matematic de control al mașinii

Pentru a realiza un astfel de model sunt necesare următoare informații inițiale:

Vectorul de pozitie al mașinii: lungimea acestui vector este notată cu și este egală cu distanța de la punctul de origine (0,0) până la spatele mașinii; vectorul este definit în coordonate polare prin : ,

Vectorul mașinii: lungimea acestui vector reprezintă lungimea mașinii și este notat cu ; în coordonate polare vectorul este definit de: ,

Vectorul roții: lungimea acestui vector o reprezintă jumătate din diametrul roții. Lungimea nu este relevantă în realizarea modelului matematic pentru a vira, dar e folositare pentru a știi la ce înălțime trebuie plasată mașina față de pământ. Unghiul vectorului a fost notat cu . De menționat, că unghiul de virare este diferența dintre acest unghi și unghiul la care se află mașina ()

Cu ajutorul funcțiilor sinus și cosins se pot calcula coordonatele fiecărui vector prezentat în imaginea de mai sus. Vectorul de poziție al masinii va fi definitit în funcție de unghiul la care se află mașina față de axa OX și lungimea mașinii. Aceste coordonate sunt de fapt coordonatele spatelui mașinii. Calcule sunt prezentate prin relațiile (5.1) si (5.2)

=> (5.1)

=> (5.2)

Relațiile (5.3) si (5.4) sunt realizate într-un mod similar și sunt folosite pentru a determina coordonatele pentru fața mașinii. După cum se poate observa, în acest caz e necesar să se adune coordonatele vectorului de poziție al mașinii.

(5.3)

(5.4)

Unghiul este ușor de calculat prin efectuarea scăderii între unghiul mașinii și unghiul roții(). Unghiul reprezintă unghiul de virare al mașinii, iar pe baza funcției tangente, se poate calcula raza cercului (5.5).

=> (5.5)

După ce s-a aflat lungimea razei cercului, se pot calcula coordonatele centrului cercului. În acest caz s-a presupus că mașina virează la stânga. Astfel unghiul folosit în ecuații, este Dacă mașina virează la dreapta, atunci unghiul va fii . Ecuațiile sunt prezentate în relațiile (5.6) si (5.7)

(5.6)

(5.7)

Pentru ca mașina să pastreze viteza dorită, trebuie calculat arcul de cerc pe care mașina trebuie să îl parcurgă pentru a păstra viteza specificată. Unghiul este unghiul prin care se definește cât trebuie mașina să se deplaseze pe cerc în funcție de distanța pe care trebuie să o parcurgă. Acest unghi este calculat cu ajutorul relației (5.8). Parametrul viteză, este defapt distanța, pe care mașina o parcurge de fiecare dată când scena este reactualizată.

(5.8)

În relația (5.9) este prezentat calculul final, și anume coordonatele pe axele X-Y la care trebuie deplasată mașina. De mentionat că unghiul mașinii este echivalent cu unghiul pe care îl face raza cu axa OX. Pe baza acestei egalități se pot realiza ecuațiile (5.9) și (5.10). În ecuațiile prezentate se i-a în considerare cazul în care mașina se deplasează în fată, din acest motiv unghiul folosit este: . Dacă mașina se deplasează în marșalier, atunci în ecuații se va folosii unghiul: .

(5.9)

(5.10)

Pe baza ecuațiilor prezentate mai sus mașina se poate comanda prin unghiul de virare și viteză. Viteza se poate prelua din curba de accelerație a mașinii, iar incetinirea mașinii din curba de decelerație. În acest moment se poate programa traseul mașinii manual, prin specificarea unghiurilor de virare, în funcție de distanta pe care mașina a parcurs-o.

Modelul poate fi imbunătățit și pentru a funcționa în cazul în care se dorește elevarea străzilor. Un astfel de model se poate realiza, prin deplasarea mașinii la următorul punct, iar când întalnește un punct care se află la o înălțime mai mare, trebuie calculată proiecția mașinii pe planul respectiv. De asemenea trebuie translatat, și sistemul prezentat în figura 5.9 . Un bun exemplu în acest sens, este dat de faptul că dacă mașina este înclinată într-o parte, atunci centrul cercului va fi mai jos, pe axa Z, iar acest lucru ar determina un viraj mai strâns. Această proprietate este folosita și în cursele NASCAR.

Modelul de mașina a fost realizat în blender și apoi importat în OpenGL, la niște coordonate inițiale:(x=0,y=0,=0). Noile coordonate sunt generate din ecuațiile prezentate mai sus. Rezultatele experimentale sunt prezentate în Fig 5.10. Linia roșie reprezintă traiectoria mașinii.

Figura 5.10 Simularea sistemului de virare

Inteligența artificială a mașinii

Prin algoritmul prezentat mai sus, mașina poate fi condusă prin setarea unghiului de virare si setarea vitezei. În acest sens a fost implementat un algoritm prin care mașina poate fi controlată de la tastatatura cu ajutorul săgeților. De remarcat în acest sens, faptul că, spre deosebire de majoritatea jocurilor, traiectoria mașinii când aceasta vireaza rămâne circulară. Jocurile sunt în așa fel concepute, încât roțile revin aproape instantaneu la pozitia inițială. Din acest motiv instalarea unui dispozitiv cu volan ar avea succes, simularea fiind foarte similara cu modul în mașina i-a virajele în realitate.

Pentru ca mașina să poată fi deplasată pe străziile încărcate în simulator, aceasta trebuie să fie capabilă să seteze unghiul de virare într-un mod automat. Acest lucru este necesar, deoarece mașina trebuie comandată să meargă spre punctele care alcătuiesc centrul benzii. Acest calcul presupune utilizarea unor formule matematice complexe, dar timpul de procesare este acceptabil. Notațiile nu vor fi prezentate din nou, deoarece au fost prezentate în capitolul anterior. De asemenea, pentru vizualizarea geometrică a modelului de virare se poate folosii Fig.5.8. Problema care se pune constă în identificarea unghiului de virare care va forma cercul ce va trece printr-un anumit punct.

Primul pas care trebuie realizat este găsirea centrului acestui cerc. Coordonatele acestui punct au notate cu , . Se poate observa că distanța de la centrul cercului până la roata din spate a mașinii, va fi egală cu distanța de la următorul punct până la centrul cercului. Formula pentru calculul distanței între două puncte într-un plan bidimensional este prezentată mai jos prin relația 5.11:

(5.11)

Coordonatele punctului următor la care trebuie să ajungă mașina au fost notate cu:, , iar notațiile folosite pentru coordonatele curente ale mașinii sunt: , . Pe baza formulei prezentate mai sus și datorită faptului că distanțele menționate sunt egale, se poate scrie următoarea relație (5.12):

(5.12)

De asemenea se cunoaște faptul că centrul cercului se află pe dreapta făcută de punctul acesta cu punctul reprezentat de spatele mașinii. Panta aceste dreptei se cunoaște, deoarece se cunoaște unghiul la care se află mașina. Astfel panta dreptei va fi unghiul la care se află mașina plus sau minus 90 de grade. Cele 90 de grade se adună sau se scad în funcție de unde se află punctul. Daca punctul se află în stânga mașinii, atunci mașina va trebui să vireze în stânga și se vor scădea 90 de grade. În mod analogic, dacă punctul se află în dreapta mașinii, mașina trebuie să vireze în dreapta și se vor aduna cele 90 de grade. Pentru a determina dacă punctul respectiv se află în stânga sau în dreapta a fost necesară implementarea unui algoritm care nu va fi discutat în lucrarea de față. Cunoscându-se punctul de pe acea dreaptă și panta dreptei se poate scrie următoarea relație (5.13):

(5.13)

S-a format astfel un sistem de două ecuații cu două necunoscute. După efectuarea calculelor se obțin relațile (5.14) si (5.15).

(5.14)

, (5.15)

Unde,

(5.15)

(5.16)

(5.17)

Cunoscând coordonatele punctelor pentru centrul cercului de virare, se poate calcula ușor și unghiul de virare. Se poate observa din figură că dreapta de la centrul cercului, până la roțile din față a mașinii este perpendiculară pe direcția de virare a roților. Panta acestei dreptei poate fi calculată ușor, iar apoi va rezulta unghiul la care trebuie rotite roțile pentru ca mașina să se deplaseze spre următorul punct.

Obținerea coordonatelor care alcătuiesc centrul străzii se realizeaza prin aplicarea mediei aritmetice pe punctele de pe cele două margini ale străzii. Se poate calcula apoi în mod similar centrul benzii. Astfel, strada poate fi împarțită într-un număr nelimitat de benzi. Totuși în cazul de față s-a presupus că strada are o singură bandă pe sens. În aplicatia prezentata mai sus strazile au fost desenate folosind un pas de trei. Acest lucru înseamnă că punctele au fost încărcate din 3 în 3 pixeli. O conversie pentru a sugera această mărime nu a fost făcută. Totuși acest lucru este relevant la deplasarea mașinii de-a lungul străzii, deoarece cu cât punctele sunt mai distanțate cu atât setarea unghiului care va duce mașina spre următorul punct va fi mai rară. Realizarea unui traseu pentru mașină în interiorul intersecției poate deveni o problemă, deoarece spre deosebire de o stradă, coordonatele din interiorul intersecției nu pot fi generate automat. Totuși algoritmul prin care mașina se deplasează din punct în punct, rezolvă în mod natural această problemă. Când mașina ajunge la finalul străzii, aceasta va fi comandată să se deplaseze spre urmatorul punct care reprezintă începutul celeilalte străzi. Astfel se va seta o traiectorie circulara, care de cele mai multe ori este și traiectoria dorită. În fig 5.11 este ilustrată acestă proprietate.

Figura 5.11 Traiectoria mașinii la intersectie

Pentru a deplasa mașina din punct în punct, controlerul mașini, va calcula distanța între mașină și următorul punct la care aceasta trebuie să se deplaseze. Dacă această distanța este mai mică de o anumită valoare, atunci se va lua din listă următorul punct. Acest algoritm, nu este totuși un algoritm exact din punct de vedere matematic, deoarece mașina poate fi comandată să meargă cu o anumită viteză, iar deplasarea pe care trebuie să o facă va depășii într-un final punctul respectiv. Acest lucru este o problemă, deoarece se poate întâmpla ca de la punctul respectiv mașina să primească o instrucțiune pentru a schimba viteza. În momentul de față mașina se va deplasa cu aceeași viteză chiar dacă a depășit acel punct. Pentru a rezolva această problemă, trebuie calculată și distanța pe care mașina trebuie să o parcurgă cu o anumită viteză.

În continuare este prezentată o parte din algoritmul care este folosit pentru a calcula urmatăoarele coordonate a mașinii, dacă se cunoaște unghiul și viteza.

void Car1:: calculateCoordinates(){

//calcularea coordonatelelor vectorului de urmarire al masinii(spatele masinii)

calculateTrackingCoordinates();

//calcularea coordonatelelor vectorului de pozitie al masinii(fata masinii)

calculateFrontCarCoordinates();

}

void Car1:: calculateTrackingCoordinates(){

tracking_angle_degrees = makeItPositive(tracking_angle_degrees);

tracking_angle_radians = getRadians(tracking_angle_degrees);

x_tracking=tracking_radius*cos(tracking_angle_radians);

y_tracking=tracking_radius*sin(tracking_angle_radians);

}

void Car1:: calculateFrontCarCoordinates(){

car_angle_degrees= makeItPositive(car_angle_degrees);

car_angle_radians = getRadians(car_angle_degrees);

car_front_x = x_tracking + car_length*cos(car_angle_radians);

car_front_y = y_tracking + car_length*sin(car_angle_radians);

}

//masina este comandata sa se deplaseze cu o anumita viteza la un anumit unghi

car->move(speed, angle);

//masina este rotita si mutata la coordonatele rezultate

glTranslatef(car1->x_tracking, car1->y_tracking,0);

glRotatef(car1->car_angle_degrees, 0, 0, 1);

TESTARE ȘI VALIDARE

Pentru evaluarea funcționării aplicației în conformitate cu specificațiile au fost rulate următoarele tipuri de teste:

Testarea funcționalităților

Testarea performaței

Tratarea erorilor

Testele au fost rulate pe un sistem având următoarele performanțe:

Procesor: Intel(R) Celeron(R) CPU P4600 @ 2.00GHz,

Memorie RAM 2.00GB

Sistem de operare Window 7, 64 bit

Placa video încorporată: Intel(R) Graphics Media Accelerator HD (Celeron), Dedicated Video Memory: 64 MB

Testarea aplicației pentru procesarea imaginii

Testarea funcționalităților

Pentru a testa dacă structura grafului a fost construită corect au fost procesate și importate în simulator mai multe hărti de dimensiuni diferite. Problemele care pot apărea în acest caz sunt în principal la procesarea intersecților. În acest caz s-a testat dacă aplicația identifică corect străzile care se ramifică din fiecare intersecție. Testarea structurii grafului s-a realizat cu ajutorul algoritmului implementat în simulator, prin care se introduc două numere de la tastatura și este colorată strada care leagă intersecțiile respective. Astfel s-a putut testa atât realizarea corecta a conexiunilor dintre intersecții, cât și numerotarea intersecților. Principala problemă care poate apărea la procesarea intersecțiilor este dată de faptul că dintr-o intersecție se pot ramifica un număr nelimitat de străzi. Toate aceste lucruri au fost testate și atât aplicația care procesează harta, cât și algoritmul care importă harta s-au dovedit a fi funcționale.

O altă problemă care poate apărea la procesarea străzilor este dată de faptul că punctele care alcătuiesc strada nu sunt neaparat ordonate în modul așteptat. Acest lucru poate genera probleme în momentul în care sunt desenate străziile, dar și în momentul în care mașina caluleaza traseul pe care trebuie să se deplaseze. Aceste probleme pot fi omise la desenarea hărții, deoarece străzile sunt desenate din poligoane „umplute”. Totuși, se poate întâmpla ca două puncte aflate la distanțe mici unele de altele să nu fie ordonate corect. Testarea acestei functionalități a fost realizată prin desenarea liniilor în locul poligoanelor. Linile sunt trasate paralel de-a lungul străzii de la o margine la cealalalta. Această problema poate devenii majora la deplasarea mașinii de-a lungul străzii, deoarece mașina calculează constant unghiul de virare pentru a ajunge în urmatorul punct. Acest punct este calculat prin calculul succesiv a mediei aritmetice a celor două margini, iar dacă apar mici erori mașina nu va mai fi capabila să urmeze traseul dorit. Desigur acest defect ar fi apărut și la testarea mașinii, dar pe măsura ce aplicația avanseză, apar tot mai multe potențiale erori, iar cu cât se întârzie mai mult detectarea lor, cu atât problema va fi mai dificil de sesizat și corectat.

De asemenea a mai fost testat și algoritmul care elimina câteva puncte din marginile străzii pentru a egala dimensiunile acestora. În acest caz, se poate întâmpla ca punctele eliminate să se afle în apropierea intersecțiilor, iar la desenarea intersecțiilor ar apărea un mic gol între strada și intersecție. Acest defect poate pune probleme și în momentul în care se calculează centrul benzii

Testarea performanței

Testarea performantelor pentru prima versiune a aplicației a produs rezultate acceptabile. Procesarea unei imagini ca cele prezentate în capitolul V (Figura 5.1) a durat aproximtiv 60 de secunde. Aplicația poate fi imbunatațită în acest sens. Totuși dezvoltarea celei de a doua aplicații s-a dovedit a fii o solutie mai bună. Timpul necesar pentru a procesa o imagine similara a scăzut sub 3 secunde. În tabelul 6.1 sunt prezentate rezultatele obținute la dublarea dimensiunilor imaginii. Pentru a păstra o oarecare consistență, nu s-au dublat doar dimensiunile imaginii, ci și numărul de intersecții și de străzi. Se poate observa că timpul crește exponential, motiv pentru care nu a fost creat un tabel și pentru prima versiune a aplicației. Totuși, rezultatele obținute au fost îndeajuns de bune pentru a încarcă o hartă de dimensiuni acceptabile în simulator.

Tabelul 6.1 Timpul de procesare al imaginii

Tratarea erorilor:

Prima eroare care poate apărea este la precizarea unei adrese greșite a imaginii care se dorește a fi procesată. În acest caz se va loga un mesaj prin care se va specifica acest lucru. De asemenea pot apărea erori la introducerea unei imagini de un format care nu este suportat de librăria OpenCV, caz în care se va loga același mesaj. Formatele suportate de librăria OpenCV sunt urmatoarele:

.bmp, .dib

.pbm, .pgm, .ppm

.sr, .ras

O altă eroare care poate apărea este ilustrată în Fig.6.1. Se poate observa că pentru ca aplicația sa funcționeze corect, linile străzilor trebuie să fie desenate perfect. În acest sens, se poate implementa un algoritm care să remedieze această problemă, dar o soluție mai fiabila este remedierea acestor probleme de către utilizator. De asemenea mai pot apărea probleme la desenarea intersecțiilor sau la folosirea culorilor. În acest caz trebuie avut grija ca intersecțiile să fie umplute cu culoare de la o margine la cealaltă a străzii. Nu toate erorile pot fi identificate și logate pentru a da sfaturi utile utilazatorului. Din acest motiv trebuie avut grijă ca harta să fie editată în conformitate cu specificațiile menționate.

Figura 6.1.Editarea incorectă a străzilor

Testarea simulatorului

Testarea funcționalităților

Testarea algoritmului de control al mașinii s-a realizat atât prin controlul acesteia de la tastatură cât și prin programarea mașinii să meargă automat pe un traseu prestabilit. Testarea algoritmului de control al mașinii s-a facut în timp ce acesta a fost dezvoltat. În acest sens au fost trasate linii și cercuri pentru a putea vizualiza corectitudinea implementării modelului matematic. Pentru testarea modelului s-a considerat doar cadranul I al sistemului de coordonate carteziene. Mașina functionează totuși și în celelalte cadrane, dar pot apărea probleme la trecerea dintr-un cadran în altul. Trecerea prin zero poate devenii o problema, deoarece algoritmul presupune multe împărțiri, și există șanse mari ca să se ajungă în situația în care o variabilă va fi împărțită la zero. De asemenea funcția tangentă poate fi o problemă în aces caz, deoarce rezultatul acesteia poate fi uneori infinit. Totuși, harta procesată nu va returna decât coordonate pozitive, motiv pentru care nu a fost nevoie să se corecteze algoritmul. Acest lucru a fost testat prin controlarea mașinii de la tastatura. Mai trebuie menționat faptul că pentru controlul mașinii de la tastatură s-a implementat un algoritm prin care mașina încetinește automat datorită forței de frecare. De asemenea a fost implementat și un algoritm prin care roțile mașinii revin la punctul inițial pe măsură ce mașina se deplasează. Rezultatele implementarii acestui algoritm nu au fost un succes complet, deoarece e nevoie de o calibrare a unor parametrii care poate pune unele probleme dificile. Totuși comportamentul mașinii dacă acești parametrii nu sunt luați în considerare s-a dovedit a fi un succes.

Programarea unui traseu pentru mașină s-a dovedit o a fi o sarcină puțin mai dificilă, deoarece și în acest caz au fost necesare diferite calibrări. Distanța între puncte a fost în acest caz problematică. Dacă distanța între puncte este prea mică, atunci mașina își schimbă direcția prea des și mașina oscilează puternic în încercarea de a rămâne pe traseu. Traseul a fost programat în așa fel încât distanța între puncte să fie îndeajuns de mare încât să se elimine oscilația mașinii, dar îndeajuns de mică încât să rămână pe traseu. Această problemă poate fi soluționată și prin implementarea unor algoritmi care ar putea permite corectarea acestui comportament.

După generarea traseelor, prin precizarea unor intersectii, a fost testată si utilizarea unor semafoare cu două stări. În Fig 6.2 sunt prezentate rezultatele experimentale obținute în urma rulării unui astfel de scenariu.

Figura 6.2. Testarea semafoarelor

Semafoarele au fost desenate prin folosirea unor dreptunghiuri care își schimbă culoarea în verde, respectiv în roșu. Pe măsură ce mașinile se apropie de un semafor, acestea verifică dacă culoarea semaforului este roșie, sau dacă este verde dar timpul rămas este prea scurt pentru a putea traversa intersecția. Dacă una dintre cele două condiții este îndeplinită, atunci mașina va fi comandată să se oprească. De asemenea mai trebuie verificat pentru fiecare mașină, dacă este pe un curs de coliziune cu mașina din față. Această condiție poate fi verificată prin calcularea distanței între cele două mașini. Dacă această distanță este mai mică decât un anumit prag, atunci mașina va fi comandată să încetinească sau să se oprească. Oprirea sau încetinirea mașinii se va realiza treptat după o anumită curbă de accelerație. În cazul de față, curba de decelerație este liniară.

Pentru realizarea scenariului s-a ales configurarea a două trasee care se intersectează. Traseele se intersectează în două puncte, iar în acele puncte au fost plasate semafoare pentru a dirija traficul. Mașinile sunt introduse în scenariu la anumite intervale de timp prestabilite, pentru a evita coliziunile și suprapopularea. După introducerea lor în scenariu, acestea sunt plasate în două liste, corespunzatoarea traseelor alese. Plasarea lor în liste este necesara pentru a detecta coliziunile.

Testarea semafoarelor a fost realizată prin modificarea numărului de mașini și a intervalelor de timp la care sunt introduse. Rularea scenarilor a arătat că atât semafoarele cât și mașinile funcționează conform specificaților

Testarea performanțelor

Principalul algoritm al acestei aplicatii constă în calculul următoarei poziții a mașinii dacă se cunoaște unghiul roților și viteza de deplasare. Algoritmul a fost discutat la partea de implementare și se poate observa că presupune efectuarea multor calcule. Totuși, timpul de procesare al acestei funcții este aproximativ 1 milisecunda.

Cel de-al doilea algoritm important, constă in calculul unghiul de virare care va duce mașina spre următorul punct. Și în acest caz timpul de răspuns a fost tot de aproximativ 1 milisecundă.

Timpul de răspuns al acestor algoritmi este foarte important, deoarece de fiecare dată când scena este redesenată, calculul noilor poziții al mașinilor trebuie să fie terminate în timp util. Dacă aceste calcule nu sunt terminate atunci simulatorul va funcționa cu intreruperi. Redesenarea scenei se poate poate face maxim la o secundă pentru a obtine rezultate tolerabile. Totuși o secundă este un pic cam mult pentru a fi tolerat de către ochiul uman. Un timp maxim tolerabil de către ochiul uman este de aproximativ 100 de milisecunde, ceea ce presupune o vizualizare de 10 cadre pe secunde. Astfel se poate spune ca un număr maxim de mașini suportate de simulator este aproximativ de 70 de mașini.

Un alt factor important care intervine în aceasta situație, este numărul vertex-urilor din care sunt alcătuite modelele de mașina. Placa grafică are un rol deosebit de important în această problemă. Modelul inițial de mașină încărcat în simulator avea aproximativ 1000 de vertex-uri, și astfel s-a putut încărca o singură mașina. După ce acest număr a fost redus la 200 de vertex-uri a fost posibilă încărcarea unui număr de aproximativ 10 mașini. Totuși, pentru a elimina complet aceste variabile, s-a încercat și încărcarea dreptunghiurilor în locul mașinilor, iar în acest caz a fost posibila încărcarea unui număr de 70 de mașini. În figura 6.2 sunt prezentate rezultatele obținute în urma încărcării a unui numar 50 de mașini. Se poate observa ca mașinile au fost desenate sub forma unor dreptunghiuri, astfel fiind posibilă și încărcarea unor modele pentru cateva blocuri. Pentru ca scena să fie cât mai realistă, se pot crea niște modele de către o persoana experimentată, care ar putea fi realizate dintr-un număr mai mic de vertex-uri dar un număr mai mare de normale. Normalele sunt vectorii perpendiculari pe fiecare poligon din care este alcătuită mașina și sunt folosiți pentru a calcula lumina reflectată. Prin realizarea unor astfel de modele, s-ar putea păstra performantele obținute, chiar dacă s-ar încarca niște modele mai sofisticate.

Figura 6.3. Testarea performanțelor

Tratarea erorilor

Încărcarea corectă a modelelor presupune o atenție deosebită. Trebuie avut grijă în acest sens la formatul modelului și la adresa de unde modelul este citit. Neîndeplinirea acestor cerințe va determina logarea unei erori.

Traseul a fost setat manual prin precizarea unor intersecții, iar linia ce trece prin mijlocul benzii a fost generată automat. Deoarece traseul a fost setat manual trebuie avut grijă ca banda pe care mașina este ghidată să fie corespunzatoare cu sensul în care mașina se îndreaptă, altfel mașina ar putea circula pe contrasens.

De asemenea trebuie avut grijă la configurarea timpilor de schimbare a culorilor semafoarelor. Trebuie în acest caz, luat în considerare dacă mașina are timp sau nu să traverseze intersecția, chiar dacă semaforul are culoarea verde. Setarea acestui parametru s-a realizat prin calibrare.

CONCLUZII

Rezumat

Lucrarea propune crearea unui simulator capabil să testeze mai multe sisteme de control pentru mașinile automate sau semi-automate. Nu toate funcționalitățile prezentate la partea de specificații au fost implementate. Până în momentul de față au fost implementate următoarele funcționalități:

Posibilitatea de a convertii o imagine a unei hărți Google într-o structură de date care poate fi importată în simulator.

Crearea unui algoritm de control al mașinii capabil să simuleze deplasarea mașinii în spațiul bidimensional.

Crearea unei inteligențe artificiale pentru mașină care e capabilă să urmeze un set minim de instrucțiuni

Posibilitatea de a încărca modele pentru a crea scenarii mai apropiate de realitate

Aplicația care procesează imaginea unei hărți are rolul de a oferii utilizatorului o modalitate intuitivă de a edita și de a importa o hartă în simulator. Se poate spune că în prima versiune a aplicației au apărut niște probleme care erau dificil de soluționat. Aceste probleme generau un timp mare de procesare, ceea ce ducea la dificultatea dezvoltării simulatorului. Dezvoltarea simulatorului a fost făcută în paralel cu dezvoltarea aplicației pentru procesarea hărții, iar din acest motiv acest timp a devenit inacceptabil. Totuși, cea de a doua versiune s-a dovedit a fi o soluție îndeajuns de fiabilă pentru a putea fi folosită, chiar dacă este necesară editarea manuală a imaginii.

Implementarea algoritmului de control al mașinii a fost de asemenea un succes. Succesul acestui algoritm se datorează timpului de procesare relativ scăzut în care se efectuează calculele necesare pentru a deplasa mașina. Dezvoltarea simulatorului a depins în mare măsura de acest algoritm, având în vedere că scopul lucrarii a constat în dezvoltarea unui sistem cât mai realist. De asemenea, mai trebuie menționat faptul că modelul matematic realizat permite configurarea mai multor tipuri de mașini. În acest sens se poate configura curba de accelerație, curba de decelerație și lungimea mașinii. Aceste caracteristici reprezintă parametrii principali care caracterizează sistemul de direcție al unei mașinii și capacitățile motorului.

Realizarea inteligenței artificiale a depins în mare măsură de algoritmul prezentat, având în vedere mecanismul prin care se calculează unghiul de virare care va duce mașina la următorul punct. Acest mecansim este deosebit de important, deoarece sistemul poate fi implementat și în realitate. Mașina a fost configurată cu o curbă de accelerație liniară, iar din loc în loc au fost plasate instrucțiuni pentru a comanda mașina să ajungă la o anumită viteză. Procesarea acestor instrucțiuni de către controlerul mașinii a putut fi testată prin implementarea semafoarelor. Aceasta funcționalitate a permis testarea scenarilor fără a fi nevoie să se ia în considerare alți parametrii care pot apărea în lumea reală.

Deși se poate pune în discutie utilitatea încărcării modelelor, la testarea simulatorului s-a putut observa că acestea au un rol deosebit de important. Acest lucru se datorează faptului că la vizualizarea scenariului se poate face o analogie mai ușoara cu lumea reală. Rezultatele obținute în urma rulării scenarilor pot fi analizate și în lipsa unor astfel de modele. Totuși atâta timp cât performanțele sistemului de calcul permit încărcarea modelelor, este recomandat ca scenariul să fie construit cât mai aproape de realitate. În cadrul simulatorului a fost testată încărcarea unor modele mai complexe pentru mașini și câteva modele mai simple pentru clădiri. Totuși, trebuie menționat faptul că modelele încărcate nu sunt realizate într-o manieră profesionistă, iar o dezvoltare ulterioara poate permite generarea unor scenarii mai sofisticate.

Posibilități de dezvoltare

Simularea traficului rutier cu ajutorul unui simulator ca cel prezentat în această lucrare presupune dezvoltarea unui sistem de o complexitate ridicată. Se poate considera că funcționalitățile implementate până în momentul de față oferă un schelet arhitectural, pe baza căruia se pot dezvolta și alte funcționalități. Aceste funcționalități oferă posibilitatea ghidării unei mașini autonome dacă pe parcursul traseului sunt amplasate semafoare la fiecare intersecție. Dezvoltarea ulterioara a simulatorului include adăugarea următoarelor funcționalități:

Elevarea străzilor

Îmbunătățirea sistemului de control al mașinii pentru a funcționa în spațiul tridimensional

Posibilitatea de conecta mai mulți utilizatori în rețea

Distribuirea sistemului

Dezvoltarea setului de instrucțiuni pentru inteligența artificială a mașinii

Implementarea unui algoritm care oferă posibilitatea de a eleva sau a curba străziile este relativ ușor de realizat. Acest lucru se datorează faptului că a fost implementat algoritmul prin care poate fi selectată orice stradă. Acest algoritm a fost dezvoltat pentru a testa aplicația, dar poate fi modificat pentru a putea selecta doar o porțiune din stradă, iar apoi se poate realiza modificarea coordonatelor acelei porțiuni. Astfel, se poate spune că elevarea sau curbarea străzilor nu este foarte dificil de realizat.

Îmbunătațirea sistemului de control al mașinii pentru a funcționa pe străzile elevate este totuși o problemă mai dificilă. Pentru a modifica sistemul trebuie ajustat modelul matematic de control al mașinii, iar acest lucru presupune utilizarea unor calcule matematice complexe. După cum a fost prezentat, nici un spațiul bidimensional un astfel de model nu a fost ușor de realizat. De asemenea mai trebuie luat în considerare faptul că timpul de procesare al fiecărei mașini va crește. Pe baza algoritmilor realizați până în prezent, se poate estima că un astfel de sistem ar crește timpul de procesare cu aproximativ o milisecundă. Acest lucru ar reduce numărul de mașini care pot fi încărcate în simulator la o treime. Totuși, dimensiunea scenarilor ar rămâne acceptabilă. De asemenea mai trebuie discutat despre introducerea proprietăților fizice care pot afecta mașina. Posibilitatea mașinii de a derapa este o problemă importantă care trebuie luată în considerare. În spațiul bidimensional, această proprietate este relativ ușor de adăugat, dar în spațiul tridimensional realizarea unui astfel de algoritm poate pune unele probleme.

Timpii de procesare sugereză că o arhitectură prin care se pot conecta mai mulți utilizatori în rețea este realizabilă. În acest sens, a fost testată o arhitectură de tip client-server, dar doar pentru a testa schimbul de mesaje. Arhitectura nu a fost implementată și în cadrul simulatorului

Distribuirea arhitecturii este probabil cea mai importantă funcționalitate care ar putea fi adăugată. Numărul mașinilor care pot fi rulate în momentul de față în simulator este acceptabil. Totusi, distribuirea arhitecturii ar putea crește considerabil acest număr. De asemenea se poate încerca și folosirea mai multor fire de execuții, dar o astfel de soluție nu ar îmbunății considerabil performanțele, ci doar ar optimiza algoritmul.

Dezvoltarea inteligenței artificiale a mașinii presupune implementarea unui algoritm de detectare a coliziunilor mai sofisticat. În momentul de față acest algoritm funcționează doar pentru mașinile autonome. Îmbunătățirea acestui algoritm ar putea permite detectarea coliziunilor și cu mașinile controlate de către utilizatori. Un astfel de algoritm nu este foarte dificil de realizat, dar poate crește timpul de procesare.

Având în vedere funcționalitățile implementate până în momentul de față, se poate spune că s-a realizat scheletul arhitectural pentru această aplicație.

Concluzii

O dată cu dezvoltarea tehnologică a sistemelor de identificare și cu creșterea semnificativă a puterii de calcul, s-a putut începe dezvoltarea diferitelor sisteme de control a mașinilor automate. Astfel de sisteme sunt necesare în ziua de astăzi, deoarece industria autovehiculelor se dezvoltă rapid, iar congestionarea traficului rutier devine o problemă din ce în ce mai mare. Tehnologiile care controlează aceste sisteme sunt încă în curs de dezvoltare, iar găsirea unei soluții nu pare a fii o sarcina ușoară.

În această lucrare s-a propus dezvoltarea acestor sisteme în paralel cu dezvoltarea unui simulator capabil să simuleze orice situație din lumea reală. Cu ajutorul unui astfel de simulator ar fi posibilă standardizarea unor teste pe care orice sistem de control al mașinii trebuie să le treacă. Rezultatele obținute în urma testării simulatorului arată că un astfel de sistem este realizabil. Testele rulate până în momentul de față au arătat că simulatorul este capabil să ruleze un număr de 50 de mașini pentru a simula diferite scenarii. Totuși, sistemul de calcul folosit este mai puțin performant, având în vedere posibilitățiile tehnologice actuale. Acest lucru indică faptul că dimensiunile scenariilor pot fi îndeajuns de mari pentru a putea testa aceste sisteme.

Un alt factor important, care încurajează folosirea unui simulator, constă în reducerea costurilor de dezvoltare. Soluțile implementate în momentul de față, propun utilizarea unor tehnologii avansate și testarea acestor mașini în mediul real. S-a discutat în acest sens despre crearea unor rute controlate în totalitate de semafoare. Acestă soluție, ar simplifica problema considerabil. Totuși, și în acest caz, trebuie folosite tehnologii avansate de identificare. Aceste tehnologii există totuși, și se dovedesc a fi din ce în ce mai fiabile.

Un rol important în dezvoltarea unor astfel de sisteme îl au și sistemele realizate până în prezent. Aceste sisteme nu sunt capabile să descrie totalitatea funcționalităților necesare pentru a realiza un vehicul complet autonom, dar trebuie remarcat faptul că fiecare poate ajuta semnificativ în creșterea calitații traficului. Diferite teste realizate în acest sens au demonstrat eficiența folosirii unui astfel de sistem. Trebuie menționat în acest caz, faptul că unele companii au început deja să integreze aceste sisteme. În 2013 Mercedes-Benz a anunțat lansarea unui model care oferă clienților săi opțiuni precum: asistență în păstrarea benzii, asistență în parcarea mașinii sau sisteme automate de frânare și de accelerare

De asemenea trebuie remarcat succesul mașinii autonome realizată de către Google. Mașina a fost testată pe străzile din Nevada, și din 300 000 de mile, 50 000 de mile au fost conduse fără intervenție umană. Aceste rezultate au permis legalizarea mașinilor autonome în patru state americane: Nevada, Florida, California și Michigan. Aceste sisteme sunt încă în faza de testare, dar având în vedere legalizarea lor, se poate spune că sunt un succes. Succesul mașinii Google nu s-a manifestat doar în America. În Europa, Germania, Franța, Olanda și Spania au permis de asemenea testarea acestor mașini, iar din anul 2015 Finlanda plănuiește să li alăture.

Totuși, o problema care poate apărea în această situație este dată de faptul că fiecare companie își dezvoltă propriul sistem. Prin această abordare, crearea unui sistem standardizat de control al unui vehicul autonom este dificil de realizat. Un astfel de simulator nu ar ajuta doar la testarea mașinilor, ci și la posibilitatea de a le dezvolta. Se poate spune astfel că realizarea unui simulator capabil să testeze aceste sisteme într-un mediu sigur este mai mult decât necesară.

Bibliografie

[1] John Sousanis, “World Vehicle Population Tops 1 Billion Units”, august 2011, articolul se poate găsi la : http://wardsauto.com/ar/world_vehicle_population_110815

[2] B. van Arem, C. M. J Tamp&egrave;re and K.M. Malone “”Modeling traffic flows with intelligent cars and intelligent roads”, Proc.IEEE Intell. Vehicles Symp., pp456-461, 2003

[3] Yizhen Zhang “Engineering Design Synthesis of Sensor and Control Systems for Intelligent Vehicles”, Degree of Doctor of Philosophy at California Institute of Technology, Mai 2006

[4] Ray Fuller, “Towards a general theory of driver behaviour” Accident Analysis & Prevention, Volume 37, Issue3, May 2005, Pages 461-472

[5] B.J.A de Graaf “Prediction and Simulation Models for Intelligent Vehicle Highway Systems” Master of Science at Delf University of Technology, Martie 2009

[6] K.Li and P Ioannou “Modelling of traffic flow of automated vehicles” IEEE Trans. Intell. Trans. Sys., vol.5, no. 2, pp.99-113. 2004

[7] Norbert Grünwald “A Mixed Reality Platform for Robotics and Intelligent Vehicles”, Masters Degree at Halmstad University – Sweden, May 2012

[8] Thomas F. Golob, Eugene T. Canty, Richard L. Gustafson, Joseph E. Vitt, “An analysis of consumer preferences for a public transportation system” Transportation Research, Volume 6, Issue 1, March 1972, Pages 81-102

[9] U. Franke  "Truck platoon in mixed traffic",  Proc. Intell. Vehicles Symp.,  pp.1 -6 1995

[10] A. Bose, P.A. Ioannou, “Analysis of Traffic Flow with Mixed Manual and Semiautomated Vehicles”, IEEE Transactions on Intelligent Transportation Systems, Vol4, No. 4, December 2003, pp. 173-188 

[11] C. Kreuzen “Cooperative adaptive cruise control” Master of Science Thesis at Delft University of Technology, Mai 2012

[12] P. Fernandes and U. Nunes  "Platooning of autonomous vehicles with intervehicle communications in SUMO traffic simulator",  Proc. 13th Int. IEEE Annu. Conf. Intell. Transp. Syst.,  pp.1313 -1318 2010 

[13] Bobby J.W. Nijssen “Cooperative Intelligent Transportation Systems”, Master Thesis at University of Twente, February 12, 2008

[14] Andreas Eidehall “An Automotive Lane Guidance System” Master Thesis at Linkoping University, Twente, 2004

[15] V. Tang , Y. Zheng and J. Cao  "An intelligent car park management system based on wireless sensor networks",  Proc. 1st Int. Symp. Pervasive Comput. Appl.,  pp.65 -70, 2006 

[16] Alejandro L´opez Vidal “Traffic flow simulation and optimization using evolutionay strategies” Master Thesis at Alto University, June 7, 2011

[17] Martin Fellendorf si Peter Vortisch “Fundamentals of Traffic Simulation”, Editura Jaume Barcelo, 2010

[18] M Fellendorf, P Vortisch “Validation of the microscopic traffic flow model VISSIM in different real-world situations”, In Proceedings of the Transportation Research Board, 2001

[19]  George Coulouris, Jean Dollimore, Tim Kindberg, Gordon Blair “Distributed Systems, 5th edition”, Addison-Wesley, 2012

[20] N. Kaempchen , U. Franke and R. Ott  "Stereo vision based pose estimation of parking lots using 3-D vehicle models",  Proc. IEEE Intell. Veh. Symp.,  pp.459 -464 2002 

[21] http://www.mathworks.com/help/curvefit/smoothing-data.html

[22] Apahidean Iancu-Horațiu , “Simulator for Automated Car System”, AQTR Student, 2014

Acronime

LIDAR – Light Detection and Ranging

TCP/IP- Transmission Control Protocol/Internet Protocol

PID – Proportional Integrativ Derivativ

OpenCV – Open Source Computer Vision

OpenGL – Open Graphics Library

GPS – Global Positioning System

OMG – Object Management Group

UML – Unified Modeling Language

CPU – Central Processing Unit

RAM – Random Access Memory

Anexa

Simulator for Automated Car System

Apahidean Iancu-Horatiu

Dept Faculty of Computer Science

Technical University of Cluj-Napoca

City Cluj-Napoca, Country Romania

E-mail: [anonimizat]

Abstract—The most common autonomous cars that are used today are based on a system that is trying to gather real-time information from video-cameras or other devices, in order to identify different objects that are important in taking a decision. However, in the real environment, such a system is dangerous, because there are a lot of variables and therefore a lot of unknown situations. Also, the environment changes in time and situations that were not taken into consideration can appear. This paper proposes a system in which both the car and the road system are taken into consideration. This will reduce the number of variables and unknown situations to a minimum, making the system much more predictable and therefore safer.

Key words: autonomous car, simulator, digital map, protocols.

Introduction

According to Wikipedia [1] an autonomous car is a vehicle capable of taking the same decisions as a human would, when driving a car. The way it works is that the vehicle gathers information from the real environment with technologies such as radar, GPS or computer vision, and a control system interprets the data and drives the car. According with the same article [1], as of 2013, four US states passed laws allowing autonomous cars to drive on their streets: Nevada, Florida, California and Michigan. This was possible because some companies that are developing autonomous cars, obtained promising results in this area. According with CNN [3], Google tested its cars in Nevada and from 300 000 miles, 50 000 where driven without human intervention. This made some of the experts believe that by 2040 autonomous cars will populate the cities.

This paper proposes a different approach that should be much cheaper and safer. The solution is to map everything into a digital 3D environment. For that every street, parking lot, intersection, traffic light and road sign should be mapped. Traffic lights will send real-time data with the current state. An accurate GPS will be mounted on the car. The GPS system needs to be capable to pin-point the car’s position in orders of centimetres. This will create a static and predictable environment, which can be simulated. The car no longer needs to identify the streets, the traffic lights or other traffic signs using complicated tools, such as image processing. The car will basically go on rails. This allows us to simulate different scenarios and to identify dangerous situations.

The way the system works is the following: the car will send its current position and the desired destination to a server. The server will send back the path and a list of instructions. The path will consist of a curved line which the car has to follow. The instructions will be placed at some particular points along the line and will contain information about the speed that the car has to reach, areas that need to be checked when reaching an intersection or information about the traffic lights. The car will constantly try to reach a certain speed and follow a certain path. For example, if the car is currently in the parking lot, the system will send the path that the car needs to follow in order to get out of the parking lot, but it will also send information regarding what areas the car needs to scan in order to be able to perform the manoeuvre. The speed that the car needs to reach can be obtained from the traffic rules, but mathematical models can be created that can help to predict the most probable speed that the car can reach. According with K. Li (2004) [8] and A. D. May(1990) [9] mathematical models have been described, that can specify the average speed and density at each section of the lane at each point in time.

This paper proposes that the real environment should be shaped by the results of the simulation. According with B. van Arem (2003) [4] a special lane for intelligent vehicles will increase traffic safety. Such a solution, might affect the traffic at first, but on the long run it should optimize the city’s traffic. Another solution would be to place intelligent semaphores or creating green lines. A centralized system can be created, that can take advantage of the predictable behaviour of the autonomous car. A good example is the wave effect, when the cars start one by one from a column. If there are only automatic cars in the column, every car can be commanded to start at the same time.

Finding a parking spot can also be transformed in a predictable situation. V. Tang (2006) [11] described a system for finding vacant parking lots, by placing sensors in every parking lot.

The simulator can also help to test other systems. According B. van Arem (2006) [5] the result of the simulation when

using Cooperative Adaptive Cruise Control showed an increase in traffic flow efficiency and A. Bose (2003) [6] says that using semi-automated cars showed an increase in fuel efficiency. Having a simulator can help to concentrate all the work on the system that controls the autonomous car and test it in an objective manner.

System’s Software Architecture

The algorithm will be comprised of two parts: a static part and a dynamic part. The static part is the part where the system does not enter in conflict with the environment. No unpredictable behaviour occurs. The car will always like to be at a particular speed in a particular point. But, for example, if there is a car in front that might be slower, then the dynamic control system will take over and slow down the car. If an obstacle suddenly appears in the car’s path, then some protocols will be followed to try to avoid the collision. If that is not possible, then the car will collide in the safest manner possible. For example, if the car is crossing an intersection and suddenly someone that is not respecting the rules jumps in the middle of the intersection, then the car will do it’s best to avoid the collision. However if avoiding the collision will put at risk someone that is respecting the rules and colliding will not, then it will chose to collide. The main components and loops of the system are described in Fig.1.

Fig.1. System’s Software Architecture

Data Processing

3.1 Processing the Static Path

The map will be held in a graph structure. A matrix of streets objects will represent the connection. The streets will be represented by two lists, holding the coordinates of the edges. Going from A->B will contain one half of the street and going from B->A will contain the other half. The path will be represented by a line made of every point of the center of the lane. The streets will also contain information about the traffic rules and the traffic lights. With this information the path and instructions for the car can be generated.

3.2 Processing the Unpredictable Input

The first thing the car will do is to scan the environment and search for objects that might interfere with the car’s static path. If it doesn’t find any, then it will follow the static path, otherwise it will search for protocols that might solve the problem. For example, if it identifies a car in front, then it would only have to slow down, keeping a safe distance. If there is a pedestrian crossing, and there are people traversing, the car will stop until the pedestrian crossing is clear. But if something unpredictable happens, like an object suddenly appearing in front of the car and it turns out to be an imminent collision, then the car needs to take a decision. If it has information about the nature of the object, then the car can take smart decisions. For example, if a dog is in the middle of the street, then it might choose to collide, but if it is human, then it will do it’s best to avoid the collision.

3.3 Class Diagram

Fig.2. describes the basic components of the simulator using a class diagram, but a more accurate description will be presented in the following pages.

Fig.2. Class Diagram

Main Components

4.1 The Map

An algorithm was created and implemented that automatically converts a Google map into a graph structure. The way the algorithm works is that it first finds a street at the edge of the picture and places a drone in the centre of the street. The drone starts to scan the picture, pixel by pixel along the edges, until it reaches a intersection. The intersections were manually coloured with a specified colour (Red=100, Green=100, Blue=100). After it finds and stores the edges, it splits, placing drones on each street that is connected with that intersection and repeats the process. After the drones have processed the map, a graph structure is created from the information which the drones hold. The coordinates of the streets and the connections are printed in a .txt file and then imported into the 3D environment. Fig.3. presents the results when processing a Google map.

a).

b).

Fig.3. a) The Initial Map; b) TheProcessed Map

A performance analysis of the algorithm, processed on Processor: Intel(R) Celeron(R) CPU P4600 @ 2.00GHz, with 2.00GB memory(RAM), and a 64 bit operating system is presented in Table.1.

Table.1. Performance analysis

The results presented in Table.1. show that when the dimensions of map are doubled, the time it takes to process the image increases exponentially. The solution to this problem would be to process smaller images, and blend the results in the 3D environment. This will ensure that the time will increase linearly. Even so, the time it takes to process the map is small enough to be able to test the simulator.

The instructions and traffic rules will be manually encoded in the .txt file that has the coordinates for the streets. The path can be automatically generated from the edges that make the streets, by taking every point of the center of the streets.

The following pseudocode presents how the path is generated from the coordinates of the edges.

4.2 The Car

The environment, in which the map was imported, is 3D, but the map is 2D. Further work is needed to be able to elevate the roads, but for now this should be enough. Therefore, the car only works in a 2D environment. The car can be commanded by two parameters: the speed and the wheel angle. The car has an acceleration and deceleration curve representing the car’s physical abilities. Fig.4. shows an example for the acceleration curve [12].

Fig.4. Acceleration Curve

We assume that the car will never slide, but this can change in the future. When steering, the car’s trajectory will form a circle. With this information, the wheel angle that will take the car to a certain point can be calculated. Also the acceleration required for the car to reach a certain speed can be calculated. In this manner the car can be commanded to go to a certain point with a certain speed. Fig.5. describes the car’s steering system. When steering, all the wheels need to be directed towards a single centre of rotation, otherwise the wheels will slip.

Fig.5. Car Steering System

4.3 The Object Detector

Every car will become an object that needs to be identified by the other cars. Other objects might be placed to simulate real scenarios, like pedestrians or obstacles. In reality such a system would consist of cameras mounted on the car that will identify objects through image processing. To copy the exact same behaviour in the simulator would be a waste of resources. Therefore an algorithm was designed that simulates a collision detector. The way it works is that it calculates the distance to every object and checks to see if the object is in the car’s visual field. The trajectories of the normal cars can be predicted, or at least a system that might help in this kind of problem can be created. G. O. Burnham (1974) [10] proposed two mathematical models for a driver behaviour in single-lane situations. For example, if one car tries to overcome another car, and is close to a collision, then each driver will naturally steer left. This might prove to be very helpful in a real situation, because humans make this kind of prediction as well and it can sometimes save lives. Other predictions can be made from the natural trajectory of the car. A good understanding of the physics of the car can help in this sense. In conclusion we can say that making good predictions is a very important factor in developing an autonomous car.

Algoritm2 describes how the collision detector works. The car trajectory is known, and the object trajectory is predicted.

4.4 The Car Controller

The controller will receive from the car, its current position, the desired destination, and the detected objects. A path and an instruction set will be generated. The controller will try to place the current situation in a known protocol and command the car to drive to the next point at the required speed. The car will respond, after it has finished the task with the new speed, the new position and the detected objects. The difficult part for the controller is to generate protocols for unpredictable situations, because situations that were not taken into consideration can always appear. Because of this, protocols will have to be created for every street and intersection in particular. Fig.6. describes how the path and the instruction set will be coded.

Fig.6. Coding the Path

4.5The Traffic Simulator

The traffic simulator will consist of cars that will follow some pre-established paths. Every car will have an independent controller. The cars will be given a list of intersections that will represent the path that the car has to take in order to reach to the destination. From that list and from the traffic rules, the controller will generate instructions for the car. Different objects can be placed to simulate the unpredictable behaviour of the real environment. Most of the objects will have a name, because we assume that the car is able to identify the objects, but situations where objects cannot be identified can also be generated. The goal is to generate as many situations as possible and try to place them in a protocol.

For now the cars can only be controlled from the keyboard. In the future an algorithm that will command the car to a certain point will be created. Fig.6. presents results from the simulator. The red circle represents the trajectory of the car.

a)

b).

Fig.6.a,b) The Simulator Seen from Different Perspectives

Conclusions

The algorithm that generates the map was implemented in c++. The map is imported in a 3D environment using openGL. The project is still in its early stages. Further work is needed to obtain concrete results, but the current stage of the project shows that the developing part should be an easy task. No physic engine was used because for now it is not needed. In the future, the simulator can be enhanced to be able to elevate the streets, to simulate weather conditions or take into consideration the physics of the car. This part of the simulator was designed to prove that the unpredictable factors in the real environment can be restrained to a minimum.

One of the biggest advantages of this simulator is that, the algorithm that controls the autonomous car can be tested in a safe environment. Another advantage is that the results should offer solutions for optimizing the real traffic system. A city is always changing, and the traffic rules change as well. Having a simulator can help to take the best decision in this kind situation, with fewer mistakes.

In conclusion, we can say, that having a simulator that is able to test different systems before they are tested in the real environment is necessary.

References

http://en.wikipedia.org/wiki/Autonomous_car

http://www.auto-ware.com/setup/ack_rac.htm

http://edition.cnn.com/2012/09/25/tech/innovation/self-driving-car-california/

B. van Arem , C. M. J. Tamp&egrave;re and K. M. Malone  "Modeling traffic flows with intelligent cars and intelligent roads",  Proc. IEEE Intell. Vehicles Symp.,  pp.456 -461 2003

B. van Arem , C. J. G. van Driel and R. Visser  "The impact of cooperative adaptive cruise control of traffic-flow characteristics",  IEEE Trans. Intell. Transp. Syst.,  vol. 7,  no. 4,  pp.429 -436 2006

A. Bose, P. A. Ioannou, "Analysis of Traffic Flow with Mixed Manual and Semiautomated Vehicles," IEEE Transactions on Intelligent Transportation Systems, Vol. 4, No. 4, December 2003, pp. 173-188.

A. Bose, P. A. Ioannou, "Mixed manual/semi-automated traffic: a macroscopic analysis," Transportation Research Part C 11 (2003), pp. 439-462. 

K. Li and P. Ioannou  "Modeling of traffic flow of automated vehicles",  IEEE Trans. Intell. Transp. Syst.,  vol. 5,  no. 2,  pp.99 -113 2004

A. D. May,  Traffic Flow Fundamentals,  1990 :Prentice-Hall

G. O. Burnham, J. Seo and G. A. Bekey, "Identification of Human Driver Models in Car Following," IEEE Transactions on Automatic Control, Vol. 19, pp. 911-915, 1974.

V. Tang , Y. Zheng and J. Cao  "An intelligent car park management system based on wireless sensor networks",  Proc. 1st Int. Symp. Pervasive Comput. Appl.,  pp.65 -70 2006 

http://www.google.ro/imgres?safe=off&sa=X&espvd=210&es_sm=122&biw=1517&bih=725&tbm=isch&tbnid=-mcJlvfdkcmU5M%3A&imgrefurl=http%3A%2F%2Fwww.studiodual.com%2F968%2F968.html&docid=XnVCQglZXGhIBM&imgurl=http%3A%2F%2Fwww.studiodual.com%2F968%2Facceleration_curve.gif&w=364&h=468&ei=En37Uq-WEceD4ASMyoDYDQ&zoom=1&ved=0CHIQhBwwCg&iact=rc&dur=680&page=1&start=0&ndsp=19

Bibliografie

[1] John Sousanis, “World Vehicle Population Tops 1 Billion Units”, august 2011, articolul se poate găsi la : http://wardsauto.com/ar/world_vehicle_population_110815

[2] B. van Arem, C. M. J Tamp&egrave;re and K.M. Malone “”Modeling traffic flows with intelligent cars and intelligent roads”, Proc.IEEE Intell. Vehicles Symp., pp456-461, 2003

[3] Yizhen Zhang “Engineering Design Synthesis of Sensor and Control Systems for Intelligent Vehicles”, Degree of Doctor of Philosophy at California Institute of Technology, Mai 2006

[4] Ray Fuller, “Towards a general theory of driver behaviour” Accident Analysis & Prevention, Volume 37, Issue3, May 2005, Pages 461-472

[5] B.J.A de Graaf “Prediction and Simulation Models for Intelligent Vehicle Highway Systems” Master of Science at Delf University of Technology, Martie 2009

[6] K.Li and P Ioannou “Modelling of traffic flow of automated vehicles” IEEE Trans. Intell. Trans. Sys., vol.5, no. 2, pp.99-113. 2004

[7] Norbert Grünwald “A Mixed Reality Platform for Robotics and Intelligent Vehicles”, Masters Degree at Halmstad University – Sweden, May 2012

[8] Thomas F. Golob, Eugene T. Canty, Richard L. Gustafson, Joseph E. Vitt, “An analysis of consumer preferences for a public transportation system” Transportation Research, Volume 6, Issue 1, March 1972, Pages 81-102

[9] U. Franke  "Truck platoon in mixed traffic",  Proc. Intell. Vehicles Symp.,  pp.1 -6 1995

[10] A. Bose, P.A. Ioannou, “Analysis of Traffic Flow with Mixed Manual and Semiautomated Vehicles”, IEEE Transactions on Intelligent Transportation Systems, Vol4, No. 4, December 2003, pp. 173-188 

[11] C. Kreuzen “Cooperative adaptive cruise control” Master of Science Thesis at Delft University of Technology, Mai 2012

[12] P. Fernandes and U. Nunes  "Platooning of autonomous vehicles with intervehicle communications in SUMO traffic simulator",  Proc. 13th Int. IEEE Annu. Conf. Intell. Transp. Syst.,  pp.1313 -1318 2010 

[13] Bobby J.W. Nijssen “Cooperative Intelligent Transportation Systems”, Master Thesis at University of Twente, February 12, 2008

[14] Andreas Eidehall “An Automotive Lane Guidance System” Master Thesis at Linkoping University, Twente, 2004

[15] V. Tang , Y. Zheng and J. Cao  "An intelligent car park management system based on wireless sensor networks",  Proc. 1st Int. Symp. Pervasive Comput. Appl.,  pp.65 -70, 2006 

[16] Alejandro L´opez Vidal “Traffic flow simulation and optimization using evolutionay strategies” Master Thesis at Alto University, June 7, 2011

[17] Martin Fellendorf si Peter Vortisch “Fundamentals of Traffic Simulation”, Editura Jaume Barcelo, 2010

[18] M Fellendorf, P Vortisch “Validation of the microscopic traffic flow model VISSIM in different real-world situations”, In Proceedings of the Transportation Research Board, 2001

[19]  George Coulouris, Jean Dollimore, Tim Kindberg, Gordon Blair “Distributed Systems, 5th edition”, Addison-Wesley, 2012

[20] N. Kaempchen , U. Franke and R. Ott  "Stereo vision based pose estimation of parking lots using 3-D vehicle models",  Proc. IEEE Intell. Veh. Symp.,  pp.459 -464 2002 

[21] http://www.mathworks.com/help/curvefit/smoothing-data.html

[22] Apahidean Iancu-Horațiu , “Simulator for Automated Car System”, AQTR Student, 2014

Acronime

LIDAR – Light Detection and Ranging

TCP/IP- Transmission Control Protocol/Internet Protocol

PID – Proportional Integrativ Derivativ

OpenCV – Open Source Computer Vision

OpenGL – Open Graphics Library

GPS – Global Positioning System

OMG – Object Management Group

UML – Unified Modeling Language

CPU – Central Processing Unit

RAM – Random Access Memory

Anexa

Simulator for Automated Car System

Apahidean Iancu-Horatiu

Dept Faculty of Computer Science

Technical University of Cluj-Napoca

City Cluj-Napoca, Country Romania

E-mail: [anonimizat]

Abstract—The most common autonomous cars that are used today are based on a system that is trying to gather real-time information from video-cameras or other devices, in order to identify different objects that are important in taking a decision. However, in the real environment, such a system is dangerous, because there are a lot of variables and therefore a lot of unknown situations. Also, the environment changes in time and situations that were not taken into consideration can appear. This paper proposes a system in which both the car and the road system are taken into consideration. This will reduce the number of variables and unknown situations to a minimum, making the system much more predictable and therefore safer.

Key words: autonomous car, simulator, digital map, protocols.

Introduction

According to Wikipedia [1] an autonomous car is a vehicle capable of taking the same decisions as a human would, when driving a car. The way it works is that the vehicle gathers information from the real environment with technologies such as radar, GPS or computer vision, and a control system interprets the data and drives the car. According with the same article [1], as of 2013, four US states passed laws allowing autonomous cars to drive on their streets: Nevada, Florida, California and Michigan. This was possible because some companies that are developing autonomous cars, obtained promising results in this area. According with CNN [3], Google tested its cars in Nevada and from 300 000 miles, 50 000 where driven without human intervention. This made some of the experts believe that by 2040 autonomous cars will populate the cities.

This paper proposes a different approach that should be much cheaper and safer. The solution is to map everything into a digital 3D environment. For that every street, parking lot, intersection, traffic light and road sign should be mapped. Traffic lights will send real-time data with the current state. An accurate GPS will be mounted on the car. The GPS system needs to be capable to pin-point the car’s position in orders of centimetres. This will create a static and predictable environment, which can be simulated. The car no longer needs to identify the streets, the traffic lights or other traffic signs using complicated tools, such as image processing. The car will basically go on rails. This allows us to simulate different scenarios and to identify dangerous situations.

The way the system works is the following: the car will send its current position and the desired destination to a server. The server will send back the path and a list of instructions. The path will consist of a curved line which the car has to follow. The instructions will be placed at some particular points along the line and will contain information about the speed that the car has to reach, areas that need to be checked when reaching an intersection or information about the traffic lights. The car will constantly try to reach a certain speed and follow a certain path. For example, if the car is currently in the parking lot, the system will send the path that the car needs to follow in order to get out of the parking lot, but it will also send information regarding what areas the car needs to scan in order to be able to perform the manoeuvre. The speed that the car needs to reach can be obtained from the traffic rules, but mathematical models can be created that can help to predict the most probable speed that the car can reach. According with K. Li (2004) [8] and A. D. May(1990) [9] mathematical models have been described, that can specify the average speed and density at each section of the lane at each point in time.

This paper proposes that the real environment should be shaped by the results of the simulation. According with B. van Arem (2003) [4] a special lane for intelligent vehicles will increase traffic safety. Such a solution, might affect the traffic at first, but on the long run it should optimize the city’s traffic. Another solution would be to place intelligent semaphores or creating green lines. A centralized system can be created, that can take advantage of the predictable behaviour of the autonomous car. A good example is the wave effect, when the cars start one by one from a column. If there are only automatic cars in the column, every car can be commanded to start at the same time.

Finding a parking spot can also be transformed in a predictable situation. V. Tang (2006) [11] described a system for finding vacant parking lots, by placing sensors in every parking lot.

The simulator can also help to test other systems. According B. van Arem (2006) [5] the result of the simulation when

using Cooperative Adaptive Cruise Control showed an increase in traffic flow efficiency and A. Bose (2003) [6] says that using semi-automated cars showed an increase in fuel efficiency. Having a simulator can help to concentrate all the work on the system that controls the autonomous car and test it in an objective manner.

System’s Software Architecture

The algorithm will be comprised of two parts: a static part and a dynamic part. The static part is the part where the system does not enter in conflict with the environment. No unpredictable behaviour occurs. The car will always like to be at a particular speed in a particular point. But, for example, if there is a car in front that might be slower, then the dynamic control system will take over and slow down the car. If an obstacle suddenly appears in the car’s path, then some protocols will be followed to try to avoid the collision. If that is not possible, then the car will collide in the safest manner possible. For example, if the car is crossing an intersection and suddenly someone that is not respecting the rules jumps in the middle of the intersection, then the car will do it’s best to avoid the collision. However if avoiding the collision will put at risk someone that is respecting the rules and colliding will not, then it will chose to collide. The main components and loops of the system are described in Fig.1.

Fig.1. System’s Software Architecture

Data Processing

3.1 Processing the Static Path

The map will be held in a graph structure. A matrix of streets objects will represent the connection. The streets will be represented by two lists, holding the coordinates of the edges. Going from A->B will contain one half of the street and going from B->A will contain the other half. The path will be represented by a line made of every point of the center of the lane. The streets will also contain information about the traffic rules and the traffic lights. With this information the path and instructions for the car can be generated.

3.2 Processing the Unpredictable Input

The first thing the car will do is to scan the environment and search for objects that might interfere with the car’s static path. If it doesn’t find any, then it will follow the static path, otherwise it will search for protocols that might solve the problem. For example, if it identifies a car in front, then it would only have to slow down, keeping a safe distance. If there is a pedestrian crossing, and there are people traversing, the car will stop until the pedestrian crossing is clear. But if something unpredictable happens, like an object suddenly appearing in front of the car and it turns out to be an imminent collision, then the car needs to take a decision. If it has information about the nature of the object, then the car can take smart decisions. For example, if a dog is in the middle of the street, then it might choose to collide, but if it is human, then it will do it’s best to avoid the collision.

3.3 Class Diagram

Fig.2. describes the basic components of the simulator using a class diagram, but a more accurate description will be presented in the following pages.

Fig.2. Class Diagram

Main Components

4.1 The Map

An algorithm was created and implemented that automatically converts a Google map into a graph structure. The way the algorithm works is that it first finds a street at the edge of the picture and places a drone in the centre of the street. The drone starts to scan the picture, pixel by pixel along the edges, until it reaches a intersection. The intersections were manually coloured with a specified colour (Red=100, Green=100, Blue=100). After it finds and stores the edges, it splits, placing drones on each street that is connected with that intersection and repeats the process. After the drones have processed the map, a graph structure is created from the information which the drones hold. The coordinates of the streets and the connections are printed in a .txt file and then imported into the 3D environment. Fig.3. presents the results when processing a Google map.

a).

b).

Fig.3. a) The Initial Map; b) TheProcessed Map

A performance analysis of the algorithm, processed on Processor: Intel(R) Celeron(R) CPU P4600 @ 2.00GHz, with 2.00GB memory(RAM), and a 64 bit operating system is presented in Table.1.

Table.1. Performance analysis

The results presented in Table.1. show that when the dimensions of map are doubled, the time it takes to process the image increases exponentially. The solution to this problem would be to process smaller images, and blend the results in the 3D environment. This will ensure that the time will increase linearly. Even so, the time it takes to process the map is small enough to be able to test the simulator.

The instructions and traffic rules will be manually encoded in the .txt file that has the coordinates for the streets. The path can be automatically generated from the edges that make the streets, by taking every point of the center of the streets.

The following pseudocode presents how the path is generated from the coordinates of the edges.

4.2 The Car

The environment, in which the map was imported, is 3D, but the map is 2D. Further work is needed to be able to elevate the roads, but for now this should be enough. Therefore, the car only works in a 2D environment. The car can be commanded by two parameters: the speed and the wheel angle. The car has an acceleration and deceleration curve representing the car’s physical abilities. Fig.4. shows an example for the acceleration curve [12].

Fig.4. Acceleration Curve

We assume that the car will never slide, but this can change in the future. When steering, the car’s trajectory will form a circle. With this information, the wheel angle that will take the car to a certain point can be calculated. Also the acceleration required for the car to reach a certain speed can be calculated. In this manner the car can be commanded to go to a certain point with a certain speed. Fig.5. describes the car’s steering system. When steering, all the wheels need to be directed towards a single centre of rotation, otherwise the wheels will slip.

Fig.5. Car Steering System

4.3 The Object Detector

Every car will become an object that needs to be identified by the other cars. Other objects might be placed to simulate real scenarios, like pedestrians or obstacles. In reality such a system would consist of cameras mounted on the car that will identify objects through image processing. To copy the exact same behaviour in the simulator would be a waste of resources. Therefore an algorithm was designed that simulates a collision detector. The way it works is that it calculates the distance to every object and checks to see if the object is in the car’s visual field. The trajectories of the normal cars can be predicted, or at least a system that might help in this kind of problem can be created. G. O. Burnham (1974) [10] proposed two mathematical models for a driver behaviour in single-lane situations. For example, if one car tries to overcome another car, and is close to a collision, then each driver will naturally steer left. This might prove to be very helpful in a real situation, because humans make this kind of prediction as well and it can sometimes save lives. Other predictions can be made from the natural trajectory of the car. A good understanding of the physics of the car can help in this sense. In conclusion we can say that making good predictions is a very important factor in developing an autonomous car.

Algoritm2 describes how the collision detector works. The car trajectory is known, and the object trajectory is predicted.

4.4 The Car Controller

The controller will receive from the car, its current position, the desired destination, and the detected objects. A path and an instruction set will be generated. The controller will try to place the current situation in a known protocol and command the car to drive to the next point at the required speed. The car will respond, after it has finished the task with the new speed, the new position and the detected objects. The difficult part for the controller is to generate protocols for unpredictable situations, because situations that were not taken into consideration can always appear. Because of this, protocols will have to be created for every street and intersection in particular. Fig.6. describes how the path and the instruction set will be coded.

Fig.6. Coding the Path

4.5The Traffic Simulator

The traffic simulator will consist of cars that will follow some pre-established paths. Every car will have an independent controller. The cars will be given a list of intersections that will represent the path that the car has to take in order to reach to the destination. From that list and from the traffic rules, the controller will generate instructions for the car. Different objects can be placed to simulate the unpredictable behaviour of the real environment. Most of the objects will have a name, because we assume that the car is able to identify the objects, but situations where objects cannot be identified can also be generated. The goal is to generate as many situations as possible and try to place them in a protocol.

For now the cars can only be controlled from the keyboard. In the future an algorithm that will command the car to a certain point will be created. Fig.6. presents results from the simulator. The red circle represents the trajectory of the car.

a)

b).

Fig.6.a,b) The Simulator Seen from Different Perspectives

Conclusions

The algorithm that generates the map was implemented in c++. The map is imported in a 3D environment using openGL. The project is still in its early stages. Further work is needed to obtain concrete results, but the current stage of the project shows that the developing part should be an easy task. No physic engine was used because for now it is not needed. In the future, the simulator can be enhanced to be able to elevate the streets, to simulate weather conditions or take into consideration the physics of the car. This part of the simulator was designed to prove that the unpredictable factors in the real environment can be restrained to a minimum.

One of the biggest advantages of this simulator is that, the algorithm that controls the autonomous car can be tested in a safe environment. Another advantage is that the results should offer solutions for optimizing the real traffic system. A city is always changing, and the traffic rules change as well. Having a simulator can help to take the best decision in this kind situation, with fewer mistakes.

In conclusion, we can say, that having a simulator that is able to test different systems before they are tested in the real environment is necessary.

References

http://en.wikipedia.org/wiki/Autonomous_car

http://www.auto-ware.com/setup/ack_rac.htm

http://edition.cnn.com/2012/09/25/tech/innovation/self-driving-car-california/

B. van Arem , C. M. J. Tamp&egrave;re and K. M. Malone  "Modeling traffic flows with intelligent cars and intelligent roads",  Proc. IEEE Intell. Vehicles Symp.,  pp.456 -461 2003

B. van Arem , C. J. G. van Driel and R. Visser  "The impact of cooperative adaptive cruise control of traffic-flow characteristics",  IEEE Trans. Intell. Transp. Syst.,  vol. 7,  no. 4,  pp.429 -436 2006

A. Bose, P. A. Ioannou, "Analysis of Traffic Flow with Mixed Manual and Semiautomated Vehicles," IEEE Transactions on Intelligent Transportation Systems, Vol. 4, No. 4, December 2003, pp. 173-188.

A. Bose, P. A. Ioannou, "Mixed manual/semi-automated traffic: a macroscopic analysis," Transportation Research Part C 11 (2003), pp. 439-462. 

K. Li and P. Ioannou  "Modeling of traffic flow of automated vehicles",  IEEE Trans. Intell. Transp. Syst.,  vol. 5,  no. 2,  pp.99 -113 2004

A. D. May,  Traffic Flow Fundamentals,  1990 :Prentice-Hall

G. O. Burnham, J. Seo and G. A. Bekey, "Identification of Human Driver Models in Car Following," IEEE Transactions on Automatic Control, Vol. 19, pp. 911-915, 1974.

V. Tang , Y. Zheng and J. Cao  "An intelligent car park management system based on wireless sensor networks",  Proc. 1st Int. Symp. Pervasive Comput. Appl.,  pp.65 -70 2006 

http://www.google.ro/imgres?safe=off&sa=X&espvd=210&es_sm=122&biw=1517&bih=725&tbm=isch&tbnid=-mcJlvfdkcmU5M%3A&imgrefurl=http%3A%2F%2Fwww.studiodual.com%2F968%2F968.html&docid=XnVCQglZXGhIBM&imgurl=http%3A%2F%2Fwww.studiodual.com%2F968%2Facceleration_curve.gif&w=364&h=468&ei=En37Uq-WEceD4ASMyoDYDQ&zoom=1&ved=0CHIQhBwwCg&iact=rc&dur=680&page=1&start=0&ndsp=19