Tehisintellekti Algkursus 2019/20 kevad

Joonis 16: Modulaarse lahenduse üldine skeem.

Modulaarne lahendus (vt joonis 16) defineerib moodulid, millel on kindlad sisendid ja väljundid:

• Tajumoodul (perception module) töötleb sensoritelt tulevat informatsiooni ja pakendab selle ülejäänud moodulite jaoks lihtsasti kasutatavale kujule, nt tuvastatud objektide asukohad ja trajektoorid ning takistuskaart (occupancy grid).
• Positsioneerimise moodul (localization module) määrab auto asukoha ruumis sentimeetri täpsusega. Selle tulemusena on autol täpselt teada, kus see asub kaardil ja kuidas oma teekonda peaks planeerima, et jõuda sihtkohta.
• Planeerimise moodul (planning module) on jaotatud kolmeks: teekonna, manöövrite ja trajektoori planeerija.

• Juhtimismoodul (control module) teisendab soovitud trajektoori juhtimiskäskudeks, st rooli pööramiseks ning gaasi/piduri pedaalide vajutusteks.

Vektorkaart on modulaarse lähenemise juures võtmetähtsusega, seetõttu alustame sellest. Seejärel vaatleme, millised on põhilised meetodid iga mooduli realiseerimiseks.

Vektorkaart

Auto poolt teel kohatavad objektid võib jagada kaheks:

• seisvad ehk staatilised objektid,
• liikuvad ehk dünaamilised objektid.

Lihtsam ja usaldusväärsem on kõik staatilised objektid eelnevalt kaardistada kui lasta tajumoodulil neid tuvastada. Nimetatud kaarti nimetataksegi vektorkaardiks (vector map). Vektorkaarti koos positsioneerimiseks vajaliku punktipilvekaardiga (point cloud map) kokku nimetatakse kõrglahutusega kaardiks (high-definition map, HD map) või ka lihtsalt 3D kaardiks.

Vektorkaart (vt joonis 17) sisaldab:

• sõiduradade plaani,
• liiklusmärke,
• valgusfoore,
• stoppjooni,
• ülekäiguradasid,
• kiirusepiiranguid,
• jne.

Joonis 17: Vektorkaardi näide - Turu-Riia ristmik Tartus. Välja on toodud sõidurajad, stoppjooned ja valgusfoorid.

Vektorkaarti võib ette kujutada kui virtuaalseid trammirööpaid - need ütlevad täpselt ette, kuhu auto võib ja kuhu ei või sõita. Piisab auto sentimeetri täpsusega positsioneerimisest, et teada kui kaugel see on lähimast “rööpast” ja kuidas see sinna tagasi juhtida. Samuti saab auto toetuda vektorkaardil kirjeldatud liiklusmärkidele ja kiiruspiirangutele.

Täpne vektorkaart lihtsustab auto juhtimisülesannet oluliselt, kuna see taandub etteantud teekonna järgimisele. Samas on täpse vektorkaardi koostamine aeganõudev käsitöö, mis nõuab spetsiaalset tarkvara ja oskusteadmisi. Mitmed firmad (nt Mapillary) uurivad võimalusi vektorkaardi automaatseks loomiseks, kuid praktikas need veel kasutatavad pole. Lisaks tuleb vektorkaarti regulaarselt uuendada, nii püsivate ümberehituste kui ajutiste teetööde tõttu. See piirab vektorkaardile toetuvad lahendused 4. taseme autonoomsusega, kuna need toimivad ainult kaardi poolt määratud alal.

Tajumoodul

Nagu eespool öeldud, siis staatilised objektid on lihtsam kirjeldada vektorkaardil. Seetõttu tajumoodul keskendub eelkõige dünaamiliste objektide tuvastamisele, nagu näiteks autod, jalakäijad ja jalgratturid. Aeg-ajalt võib olla siiski vajalik etteantud trajektoorilt kõrvale kalduda, nt kui on teetööd või sinu sõidureas pargib auto. Sellistes olukordades peab olema tajumoodul hindama kas möödapõikeks valitud teekond on takistustevaba (free space estimation).

Tajumooduli lahendused sõltuvad väga palju kasutatavast sensorist, seetõttu on mõistlik neid vaadelda sensoripõhiselt.

Lidar
Kõige lihtsam viis takistuste tuvastamiseks lidariga on eemaldada lidari punktipilvest punktid, mis moodustavad maapinna. Kõik punktid mis on maapinnast kõrgemal - need ongi takistused, millele me otsa sõita ei taha. Maapinna eemaldamiseks on mitu võimalust:

1. lihtsalt eemaldada kõik punktid, mis on madalamal teatud kõrgusest,
2. leida tasapind, mis langeb kokku võimalikult paljude punktidega ja eemaldada punktid selle tasapinna lähedusest (töötab ainult siis, kui maapind on sile),
3. nn simuleeritud kanga (simulated cloth) meetod, kus punktipilv keeratakse tagurpidi ning sellele nagu laotatakse kangas (vt joonis 18). Maapinnaks loetakse kõik need punktid, mida kangas puudutab.

Joonis 18: Simuleeritud kanga meetod. Lidari poolt tuvastatud punktipilv keeratakse tagurpidi ning sellele laotatakse simuleeritud kangas. Kõik punktid, mida kangas puudutab, loetakse maapinnaks. Kõik ülejäänud punktid (pildil maja ja puu) loetakse takistusteks. (Allikas)

Eelnev töötab suhteliselt hästi staatiliste takistuste (sein, laternapost) tuvastamiseks, aga dünaamiliste takistuste (auto, jalakäija) puhul on meil tarvis hinnata ka nende liikumiskiirust ja trajektoori, et ise-enda liikumist ilma kokkupõrgeteta planeerida. Selleks, et käsitleda maapinnast ülejäävaid punkte kui terviklikke objekte, on võimalik kasutada Eukleidilist klasterdamist (vt joonis 19). Eukleidiline klasterdamine vaatleb punktide omavahelisi kaugusi ning paigutab samasse klastrisse kõik punktid, mille omavaheline kaugus on väiksem teatud lävendist (nt 10 cm). Eukleidiline klasterdamine ei sea piiranguid klastrite arvule ega kujule. Kui punktide arv klastris jääb alla teatud piirarvu, siis loetakse need punktid müraks ja klastrit ei looda. Levinud Eukleidilise klasterdamise meetod on DBSCAN (Density Based Spatial Clustering of Applications with Noise). Joonisel 20 on näha Eukleidilise klasterdamise tulemus reaalses tänavasituatsioonis.

Joonis 19: Eukleidilise klasterdamise põhimõte, punktid grupeeritakse nende omavahelise kauguse põhjal. Üksikuks jäänud punktid loetakse müraks.

Joonis 20: Eukleidilise klasterdamise tulemus reaalses tänavasituatsioonis. Leitud klastrid (objektid) on ümbritsetud piirjoonega.

Tuvastatud objektide liikumissuuna ja -kiiruse hindamiseks saab kasutada Kalmani filtrit (Kalman filter). Kalmani filter ennustab objekti uut asukohta tema senise liikumissuuna ja -kiiruse põhjal ning korrigeerib seda objekti uue tuvastatud asukoha alusel. Oluline aspekt siin on see, kuidas seostada eelmisel ajahetkel tuvastatud objektid järgmisel ajahetkel tuvastatud uute objektidega. Levinud meetod siin on läheduse põhjal - kui objekti ennustatud uus asukoht on lähedane mõne tuvastatud uue objekti asukohaga, siis on tegemist sama objektiga.

Erinevat tüüpi objektid, nt autod, jalakäijad või jalgratturid, liiguvad üsna erinevalt ja nende edasise käitumise ennustamisel võib olla mõistlik kasutada erinevaid profiile. Lihtne maapinna eemaldamine ning Eukleidiline klasterdamine annab meile objektid, aga ei anna teada, mis tüüpi objektiga on tegemist. Seetõttu kasutatakse kaasaegsetes süsteemides objektide tuvastamiseks punktipilvest närvivõrke. Üheks selliseks näiteks on PointPillars võrk, mille sisendiks on punktipilv ning väljundiks objektide 3D asukohad (vt joonis 21).

Joonis 21: PointPillars võrgu poolt tuvastatud autod. (Allikas)

PointPillars võrgu poolt väljastatud objektid saab samuti lasta läbi Kalmani filtri, mis lisab neile kiirused ja liikumissuunad.

Kaamera
Kaamera on väga võimekas ning mitmekülgne sensor, kuid selle tulemuse töötlemine nõuab suurt arvutusressurssi. Tänapäeval kasutatakse kaamerapildi töötlemiseks enamasti tehisnärvivõrke. Need närvivõrgud võivad täita küllaltki erinevaid ülesandeid (vt joonis 22):

• Klassifitseerimine (classification) - määrab ühe klassi terve pildi jaoks, nt kas valgusfooris põleb pildil punane, kollane või roheline tuli.
• Objektide tuvastamine (object detection) - tuvastab pildilt objektid, nt kus asuvad pildil autod, inimesed või jalgratturid.
• Semantiline segmenteerimine (semantic segmentation) - märgendab pildil iga piksli sellele vastava klassiga, nt sõidetav tee, kõnnitee, inimene jne.
• Individuaalsete objektide segmenteerimine (instance segmentation) - toob välja objektid ja nende piirjooned, nt autod ja inimesed.

Joonis 22: Ülal vasakul: klassifitseerimine. (Allikas) Ülal paremal: objektituvastus. (Allikas) All vasakul: semantiline segmentatsioon. (Allikas) All paremal: objekti segmentatsioon. (Allikas)

Klassifitseerimiseks on kasutusel enamasti ResNeti baasil ehitatud võrgud, mis on eeltreenitud ImageNet andmestiku peal. Objektituvastusel on laialt kasutatav YOLOv3 nimeline võrk, mis on treenitud MS COCO andmestikuga. Levinud semantilise segmenteerimise võrk on DeepLabv3+, mis on treenitud Cityscapes andmestikul. Semantilise segmenteerimise põhiline kasutusjuht isejuhtivate autode kontekstis on sõidetava ala (free space, drivable area) tuvastamine, selleks et mööda põigata ootamatutest takistustest, nt teetööd. Individuaalsete objektide segmenteerimisel on tuntuim MaskRCNN võrk, mis on samuti treenitud MS COCO andmestikul.

Kaamera ja lidari kombinatsioon
Nagu näha, siis kõik kaamera põhise tuvastuse tulemused on esitatud kahemõõtmelisena kaamerapildi kontekstis. Praktikas ei ole sellise tulemusega suurt midagi peale hakata - me vajame objektide ning takistustevaba ala asukohti kolmemõõtmelises ruumis, mida kaamera meile ei paku. Sellepärast osutubki vajalikuks kombineerida kaamera ja lidari infot - kaamera poolt on kiire ja täpne objektituvastus, lidari poolt kauguse hinnang.

Selleks, et kombineerida lidari ja kaamera andmeid, on tarvis need kalibreerida - leida teisendusmaatriks lidari ja kaamera vaatepunktide vahel (transformation matrix, extrinsic matrix) ja kaamera maatriks (camera matrix, intrinsic matrix). See võimaldab meil kuvada iga lidari punkti kaamera pildile (vt joonis 24). Seda saame kasutada:

• objekti kauguse hindamiseks - näiteks võtame keskmise või mediaankauguse üle kõikide lidari punktide, mis sattusid objekti kasti sisse kaamerapildil.
• lidari punktide märgendamiseks - näiteks märgime lidari punkti klassiks vastava piksli semantilise segmentatsiooni klassi.

Joonis 24: Lidari punktid kuvatuna kaamera pildile.

Praktikas on lidari ja kaamera andmete kombineerimine veidi keerulisem, alates kaamera läätsede moonutustest ja kalibreerimise ebatäpsustest kuni selleni, et kaamera pilt ja lidari punktipilv pole võetud ajaliselt täpselt samal ajal. Seetõttu vajab see hoolikat seadistust.

Iseseisev ülesanne (vabatahtlik)

• Tee oma telefoniga pilt reaalsest liiklusolukorrast (või kasuta juba olemasolevat pilti).
• Lae pilt üles Google Cloud Vision API lehele.
• Kas kõik autod ja inimesed tunti ära? Milliste objektide äratundmine valmistas tehisnärvivõrgule probleeme?

Positsioneerimise moodul

Positsioneerimise mooduli ülesandeks on määrata auto asukoht sentimeetri tasemel täpsusega. See on eelduseks kogu edasise tegevuse planeerimisel, nt kas tuleks hakata pidurdama, kuna ees on stopp-märk, või kas tuleks vahetada sõidurada, et pöörata paremale. Positsioneerimisel on kasutusel kaks põhilist meetodit: satelliitpositsioneerimine ja lidaril põhinev positsioneerimine.

Satelliitpositsioneerimine
Nagu eespool öeldud kasutab satelliitpositsioneerimine satelliitidelt saadetavaid signaale, et määrata auto asukoht ruumis. Tavalise satelliitpositsioneerimise täpsus jääb umbes 3 meetri kanti, mis pole piisav sõiduraja määramiseks. RTK (real-time kinematic) korrektsioonimeetodi abiga on võimalik täpsust suurendada kuni 5 sentimeetrini. Kuid isegi RTK-korrektsiooniga satelliitpositsioneerimine jääb hätta suurte majade vahel, metsas või tunnelis. Seetõttu kasutatakse lisaks ka inertsiaalandurit, mis võimaldab suhtelise positsioneerimise abil jätkata asukoha tuvastamist kuni 10 sekundit pärast satelliitsignaali kaotamist (vt joonis 25). Lõputult siiski inertsiaalandurile toetuda ei saa, kuna selle pisivead akumuleeruvad ning võivad lõpuks väljenduda märkimisväärses veas asukoha määramisel.

Joonis 25: Satelliitpositsioneerimise ja inertsiaalanduri kombineerimine. Majade vahel kaotab auto satelliitsignaali ja toetub inertsiaalandurile. Inertsiaalanduri vead aga kumuleeruvad ning pikalt sellele toetuda ei saa. Seetõttu majade vahelt väljudes toetub auto jälle satelliitpositsioneerimisele ja kombineerib seda inertsiaalanduriga. (Allikas)

Lidaripõhine positsioneerimine
Satelliitpositsioneerimine on väga töökindel ja täpne süsteem, seni kui arvestada selle piirangutega - ebatäpsused suurenevad kiiresti suurte majade ja puude vahel ning tunnelis. Tänapäeva suurlinnades on aga sellised tingimused üsna tavalised. Seetõttu tuleb appi võtta alternatiivne positsioneerimismeetod - lidaripõhine positsioneerimine.

Lidaripõhise positsioneerimise eelduseks on, et piirkonna kohta on eelnevalt kogutud 3D kaart punktipilve kujul ehk punktipilvekaart (vt joonis 26). Selleks tuleb piirkond kõigepealt läbi sõita ning salvestada punktipilv (ning soovitavalt GPS koordinaadid) igas trajektoori punktis. Selleks saab kasutada sama lidarit, mida kasutatakse ka hiljem positsioneerimiseks. GPS koordinaadid on vajalikud 3D kaardi joondamiseks tavapärase 2D kaardiga.

Joonis 26: Tartu kesklinna kaart punktipilve kujul.

Auto positsioneerimiseks olemasoleva punktipilvekaardi suhtes on kasutusel iteratiivne lähima punkti (iterative closest point) algoritm. See leiab asukoha punktipilvekaardis, mis kõige paremini sobitub viimase lidari skaneeringuga. Nimetatud algoritm vajab alustuseks piisavalt lähedast algasukohta, milleks kasutatakse tihtipeale satelliitpositsioneerimise tulemust. See on ka põhjus, miks on vajalik, et 3D punktipilv oleks joondatud tavalise 2D kaardiga (GPS-koordinaadistikuga). Iteratiivne lähima punkti algoritm on kontseptuaalne idee, selle üks laialt kasutatavaid realisatsioone on NDT (normal distributions transform), mida ongi mõistlik praktikas kasutada.

Sama algoritmi saab kasutada ka punktipilvekaardi enda koostamisel - lihtsalt iga uus lidari skaneering tuleb positsioneerida eelnevalt kogutud punktide suhtes ja seejärel lisada sinna. Sellise lähenemise nimi on SLAM (simultaneous localization and mapping). Siiski tuleb SLAM puhul tähelepanelik olla kumuleeruvate vigade suhtes, näiteks sõites ümber kvartali, ei pruugi ring lõppeda täpselt seal kus algas. Seetõttu on vajalik kaardi koostamisel arvesse võtta ka satelliitpositsioneerimise tulemusi.

Kombinatsioon
Kui satelliitpositsioneerimine võib jääda hätta suurte majade ja puude vahel ning tunnelis, siis lidaripõhine positsioneerimine on tundlik muutuste suhtes. Kui on ehitatud uus maja või on tänaval teetööd või on ilmunud suured rahvahulgad, siis kõik see võib lidaripõhist positsioneerimist segadusse ajada. Seetõttu praktikas tavaliselt kombineeritakse kõiki võimalikke positsioneerimisviise:

1. satelliitpositsioneerimine (absoluutne),
2. lidaripõhine positsioneerimine (suhteline, punktipilvekaardi suhtes või eelmise asukoha suhtes),
3. inertsiaalandur (suhteline, eelmise asukoha suhtes),
4. odomeetria, so auto rataste kiiruse ja asendi põhjal (suhteline, eelmise asukoha suhtes),
5. visuaalne, so kaamerast tuvastatud punktide põhjal (suhteline, eelmise asukoha suhtes).

Erinevatest allikatest pärinevate positsioneerimistulemuste kombineerimiseks on kasutusel Kalmani filter. Sellest on mitmeid eri versioone - laiendatud Kalmani filter (EKF, Extended Kalman Filter), lõhnatu Kalmani filter (UKF, Unscented Kalman Filter), osakeste filter (PF, Particle Filter) jne. Nendest praktikas enim kasutatud on UKF.

Iseseisev ülesanne (vabatahtlik)

• Paigalda oma telefoni Geopeituse rakendus, kas Androidi või iOS jaoks.
• Otsi oma lähikonnast üles mõni geopeituse aare!
• Kui täpselt sinu telefon suutis näidata geopeituse aarde asukohta?

Planeerimise moodul

Planeerimise moodulil on kõige vastutusrikkam ülesanne - siin määratakse sisuliselt auto käitumine erinevates liiklusolukordades. Seetõttu on see ka kõige keerulisem moodul ja koosneb kolmest erinevast alammoodulist: teekonna planeerija, manöövrite planeerija ja trajektoori planeerija. Kõik need alammoodulid on omavahel tihedalt seotud, kuid samas selgelt erinevate ülesannetega. Järgnevalt vaatleme neid alammooduleid ja nende realisatsioonimeetodeid lähemalt.

Teekonna planeerija
Teekonna planeerija ülesandeks on leida kiireim teekond punktist A punkti B. See on väga sarnane sellele, mida teeb navigatsioonirakendus sinu mobiiltelefonis. Teedevõrku esitatakse arvutis tavaliselt graafina (vt joonis 27). Graaf koosneb tippudest (nt linnad) ja servadest (nt ühendused linnade vahel). Servadele võivad olla määratud kaalud (nt linnadevahelised kaugused või sõiduajad). Navigeerimiseks vajalik graaf on muidugi oluliselt detailsem, lihtsustatult võib öelda, et selle tippudeks on ristmikud ja servadeks tänavalõigud. Isejuhtiva auto vektorkaart on aga esitatud lausa sõiduradade täpsusega.

Joonis 27: Eesti linnade graaf. Graafi tipud on linnad, servad on teedeühendused linnade vahel ning servade kaalud on kaugused linnade vahel. Isejuhtiva auto vektorkaart on oluliselt suurema detailsusega, sõiduraja täpsusega. (Allikas)

Levinud graafiülesanne ongi leida lühim tee kahe tipu vahel, nii et läbitud servade kaalude summa oleks minimaalne. Klassikaline lahendus sellele on Dijkstra algoritm, mis kasutab laiuti otsingu meetodit - otsingut jätkatakse sellest tipust, milleni viib seni lühim teekond (vt joonis 28). Dijkstra algoritm ei leia mitte ainult lühimat teed kahe punkti vahel, vaid etteantud punkti ja kõikide ülejäänud punktide vahel.

Joonis 28: Dijkstra algoritmi visualisatsioon. Alustatakse kollasest punktist all paremas nurgas ning järgmiseks vaadeldakse seni lühima teekonnaga punkti. (Allikas)

Praktikas on kasutusel mitmed Dijkstra algortimi modifikatsioonid, nt A* algoritm, mis töötleb esimesena mitte kõige lühema kaugusega tippu algtipust, vaid võtab arvesse ka hinnangulist kaugust siht-tipust (nt linnade puhul kaugust linnulennult). Ehk siis tippe töödeldakse järjekorras, mille määrab senise teekonna ja hinnangulise järelejäänud teekonna summa.

Boonus materjal (vabatahtlik)

1. Mine Dijkstra algoritmi visualiseerimise lehele.
2. Sisesta algtipp (Start vertex), nt 0.
3. Vajuta nupule Run Dijkstra.
4. Püüa algoritmi toimimist mõista. Vajadusel saad käivitada algoritmi sammhaaval. Abiks on ka algoritmi kirjeldus.

Manöövrite planeerija
Manöövrite planeerija peab ühest küljest arvesse võtma planeeritud teekonda ja teisest küljest reaalset liiklussituatsiooni. Näiteks kui parempöörde jaoks tuleks reastuda paremasse ritta, aga seal ei ole ühtegi vaba kohta, siis on autol võimalus kas jääda seisma ja oodata, või siis sõitmist jätkata ja teekond ümber planeerida.

Manöövrite planeerija on tihti realiseeritud olekumasinana (vt joonis 29). Sellise olekumasina olekuteks on näiteks SõidaEdasi, JärgiEessõitjat, MööduEessõitjast, PeatuValgusfooriEes, OotaRohelistTuld, PeatuStoppjooneEes, AnnaTeed jne. Üleminekud ühest olekust teise on määratud kindlate reeglitega ning igas olekus on autol erinev käitumine. Nt auto alustab sõitu olekus SõidaEdasi ja järgib etteantud trajektoori ning sõidukiirust. Kui auto jõuab järele aeglasemale eesõitvale autole, siis muutub olek JärgiEessõitjat ning auto hoiab oma kiirust samana eessõitjaga. Kui auto läheneb valgusfoorile, kus põleb punane tuli, siis muutub olekuks PeatuValgusfooriEes ja auto hakkab pidurdama. Pärast peatumist muutub olekuks OotaRohelistTuld ning auto jälgib valgusfoori. Nimetatud olekust saab välja ainult siis, kui fooris süttib roheline tuli, mille peale seisund muutub jälle SõidaEdasi ning auto jätkab sõitu.

Joonis 29: Erinevad manöövrid OpenPlanner planeerimismoodulis. (Allikas)

Nagu võib arvata, siis kõikehaarava loetelu koostamine olekutest ja nende vahel liikumise reeglitest on küllaltki keeruline ülesanne. See on ka üks põhilisi nõrku kohti modulaarse lähenemise juures - reaalseid liiklussituatsioone on liiga palju, et neid oleks võimalik kirjeldada lihtsate kui-siis reeglite kaudu.

Trajektoori planeerija
Kui teekonna planeerija määrab, milliseid tänavaid peaks läbima sõitmaks punktist A punkti B ja manöövrite planeerija valib, milliseid manöövreid tuleks kasutada nende tänavate läbimiseks, siis trajektoori planeerija leiab ohutu trajektoori etteantud manöövri saavutamiseks. Selline trajektoor peab arvestama lisaks sõiduradadele ja takistustele ka teiste sõidukite tulevasi trajektoore, mis väljastatakse tajumooduli poolt.

Trajektoori planeerimisel on tihti aluseks takistuskaart (occupancy grid, costmap). See on lihtne ruudustik, mille iga ruudu väärtus on 1 või 0, sõltuvalt sellest, kas selles ruudus on takistus või mitte (vt joonis 30). Takistuskaart võib olla ka tõenäosuslik, kus number 0 ja 1 vahel näitab tõenäosust, et selles ruudus on takistus (meie tajud pole kindlad). Lisaks võib takistuskaart olla ka ajas muutuv, st meil on tegelikult mitu takistuskaarti, üks iga järgneva ajasammu jaoks.

Joonis 30: Takistuskaardi näide. Mustad ruudud on teadaolevad takistused (väärtus 1), valged ruudud on vaba ala (väärtus 0), hallid ruudud on teadmata (väärtus 0.5). (Allikas)

Kui takistuskaart on olemas, saab iga valitud trajektoori jaoks arvutada välja tema “hinna” - see on summa kõikide ruutude väärtustest, mida trajektoor läbib. Arvutades välja erinevate trajektooride hinnad on võimalik valida trajektoor, mis on väikseima hinnaga, st ei läbi takistusi. Loomulikult peavad need trajektoorid olema kooskõlas soovitud manöövriga ja auto liikumisvõimalustega, nt auto ei saa teha koha peal 90-kraadilist pööret.

Takistuskaardile saab lisada ka soovitava ideaaltrajektoori, nii et kõik kõrvalekaldumised sellest on pisut kõrgema väärtusega, aga siiski madalamad kui objektiga kokkupõrkamine. See võimaldab leida tasakaalu teekonna planeerija soovitud ideaaltrajektoori järgimise ja takistustest hoidumise vahel - takistus soovitud trajektooril suurendab selle hinda, samas kui takistusest möödapõikamisel suureneb hind ainult ideaaltrajektoorist kõrvalekaldumise võrra, mis on eeldatavasti väiksem (vt joonis 31).

Joonis 31: Potentsiaalsed auto trajektoorid. Vasakul: takistus asub kaugel vasakul, madalaima hinnaga trajektoor (lilla) langeb kokku ideaaltrajektooriga keskel. Keskel: takistus asub keskelt veidi vasakul, seega osutub madalaima hinnaga trajektooriks (lilla) äärmine parempoolne trajektoor. Paremal: takistus asub tee paremas ääres, madalaima hinnaga trajektoor (lilla) nihkub vasakule. (Allikas)

Levinud algoritm trajektoori planeerimiseks takistuskaardil on MPC (model predictive control). See kasutab matemaatilisi optimiseerimismeetodeid leidmaks minimaalse hinnaga trajektoori igal ajasammul.

Juhtimismoodul

Juhtimismooduli ülesandeks on leida etteantud trajektoori järgimiseks vajalikud roolimiskäsud. Lisaks rooli keeramisele on juhtimismooduli ülesandeks ka muuta auto kiirust, vajadusel seda kiirendades või aeglustades. Mõnes mõttes on juhtimismooduli töö lihtne - kogu keeruline planeerimistöö on varem juba ära tehtud, nüüd on tarvis ainult etteantud trajektoori ja kiirust jälgida. Seetõttu ongi kasutatavad meetodid mõnevõrra lihtsamad. Järgnevalt vaatleme kiiruse juhtimise ja roolimise kahte alamülesannet eraldi.

Kiirus
Teades auto hetkekiirust ning soovitud kiirust, on võimalik kasutada PID-regulaatorit (PID controller) kiiruse korrigeerimiseks. PID-regulaator arvutab soovitud ja hetkekiiruse vahe põhjal välja, palju tuleb rakendada gaasi või pidurit, et soovitud kiirust saavutada. PID-regulaatori käitumisest, kui sujuvalt auto kiirus muutub, määravad ära tema parameetrid. Nende häälestamine on küllaltki aeganõudev ning keeruline (vt joonis 32).

Joonis 32: PID-regulaatori käitumine erinevate parameetrite väärtuste puhul. Sinine on soovitud kiirus, punane on tegelik kiirus. Vertikaal- ja horisontaalteljel on PID-kontrolleri P ja I parameetrite väärtused. Nagu näha kipub auto kas ületama soovitud kiirust või saavutab selle liiga aeglaselt. (Allikas)

Roolimine
Ka auto trajektooril hoidmist on võimalik realiseerida PID-regulaatorina - auto kauguse põhjal lähimast trajektoori punktist arvutatakse välja rooli soovitav asend. Selline lahendus töötab, kuid reageerib viivitusega kurvidele.

Parem lahendus on nn puhta jälitamise (pure pursuit) algoritm. Selles algoritmis fikseeritakse etteantud trajektooril kindlal kaugusel olev nn ettevaatamise punkt (look ahead point) ning auto hoiab kogu aeg suunda selle punkti poole (vt joonis 33). Puhta jälitamise algoritm on sujuvam kui PID-regulaator, sest see oskab kurve ette näha ning “silub” need ära. Ettevaatamise punkti kaugust on võimalik muuta sõltuvalt kiirusest.

Joonis 33: Puhta jälitamise algoritmi tööpõhimõte. Trajektooril on määratud nn ettevaatamise punkt ning auto hoiab oma suunda pidevalt selle punkti poole.

Veelgi paindlikum lahendus on nn Stanley kontroller, mis püüab minimiseerida nii auto kaugust trajektoori lähimast punktist kui ka suunda võrreldes trajektooriga. Stanley kontroller on oma nime saanud 2005. aastal DARPA Grand Challenge võistluse võitnud auto järgi, kus seda esimest korda kasutati. Stanley kontroller töötab ühtmoodi hästi nii väikestel kui suurtel kiirustel.

Boonus materjal (vabatahtlik)

• Vaata videot PID regulaatori kasutamise kohta roolimiseks (4:40)

Näited

Waymo on oma tarkvara üles ehitanud modulaarse lähenemise baasil. See tagab töökindluse, mis võimaldab neil turvajuhist loobuda, senikaua kuni sõidetakse etteantud piirkonnas. Olulist rolli mängib Waymo tarkvaras vektorkaart, mis samas muudab selle lahenduse kasutuselevõtu uutes linnades kalliks ja töömahukaks.

Autoware on Jaapanis Nagoya ülikoolis välja arendatud modulaarne isejuhtivate sõidukite tarkvara. Autoware põhineb ROS-il (robotite operatsioonisüsteemil) ja sisaldab valmismooduleid takistuste tuvastamiseks, teekonna planeerimiseks jne. See on hetkel populaarseim vabavaraline platvorm isejuhtivate autode tarbeks.

Apollo on Hiina juhtiva otsimootori Baidu vabavaraline lahendus isejuhtivate autode jaoks. Baidu soov on, et Apollo oleks isejuhtivate autode analoog mobiiltelefonidel kasutatavale Android operatsioonisüsteemile - vaba ja kõigile tasuta ning seetõttu üldlevinud. Praktikas on Apollo pisut võimekam kui Autoware, aga riistvara suhtes palju nõudlikum.

NVIDIA DRIVE on tuntud graafikakaartide tootja poolt pakutav platvorm - komplekt riistvaralistest ja tarkvaralistest komponentidest isejuhtiva auto ehitamiseks. Eelkõige sisaldab see eeltreenitud närvivõrke takistuste, sõidetava ala jms tuvastamiseks. Paljud autotootjad on ehitanud oma lahendused sellele platvormile.

Boonus materjal (vabatahtlik)

• Vaata väga head ülevaadet Waymo funktsionaalsusest (7:44 min)

Kokkuvõte

Nagu eelnevalt nägime, siis modulaarne lähenemine jaotab isejuhtimise ülesande väiksemateks alamülesanneteks, mida on lihtsam kirjeldada ja testida. Samas on modulaarsel lähenemisel mitu puudust:

• Kuna see toetub eelnevalt kaardistatud vektorkaardile, siis ei ole auto võimeline sõitma suvalistel teedel, vaid ainult nendel, mille kohta on olemas täpne vektorkaart.
• Kuna käitumine erinevates liiklussituatsioonides on kirjeldatud kui-siis reeglitena, siis on väga keeruline, kui mitte võimatu, kirjeldada kõiki võimalikke olukordi liikluses.

Eelnevast lähtuvalt on modulaarse lähenemise piiriks 4. taseme autonoomsus.