Samu Hämäläinen
AUTONOMISEN AUTON LIIKKEEN SUUNNITTELU
Informaatioteknologian ja viestinnän tiedekunta Kandidaattitutkielma Kesäkuu 2021
Samu Hämäläinen: Autonomisen auton liikkeen suunnittelu Kandidaattitutkielma
Tampereen yliopisto
Tietojenkäsittelytieteiden tutkinto-ohjelma Kesäkuu 2021
Tässä tutkielmassa tehdään kirjallisuuskatsaus autonomisiin kulkuneuvoihin ja tarkemmin nimenomaan itseohjautuviin autoihin sekä siihen miten ne suunnittelevat tekemänsä liikkeen esteen kohdatessaan. Työn tavoitteena on koota yhteen aiemmin tehtyä tutkimusta ja tarkastella autonomisia autoja yleisellä tasolla, niiden kehityksen historiaa sekä missä tilanteessa niiden kehitys on nykyään. Myöskin tavoitteisiin kuuluu käydä tarkemmin läpi miten liikkeen suunnittelu reaaliajassa tapahtuu eli miten ajoneuvo väistää kohdatun esteen.
Autonomiset ajoneuvot jaetaan kategorioihin sen mukaan toimivatko ne maalla, vedessä vai ilmassa. Ne voidaan jakaa myös toiminnan mukaan eri tasoihin sen mukaan, kuinka paljon kuljettajalta vaaditaan päätöksiä. Näistä tämän tutkielman kohteena ovat täysin autonomiset maalla liikkuvat ajoneuvot. Tässä tutkielmassa tarkastellaan myös DARPA:n järjestämiä haasteita, joissa kilpailijat yrittivät suorittaa radan suunnittelemallaan itseohjautuvalla autolla ja kuinka olennaisia nämä olivat autonomisten autojen kehitykselle, vaikka ensimmäisestä haasteesta ei vielä selvinnytkään kukaan maaliin asti. Myöhemmissä haasteissa kilpailijat pärjäsivät paljon paremmin ja niissä hyödynnettyä lidar-teknologiaa käytetään edelleenkin.
Autonomiset autot havainnoivat ympäristöään valotutkan eli lidarin ja muiden tutkien avulla ja käyttävät navigointiin inertiajärjestelmää (INS) ja paikannusjärjestelmää (GPS). Näiden avulla ajoneuvo rakentaa itselleen sisäisen kartaston ympäristössä navigointia varten. Työssä esitellään lisäksi malleja, joita käytetään autonomisten autojen kanssa ja jotka jaetaan kolmeen eri tyyppiin sen mukaan, mitä tietoja niissä on esitettynä eli geometriseen, kinemaattiseen ja dynaamiseen.
Lopuksi perehdytään myöskin tarkemmin liikkeen suunnitteluun ja erityisesti algoritmiin, joka graafihaun avulla selvittää reitin, jota ajoneuvon tulee seurata väistääkseen kohdatun esteen tehden siitä ajoneuvolle sujuvan kulkea.
Avainsanat: autonominen auto, lidar, liikkeen suunnittelu
Tämän julkaisun alkuperäisyys on tarkastettu Turnitin OriginalityCheck –ohjelmalla.
Sisällysluettelo
1 Johdanto ... 1 2 Yleistä autonomisista kulkuneuvoista ... 2
3 Ympäristön havainnointi ... 3
3.1 LiDAR 3
3.2 Visuaalinen havainnointi 4
4 Auton navigointi ... 4
5 Mallit ... 5
5.1 Geometrinen malli 5
5.2 Kinemaattinen malli 6
5.3 Dynaaminen malli 6
6 Suunnittelu ... 6
6.1 Liikkeen suunnittelu algoritmi 6
7 Yhteenveto ja johtopäätökset ... 10 Lähdeluettelo ... 10
1 Johdanto
Autonomiset autot ovat joskus tuntuneet futuristiselta ajatukselta, mutta nyt ne ovat hyvin ajankohtainen aihe. Niiden kehitys jatkuu parhaillaan ja on vain ajan kysymys kun ne tulevat yleiseen käyttöön. Kehityksessä ovat mukana monet eri yhtiöt, joista tunnetuimpia ovat esimerkiksi: Google, Tesla, Uber ja Lyft (Badue ja muut, 2019). Seuraavaksi hieman tarkemmin Googlen ja Teslan autonomisten autojen kehityksestä ja miten niiden ratkaisut eroavat toisistaan. Googlen autonomisten autojen kehitys on alkanut jo vuonna 2009 ja sitä johti silloin Sebastian Thrun, joka voitti DARPA:n vuonna 2005 järjestämän haasteen Stanley tiimissä, mutta nykyään kehitystä jatkaa yksityinen yritys Waymo. (Badue ja muut, 2019). Googlen ratkaisu käyttää lidaria ympäristön havainnointiin ja tarkan kartaston luomiseen, tutkia havaitsemaan kaukaisemmat kohteet ja niiden nopeudet sekä tarkkalaatuista kameraa tunnistamaan esimerkiksi liikennevalon värin (Badue ja muut, 2019). Tesla on sen sijaan keskittynyt siihen että saa teknologian kuluttajien käyttöön mahdollisimman nopeasti ja niinpä ei käytä lidaria, joka on tällä hetkellä erittäin kallista.
Tesla Model S sisältää autopilottiohjelman, joka pystyy tällä hetkellä säätämään nopeutta olosuhteiden mukaan, ajamaan kaistaa pitkin ja vaihtamaan sitä, poistumaan moottoritieltä, parkkeeraamaan sekä ajamaan autotalliin ja poistumaan sieltä kutsuttaessa (Badue ja muut, 2019). Jopa Suomesta löytyy autonomisten autojen toimintaa, sillä kesäkuussa 2020 Helsingissä käytössä oli kolme autonomista julkista kulkuneuvoa, kuljettamassa matkustajia korttelin ympäri. Kyseisen tekniikan on kehittänyt suomalainen Sensible4 joka on keskittynyt autonomiseen ajamiseen, jopa Suomen talvisäässä.
Tässä tutkielmassa tehtiin kirjallisuuskatsaus autonomisten autojen toiminnallisuuteen, miten ne havaitsevat ympäristöään ja miten ne käyttäytyvät kohdatessaan jonkinlaisen esteen. Tavoitteena työssä on koota yhteen aiempaa tutkimusta, perehtyä autonomisiin autoihin yleisellä tasolla sekä tarkastella niiden historiaa ja nykytilaa. Tarkemmin pohditaan miten ajoneuvo väistää kohtaamansa esteen tiellä. Aluksi käsitellään autonomisia kulkuneuvoja yleisellä tasolla ja miten niitä voidaan jakaa autonomian eri tasoihin. Katsotaan läpi myöskin itseohjautuvien autojen kehitykseen liittyviä DARPA:n järjestämiä haasteita. Seuraavaksi tarkastellaan ympäristön havainnointikeinoja joista keskitytään erityisesti lidariin eli valotutkaan sekä visuaaliseen havainnointiin ja perehdytään siihen miten ajoneuvo hyödyntää INS ja GPS järjestelmiä ja muodostaa näiden avulla itselleen sisäisen kartaston ympäristössä navigointia varten. Tarkastellaan myös miten autonomisen ajoneuvon suunnittelun yhteydessä käytetään erilaisia malleja kuten geometristä, kinemaattista ja dynaamista mallia. Käsitellään myös tarkemmin yhtä liikkeen suunnittelussa käytettyä algoritmia,
jonka avulla ajoneuvo väistää reitillä olevan esteen. Tutkielman lopuksi pohditaan tuloksia ja vedetään johtopäätöksiä.
2 Yleistä autonomisista kulkuneuvoista
Autonominen kulkuneuvo on älykäs kulkuneuvo, joka on kokonaan tietokoneen ohjaama ja pystyy ympäristöään havaitsemalla tekemään päätöksiä. Autonomisia kulkuneuvoja on eri ympäristöissä ja ne voidaan Amer ja muut (2016) mukaan jakaa kolmeen kategoriaan:
maan pinnan yläpuolella lentäviin miehittämättömiin ilma-aluksiin (UAV), veden pinnan alapuolella toimiviin miehittämättömiin vedenalaisiin-aluksiin (UUV) ja maan pinnalla toimiviin autonomisiin kulkuneuvoihin (AGV), joihin kuuluvat tämän tutkielman kohteena olevat autonomiset autot. Ajoneuvolla voi olla eriasteisia autonomian tasoja, kuten taulukosta 1 nähdään. Tässä tutkielmassa tarkastellaan täysin autonomisia autoja eli tasolle 5 sijoittuvia, joilla on täysi autonomia ja pystyvät toimimaan ilman kuljettajan avustusta.
Taulukko 1. Autonomian tasot (SAE-J3016 2014)
Tärkeänä osana autonomisten autojen kehitystä voidaan pitää DARPA:n järjestämiä haasteita, jotka nopeuttivat teknologian kehitystä. Ensimmäinen haaste järjestettiin vuonna 2004, jossa tarkoituksena oli navigoida 142 mailin rata Mojaven autiomaan läpi kymmenessä tunnissa, mutta kaikki ajoneuvot epäonnistuivat jo ensimmäisten mailien aikana (Thrun, 2010). Vaikka kukaan ei päässytkään maaliin asti, tämä haaste nopeutti autonomisten autojen kehitystä, sillä jo seuraavana vuonna 2005 haaste järjestettiin uudelleen. Tästä haasteesta neljä osallistujaa selvisi maaliin asti, joista voittajana oli Stanfordin Stanley (Thrun, 2010). Jo näiden haasteiden aikaan autonomisissa autoissa oli Taso 0 Ajoneuvon hallinta on kokonaan ihmisen vastuulla. Automaattinen
järjestelmä voi kuitenkin antaa varoituksia.
Taso 1 Joitakin automaattisia avusteita on saatavilla, kuten mukautuva vakionopeudensäädin, kaistantunnistaja ja pysäköintiavustaja.
Taso 2 Automaattinen järjestelmä voi kiihdyttää, jarruttaa ja ohjata, mutta kuljettaja voi ottaa hallinnan itselleen takaisin.
Taso 3 Automaattinen järjestelmä voi ajaa rajatuilla ja tunnetuilla alueilla, kuten moottoriteillä.
Taso 4 Automaattinen järjestelmä voi hallita ajoneuvoa melkein kaikissa olosuhteissa, paitsi erittäin huonolla säällä.
Taso 5 Automaattisella järjestelmällä on täysi autonomia, eikä kuljettajan tarvitse tehdä mitään. Autonominen kulkuneuvo voi ajaa mihin tahansa missä sen on laillista olla.
samankaltaista teknologiaa. Stanley hyödynsi viittä eteenpäin suunnaattua etäisyyden mittaavaa laseria auttamaan navigoinnissa (Thrun, 2010). Tämä on samankaltainen Lidarin kanssa, jossa laserilla mitataan etäisyyttä. Stanleyn tapauksessa riitti mitata etäisyyttä vain eteenpäin, sillä haaste toteutettiin avoimella alueella. Vuonna 2007 DARPA järjesti urbaanihaasteen, jossa autonomisten autojen oli tarkoituksena navigoida tekokaupungissa. Kun autot kohtasivat niiden piti noudattaa liikennesääntöjä. Tästä haasteesta voittajaksi selvisi Carnegie Mellon yliopiston Boss ja toiseksi päätyi Stanfordin Junior. Junior käytti havainnointiin myös viittä laseria, mutta tärkein niistä oli pyörivä sensori, joka skannasi ympäristöä. Stanley ja Junior käyttivät molemmat GPS- ja INS-teknologiaa. (Thrun, 2010). Nämä haasteet nopeuttivat autonomisten autojen kehitystä ja innovoivat keksimään uusia ratkaisuja, jotka näkyvät vielä nykyajankin teknologiassa.
Itseohjautuvien auton teknologia voidaan jakaa neljään eri toiminnalliseen tyyppiin:
ympäristön havainnointi, auton navigointi, liikkeen suunnittelu ja auton hallinta (Zhao ja muut, 2018). Näistä ajoneuvon hallinta on rajattu tästä tutkielmasta pois, sillä se on liian mekaanista toimintaa ajatellen tätä tutkielmaa.
3 Ympäristön havainnointi
Ajoneuvo havainnoi ympäristöään tutkien ja sensoreiden avulla ja rakentaa näistä itselleen sisäisen kartaston, jota voi hyödyntää navigoimiseen. Näistä suuressa käytössä olevat tekniikat ovat lidar ja visuaalinen havainnointi.
3.1 LiDAR
Lidar eli laser mittaus on ollut olemassa jo 1960-luvulta asti jolloin MIT:n Lincoln laboratorio mittasi etäisyyden kuuhun ampumalla 50 joulen pulsseja laserilla (Hecht, 2018). Lidar eli valotutka toimii periaatteeltaan samaan tapaan kuin tavallinen tutka, jossa lähetin lähettää radioaaltoja ja vastaanotin mittaa heijastuksesta aiheutuvan kaiun.
Behroozpourin ja muiden (2017) mukaan lidar mittauksessa moduloidaan haluttua tehoa, vaihetta ja taajuutta lähetetylle valolle ja mitataan aika kunnes se on heijastunut vastaanottimeen. Autonomisten autojen tapauksessa käytetään lidaria, joka lähettää eri suuntiin samanaikaisesti laserin, pyörii alustan päällä tai niiden yhdistelmällä. Näiden palauttamista heijastuksista mitataan etäisyydet ja rakennetaan 3D näkymä, jota ajoneuvo käyttää navigoinnissa. (Behroozpour ja muut, 2017)
DARPA haasteessa vuonna 2005 Velodynen perustaja David Hall rakensi pyörivän lidarin ajoneuvonsa päälle, muttei päässyt maaliin. Hän paransi myöhemmin luomustaan lisäämällä yhteensä 64 laseria ja sensoreita jotka havaitsivat ympäristöä. Vuoden 2007
haasteessa viidessä kuudesta maaliin päässeistä oli katolla Velodynen lidar ajoneuvon päällä (Hecht, 2018).
Behroozpourin ja muiden (2017) mukaan yleisimmin käytetyt lidarin aallonpituudet ovat 905, 1300 ja 1550 nm, jotka ovat lähellä televiestinnässä käytettyjä aallonpituuksia.
Näistä 905 nm aallonpituus oli pitkän aikaa paras ratkaisu autonomisille autoille, sillä ne olivat halvempia valmistaa ja niitä pystyttiin hyödyntämään silikoni-ilmaisimien kanssa (Hecht, 2018). Tämä aallonpituus on kuitenkin ihmissilmälle vaarallinen, joten pulssien tehoa täytyy laskea, mikä vähentää mahdollista maksimikantamaa (Hecht, 2018). Muissa käyttökohteissa tämä ei ole ollut ongelma, sillä Hechtin mukaan (2018) paikallaan oleva lidar voi lähettää monta pulssia kerrallaan ja hyödyntää pulssien keskiarvoa pidentämään mahdollista mitattavaa etäisyyttä. Tästä ei kuitenkaan ole hyötyä autonomisten autojen kanssa, sillä liikkuvan lidarin pulssien keskiarvoa ei voida Hechtin (2018) mukaan hyödyntää, sillä ne voivat lähettää samassa kohdassa vain yhden pulssin kerrallaan.
Tähän 905 nm aallonpituuden aiheuttamaan ongelmaan on keksitty erilaisia ratkaisuja. Google päätti rajoittaa autonomisten autojen ajotestien nopeutta 25 mph eli n.
40 km/h, jotta ajoneuvo ehtisi havaita esteet tarpeeksi ajoissa lyhyelläkin kantamalla (Hecht 2018). Sen sijaan Luminarin ratkaisuna oli vaihtaa 1550 nm laseriin, sillä se ei ole ihmissilmälle vaarallinen. Tämä mahdollistaa suurempien pulssitehojen käyttämisen, jolloin moottoritienopeuksia kulkeva ajoneuvo pystyy havaitsemaan esteet tarpeeksi ajoissa ehtiäkseen reagoida. (Hecht 2018)
3.2 Visuaalinen havainnointi
Visuaalisesssa havainnoinnissa käytetään jonkinlaista kameraa ja tekoälyä kuvantunnistuksen yhteydessä tunnistamaan esimerkiksi liikennemerkit, liikennevalot ja muutkin liikenteessä olevat merkit, jotka on suunniteltu ihmisiä varten. Tämä on myöskin se mihin Teslan ratkaisu pääosin perustuu. Zhaon ja muiden (2018) mukaan visuaalisessa havainnoinnissa on olemassa kaksi pääkehityssuuntaa. Ensimmäinen on kartan pohjalta tehtävä yhtäaikainen lokalisointi ja kartoitus, englanniksi Simultaneous Localization And Mapping (SLAM). Toisena on konenäön sekä koneoppimisen kanssa kuvien analysointi, joiden avulla ajoneuvo rakentaa 3D näkymän navigointia varten ja tunnistaa erilaiset liikenteessä olevat merkit ja ohjeet.
4 Auton navigointi
Zhaon ja muiden (2018) mukaan suhteellinen sijanti määritellään kun tämän hetkiseen sijaintiin lisätään liikuttava määrä ja suunta. Yksi yleisimmistä tavoista on inertianavigointijärjestelmä (INS), jossa gyroskoopin ja kiihtyvyysmittarin avulla mitataan ajoneuvon kiihtyvyys sekä kulmanopeus, joka kertoo kuinka nopeasti auto
kääntyy. Näistä luvuista saadaan integroimalla ajoneuvon kulma ja nopeus ja kun nämä edelleen integroidaan saadaan selville ajoneuvon suunta ja kuljettu matka. Näiden sijaintitietojen avulla saadaan laskettua ajoneuvon sijainti, kuitenkin vain suhteellinen, sillä ajoneuvon värinä aiheuttaa virhearvioita (Zhao ja muut, 2018).
Zhaon ja muiden (2018) mukaan ajoneuvon absoluuttinen sijainti määritellään käyttämällä paikannusjärjestelmän antamaa tietoa. Näistä yleisimpiä ovat satelliittipaikannusjärjestelmät, kuten esim. GPS, GLONASS ja Galileo. Tämäkään ei kuitenkaan ole virheetön tapa, sillä satelliittisignaali on altis sääolosuhteille ja rakennukset sekä vuoret voivat aiheuttaa virheitä mitatussa sijainnissa (Zhao ja muut, 2018).
Hybridisessä sijainnissa yhdistetään näiden kahden edellisen sijantitavan piirteitä ja näin ollen se onkin käytetyin menetelmä, kun halutaan selvittää itseohjautuvan auton sijainti (Zhao ja muut, 2018).
5 Mallit
Malleissa käytetään yleisesti polkupyöräkonseptia, jossa ajoneuvon takarenkaat ja eturenkaat yhdistetään keskenään, jolloin oikea ja vasen rengas ovat yhdistyneet (Amer ja muut, 2016). Näin tehdään, sillä reaalimaailmassa auton renkaat käätyvät akselinsa varassa aina samaan suuntaan, jolloin mallia voidaan yksinkertaistaa ja resurrseja säästää.
Amerin ja muiden (2016) mukaan mallit voidaan jakaa kolmeen eri tyyppiin.
Geometrisessä mallissa keskitytään geometrisiin ulottuvuuksiin ja kinemaattiset sekä dynaamiset ominaisuudet jätetään huomioimatta. Samankaltaisesti kinemaattisessa mallissa keskitytään kiihtyvyyteen ja nopeuteen. Dynaamisessa mallissa sen sijaan tarkkaillaan ajoneuvon sisäisiä voimia, inertiaa ja energian ominaisuuksia. Eri tyyppisiä malleja käsitellään seuraavissa osioissa hieman tarkemmin.
5.1 Geometrinen malli
Geometrisessä mallisssa keskitytään ajoneuvon ulottuvuuksiin sekä sijaintiin kääntymistilanteessa ja jätetään huomiotta nopeus ja kiihtyvyys. Amerin ja muiden (2016) mukaan tämä on kehitetty Ackermannin ohjausjärjestelmän perusteella, jossa kohtisuorassa ajoneuvon renkaaseen olevan suoran pitäisi leikata kääntymiskulman keskipisteessä. Geometrinen malli on tärkeä, sillä sen avulla on kehitetty yksi suosituimmista reitinhakuohjaimista, Pure Pursuit. Toinen esimerkki geometrisesta mallista suhteuttaa ajoneuvon sijainnin suunnan ja sen virheen mukaan. Tällä mallilla arvioidaan ajoneuvon todellisen sijainnin ja halutun suunnan virhe, joka on Stanley ohjaimen perustana. (Amer ja muut, 2016)
5.2 Kinemaattinen malli
Kinemaattinen malli eroaa geometrisestä mallista, sillä siinä otetaan huomioon myös ajoneuvon nopeus sekä kiihtyvyys, mutta ei kuitenkaan huomioida sisäisiä voimia, eli inertiaa ja energiaa (Amer ja muut, 2016). Joten kinemaattisessa mallissa otetaan huomioon ajoneuvon sijainti, ulottuvuudet, nopeus sekä kiihtyvyys. Kinemaattinen malli on yleinen sen yksinkertaisuuden vuoksi.
5.3 Dynaaminen malli
Edellä mainituista malleista eroten dynaamisessa mallissa otetaan huomioon sisäiset voimat, eli energia ja liikemäärä (Amer ja muut, 2016). Käytännössä tämä tarkoittaa sitä että mallinnuksessa otetaan huomioon renkaisiin kohdistuvat voimat sekä ajoneuvon massa ja siihen liittyvät voimat.
6 Suunnittelu
Ajoneuvo havaitsee ympäristöään sensoreilla ja käyttää digitaalisen kartan tietoja hyväkseen luodakseen digitaalisen esityksen tieverkostosta ja käyttää tätä hyväkseen reitinsuunnittelussa (Katrakazas ja muut, 2015). Katrakazasin ja muiden (2015) mukaan reitinsuunnittelu voidaan jakaa kolmeen vaiheeseen. Ensimmäisessä etsitään paras mahdollinen geometrinen reitti ajoneuvolle, jolla väistetään esteet ja pysytään reitillä ilman optimointia. Toisessa vaiheessa etsitään paras mahdollinen suoritettava liike kohdattaessa este. Kolmannessa vaiheessa geometrinen kaari optimoidaan.
6.1 Liikkeen suunnittelu algoritmi
Liikkeen suunnittelu alkaa algoritmin 1 Graafihaku avulla, joka esittää miten ajoneuvo luo sensoreista saamiensa tietojen avulla sisäisen kartaston. Algoritmissa G on graafi johon lisätään vektoreita u joilla on koordinaatit muodossa (x, y) sekä suunta. Aluksi ajoneuvon alkutila qalku ja ajoneuvon määränpää qloppu asetetaan vastaavasti vektoreihin ualku ja uloppu. Vektori q kertoo ajoneuvon tilan eli sijainnin sekä suunnan. Tämän jälkeen alkuvektori ualku lisätään listaan Q, joka on järjestetty hyötyfunktion f avulla, ja aloitetaan varsinainen iteraatio. Jokaisella kierroksella listasta Q otetaan seuraava vektori u ja sitä käytetään luomaan uusi toimeenpide funktiolla LuoToimenpide.
Graafihaku(G, qalku, qloppu) ualku ← (qalku, G) uloppu ← (qloppu, G) Q ← {ualku}
while Q ≠ ∅ do u ← minu∈Q f(u) Q ← Q \ {u}
if |u-uloppu|2 ≤ Bg then
return UudelleenrakennaReitti (G, u)
endif
M ← LuoToimenpide (G, u) LisääToimenpide (G, u, M) end while
Algoritmi 1. Graafihaku (Chu ja muut, 2015)
Algoritmissa 2 käydään läpi kaikki K:n alkiot κi, jotka ovat kaikki mahdolliset kaarevuudet suhteessa ajoneuvon tilaan. Tämä uusi qi muodostetaan ajoneuvon tilan ja kaarevuuden avulla ja lisätään toimenpidejoukkoon M.
LuoToimenpide(G, u) M = θ
foreach κi ∈ Κ q ← (G, u) qi = q + Δqi
M = M ∪ {qi} end
return M
Algoritmi 2. LuoToimenpide (Chu ja muut, 2015)
Tämän toimenpidejoukon avulla kutsutaan algoritmin 3 LisääToimenpide-funktiota, joka katsoo onko siinä kohdassa estettä, johon toimenpide q ohjaisi ajoneuvon. Jos näin on tämä tila karsitaan ja otetaan huomioon viereisten tilojen kanssa. Jos kyseessä on esteetön tila graafiin merkitään reunat e ja tila uuusi lisätään listaan Q. Näin ollen saadaan graafihaun avulla löydettyä esteetön primitiivinen reitti ajoneuvolle.
LisääToimenpide(G, u, M) foreach q ∈ M do
if EsteVapaa(q) then
uuusi ← (q, G)
e ← (u, uuusi, G) Q ← Q ∪ {uuusi} PäivitäHinta(e, uuusi, G)
else if
PäivitäHintaEste(u, G)
end if
end
Algoritmi 3. LisääToimenpide (Chu ja muut, 2015)
Saatu liike pitää kuitenkin vielä sulavoida, jotta ajoneuvo pystyy sitä pitkin kulkemaan ja sitä varten kutsutaankin algoritmin 4 LiikkeenSulavointi-funktiota. Funktion tehtävänä on ottaa alkeellinen liike esteen väistämiseksi ja sulavoida sitä Chun ja muiden (2015) esittämien kaavojen avulla, jotta se on ajoneuvolle luonnollisempi kulkea. Funktio saa aluksi syötteekseen sekvenssin liikealkeellinen, joka koostuu tiloista q0, q1, ..., qn ja alkaa iteroimaan sitä kauimmaisesta tilasta eli N alkaen. Jokaisella kierroksella luodaan kaavojen mukainen kolmannen asteen käyrä alkutilasta q0 valittuun tilaan qi asti.Jos tällä käyrällä ei ole kolareita ja se on muutenkin mahdollinen. niin sekvenssistä liikealkeellinen
otetaan häntä irti alkaen qi aina lopputilaan qn asti. Lopuksi nämä yhdistetään ja näin saadaan sulavoitu liike.
LiikkeenSulavointi(liikealkeellinen) liikesulavoitu ← ∅
for i ← N to 0 do
liikePH ← PH_Kolmannen (q0, qi, Δs)
if KolariVapaa(liikePH) and Mahdollinen(liikePH) then liikehäntä = {qi, …, qn}
return liikesulavoitu ← liikePH ∪ liikehäntä
endif
end for
if liikesulavoitu = ∅ then return liikealkeellinen
endif
Algoritmi 4. LiikkeenSulavointi (Chu ja muut, 2015)
Lopuksi tarkastellaan algoritmin 5 LiikkeenSuunnittelu-funktiota, joka esittää koko liikkeen suunnitteluprosessin reaaliajassa ja mitä siinä tarvitsee ottaa erikseen huomioon.
Aluksi aikaisempaa liikettä liikeaikaisempi käytetään pohjana, jotta vähennetään vaadittua laskentatehoa ja yhdistetään se nykyiseen tilaan ja luodaan sen avulla uusi graafi. Tämän liikeyhdistetty tiloja käytetään luomaan vektorit uuusi ja rajat euusi, nämä lisätään listaan Q ja lasketaan hinnat samoin kuten algoritmissa 3 tehtiin. Sen jälkeen graafia laajennetaan samalla prosessilla mitä algoritmissa 1 käytettiin, mutta tällä kertaa hyödynnetään edellistä tulosta. Tämän jälkeen algoritmia 4 käytetään sulavoimaan saatu liike ja tämä sulavoitu liike otetaan talteen muuttujaan liikeaikaisempi, jotta sitä voidaan hyödyntää seuraavalla kerralla.
LiikkeenSuunnittelu(qalku, qloppu)
liikeyhdistetty ← PäivitäAikaisempiLiike(liikeaikaisempi, qalku) ualku ← (qalku, G), uloppu ← (qloppu, G)
foreach q ∈ liikeyhdistetty do
uuusi ← (q, G), euusi ← (u, uuusi, G) Q ← Q ∪ {uuusi}
PäivitäHinta(e, uuusi, G), u ← uuusi
end
while Q ≠ ∅ do
u ← pieninu∈Ο ƒ(u) Q ← Q \ {u}
if ||u-uloppu||2 ≤ Bg then
return liikealkeellinen ← UudelleenrakennaLiike(G, u)
endif
M ← LuoToimenpide(G, u) LisääToimenpide(G, u, M)
end while
liikesulavoitu ← LiikkeenSulavointi(liikealkeellinen) liikeaikaisempi ← liikesulavoitu
return liikesulavoitu
Algoritmi 5. LiikkeenSuunnittelu (Chu ja muut, 2015)
7 Yhteenveto ja johtopäätökset
Tässä tutkielmassa tehtiin kirjallisuuskatsaus autonomisiin autoihin ja tarkasteltiin miten ne käyttäytyvät esteen kohdatessaan. Niin kuin edellä kerrottiin, autonomiset autot havaitsevat ympäristöänsä lidarin avulla heijastuttamalla sen ympärillä olevista objekteista ja käyttävät sitä yhdessä visuaalisen havainnon kanssa saadakseen tarkemman tuloksen ja tunnistaakseen ihmisille suunniteltuja merkkejä liikenteessä. Näiden lisäksi ajoneuvo hyödyntää inertiajärjestelmää (INS) ja paikannusjärjestelmää (GPS) muodostaakseen sisäisen kartaston navigointia varten. Tämän sisäisen kartaston avulla auto voi väistää vastaan tulevat esteet, niin kuin algoritmin toiminnasta pystyimme päättelemään. Esitelty algoritmi toimii graafihaun avulla hakemalla kaikki mahdolliset liikkeet mitä on mahdollista tehdä ja laskee niille hinnan sen mukaan osuvatko ne esteeseen tai ovatko liian lähellä estettä. Sen jälkeen algoritmi sulavoi saadun reitin ajoneuvolle sopivaksi kulkea.
Autonomiset autot alkavat olla kehityksessään siinä vaiheessa, että ne voisivat siirtyä kuluttajien käyttöön. Isona ongelmana on kuitenkin teknologian kalleus nimenomaan lidarin kohdalla, joka on suurimmassa osassa sensorijärjestelmiä olennainen osa. Tesla on yksi harvoista, jotka yrittävät ratkaista ongelman ilman lidaria ja sen sijaan hyödyntävät pelkkää visuaalista havainnointia ympäristön navigoimiseen. Kehitys on vielä heidänkin osalta kesken, mutta loogisesti ajateltunakin visuaalisen havainnoinnin yhdistäminen lidariin olisi tehokkain ja tarkin ratkaisu itseohjautuvissa autoissa, mutta futuristinen tulevaisuus ei voi olla vielä mahdollinen ennen kuin teknologia kehittyy niin paljon, että lidarilla varustettujen sensorijärjestelmien kustannukset muuttuvat kuluttajaystävällisemmiksi ja näin siirtyvät jokapäiväiseen käyttöön. Mahdollisuutena on myöskin että Tesla tai joku muu saa kehitettyä ratkaisun ilman lidaria ja näin saa kustannukset pidettyä pienempinä.
Lähdeluettelo
Amer, N. H., Zamzuri, H., Hudha, K. & Kadir, Z. A. (2017). Modelling and control strategies in path tracking control for autonomous ground vehicles: a review of state of the art and challenges. J. Intell. Robot. Syst. 86(2), 225–254.
https://doi.org/10.1007/s10846-016-0442-0
Behroozpour, B., Sandborn, P. A. M., Wu, M. C. & Boser, B. E. (2017). Lidar system architectures and circuits. IEEE Communications Magazine. 55(10) 135–142.
https://doi.org/10.1109/MCOM.2017.1700030
Chu, K., Kim, J., Jo, K. & Sunwoo, M. (2015). Real-time path planning of autonomous vehicles for unstructured road navigation. Int. J. Automot. Technol. 16(4), 653–
668. https://doi.org/10.1007/s12239-015-0067-5
Hecht, J. (2018). Lidar for Self-Driving Cars. Optics & Photonics News. 29(1), 26–33.
Katrakazas, C., Quddus, M., Chen, W. & Deka, L. (2015). Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research di- rections. Transportation Research Part C: Emerging Technologies. 60, 416–442.
https://doi.org/10.1016/j.trc.2015.09.011
SAE-International. (2014). Standards. Taxonomy and definitions for terms related to on-road motor vehicle automated driving systems J3016_201401.
https://www.sae.org/standards/content/j3016_201401/
Thrun, S. (2010). Toward robotic cars. Commun. ACM. 53(4), 99–106.
https://doi.org/10.1145/1721654.1721679
Zhao, J., Liang, B. & Chen, Q. (2018). The key technology toward the self-driving car.
International Journal of Intelligent Unmanned Systems. 6(1), 2–20.
https://doi.org/10.1108/IJIUS-08-2017-0008
