Kelio planavimo algoritmai PDF

Kelio planavimo algoritmai Kam reikalingi kelio planavimo algoritmai? Pramonės robotai: nustatyti optimaliausią kelią tarp taškų ir atlikti užduotis kuo efektyviau. Autonominiai transporto priemonės: saugiai judėti tarp taškų be žmogaus įsikišimo. Namų robotai: siurblių robotai, robotai...

Kelio planavimo algoritmai Kam reikalingi kelio planavimo algoritmai? Pramonės robotai: nustatyti optimaliausią kelią tarp taškų ir atlikti užduotis kuo efektyviau. Autonominiai transporto priemonės: saugiai judėti tarp taškų be žmogaus įsikišimo. Namų robotai: siurblių robotai, robotai langų valytojai ir kt. – efektyvus teritorijos apėjimas (‘ploto padengimas’) Moksliniai tyrimai: robotai, kurie tyrinėja sudėtingas aplinkas 2 Kelio planavimo problema  Užduotis: Laisva erdvė važiuoti nuo pradžios taško iki pabaigos taško, vengiant Pradžia kliūtis kliūčių kliūtis kelias Prielaidos: Pasaulis yra 2D plokštuma Robotas yra sumodeliuotas kaip taškas plokštumoje Robotas žino savo poziciją Kelio pradžia ir pabaiga žinomi Kliūčių padėtis yra nežinoma Kliūtims aptikti naudojami paprasti susidūrimo jutikliai Robotas gali sukti ir važiuoti bet kuria kryptimi 3 Kelio planavimo strategija  Dalinės problemos Aptikta kliūtis Kliūties vengimas Važiuoti Apvažiuoti Sienos sekimas tikslo link kliūtį Sprendimas yra garantuotas, jei kelias egzistuoja Kliūties vengimas  Kliūčių tipai Įgaubtas daugiakampis Išgaubtas daugiakampis  Akligatvio („Cul-de-sac“) problema Neišgaubta Kliūtys gali būti sudėtingos kliūtis formos Tikslas Tikslas yra už kliūties Problema: manevravimas Pradžia aplink neišgaubtą kliūtį Sujungia kliūčių išvengimą su sekimu sienoje  Kelio planavimo algoritmai Kelio paieška tinklelyje Sukurkite kelių tinklą ir naudokite grafiko paieškos algoritmą, kad rastumėte sprendimo kelią „Bug“ algoritmai Norėdami pasiekti tikslą, naudokite vietinę informaciją apie kliūčių formą Teritorijos padengimo algoritmai Naudojamas teritorijos aprėpties problemoms spręsti  Kelio paieška tinklelyje Galima naudoti tik tada, kai yra visiškai žinomos visų kliūčių vietos Aplinka modeliuojama kaip tinklelis sudarytas iš mazgų ir kraštinių Pašalinkite iš tinklelio visas viršūnes, esančias kliūtyse Pašalinkite kraštines, kertančias kliūtis Likęs grafas parodys kelią nuo pradžios iki tikslo. Nepraktiška realioje aplinkoje  Matomumo grafo metodas a b c (a) Nubrėžkite nesusiduriančias briaunas nuo kiekvienos viršūnės iki kiekvienos kitos viršūnės (b) Gaunamas matomumo grafas (c) Norėdami rasti trumpiausią kelią, naudokite trumpiausio kelio paieškos grafe algoritmą Netinka realaus pasaulio mobiliajai robotikai: kampą aptikti sunku! „Bug“ tipo kelio planavimo algoritmai „Bug“ tipo algoritmai Bug-0, Bug-1, Bug-2 Alg1, Alg2 DistBug, TangentBug … Tinka vidaus navigacijai mažose, ribotų išteklių turinčiose robotinėse sistemose  „Bug“ algoritmų principai Robotas turi turėti: Kontaktinį jutiklį arba nuotolio jutiklį, skirtą nustatyti, kada robotas liečia kliūtį arba artėja prie jos Būdą nustatyti dabartinę roboto vietą ir tikslo vietą Mažas atminties kiekis Paprastų elgsenų derinys: Sekti sieną Judėti tiesia linija tikslo link Bug-0 Algoritmas Pabaiga 1 2 Kartoti: 3 1. Eiti link tikslo 1 2. Jei pasiektas tikslas, sustoti 3. Jei yra kliūtis – sekti kliūties 3 kraštu į kairę tol, kol vėl 1 galima eiti link tikslo Pradžia  Bug-0 algoritmas: pavyzdys turn left when hitting an obstacle Go toward the goal and go around obstacle continue towards the goal when possible  Bug-0 algoritmas https://www.youtube.com/watch?v=C6GmD4qS3b s Bug-0 su kairiojo ir dešiniojo posūkio taisykle Bug-0 Pabaiga Ne! Pabaiga trūkumas: negali garantuoti Pradžia pabaigos pasiekimo Pradžia  Bug-1 Algoritmas Roboto nuvažiuojamas kelias: L2 Pabaiga Kartoti: Eiti link tikslo Jei pasiektas tikslas, sustoti Jei kliūtis – eiti aplink kliūtį ir ieškoti taško L , L1 i artimiausio tikslui Grįžti trumpiausiu keliu prie L i Pradžia Bug-1 algoritmas: būsenos diagrama Bug-1 algoritmas https://www.youtube.com/watch?v=IPZM8wWoS8U Educational videos: Bug algorithms Bug1: https://youtu.be/iJWULA_gIy8  Bug-1 trūkumas: begalinis ciklas 21 Bug-1 trūkumas: negali nustatyti, kad tikslas nepasiekiamas Pabaiga Algoritmo patobulinimas: L1 Kartoti: Eiti link tikslo Jei pasiektas tikslas, sustoti Jei kliūtis – eiti aplink kliūtį ir ieškoti taško Li , artimiausio Pradžia tikslui Grįžti trumpiausiu keliu prie Li Jei vektorius nuo Li link pabaigos rodo į kliūtį, tuomet tikslo pasiekti negalima, sustoti Bug-2: Bug-1 patobulinimas Tarkime, kad robotas „žino“ tiesiausią kelią iki tikslo, jei nebūtų kliūčių  Bug-2 Algoritmas Pabaiga nuvažiavimo taškas susidūrimo taškas Tikslo linija Pradžia Roboto nuvažiuojamas kelias: Kartoti: 1. Eiti link tikslo išilgai tikslo linijos 2. Jei tikslas pasiektas, sustoti 3. Jei pasiektas susidūrimo taškas, sukti į kairę ir sekti kliūties siena tol, kol pasiekiama tikslo linija ties nuvažiavimo tašku arčiau tikslo nei ankstesni susidūrimo taškai  Bug-2 algorithm: example Go around obstacle until it meets the line Follow the line from the start to the goal again at a closer point to the goal Continue to follow the line to the goal Bug-2 algoritmas: būsenos diagrama Educational videos: Bug algorithms Bug2: https://youtu.be/Z5-TBsKPCF0  “Aklavietės” aplinka Bug 1 nepasiekia tikslo Bug 2 pasiekia tikslą Bug-0, Bug-1 ir Bug-2 palyginimas https://www.youtube.com/watch?v=QCcq92Wn9Vc 29 Bug-2‘ algoritmas Pradžia Kartoti: 1. Eiti link tikslo išilgai tikslo linijos 2. Jei tikslas pasiektas, sustoti Pabaiga 3. Jei pasiektas susidūrimo taškas, sukti į kairę ir sekti kliūties siena tol, kol pasiekiama tikslo linija ties nuvažiavimo tašku, kuris nebuvo aplankytas anksčiau Alg1: Būsenos diagrama Alg1: Pseudokodas Alg2: Būsenos diagrama Alg2: Pseudokodas Alg1 ir Alg2 algoritmų palyginimas DistBug algoritmas  Kai robotas susiduria su kliūtimi, jis pradeda sekti kliūties kraštą, skaičiuodamas ir išsaugodamas atstumą nuo dabartinės padėties iki tikslo. Robotas saugo mažiausią atstumą nuo paskutinio susidūrimo taško. DistBug algoritmo būsenų diagrama 37  DistBug algoritmas https://www.youtube.com/watch?v=tzP2eu z-MT4 „Bug“ algoritmai + Atstumo jutikliai  Tarkime, kad robotas turi informaciją apie jo aplinką ir atstumą iki klIūties r Pvz., IR, ultragarso jutikliai Robotas gali suplanuoti savo kelią pagal gautą informaciją Rezultatas: trumpesnis roboto kelias Algoritmai su atstumo jutikliais TangentBug algoritmas Bug-2 patobulinimas Nustato trumpesnį kelią į kelionės tikslą naudojant atstumo jutiklį su 360º regėjimo lauku Tegul T yra tikslas, R yra robotas Tegul P yra roboto pasiekiamas (matomas) taškas Tegul d_sek (T) = minimalus atstumas nuo T iki kliūties --- -> važiavimas link tikslo Nuvažiuoti nuo kliūties krašto, -.- -> kliūties apvažiavimas kai d (P, T) < d_sek (T) 42 TangentBug TangentBug Privalumai: Gali būti efektyvesnis už kitus "Bug" algoritmus tam tikrose aplinkose, nes jis naudoja tangentinę informaciją apie kliūtis, kad rastų trumpesnį kelią. Gali būti naudingas tam tikrose aplinkose, kur reikia efektyvaus kelio planavimo be išankstinės informacijos apie kliūtis. Trūkumai: Reikalauja daugiau skaičiavimo resursų nei paprastesni "Bug" algoritmai, nes turi nustatyti ir vertinti tangentinės linijos taškus. Gali būti neefektyvus sudėtingose aplinkose su daug kliūčių. 44 Virtualios kliūtys 45 Bug algoritmų privalumai ir trūkumai  Privalumas: Paprastumas Trūkumai: Supaprastintas pasaulio modelis 46  Bug algoritmų santrauka „Tikslo linijos“ algoritmai (Bug2) žino tiesią liniją (ir kryptį) tarp pradinės padėties ir tikslo „Įvykių taškų įsiminimo“ algoritmai (Alg1 ir Alg2) gali patikrinti ar neatsidūrė jau anksčiau aplankytoje vietoje „Kampo“ algoritmai (DistBug) turi žinoti atstumą ir krypties kampą nuo savo padėties taško iki taikinio. „Atstumo jutiklio“ algoritmai (TangentBug) turi turėti atstumo jutiklį, su kuriuo gali skenuoti aplinką ir nustatyti atstumus iki visų kliūčių  Teritorijos padengimo problema Kelių planavimo problemos pratęsimas teritorijoms Tikslas: apvažiuoti visą pasirinktą teritoriją Problema nustatant kelią, kuris nukreipia robotą, kad jis galėtų įveikti dominančią sritį, tuo pačiu išvengiant kliūčių toje srityje Bustrofedono metodas – plotas padengiamas lygiagrečiomis linijomis  Įgaubtos formos teritorijos padengimas Išskaidykite plotą į išgaubtus posričius (celes). Kiekvienai celei taikomas Bustrofedono metodas, siekiant gauti aprėpties kelius Celės yra sujungtos keliais Optimalūs keliai randami naudojant keliaujančio pardavėjo problemos sprendimą, kuris sumažina kelionės atstumą / laiką iki visų celių aplankymo a) dominanti sritis; b) skaidymas į celes; c) visas aprepties kelias, Kelio padengimas naudojant daug robotų Duota 1) Sritis (teritorija) 2) Daug robotų 3) Robotų pradinės padėtys Tikslas: Suplanuoti robotų kelius, kurie padengtų teritoriją per kuo trumpesnį laiką Problemos: Elgsenos koordinavimas Komunikavimas  Kelio padengimas naudojant daug robotų Voronojaus erdvės sudalinimo algoritmas 1. Apskaičiuoti atstumą nuo kiekvieno roboto iki erdvės taško 2. Kiekvienas erdvės taškas priskiriamas artimiausiam robotui. 3. Kiekvienas robotas apeina jam priskirtą teritoriją