Localizarea Unui Robot Mobil Utilizand Tehnica Slam cu Ajutorul Senzorului Laser

Capitolul I. INTRODUCERE

I.1. Generalități

Roboții sunt unul din lucrurile indispensabile funcționării societății umane a secolului XXI. Întâlniți atât în procesele de producție, cât și în alte arii de interes precum divertisment, transporturi, comunicații, medicină sau agricultură, roboții îmbunătățesc performanțele umane din punct de vedere cantitativ și calitativ. Roboții industriali sunt cel mai folosit tip de roboți, aceștia fiind și primii care au apărut, ca răspuns la nevoia efectuării mai rapide și mai exacte a unor operații repetitive, deseori întâlnite în procesele de producție. În ultimele decenii, în vederea soluționării problemelor legate de transportul local, au fost introduse în industrie vehiculele ghidate în mod automat (AGV – „Automated Guided Vehicle”).

În ultima perioadă de timp eforturile de cercetare în domeniul concepției și proiectării de vehicule s-au concentrat și în direcția dezvoltării de vehicule autonome în care sunt integrate dispozitive specifice care conferă acestora comportare inteligență bazată pe metode și tehnicile inteligenței artificiale. Aceasta se realizează, pe de o parte, ca un răspuns la actualele nevoi ale consumatorului și ale mediului de afaceri, precum și, pe de altă parte, ca urmare a acutei necesități de a transforma autovehiculul într-un sistem sigur, atât pentru om cât și pentru mediu, capabil de efectuarea unor task-uri tot mai complexe și mai numeroase cu participarea cât mai redusă a operatorului uman.

Sistemul de fabricație total automatizat reprezintă o configurație controlata de către calculatoarele componentelor inteligente. Rolul strategic al unui sistem de transport intern a materialelor și semifabricatelor este de a furniza cantitatea necesară intr-un timp eficient la locați stabilită. Costurile transportului și manipulării materialelor și semifabricatelor reprezintă o proporție semnificativa in costurile de producție. Integrarea vehiculelor de tip ARM (Automobil ca și Robot Mobil) în cadrul proceselor industriale ca mijloace de transport intern conduce la scurtarea timpilor de producție în paralel cu creșterea siguranței muncii. Metodologiile prin care se planifică logistica industrializată de transport intern se refera la analiza proceselor de producție în corelație cu programele de conducere a vehiculelor autonome de transport. În literatură s-au identificat mai multe variante de implementare a ARM-urilor în transportul automatizat de mărfuri.

Una dintre cele mai importante abilități care caracterizează roboții mobili autonomi este capacitatea acestora de a naviga în medii complexe. Performanța unui bun algoritm de navigare se află în strânsă legătură cu procesul de evitare a obstacolelor care pot să apară în calea robotului și cu procesul de localizare și mapare simultană. Cu alte cuvinte, prin procesul de localizare și mapare simultană se înțelege capacitatea unui robot mobil autonom de a genera o hartă a mediului în care se deplasează și, în același timp, de a utiliza informațiile referitoare la harta creată pentru a-și determina poziția în spațiu. Pentru realizarea procesului de navigație robotul trebuie să fie dotat cu un sistem de senzori capabil să măsoare distanța relativă dintre robot și elementele componente ale scenei.

Robotul industrial a apărut ca rezultat firesc al existenței unor limite de flexibilitate legate de gradul de intervenție al omului în procesul de producție. În evoluția mașinilor, utilajelor și sistemelor tehnologice de prelucrare și de asamblare cu cerințe ridicate de productivitate și calitate, robotul poate fi considerat ca fiind un sistem complex capabil să asiste sau să înlocuiască, parțial sau total, acțiunile operatorului uman în cadrul proceselor de producție a bunurilor materiale și serviciilor.

Robotul industrial operează în medii tehnologice cu următoarele scopuri: transport de piese, dispozitive sau scule în poziții și orientări diverse; execuție de operații tehnologice de vopsire, de sudare, de polizare etc.; asamblare de produse sau subansamble ale acestora prin așezarea și fixarea elementelor componente în pozițiile cerute de funcționalitate; inspecție în vederea identificării și măsurării atributelor (dimensiuni, forme, culoare, greutate etc.) unor piese sau procese; monitorizare/supervizare sisteme și procese. La proiectarea, dezvoltarea și implementarea roboților industriali (ficși și mobili) se urmărește, pe de-o parte, mărirea eficienței acțiunilor asupra mediilor tehnologice prin creșterea vitezei și preciziei de execuție și, pe de altă parte, înlocuirea operatorilor umani care execută operații simple repetitive sau care lucrează în medii austere (căldură/frig, lumină/întuneric, vibrații/zgomote etc.) și nocive (cu radiații, poluate etc.).

Roboții mobili industriali sunt considerați drept hipersisteme mecatronice complexe compuse din următoarele părți principale: sistemul mecanic care realizează mișcarea dorită a obiectului manipulat în mediul de operare prin acționarea manipulatorului și/sau a platformei mobile; sistemul de acționare cu funcția de a pune în mișcare cuplele cinematice ale sistemului mecanic prin intermediul unor subsisteme de antrenare cu motoare legate la sursa de energie; sistemul senzorial prin care se culeg informații privind valorile parametrilor interni care descriu starea sistemului robotului industrial, precum și valorile parametrilor externi asociați spațiului de operare și/sau sistemului perirobot; sistemul de conducere care procesează informațiile primite de la sursa de informație (operatorul uman, sisteme de conducere similare și superioare) și/sau de la sistemul senzorial.

În acest sens un vehicul se deplasează complet autonom într-un mediu specific, interior și/sau exterior realizând o hartă virtuală în timp real cu ajutorul senzorilor, hartă în care apoi se localizează și operează, un trend vizionar foarte dezbătut în prezent. În literatura de specialitate conceptul de Cartografiere și Localizare Simultană (SLAM) reprezintă o tematică deschisă privind navigarea optimă a vehiculelor autonome. Comunicația dintre sistemul central de comandă și vehiculele autonome este bazată pe un schimb de informații în scopul procesării în timp real a sarcinilor și totodată permite utilizarea multiplă a datelor existente, reprezentând un avantaj major și pentru sistemul de planificare sau gestiune și o parte componentă în dezvoltarea obiectivului acestei lucrări. Latura de siguranță în operare privind conducerea fără coliziuni, evitarea obstacolelor și a celorlalte componente de manipulare, respectiv a oamenilor și obiectelor aflate în mișcare, reprezintă un aspect important și este tratat ca parte componentă a evoluției mijloacelor de transport fără operator uman.

Problema cartografierii și localizării simultane (SLAM) cercetează dacă este posibil ca un robot mobil să fie plasat într-o locație necunoscută, într-un mediu necunoscut, iar el să contruiască treptat o hartă coerentă a acestui mediu în timp ce simultan determină locația sa în această hartă. O soluție la problema SLAM a fost văzută ca un „Sfant Graal” pentru comunitatea de robotică mobilă, deoarece ar oferi mijloacele pentru a face un robot cu adevărat autonom.

„Soluția” problemei SLAM a fost una dintre succesele notabile ale comunității roboticii în ultimul deceniu. SLAM a fost formulat și rezolvat ca o problemă teoretică într-o serie de forme diferite. SLAM, de asemenea, a fost pusă în aplicare într-o serie de domenii diferite de la roboți de interior, la sisteme în aer liber, sub apă și în aer. La un nivel teoretic și conceptual, SLAM poate fi acum considerată o problemă rezolvată. Cu toate acestea, aspectele esențiale rămân în realizarea, practică a mai multor soluții generale SLAM și în special în construirea și utilizarea de hărți bogate, ca parte a unui algoritm SLAM.

Cartografierea și localizarea simultană (SLAM) este o tehnică utilizată de către roboți și vehicule autonome pentru a construi o hartă într-un mediu necunoscut (fără o cunoaștere a priori), sau pentru a actualiza o hartă într-un mediu cunoscut (cu o cunoaștere a priori de la o anumită hartă ), și menținând în același timp urma locației curente.

Definire operațională

Hărțile sunt folosite pentru a determina o locație într-un mediu și pentru a descrie un mediu de planificare și de navigație; acestea susțin evaluarea locației actuale de înregistrare a informațiilor obținute de la o formă de percepție și comparând-o cu un set de curent de percepții. Beneficiul unei hărți în sprijinirea evaluării unei locații crește pe măsură ce precizia și calitatea percepțiile actuale scade. Hărțile reprezintă, în general, situația în momentul în care harta este întocmită, acest lucru nu este neapărat în concordanță cu starea mediului în momentul în care harta este utilizată.

Complexitatea proceselor tehnice de localizare și de cartografiere în condiții de erori și de zgomot nu permit o soluție coerentă a ambelor sarcini. Cartografierea și localizarea simultană (SLAM) este un concept care leagă aceste procese într-o buclă și prin urmare, sprijină continuitatea ambelor aspecte în procese separate; feedback-ul iterativ de la un proces la altul îmbunătățeste rezultatele celor două etape consecutive.

Cartografierea este o problemă de integrare a informațiilor colectate printr-un set de senzori într-un model consistent și care prezintă aceste informații ca o reprezentare dată. Ea poate fi descrisă de o întrebare caracteristică în primul rând: „Cum arată lumea?” Aspectele centrale în cartografiere sunt reprezentări ale mediului și interpretări ale datelor date senzor.

In contrast cu aceasta, localizarea este problema de estimare a locului (și poziția) a robotului în raport cu o hartă, cu alte cuvinte, robotul trebuie să răspundă la a doua întrebare caracteristică, „Unde sunt eu?” De obicei, soluțiile includ urmărirea, în cazul în care locația inițială a robotului este cunoscută, și localizarea la nivel mondial, în care niciuna sau doar o parte din cunoștințele despre caracteristicile de mediu ale poziției de pornire sunt date.

SLAM este, prin urmare, definită ca problema de construire a unui model care conduce la o hartă nouă, sau de îmbunătățirea repetată a unei hărți existente, și în același timp, localizarea robotului pe hartă. În practică, răspunsurile la două întrebări caracteristice nu pot fi date independente unul de celălalt.

Înainte ca un robot să poată contribui la a răspunde la întrebarea despre cum arată mediul, având în vedere un set de observații, el trebuie să știe de exemplu:

Cinematica proprie a robotului;

Ce calități are achiziția autonomă;

Din ce surse adiționale au fost făcute observațiile.

Este o sarcină complexă pentru a estima locația curentă a robotului, fără o hartă sau fără o direcție de referință. Aici, locația este doar poziția robotului sau ar putea include, de asemenea, orientarea acesteia.

Probleme tehnice

SLAM poate fi gândit ca o problemă despre pui sau ouă: este nevoie de o harta imparțială pentru localizare în timp ce o estimare a poziției este necesară pentru construirea acelei hărți. Aceasta este condiția de plecare pentru soluțiile strategice matematice. În comparație, modelul atomic orbital poate fi văzut ca o abordare clasică a modului de a comunica rezultate suficiente, în condiții de observare imprecise.

În afară de aceasta, răspunzând celor două întrebări caracteristice nu este atât de simplu cum ar putea suna datorită incertitudinilor inerente în a distinge mișscările relative ale robotului de la diferiți senzori. În general, datorită volumului de zgomot dintr-un mediu tehnic, SLAM nu are doar soluții compacte dar contribuie la obținerea rezultatelor cu foarte multe concepte fizice.

Dacă la urmatoarea iteratie a creării harții distanța măsurată și direcția parcursă există p multitudine de inexactități, conduse cu precizie inerentă limitată de senzori și zgomot ambiental suplimentar, atunci orice caracteristici fiind adăugate pe hartă vor conține erori corespunzătoareui de a comunica rezultate suficiente, în condiții de observare imprecise.

În afară de aceasta, răspunzând celor două întrebări caracteristice nu este atât de simplu cum ar putea suna datorită incertitudinilor inerente în a distinge mișscările relative ale robotului de la diferiți senzori. În general, datorită volumului de zgomot dintr-un mediu tehnic, SLAM nu are doar soluții compacte dar contribuie la obținerea rezultatelor cu foarte multe concepte fizice.

Dacă la urmatoarea iteratie a creării harții distanța măsurată și direcția parcursă există p multitudine de inexactități, conduse cu precizie inerentă limitată de senzori și zgomot ambiental suplimentar, atunci orice caracteristici fiind adăugate pe hartă vor conține erori corespunzătoare. În timp și spațiu, cartografierea și localizarea erorilor construiesc cumulativ, extrem de denaturat față de hartă și deci, cu suficientă acuratețe capacitatea robotului de a stabili (știi) locația sa efectivă față de hartă.

Există diverse tehnici pentru a compensa erorile, cum ar fi recunoașterea caracteristicilor care au mai fost întâmpinate și reschițarea părților recente de pe hartă pentru a se asigura că două instanțe devin una. Unele dintre tehnicile statistice utilizate în SLAM includ filtre Kalman, filtre de particule și scanare datelor gamă.

Cartografierea

SLAM în comunitatea mobilă robotică, în general, se referă la procesul de creare a hărților geometrice consecvente ale mediului. Hărțile topologice sunt o metodă de reprezentare a mediului, care captează conectivitatea (de exemplu, topologia), mediului, mai degrabă decât a crea o hartă exactă din punct de vedere geometric. Ca rezultat, algoritmii pentru crearea hărților topologice nu sunt menționați în continuare SLAM.

SLAM este adaptată la resursele disponibile, prin urmare, nu vizează perfecțiunea, ci conformitatea operațională.

În general se consideră că "rezolvarea" problemei SLAM a fost una dintre realizările notabile ale roboticii de cercetare în ultimele decenii. Problemele legate de date de asociere și de complexitatea de calcul se numără printre problemele care urmează să fie încă pe deplin rezolvate.

Un avans semnificativ recent în funcția de baza din literatura de specialitate SLAM a implicat re-examinarea fundamentului probabilistic pentru cartografierea și localizarea simultană (SLAM), în cazul în care aceasta a fost pusă în termeni de filtrare Bazesiană multi-obiect cu seturi aleatoare finite, care oferă performanțe superioare de conducere a algoritmulor-caracteristici pe baza SLAM în provocarea scenariilor de măsurare cu rate mari de alarmă falsă și a ridicat ratele de detectare fără a fi nevoie de date de asociere. Algoritmii au fost elaborați pe baza ipotezei tehnicilor de filtrare Probabilitate Densitate (DSP).

Senzorii

SLAM va utiliza întotdeauna mai multe tipuri diferite de senzori pentru a obține date cu erori statistice independente. Independența statistică este cerința obligatorie pentru a face față măsurătorilor de zgomot.

Astfel de senzori optici ar putea fi cel dimensional sau 2D (fază unică) telemetrele cu laser, 3D Flash LIDAR, senzorii sonari 2D sau 3D și una sau mai multe camere 2D. Începând cu anul 2005, a fost efectuată o cercetare intensivă referitoare la VSLAM (SLAM vizual), folosind în principal seonzori (camere) vizuale, datoirtă creșterii ubicuității tot mai mari de camere, cum ar fi cele în dispozitivele mobile.

Abordările recente aplică wireless cvasi-optic variind pentru „multi-lateration” – sisteme de localizare în timp real (RTLS), sau multi-angularea coroborată cu SLAM ca un omagiu adus unor măsuri haotice fără fir.

Localizarea

Rezultatele de la senzor vor alimenta algoritmii de localizare. Conform propunerilor din geometrie, orice detectare trebuie să includă cel puțin un „lateration” și (n +1) ecuații de stabilire pentru o problemă n-dimensională. În plus, trebuie să existe o cunoaștere suplimentare prioritară despre orientarea față de rezultatele sistemelor de coordonate absolute sau relative cu rotatie si oglindire.

Modelarea

Contribuția la cartografiere poate lucra în modelarea 2D și reprezentarea respectivă sau în modelare 3D si reprezentare 2D, precum proiectare. Ca parte a modelului, cinematica a robotului este inclusă, pentru a îmbunătăți estimările de detectare în condiții de zgomot ambiental și inerente. Modelul dinamic echilibrează contribuțiile de la diferiți senzori, diferite modele parțiale de eroare și în cele din urmă cuprinde într-o descriere virtuală precisă ca o hartă cu locația și direcția robotului ca un nor de probabilitate. Cartografierea este reprezentarea finală a unui astfel de model, harta este fie descrierea sau termenul abstract pentru modelul respectiv.

Modelarea mediilor în care operează RMI presupune determinarea formelor, pozițiilor și dimensiunilor obiectelor și obstacolelor de tip construcție (pereți, stâlpi, paravane etc.) care stau la baza elaborării unei hărți necesare pentru planificarea traseelor de navigare. Problema navigării roboților mobili, inclusiv a celor industriali, în mediile care operează, presupune parcurgerea următoarelor etape: localizare (absolută sau relativă) bazată pe senzori (percepție), generare hartă locală (mapare), planificarea traseului (căii) și urmărirea acestuia. În practica modelării mediilor de operare primele două etape, fiind strâns legate, se realizează de obicei simultan, sub denumirea de localizare și mapare simultană (SLAM – Simultaneous Localization And Mapping).

I.2 Istoria problemei S.L.A.M.

Originea problemei SLAM probabilistică a avut loc în 1986 la Conferința IEEE Robotică și Automatizări din San Francisco. Era o vreme când metode probabilistice abia incepeau să fie implementate în robotică și în automatizări.

Un număr de cercetători urmărea sa aplice metodele teoretice de estimare a problemei cartografierii și localizării; aceștia erau inclus Peter Cheeseman, Jim Crowley, și Hugh Durrant- Whyte. Pe parcursul conferinței

au fost doar la început urmează să fie introdus în ambele robotică și AI. O serie de cercetatori au fost cautati la aplicarea metodelor de estimare-teoretice la probleme de cartografiere și localizare; aceste inclus Peter Cheeseman, Jim Crowley, și Hugh Durrant-Whyte. Pe parcursul conferinței, au fost prezentate multe articole, rezultate ale cercetatorilor din domeniu mapării. Pe lângă acestea, Raja Chatila, Oliver Faugeras, Randal Smith și alții au adus de asemena contribuții la problema discutată. Rezultatul acestei discuții a fost faptul că această cartografiere consistent probabilistică a fost o problemă fundamentală în robotică cu probleme majore conceptuale și de calcul care aveau nevoie să fie abordate.

De-a lungul următorilor ani au apărut o serie de documente cheie. Lucrările lui Smith și Cheesman (On the representation of spatial uncertainty. Int. J. Robotics Research,) si Durrant-Whyte (Uncertain geometry in robotics. IEEE Trans. Robotics and Automation) a stabilit o bază statistică pentru descrierea relațiilor dintre repere și manipularea incertitudinii geometrice. Un element cheie al acestei lucrări a fost să arate că trebuie să existe un grad ridicat de corelare între estimările localizării diferitelor repere de pe o hartă și că intr-adevăr din aceste corelații vor rezulta observații importante. În același timp, Ayache și Faugeras au inițiat contribuții la navigarea vizuală, Crowley (World modeling and position estimation for a mobile robot using ultra-sonic ranging. In Proc. IEEE Int. Conf. Robotics and Automation) și Chatila și Laumond (Position referencing and consistent world modeling for mobile robots. In Proc. IEEE Int. Conf. Robotics and Automation) la navigarea roboților mobili cu sonare folosind algoritmi Kalman. Aceste două componente de cercetare au avut multe în comun și au apărut la scurt timp după lucrările lui Smith, Sinele și Cheeseman (Estimating uncertain spatial relationships in robotics. In I.J. Cox and G.T. Wilfon, editors, Autonomous Robot Vehicles). Această lucrare a prezentat cum un robot mobil se poate deplasa într-un mediu necunoscut după observații relative asupra unor repere, este necesar ca estimările acestor repere să fie corelate între ele datorită erorii comune în estimarea locației robotului. Această implicație avea să fie fundamentală: o soluție în concordanță deplină cu localizarea combinată și problema cartografierii ar avea nevoie de o îmbinare a pozițiilor compuse ale robotului și fiecare poziție a reperului, care sa fie actualizată urmărind fiecare observație a reperului. În moed hotărâtor aceasta nu a ținut cont de proprietățile convergente ale hărții sau comportamentul acesteia la echilibru. Într-adevăr, ea a fost abordată pe larg în momentul în care erorile estimate nu ar converge și ar expune în schimb un comportament de mers aleator cu o creștere de eroare nemărginită. Astfel, având în vedere complexitatea de calcul a problemei de cartografiere și fără a cunoaște comportamentul de convergență al hărții, cercetatorii, în loc să se axeze pe o serie de aproximări la solutia problemei coerente de cartografiere, au forțat corelații între repere care urmau să fie minimizate sau eliminate, astfel că până la reducerea filtrului complet și înlocuirea cu o serie de repere cu filtre decuplate.

De asemenea, din aceste motive, lucrările teoretice privind localizarea combinată și problema de cartografiere au ajuns la o oprire temporară, iar munca s-a axat fie pe cartografiere, fie pe localizare ca și probleme separate.

Descoperirea conceptuală a venit odată cu înțelegerea faptului ca problemele combinate de cartografiere și localizare, fiind formulate ca o singură problemă de estimare, au fost de fapt convergente. Cel mai important a fost faptul că recunoașterea corelațiilor dintre repere, pe care mulți cercetători au încercat să o minimizeze, a fost de fapt partea critică a problemei si care, din contră, cu cât creșteau mai mult aceste corelații, cu atât mai bună era soluția. Structura problemei SLAM, convergența rezultatului, și acceptarea acronimului „SLAM” au condus la prima lucrare despre roboți mobili prezentată în 1995 la International Symposium on Robotics Research.

Între timp, au fost îmbunătățite și metodele de calcul în asociere cu „închiderea buclei”. International Symposium on Robotics Research din 1999 a fost un punct de întâlnire foarte important unde a fost ținută prima sesiune SLAM și unde a fost realizată prima convergență între metodele SLAM bazate pe filtrul Kalman și metodele de localizare și cartografiere prezentate de Thrun. La sesiunea de lucru IEEE ICRA din 2000 au participat 15 cercetători care s-au axat pe probleme privind complexitatea algoritmilor și provocările privind asocierea și implementarea informațiilor. Următoarea sesiune de lucru din 2002 a atras 150 de cercetători cu o gamă largă de preocupări și aplicații în domeniu. Școala de vară SLAM din 2002, găzduită de Henrik Christiansen la KTH în Stockholm a astras toți cercetătorii cheie împreună cu 50 de doctoranzi din toată lumea și a fost un succes nemaipomenit în structurarea domeniului.

În ultimii ani, interesul pentru SLAM a crescut exponențial, iar lucrările sunt susținute în continuare la ICRA și IROS.

Un grafic al evoluției vehiculelor utilizate în industrie din anul 1959 până în anul 2000 este reprezentat mai jos având la bază cercetările institutului Frauenhofer din Stuttgart/Germania. De menționat sunt cele trei mari categorii relevante în dezvoltare de-a lungul anilor.

Figura I.1 – Evoluția vehiculelor autonome

Conform statisticii federației internaționale de robotică, 76.600 de unități de roboți în valoare totală de 13,2 miliarde dolari, care acoperă domeniul serviciilor în industrie au fost comercializați până în anul 2009. Din acest total 5% reprezintă domeniul logistic, și 6% platforme mobile de uz general în domeniul fabricației. Se observă un trend crescând al utilizării acestora pentru perioada următoare.

Figura I.2 – Valori statistice ale vânzărilor de roboți pentru servicii

în domeniul industrial și profesional în anul 2009

O abordare a realizării unei hărți virtuale prin extragerea de particularități (feature-based) asemănătoare celor descrise în este realizată cu ajutorul unui algoritm propriu de reducere a datelor având la bază algoritmul de evoluție discretă a contururilor DCE. O serie de fenomene specifice cum sunt, de exemplu, cel de ocluzionare a obiectelor în timpul scanării mediului sau a comparației traiectoriei de deplasare de parcurs și parcursă sunt particularizate și analizate, iar ulterior este prezentată o soluție implementată a acestora. Stabilirea traiectoriei vehiculului reprezintă o problema tratată la nivel macro. În acest sens, focalizarea merge pe pregătirea datelor necesare pentru generarea traiectoriei de deplasare, mai concret, pe abordarea în detaliu a conceptului de (SLAM). Traiectoria vehiculului este generată prin metoda câmpurilor potențiale. Un mecanism de detecție și evitare a obstacolelor este prezentat în continuarea capitolului bazat pe integrarea matricială a curbelor specifice (clotoide și curbe Bezier). Pentru localizarea vehiculului în harta generată, considerat un proces simultan de navigație, este prezentat un model implementat de extragere a reperelor rezultând în urma informațiilor extrase din mediu în timpul procesului de cartografiere. O transformare într-un cvasi spațiu Hough a parametrilor unei linii este realizată pentru extragerea datelor relevante și reducerea acestora la un minim necesar. Cu ajutorul unui filtru Kalman extins (EKF) modelat, reperele sunt înregistrate și adăugate datelor de odometrie ale vehiculului pentru realizarea unei localizări cât mai exacte și predicția următoarelor date relevante necesare pentru susținerea vehiculului în timpul navigației.

Strategii de operare a AGV-urilor industriale

Pe baza regulilor de expediție este realizată navigarea vehiculelor ghidate automat în vederea îndeplinirii de sarcini. Performanța modelelor analitice depinde de regula de expediție adoptată. O distribuție paralelă a sarcinilor reprezintă un avantaj în procesarea acestora fiind o tematică relativ nouă și în acest domeniu. Practic, un vehicul autonom devine responsabil pentru îndeplinirea altor sarcini în drum spre sarcina primită de la sistemul de comandă central. Avantajele și dezavantajele sistemelor de ghidare sunt descrise conform tabelului de mai jos cu extinderea criteriilor de navigație cu ghidare video și GPS, două componente introduse ca evoluție în ceea ce privește sistemele de navigație a vehiculelor specifice.

Tabelul I.1 – Prezentarea criteriilor calitative a sistemelor de ghidare

În vederea atingerii unei flexibilități optime în sistemul de fabricație se recomandă utilizarea sistemului celui mai rapid în implementare și a investițiilor cu costuri minime. Având scopul maximizării flexibilității atât în manipulare, cât și în navigație, sistemele cu ghidare Laser și video reprezintă pentru mediul intern un beneficiu în cele două direcții.

Vehiculele autonome cu utilizări industriale reprezintă un avantaj în flexibilitatea manipulării materiei prime în cadrul producției, cât și în domeniul logistic. În acest sens, dezvoltarea acestor sisteme poate reduce continuu costurile producției conform studiilor, Stadiul actual 10 având la bază concepte de fabricație precum „just-in-time” sau „flexible manufacturing” și contextul actual global de dezvoltare a producției bazat pe continua adaptare. Costurile manipulării materialului reprezintă o proporție semnificativă în costurile de producție. În lucrarea lor, Eynan și Rosenblatt indică faptul că aceste costuri pot atinge 30% din costul total al producției. În acest sens, tematica abordată devine importantă datorită flexibilității, caracteristică a sistemului de producție. Este importantă abordarea interacțiunii dintre mașini, manipularea materialului și sistemul informatic. Nivelul de automatizare permite stabilirea unei comunicații între sistemul central de comandă și vehiculele autonome sau între unitățile autonome. Criteriile de evaluare a actualelor arhitecturi de transport și noile posibilități de realizare tehnică oferă o privire de ansamblu asupra direcțiilor de cercetare viitoare. Indiferent de domeniul de aplicație, tendința este de a automatiza procesele prin introducerea vehiculelor specifice. Având la bază evoluția ultimilor cincizeci de ani a vehiculelor utilizate în industria auto, se poate afirma că noutățile tehnice și informaționale a timpilor respectivi au fost acumulate și dezvoltate cu succes și în zona de transfer a spațiilor industriale.

Odată cu apariția senzorilor performanți, vehiculelor le-au fost dezvoltate și alte funcții, crescând prin acest lucru în primul rând flexibilitatea. Produsele primesc prin integrarea inteligenței artificiale un grad tot mai înalt de adaptivitate, fapt confirmat și de topul privind direcția de cercetare și implementare a vehiculelor autonome la nivel mondial. În acest context au fost realizate următoarele cercetări:

un studiu al literaturii de specialitate și de piață care sa evidențieze evoluția de pe piață actuala și viitoare a vehiculelor autonome utilizate atât în industrie cât și în alte domenii;

analiză a principiilor de funcționare a celor mai utilizate sisteme de ghidare din industria de fabricație;

cercetarea unui layout de fabricație în scopul identificării si evidențierii strategiilor de lucru posibile din acesta;

un studiu al flexibilității în manipulare a diferitelor sisteme de ghidare.

Trendul în robotică este acoperirea și automatizarea a câtor mai multe domenii în speranța simplificării sarcinilor oamenilor, a siguranței și preciziei producției, a asistenței rutiere, respectiv a dezvoltării zonei de servicii în general. În toate aceste domenii roboții mobili au cunoscut o dezvoltare generoasă în ultimii ani. Deosebirea de aplicații este definită de criteriile de operare în mediile specifice:

mediul intern structurat

mediul extern nestructurat.

Capitolul II – ALGORITMUL S.L.A.M.

II.1 Structura algoritmului S.L.A.M.

Acest concept se referă la cartografiere și localizare simultană (SLAM) și reprezintă o tehnică creată de comunitatea de robotică în scopul de a analiza posibilitatea unui vehicul autonom de a porni dintr-o locație necunoscută și asimilând informații despre mediul în care activează, creează o hartă a spațiului activ care este construită incremental. Prin utilizarea senzorilor și completarea simultană a noilor date în harta generată, vehiculul se poate localiza singur. Atât harta, cât și estimările despre localizarea vehiculului în urma unei activități de SLAM reprezintă suportul pentru viitoarele sarcini pe care le îndeplinește vehiculul inteligent autonom. O soluție practică privind localizarea proprie și cartografierea reprezintă o valoare inestimabilă în ceea ce privește realizarea unui vehicul inteligent autonom după cum este descris în. Privind evoluția tematicii SLAM au fost dezvoltate o serie de concepte și abordări. Este posibil a clasifica diferitele abordări în funcție de metoda de reprezentare utilizată pentru realizarea hărții, care reprezintă un punct cheie, deoarece aceasta determină tipul de informații în mod explicit exprimate în model. Cele mai comune metode de reprezentare sunt:

Grilele de ocupare. Acestea descriu împrejurimile vehiculelor prin împărțirea spațiului în mai multe celule regulate și atribuirea unei valori probabilistice care stabilește zone goale, necunoscute și ocupate.

Hărți topologice. Un exemplu de astfel de hărți îl reprezintă diagramele Voronoi.

Harți bazate pe trăsături particulare. Elementele de bază a reprezentării mediului se realizează prin utilizarea unui set de primitive geometrice, cum ar fi puncte, linii și plane anterior extrase din date brute ale senzorilor.

Figura II.1 – Realizarea hărților prin extragerea de linii din puncte

Harți realizate din scanări succesive. Datele neprelucrate ale senzorilor sunt aliniate în mod direct printr-un proces de translație și rotație prin găsirea unui maxim de 18 suprapunere cu datele conținute în scanarea anterioară. Se obțin astfel segmente de hărți care sunt fuzionate la fiecare achiziție de date noi. Este potrivit pentru utilizarea în situații în care nicio reprezentare geometrică simplă de mediu nu poate fi obținută. Până în prezent, aceasta nu a fost dovedită cu succes decât pentru laser, conform studiilor.

Figura II.2 – Hărți generate din scanări succesive

Odată ce a fost selectată metoda de reprezentare, dificultatea tehnică principală pentru realizarea SLAM-ului este definită prin reducerea pe cât posibil a incertitudinilor crescânde, cât și a reducerii de zgomot, respectiv a erorilor senzorilor. Este esențial să se găsească o metodă eficientă din punct de vedere al calculului capabilă să facă față incer titudinilor, să realizeze o reprezentare acurată pentru a obține o hartă precisă și, prin urmare, o localizare fiabilă a vehiculului. Alte dificultăți tehnice legate de problematica SLAM se referă la extragerea trăsăturilor particulare și problema asocierii. Obținerea informațiilor credibile și de la datele cu zgomot ale senzorilor, cât și discernământul de identificare a explorării anterioare a aceluiași teritoriu reprezintă elemente cheie pentru convergența unui algoritm SLAM.

Extragerea trăsăturilor particulare din mediul de navigație

Reprezentările depind de alegerea mediului de navigație, cât și de tipul senzorilor utilizați. Alegerile făcute cauzează diferențe mari în interpretare. Spre exemplu, datele unui senzor laser pot fi utilizate atât direct, prin realizarea transformării în coordonatele globale sau prin prelucrarea acestora în trăsături particulare. Grilele de ocupare utilizează în mod frecvent modelul senzorului utilizat pentru a furniza informația privind volumele ocupate. Metodele bazate pe extragerea trăsăturilor particulare din mediul de navigație sunt utilizate în principal pentru procesarea datelor de la senzori în ordinea de a găsi entitățile care pot fi identificate în mod repetat. Aceste entități se numesc trăsături particulare, iar procesul de obținere a acestora poartă denumirea de extragere a trăsăturilor particulare. Prin această tehnică, de obținere a trăsăturilor particulare, informația furnizată de diferiții senzori este manipulată în așa fel încât să se realizeze o extragere cât mai fezabilă și care să îndeplinească o serie de criterii.

Asocierea utilizând cea mai apropiată vecinătate (Nearest Neighbour)

O metodă de calcul rapidă privind asocierea observațiilor senzorilor interni (ai vehiculului) este descrisă de metoda celei mai apropiate vecinătăți. Se începe de la un obiect aleatoriu căruia îi este asociat obiectul cel mai apropiat ca distanță în spațiu în funcție de un parametru stabilit. În acest mod se caută vecinătatea care poate fi asociată. Varianta algoritmului utilizată asociază obiectele în interiorul unei așa numite regiuni de interes (ROI), care limitează spațiul de asociere a datelor. Prin definirea acestuia se reduce consistent efortul computațional în comparație cu alți algoritmi existenți, iar asocierea de date este maximală.

Figura II.3 – Asocierea datelor în regiunea de interes (ROI)

Dacă există prin limitarea ROI doar o singură asociere, aceasta este realizată. Celelalte rânduri și coloane ale matricei conținând datele extrase sunt excluse calculului. Pentru realizarea unei hărți de navigare precisă, valorile senzorilor trebuie interpretate perceptual. Astfel se extrag particularitățile mediului și se interpretează scene specifice ale mediului în scopul de a minimiza impactul individual al imperfecțiunii senzorilor, cât și pentru a obține robustețea necesară navigării. Asocierea corectă a datelor este o componentă crucială în realizarea algoritmilor SLAM care pot influența metode estimative cum sunt filtrele extinse Kalman (EKF-extended Kalman Filter). Metodele de asociere a datelor sunt dependente de tipurile de date provenite de la senzori. Aplicațiile care utilizează datele neprelucrate ale senzorilor cum sunt lanțurile succesive de scanare realizează o potrivire a datelor scanării în observație cu reprezentarea anterioară a hărții.

Acest tip de tehnică se poate clasifica în două categorii:

care utilizează date neprelucrate pentru reprezentare;

care utilizează reprezentări geometrice pentru redarea mediului scanat.

Un concept foarte utilizat în realizarea hărților este „map matching”, în care se caută elementele comune din segmentele de hărți generate și suprapunerea acestora într -o nouă hartă.

Metoda de suprapunere necesită resurse semnificative atât pentru reprezentare, cât și pentru efectuarea calculului final deoarece procesarea se face punct cu punct. În acest sens, o abordare simplă și aplicată în acest proiect o reprezintă împerecherea imediată a particularităților extrase aflate într-o zonă de interes prestabilită a vehiculului aflat în deplasare.

Localizarea vehiculului autonom

Localizarea unui vehicul autonom este răspunsul la întrebarea: „Unde mă aflu?” În acest context provocarea o reprezintă extragerea de particularități și asocierea de date cât mai precisă în vederea unei localizări cât mai exacte. Mediul în care operează un vehicul reprezintă un rol important atât datorită condițiilor suprafețelor de contact care influențează odometria vehiculului, cât și datorită obiectelor de identificat în vederea extragerii de particularități. Prin aplicarea filtrelor de corecție, aceste neajunsuri pot fi îndepărtate. Găsirea unei soluții optime depinde de mediul caracteristic în care operează vehiculul.

Figura II.4 – Schema generală a localizării unui vehicul autonom

Un element important îl constituie pe lângă extragerea de particularități, definirea unor observații care să constituie așa numitele repere de navigație. Cu ajutorul acestora se realizează actualizarea poziției vehiculului autonom.

Figura II.5 – Localizarea cu ajutorul reperelor

Un algoritm dezvoltat în vederea localizării proprii a vehiculului se referă la extragerea reperelor din linii, reprezentând muchii ale obiectelor scanate. Reperele sunt principalele particularități extrase, iar prin re-scanarea acestora în timpul navigației se realizează localizarea în spațiu. Reperele se evidențiază în timpul construcției hărții, de aceea fenomenul de localizare este strict legat de generarea hărții. În acest fel, cele două componente de cartografiere și localizare se completează reciproc

Cartografierea mediului de navigație în timp real

Cartografierea reprezintă problema integrării informației în urma achiziției datelor de la senzori și reprezentarea acestora într-o hartă. Acest proces poate fi descris de întrebarea „cum arată mediul în care se activează?” Aspectele centrale se referă la reprezentarea mediului și interpretarea datelor provenite de la senzori. În contrast, problema localizării se referă la estimarea poziției robotului relativă la o hartă. Cu alte cuvinte, robotul trebuie să răspundă întrebării „unde mă aflu?”. Se realizează o distincție între urmărirea poziției, unde poziția inițială a vehiculului este cunoscută, și localizarea globală proprie a vehiculului robot, unde nu există o informație cunoscută a priori. Problema controlului sau cea a determinării traiectoriei de deplasare implică eficiența de a ghida un vehicul către un punct stabilit.

Soluția ar cuprinde răspunsul la întrebarea: „Cum ajung cel mai eficient la o locație dată?”. Problema majoră este faptul că cele trei nu pot avea o abordare independentă. Înainte ca un robot să poată răspunde la întrebarea despre cum arată mediul în funcție de seturile de observații, trebuie să cunoască și perspectiva localizării din care s-au realizat observațiile. În același timp este greu de estimat poziția vehiculului fără o hartă.

Abordările integrate reprezintă și soluții pentru planificare, localizare și cartografiere simultană. În final, se presupune ca robotul mobil a realizat un model acurat al mediului și și-a determinat poziția proprie relativă la acest model.

Figura II.6 – Sarcini obligatorii pentru un robot mobil pentru ca acesta să înregistreze modele acurate ale mediului. Domeniile care se suprapun reprezintă zone cu elemente comune ale domeniilor.

Problemele cheie în contextul cartografierii în timp real se referă la întrebările de tipul:

încotro să fie ghidat un robot în timpul unei explorări autonome?

cum se rezolvă problema zgomotului în cazul estimării poziției și a reperelor observate?

cum se interpretează incertitudinea robotului în modelul global și cum sunt interpretate datele de la senzori?

cum se modelează modificările mediului variabile în timp?

cum se coordonează eficient un vehicul mobil autonom?

Contribuțiile prezentate în acest context prezintă soluții ale diferitelor aspecte prezentate anterior privind învățarea unei hărți globale și localizarea unui vehicul mobil autonom în harta generată. În ceea ce privește achiziția datelor, în domeniul roboților mobili, un factor important este reprezentat de localizarea robotului într-un mediu necunoscut. O estimare precisă a poziției reprezintă nucleul oricărui sistem de navigație cuprinzând localizarea, construcția dinamică a hărții și planificarea traiectoriei. Utilizarea datelor provenite de la odometria vehiculului robot nu sunt suficiente datorită faptului că acestea introduc în sistemul de poziționare erori și a măsurătorilor realizate și evidențiate în secțiunea realizării prototipului prezentată anterior. Soluționarea problemei este reprezentată de utilizarea diferiților senzori complementari (sonar, infraroșu, laser, video, etc.) și fuzionarea ulterioară a datelor prelucrate.

II.2 Algoritmi de calcul în procesul de cartografiere

În procesul de cartografiere există o serie de abordări atât de calcul, cât și de reprezentări grafice. Cele mai uzuale tehnici se referă la extracția particularităților din datele senzorilor, dar și procesarea directă a datelor neprelucrate ale senzorilor. Abordările care se referă la extragerea particularităților geometrice din datele inițiale ale senzorilor au fost studiate intensiv în domeniul localizării roboților mobili. De menționat este însă că în cazuri particulare o abordare combinată reușește să satisfacă împlinirea sarcinii de realizare a unei hărți precise de navigare. Segmentele de linie reprezintă printre primitivele geometrice cel mai simplu element. Este ușor de descris în aproape orice mediu și reprezintă totodată și cel mai comun mod de abordare în ceea ce privește reprezentarea 2D.

Figura II. 7 – Problema esențială SLAM.

O estimare simultană a robotului și locațiilor este necesară. Locațiile adevărate nu sunt cunoscute și nici măsurate direct. Observațiile sunt făcute între robotul adevărat și locațiile reperelor.

Să considerăm un robot mobil care se deplasează printr-un mediu, având observațiile relative ale unui număr de repere necunoscute, cu un senzor situat pe robot așa cum se vede în figura II.7. La un timp constant k, sunt definite următoarele mărimi:

xk: vector de stare care descrie locația și orientarea vehiculului;

uk: vector de control, aplicat la timpul kj1 pentru a conduce vehicolul la starea xk din timpul k;

mi: vector care descrie locația reperului cu numărul i a cărui locație reală se presupune a fi în timp invariant;

zik: o observație preluată de la vehicul, a locației reperului cu numărul i la timpul k. Când avem multiple observații ale reperului la diverși timpi sau cand reperele specifice nu sunt relevante, observația va fi pur și simplu scrisă ca zk.

În plus, sunt definite următoarele seturi:

X0:k = {x0, x1 …, xk} + {X0:k-1, xk}: Locațiie precedente ale vehiculului.

U0:k = {u0, u1 …, uk} + {U0:k-1, uk}: detalii referitoare la inputurile de control.

m = {m1, m2, …, mn} Setul tuturor reperelor.

Z0:k = {z0, z1 …, zk} + {Z0:k-1, zk}: Setul tuturor observațiilor reperelor

II.2.1 SLAM Probabilistic

În forma probabilistică, pentru problema creării cartografierii și localizării simultane este necesar ca distribuția probabilității

P (xk, m ǀ Z0:k, U0:k, x0) (1)

să fie calculată pentru toți timpii k. Această distribuție descrie desimea comună ulterioară a locației reperelor și starea vehiculului (la timpul k) date fiind observațiile înregistrate și inputurile de control până la și incluzând timpul k împreună cu starea inițială a vehiculului. În general, o soluție recurentă a problemei SLAM este de dorit. Începând cu estimare distribuției P(xk-1, m ǀ Z0:k-1, U0:k-1) la timpul k-1, îmbinarea ulterioară, după un control uk și o observație zk, este calculată utilizînd teorema lui Bayes. Acest calcul necesită un model în stare de tranziție și este definit un model de observație care descrie efectului controlului de intrare și respectiv, observația.

Modelul de observație descrie probabilitatea de a face o observație zk cand locația vehiculului și locațiile reperelor sunt cunoscute, și în general sunt descrise sub forma:

P(zk ǀ xk, m) (2)

Este rezonabil să presupunem că odată ce locația și harta vehiculului sunt definite, observațiile sunt independente în funcție de harta dată și starea curentă a vehiclului.

Modelul de mișcare pentru vehicul poate fi descris în termenii unei distribuții probabilistice în stare de tranziție sub forma:

P(xk ǀ xk-1, uk) (3)

Adică, se presupune că starea de tranziție este un proces Markov în care următoarea stare xk depinde doar de starea imediată de acțiune xk-1 și controlul aplicat uk, și este independentă atât de observații, cât și de hartă.

Acum, algoritmul SLAM esre implementat într-o predicție (actualizarea timpului) standard în doi pași, recurentă (secvențială) cu corecție (actualizarea măsurătorilor) de forma:

Actualizarea timpului:

(4)

Actualizarea măsurătorii

(5)

Ecuațiile 4 și 5 furnizează o procedură recurentă pentru calculul îmbinărilor ulterioare pentru starea xk a robotului și harta m la timpul k pe baza observațiilor Z0:k și toate intrările de control U0:k până la și inclusiv timpul k. Recurența este o funcție a modelului de vehicul P (xk ǀ xk-1, uk) și modelului de observație P(zk ǀ xk, m).

Problema construirii hărții poate fi formulată pe baza unui calcul al aglomerării: . Aceasta presupune că locația vehicului xk este cunoscută (sau cel puțin determinată) pentru toți timpii, cunoscând locația inițială. O hartă m este apoi constuită prin combinarea observațiilor de la diferite locații. În schimb, problema localizării poate fi formulată prin calculul probabilității distribuției . Aceasta presupune că locațiile reperelor sunt cunoscute cu certitudine și obiectivul este acela de a calcula o estimare a locației vehiculului cu referire la aceste repere.

II.2.2 Algoritmul împarte și îmbină (“split and merge”)

Segmentarea imaginilor a devenit o problemă , datorită creșterii dramatice în ultimii ani a utilizării calculatorului si in special a internetului. Pentru acest aspect au fost creeați diverși algoritmi. Printre aceștia, s-a dovedit pe parcurs că algoritmul “split and merge” este extrem de folosit datorită eficienței si simplității sale în sectorul prelucrării de imagini.

Segmentarea harților se bazează pe extragerea caracteristicilor din acestea, și anume determinarea zonelor din imagine care conțin pixeli cu caracteristici similare, culoare sau textură.

Practic, acesta este un process care implică partiționarea unei imagini în mai multe astfel de regiuni, verificând un anumit criteriu (cum ar fi de exemplu, culoarea). Unirea acestor regiuni trebuie sa restabilească harta inițială la sfârșit.

Procesul de segmentare este un pas extrem de important pentru extragerea de informații de calitate ale imaginii. Fiecare regiune segmentată este conectată la vecinii săi și oferă informații calitative, cum ar fi mărime, culoare sau formă.

Metodele de segmentare se impart în următoarele categorii:

a. Segmentarea prin divizare (“splitting”):

Se pleacă de la o zonă mare, de exemplu întreaga hartă, care se sparge în mai multe regiuni. Dacă regiunile obținute nu sunt omogene, se continuă spargerea până când se obțin regiuni omogene (care satisfac un anumit criteriu de omogenitate, după caz.)

b. Segmentarea prin divizare și unificare (“split and merge”):

Se pleacă de le regiuni de mărime medie, de exemplu pătrate de mărime fixă, se unifică regiunile similare și apoi se divizează regiunile care nu au fost unificate (Fig.II.8).

Figura II.8 – Principiul segmentării ”Divizare și unificare”

c. Segmentarea prin extindere(“merging”):

Pornind de la o regiune mică, de exemplu de un pixel, se dizolvă regiunea treptat, până când criteriul de extindere nu mai este satisfăcut.

d. Segmentarea prin extindere și unificare:

O hartă segmentată conține mai multe regiuni, pixelii fiecărei regiuni având aceeași intensitate, culoare sau textură.

Metodele pure de unificare sunt, din punct de computațional relativ scumpe și necesită resurse destul de mari, deoarece pornesc inițial de la regiuni mici (puncte individuale). Putem realiza acest lucru mult mai eficient prin divizarea recursivă a imaginii în regiuni mici și mai mici până când toate regiunile individuale sunt coerente, apoi tot recursiv fuzionarea acestora pentru a produce regiuni mai mari coerente.

Structura de bază de reprezentare este una de tip piramidal, adică o regiune pătrat de dimensiune m x n, un nivel al unei piramide are 4 subregiuni de mărime m/2 și n/2 care o alcătuiesc. De obicei, algoritmul pornește de la ipoteza inițială că intreaga hartă este o singură regiune, apoi calculează criteriul de omogenitate pentru a vedea dacă este adevărat (TRUE). Dacă, condiția nu este îndeplinită (FALSE), regiunea pătrat este subdivizată în alte 4 regiuni mai mici. Acest proces este repetat și pe fiecare dintre subregiunile create până când nu mai necesită divizare. Aceste regiuni rezultate sunt îmbinate, în cazul în care sunt similare, pentru a rezulta regiuni noi neregulate. Problema apare (cel puțin din punct de vedere al programării) când orice două regiuni pot fi fuzionate în cazul în care sunt adiacente și în cazul în care regiunea mai mare îndeplinește criteriile de omogenitate, dar regiunile care sunt adiacente pot avea “părinți” diferiți sau să fie la diferite niveluri (de exemplu, diferite în mărime), în structura piramidală. Procesul se termină atunci când nu se mai pot efectua unificări în continuare.

Figura II.9 – Structură de tip piramidal

În mod obișnuit, algoritmul începe cu existența unei singure regiuni, dar pot apărea excepții și este posibil să înceapă la un nivel intermediar. În acest caz este posibil ca patru regiuni să fi fuzionat pentru a forma o regiune părinte. Pentru simplificare, se presupune că se va începe cu o singură regiune, de exemplu imaginea de ansamblu. Apoi, procesul de divizare este simplu.

II.2.3 Algoritmul RANSAC

Random Sample Consensus (RANSAC) este o paradigmă pentru potrivirea unui model la date experimentale, introdusă de Martin A. Fischler si Robert C. Bolles in 1981. Dupa cum au declarat Fischler și Bolles ”Procedura RANSAC este opusul tehnicilor convenionale de filtrare: în loc să folosim cât mai multe date posibile pentru a obține o soluție inițială, și apoi să eliminăm punctele invalide, RANSAC folosește un set inițial de date cât mai mic posibil și apoi mărește acest set cu date valide atunci când este posibil.” Algoritmul RANSAC este descris după cum urmează:

1. Selecție aleatoare a unui eșantion de puncte s din multimea S și instanțiere a modelului din acest eșantion.

2. Determinarea multimii de date Si care conține puncte situate la o distanță mai mică decât un prag t de model. Mulțimea Si este mulțimea de consens a eșantionului, și definește punctele din S care satisfac modelul.

3. Dacă dimensiunea lui Si (numărul de puncte care satisfac modelul) este mai mare decât un prag T, algoritmul se termină. Opțional, se poate re-estima modelul folosind toate punctele din Si.

4. Dacă dimensiunea lui Si este mai mică decat T, se selectează un nou subset și se repetă pașii anteriori.

5. După N încercări, se selectează mulțimea de consens Si cu cele mai multe puncte, și (opțional) modelul este re-estimat folosind toate punctele din această mulțime.

RANSAC pentru linii

Figura II. 10

Figura II.11

Problema, ilustrată în figura II.10, este următoarea: fiind dată o mulțime de puncte 2D, trebuie găsită linia care minimizează suma distanțelor perpendiculare (regresie ortogonală), în condițiile în care nici unul din punctele valide nu deviază de la linie cu mai mult de t unități. Există de fapt două probleme: potrivirea unei linii la date, și clasificarea datelor în puncte valide și puncte zgomot. Pragul t este selectat în functie de zgomotul propriu măsurătorii.

Ideea este să se selecteze două puncte aleatoare, iar aceste puncte vor defini o linie. Mulțimea suport (consens) pentru această linie este dată de punctele care sunt la mai puțin de o distanță prag de această linie. Selecția aleatoare este repetată de mai multe ori, și linia care are cele mai multe puncte support este considerată potrivirea cea mai robustă. Intuitiv, dacă unul din cele două puncte alese pentru potrivirea liniei este parte a zgomotului, linia estimată nu va avea o mulțime suport foarte mare. Mai mult, dacă măsurăm calitatea unei linii prin mărimea mulțimii suport, avem avantajul de a favoriza cele mai bune linii de la început. Astfel, linia (a,b) din figura II.11 are o mărime a suportului de 10, pe când linia (a, d) are un suport de doar 4. Astfel, deși nici una din linii nu conține zgomot, va fi selectată linia (a,b).

Parametrii algoritmului:

1. Pragul de distanță: Se alege pragul t astfel încât un punct este valid cu o probabilitate a. Acest calcul implică cunoașterea distribuției de probabilitate pentru distanța unui punct valid la model. În practică, acest prag este ales empiric.

2. Numărul de eșantioane: Numărul de eșantioane N este ales pentru a asigura, cu o probabilitate p, că cel puțin unul din eșantioane nu conține zgomot. De obicei p este ales ca 0.99. Daca w este probabilitatea că orice punct selectat este valid, ε = 1-w este probabilitatea ca el să fie zgomot. Sunt necesare cel putin N selectii, încât (1-ws)N = 1-p deci, N = log(1-p)/log(1-(1-ε)s).

3. Mărimea pragului pentru mulțimea consens: O regulă simplă este ca algoritmul să se finalizeze în momentul în care dimensiunea mulțimii consens este similară cu numărul de puncte valide presupuse a fi în setul de date, dându-se proporția dintre puncte valide și zgomot. De exemplu, pentru n puncte T=(1- ε)n.

II.2.4 Transformarea Wigner-Hough

Teoria analizei imaginilor ne oferă instrumente care se pot folosi pentru îmbunătățirea interpretării reprezentărilor timp-frecvență. Unul dintre aceste instrumente îl reprezintă transformarea Hough. Transformării Hough pentru o linie cu ecuația parametrică în coordonate polare este:

ρ = x ⋅ cosθ + y ⋅ sinθ (6)

Pentru fiecare punct de imagine (x,y), tranformata Hough asociază o sinusoidă în planul (ρ,θ), amplitudinea fiecărui punct fiind egală cu intensitatea pixelului (x,y). Astfel, se realizează integrarea de-a lungul liniilor imaginii I, iar valoarea fiecarei integrale este asociată punctului (ρ,θ). Ca rezultat, dacă într-o imagine mai mulți pixeli de intensitate mai mare sunt concentrați de-a lungul unei drepte, se va observa, în domeniul (ρ,θ) un vârf ale cărui coordonate sunt legate direct cu parametrii liniei. Aplicând transformata Hough distribuției Wigner-Ville, se obține o nouă transformare, numită transformarea Wigner-Hough (WHT), a cărei expresie este:

(7)

Ca test de detecție se folosește compararea valorilor WHT cu un anumit prag, iar estimarea parametrilor necunoscuți f0 și β o reprezintă chiar valorile coordonatelor vârfului detectat al reprezentării. Trecerea la valorile f și t se face cu o relație de tipul 6).

Se va testa WHT cu ajutorul unui semnal chirp cu două componente pe fondul zgomotului. Forma semnalului, spectrul său și spectrul Wigner-Ville asociat sunt prezentate în fig.II.12, iar transformata sa Wigner-Hough, în fig.II.13.

Figura II.12 – Semnal chirp cu două componente pe fondul zgomotului:

a) forma; b) spectrul; c) transformata Wigner-Ville (reprezentare în plan);

d) transformata Wigner-Ville (reprezentare 3D).

Figura II.13 – Semnal chirp cu două componente pe fondul zgomotului: transformata Wigner-Hough

Se poate constata foarte buna separare, în spațiul parametrilor WHT, a componentelor semnalului; această separare era, practic, invizibilă în forma sau spectrul semnalului și foarte greu vizibilă în reprezentarea sa Wigner-Ville. Este, de asemenea de remarcat faptul că, în toate cazurile, în ciuda caracterului neliniar al transformatei Wigner-Hough, toate componetele semnalelor analizate sunt bine separate, în planul parametrilor (ρ,θ), chiar și în cazul semnalelor complexe pe fondul zgomotelor.

II.2.5 Algoritmul de extracție a liniilor bazat pe tehnica DCE (Discrete curve evolution) extDCE

Având în vedere dezvoltarea algoritmilor care să funcționeze în timp real, pe baza analizei rezultatelor și eficienței algoritmilor anterior prezentați a fost realizat un algoritm propriu care să satisfacă cerințele proiectului. Acest algoritm se bazează pe extracția succesivă a liniilor în timpul deplasării vehiculului. Spre deosebire de algoritmii anteriori, care au la bază colectarea de date înainte de aplicarea algoritmului, algoritmul de extracție a liniilor bazat pe tehnica DCE realizează o procesare imediată, pentru colectare fiind definit un „buffer” pentru determinarea punctelor necesare extragerii de linii rezultat în urma ciclurilor de scanare. Pentru acest fapt algoritmul este utilizat în procesarea aplicației software de generare a hărții virtuale în timp real.

Algoritmul provine din domeniul grafic unde extragerea liniilor reprezintă o tehnică de bază.

1. Inițializare: colectarea unui număr de N scanări (minim 3 puncte)

2. Verificarea distanței minime între 3 puncte definită de un parametru

3. Dacă valoarea parametrului este mai mică, se parcurge pasul 5

4. În caz contrar punctele sunt reintroduse în ciclul de N scanări pentru noi asocieri

5. Se verifică valoarea unghiulară stabilită cu ajutorul unui parametru cât și condiția L12<L1+L2 pentru trei puncte consecutive

6. Procesarea celor N scanări în linii aplicând algoritmul DCE extins

7. În cazul în care valoarea unghiulară a liniilor generate coincide, acestea sunt comasate într-o nouă linie.

Comparația algoritmilor de cartografiere a fost evaluată având la bază criteriile descrise în tabelul de mai jos.

Tabelul II.1 – Comparația algoritmilor

II.2.6 Reducerea datelor prin fuzionarea liniilor cu proprietăți comune

Forma obstacolelor și orientarea acestora, precum și eroarea de localizare a vehiculului determină deviația de poziționare a liniilor reprezentând muchiile obstacolului identificat în mod eronat.

Figura de mai jos evidențiază un asemenea caz.

Figura II.14 – Fenomenul de extragere a muchiilor

Pentru soluționarea acestei probleme de reprezentare se consideră calculul distanței euclidiene între două segmente de linie prin determinarea distanței minime între oricare element al celor două linii.

Figura II.15 – Substituția segmentelor de linie mici aparținând aceluiași cluster cu segmente de linie complete lungi

În urma calculului distanței dintre liniile generate se realizează o reducere de date prin fuzionarea liniilor care au parametrii comuni și aparțin aceluiași cluster. Se obține astfel o reducere de date de până la 70% din sistemul de extragere a particularităților prin fuzionarea liniilor de parametri comuni.

II.2.7 Extragerea reperelor din mediul de navigație pentru localizarea vehiculului

Pentru extragerea reperelor se ia în considerare algoritmul de reducere a liniilor DCE extins, realizat pentru reprezentarea muchiilor din mediul de navigație. Completarea este descrisă mai jos, având ca inițializare punctele de capăt ale liniilor extrase. Reidentificarea aceluiași reper asigură în spațiul phi/rho o reprezentare de aglomerare de puncte în aceeași zonă.

Figura II.16 – Extragerea reperelor din particularități (linii)

II.2.8 Modelul filtrului Kalman utilizat pentru corecția odometriei

Filtrul Kalman constă într-un sistem de ecuații matematice bazat pe minimizarea pătratelor erorilor și reprezintă astfel un estimator optim și pentru corecția poziției unui vehicul autonom. Cu toate acestea apare întrebarea: De ce tocmai un filtru Kalman? Argumentele care susțin utilizarea acestuia în industria de automatizare se referă la:

eficiența în aplicare;

estimarea stărilor trecute, actuale și a celor în viitor posibile;

măsurarea stărilor “ascunse”;

măsurarea calitativă a unei predicții prin varianțe;

robustețe; filtrul se descurcă foarte bine în modelele inexacte și este stabil sub condiții specifice. Funcționarea modelelor se bazează pe următoarea schemă ciclică:

Figura II.17 – Algoritmul de estimare și corecție a filtrului Kalman

Prima fază cuprinde update-ul temporar în care se realizează o estimare a vectorului de stare pentru pasul următor. În faza următoare se realizează o estimare a stării primei faze prin adaptarea acesteia la o măsurare actuală, astfel ca aceasta să poată fi corectată. Diferența de reglare este estimabilă, astfel încât o predicție cu ajutorul filtrului Kalman ar reduce această diferență dintre curba teoretică și cea reală la un minim, sistemul devenind unul mai precis. Estimarea și calculul traiectoriei de deplasare, respectiv a îmbunătățirii odometriei vehiculului este evidențiată în capitolul 4 într-o aplicație dezvoltată pe vehiculul autonom la scară.

II.2.9 Utilizarea Filtrului Kalman Extins (EKF) pentru poziționare cu ajutorul reperelor

Modelul matematic al filtrului Kalman extins pentru corecția poziției vehiculului inteligent autonom, utilizând datele odometrice și informațiile reperelor este descris după modelul din. Vectorul de condiție conține poziția actuală a vehiculului (xr, yr, vr, ϴr), cât si poziția absolută a reperelor sub forma (xn, yn ). Dimensiunea vectorului este 4+2n unde n reprezintă numărul reperelor.

II.3 Senzorul SICK LMS111

Una din cele mai precise categorii de senzori de distanță o constituie categoria senzorilor laser. Cu ajutorul acestor senzori se pot măsura distanța, viteza cât și accelerația anumitor obiecte din mediu față de robotul mobil. Principiul cu care operează un senzor laser este similar cu cel al unui senzor sonar, însă în loc de a trimite un semnal acustic, un puls scurt de lumină este trimis. Timpul între transmisia și recepția pulsului luminos este apoi folosit pentru a determina distanța până la obiectul respectiv.

Distanța maximă detectabilă a unui senzor laser poate fi de la câteva sute de metri la kilometrii sau chiar sute de kilometrii. Aceeași tehnologie a fost folosită pentru a măsura distanța de la Pâmânt la Lună cu acuratețe foarte mare.

Acuratețea distanței este undeva în domeniul milimetrilor, deci cu precizie de cateva zeci (chiar sute în unele cazuri) de ori mai mare decât cea a senzorilor ultrasonici. Datorită capacităților sale, senzorul laser este însă foarte scump, majoritatea aplicațiilor nejustificând încă achiziționarea unui astfel de sistem. Unul dintre cele mai cunoscute modele de senzori laser folosiți în robotică este modelul LMS 200 produs de firma SICK.

Senzor pentru măsurarea distanței LMS (Laser Measurement Sensors) – sisteme de măsurare rapidă cu laser

Senzorul LMS 111 are o gamă de scanare de până la 20m cu 13% ::::: și carcasă cu clasa de protecție IP 67.

Senzorii LMS sunt sisteme de măsurare electro-optice care scanează perimetrul din jurul său cu ajutorul unor fascilcule laser. Sunt măsuri bidimensionale în coordonate polare. În cazul în care un fascicul laser detectează un obiect, poziția este determinată, în formă de distanță și direcție.

Figura II.18 – Principiul de măsurare al senzorului LMS

Scanarea se face într-un plan pe 270°. LMS emite fascicule laser de impulsuri folosind o diodă laser. Dacă un astfel de impuls laser detectează un obiect sau o persoană, aceasta se reflectă la suprafața sa. Reflecția este detectată în receptorul sistemului de măsurare cu laser, folosind o fotodiodă.

Figura nr. II.19 – Principiul de operare pentru măsurarea propagării impulsului în timp

Gama de scanare a senzorului LMS depinde de remiterea obiectelor ce trebuie detectate. Cu cât suprafața reflectă mai bine raza de incidență, cu atât este mai mare gama de scanare a LMS. Figura de mai jos indică relația dintre remitere și detecție.

Figura nr. II 20 – Gama de scanare a senzorului LMS111

II.4 Pioneer 3 DX

Robotul Pioneer 3 DX are dimensiunile de 44x38x22cm, având scheletul mecanic construit din aluminiu. Roțile au diametrul de 16.5 cm. Pe lângă cele două roți mai există o a treia roată mică în spatele robotului pentru stabilitate.

Specificațiile Pioneer 3 DX: viteza lui maximă poate atinge 1.6m/s pe teren drept, suportă greutăți de până la 23kg și de asemenea, poate urca pe teren în rampă cu o înclinație de maxim 25%.

Figura II.21 – Pioneer 3 DX, vedere frontală

În varianta de bază, robotul Pioneer 3 DX are 8 sonare (senzori cu ultrasunete), așezate într-o configurație de 180 grade (fig. II.21). Senzorii pot citi date corect între distanțe de 15cm și 7m.

Există o largă gamă de accesorii pentru, robotul Pioneer 3 DX, printre care:

Acces la rețea wireless ethernet;

Sistem localizare și navigare bazat pe senzori laser;

Gripper;

Senzori pentru coliziune (bumper sensors) pentru evitarea coliziunilor în cazul în care robotul este prea aproape de perete și sonarele nu mai detectează sub o anumită distanță;

Cameră stereo video;

Senzori bazați pe unde în spectru infraroșu;

Sistem localizare bazat pe GPS (Global Positioning System).

Figura II.22 – Pioneer 3 DX, vedere spate

Senzorii cel mai des folosiți la roboții Pioneer sunt senzorii cu utrasunete. În modulul de bază al roboților Pioneer Dx există 8 astfel de senzori dispuși ca în fig. II.23. Unghiul de dispunere al senzorilor este:

Figura II.23 – Dispunerea senzorilor sonar

În figura II.24 se prezintă o schemă Pioneer 3 DX, împreună cu principalele elemente componente.

Figura II.24 – Schema de bază a robotului

BIBLIOGRAFIE

1. R. Luca, Contribuții privind sistemele de navigație a vehiculelor autonome, Rezumatul tezei de doctorat, Universitatea “Lucian Blaga” din Sibiu, 2011.

2. Lt. Col. Ing. Andrei Szilagyi, Contribuții la realizarea modelării receptoarelor de război electronic de radiolocație, Rezumatul tezei de doctorat, Academia Tehnică Militară, Bucuresti, 2006

3. SICK, Intelligence Sensors, Laser Measurement Systems of the LMS100 Product Family

4. Robert C. Bolles, Martin A. Fischler: A RANSAC-Based Approach to Model Fitting and Its Application to Finding Cylinders in Range Data, 1981

5. Richard Hartley, Andrew Zisserman: Multiple View Geometry in Computer Vision, 2003

6. R. Smith and P. Cheesman. On the representation of spatial uncertainty. Int. J. Robotics Research, 5(4):56{68, 1987.

7. H.F. Durrant-Whyte. Uncertain geometry in robotics. IEEE Trans. Robotics and Automation, 4(1):23{31, 1988.

8. R. Smith, M. Self, and P. Cheeseman. Estimating uncertain spatial relationships in robotics. In I.J. Cox and G.T. Wilfon, editors, Autonomous Robot Vehicles, pages 167{193. Springer- Verlag, 1990.

9. M. Csorba. Simultaneous Localisation and Map Building. PhD thesis, University of Oxford, 1997.

10. J.J. Leonard and H.F. Durrant-Whyte. Directed Sonar Navigation. Kluwer Academic Press, 1992.

11. W. D. Renken. Concurrent localization and map building for mobile robots using ultrasonic sensors. In Proc. IEEE Int. Workshop on Intelligent Robots and Systems (IROS), 1993.

12. H. Durrant-Whyte, D. Rye, and E. Nebot. Localisation of automatic guided vehicles. In G. Giralt and G. Hirzinger, editors, Robotics Research: The 7th International Symposium (ISRR'95),

pages 613{625. Springer Verlag, 1996.

13. S. Thrun, D. Fox, and W. Burgard. A probabilistic approach to concurrent mapping and localization for mobile robots. Machine Learning, 31(1):29{53, 1998

14. http://mobilerobots.org, accesat la data de 19.12.2011

15. Pioneer 2/PeopleBot Operations Manual, 2001, ActivMedia Robotics, LLC

16. Sebastian T., Learning Occupancy Grid Maps With Forward Sensor Models, School of Computer Science, Carnegie Mellon University, 2003

17. Stachniss C., Robotic Mapping and Exploration, Springer Verlag, ISBN-13 97836420110965, 2009.

18. Siegwart R., Nourbakhsh I.R., Scaramuzza D., Introduction to Autonomous Mobile Robots, Second Edition, The MIT Press. Massachusetts, ISBN 978-0-262-01535-6, 2011.