Úvod do robotiky

• zkouška ústní podle sylabu
  • nejdřív musíme mít odevzdané a opravené všechny teoretické domácí úkoly
• zápočet za docházku, domácí úkoly a finální projekt
  • dvě absence jsou povoleny (víc radši ne)
  • domácí úkoly
    • do SISu
    • první verzi nejpozději den před příštím cvičením (odevzdat aspoň pokus o řešení)
    • na cvičeních se proberou nejčastější špatná řešení (ale můžeme se i doptat na to svoje konkrétní)
    • pak nahrát opravnou verzi (dříve než se přihlásím ke zkoušce; do SISu se odevzdává jako correction)
    • u zkoušky bych měl být schopen všechny své úkoly obhájit
    • pokud se v SISu u mého řešení objeví OK $\implies$ úkol je v pořádku (platí pouze tato jediná implikace, o kontrolu našeho řešení můžeme výslovně požádat po cvičení)
    • v první fázi teoretické úkoly, pak práce s roboty
  • závěrečný projekt předvést do konce zkouškového v zimním semestru
  • na výjimkách je potřeba se domluvit předem
• Parallax BoeBot
• programuje se v C++
• první úkol
  • přečíst Runaround
  • vymyslet ke každému zákonu výjimku (tenhle zákon tvrdí tohle, ale bylo by dobré, kdyby ho v této situaci robot porušil)
  • stačí TXT, nahrát do SISu
  • uvažovat robota s limity a omezenými informacemi
  • zákon je formulovaný slovně, můžeme v úkolu popsat, jak ty věci chápeme
  • nemusí to být extra dlouhé, máme se zamyslet a popsat nějakou myšlenku

Kinematika

• póza = poloha + orientace
  • ale občas se póza zaměňuje s polohou
  • typicky nás zajímá stav robota, tzn. poloha, orientace, stav nabití baterie, …
• dopředná úloha kinematiky – víme, o kolik jsme pohli manipulátorem, zajímá nás, kam se dostal
• zpětná úloha kinematiky – víme, kam se chceme dostat, zajímá nás, jak to uděláme
• kinematika = pohyb jednotlivých částí robota bez vztahu k silám
• obvykle nás zajímá ještě dynamika
• dopředná úloha kinematiky je vlastně násobení transformačních matic
• ve zpětné úloze kinematiky počítáme úhly pomocí původních a cílových souřadnic
• stupně volnosti
  • stupeň volnosti = počet nezávislých proměnných v systému
  • často se mluví o stupni volnosti v prostoru
    • na přímce 2 (pohyb, dopředu/dozadu)
    • v rovině 3 (pohyb, dopředu/dozadu, natočení)
  • ve 2D
    • 3 stupně volnosti (DOF = Degrees of Freedom)
    • kartézská soustava souřadnic $[x,y,\alpha]$
  • ve 3D
    • 6 stupňů volnosti
    • $[x,y,z,\alpha,\beta,\gamma]$
    • někdy se jeden úhel nepočítá vůči rovině, ale vůči ose otáčení daného nástroje (např. šroubováku)
    • natočení
      • podle $x$ = roll, náklon
      • podle $y$ = pitch, sklon, zdvih, sklopení
      • podle $z$ = yaw, otočení, směr (to není úplně vhodné označení)
    • používáme pravotočivý systém (pravou rukou, prsty ukazují směrem $x$, zavřením dlaně je otočím k ose $y$, palec ukazuje směr osy $z$)
    • kladný směr otáčení je proti směru hodinových ručiček
• manipulátor vs. robot
  • manipulátor – je připraven pro vykonávání dané operace
  • robot – je snadno přeprogramovatelný
• manipulátor
  • stav jednoho kloubu popisuje jedna proměnná (joint variable $q_i$)
    • může být vícesložková
  • stavový vektor (joints state) $q=[q_1,q_2,\dots,q_n]$
    • $n$ stupňů volnosti
  • pracovní prostor (working space) – kartézský součin všech proměnných
  • lokální vs. globální souřadný systém (local × global coordinate system – LCS, GCS)
    • lokální systém je někdy výhodnější – pokud se něco změní u jednoho kloubu, stačí to softwarově změnit pouze u něj
    • typicky nás zajímají globální souřadnice
  • typy kloubů
    • otočný (revolute) – 1 stupeň volnosti
    • prismatický = píst (prismatic) – 1 stupeň volnosti
    • šroub (helical) – 1 stupeň volnosti
    • cylindrical – 2 stupně volnosti
    • spherical – 3 stupně volnosti (pohyb kolem dvou os + otáčení)
    • planar – 3 stupně volnosti (posun ve dvou osách + otáčení)
  • obvykle se používají prismatický a otočný
  • poloha … stavový vektor o tolika složkách, kolik jich potřebujeme
  • rotace
    • $P$ … poloha
    • $R$ … rotační matice
    • $P'=R\cdot P$
    • $R_{x,\phi}=\begin{bmatrix}1&0&0\\0&\cos\phi&-\sin\phi\\0&\sin\phi&\cos\phi\end{bmatrix}$
      • rotace podle osy $x$
    • používáme písmenka fí $\phi$, psí $\psi$, xí $\xi$
  • rotace a translace
    • $P'=R\cdot P+T$
    • místo $T$ (translation) se někdy píše $D$ jako displacement
  • jak to kombinovat?
    • $P'=R_2\cdot(R\cdot P+T)+T_2$
    • …
  • homogenní souřadnice ve 2D
    • bod vyjádřím jako $p=(x,y,w)^T$
    • kde $w$ je projekce do nějaké roviny
    • budeme pracovat s $w=1$
    • rotace v rovině vypadá stejně jako rotace podle osy $z$ v prostoru (takže u třetí souřadnice bude identita)
    • translaci $p'=p+\mathcal D_p$ uděláme pomocí násobení matic
    • $(x',y',w')^T=\begin{pmatrix}1&0&d_x\\0&1&d_y\\0&0&1\end{pmatrix}\cdot\begin{pmatrix}x\\ y\\ w\end{pmatrix}$
  • dopředná kinematika ve 3D
    • $P=f(q)$
    • $q=[q_1,q_2,\dots,q_6]$
    • $P=[x,y,z,\alpha,\beta,\gamma]$
  • složení systému
    • obecné
      • každý kloub je reprezentován svou geometrickou transformací
      • přechod mezi lokálními souřadnicovými systémy
      • může být těžké vytvořit celkovou zkombinovanou transformační matici
    • Denavit-Hartenberg
      • pokud jsou systémy šikovně navrženy
      • funguje ve 3D
      • fiktivní pohyby spojující dva systémy – rotate (podle osy $z$), move (po ose $z$), move (po ose $x$), rotate (podle osy $x$)
      • v libovolně dlouhé sekvenci
• Denavit-Hartenberg (DH) systém
  • systém je složen z rotačních a posuvných kloubů, mezi klouby jsou spoje
  • vztah mezi $LCS_{i-1}$ a $LCS_i$ je složená trasformace
    • natočení osy $x_{i-1}$ kolem osy $z_{i-1}$ o úhel $\vartheta_i$
    • posunutí osy $x_{i-1}$ ve směru osy $z_{i-1}$ o vzdálenost $d_i$
    • posunutí počátku $LCS_{i-1}$ podél osy $x_i$ o vzdálenost $a_i$
    • natočení osy $z_{i-1}$ kolem osy $x_i$ o úhel $\alpha_i$
  • DH parametry $\vartheta_i,d_i,a_i,\alpha_i$
    • $\vartheta_i$ … úhel mezi osami $x$ kolem $z_{i-1}$
    • $d_i$ … vzdálenost mezi osami $x$
    • $a_i$ … vzdálenost mezi osami $z$
    • $\alpha_i$ … úhel mezi
  • osy $z$ jsou dány tím, jak to kdo vyrobil
  • osu $x$ si zvolím tak, aby byla kolmá na $z_i$ a $z_{i-1}$
  • $\vartheta_i$ a $d_i$ jsou proměnné, zbytek jsou konstanty (?)
  • konstrukce D-H řetězce
    • očíslování kloubů $0$ až $n$ ($0$ je první, pevný)
    • očíslování článků $1$ až $n$ (článek $i$ spojuje klouby $i-1$ a $i$)
    • používáme ortonormální pravotočivý souřadný systém
    • …
  • někdy je potřeba přeznačit osy – v takové situaci bude jeden řádek tabulky bez proměnné

Mobilní zařízení (motion model)

• holonomní / neholonomní vozidla
• Heinrich Hertz – stupně volnosti
  • vozidlo je holonomní, pokud se počet lokálních stupňů volnosti rovná počtu globálních stupňů volnosti
  • opak = přezadaný systém, v reálném světě se některá kola smýkají
• vlak … holonomní (v 1D prostoru jezdí dopředu a dozadu)
• auto … neholonomní (v 2D prostoru jezdí dopředu a dozadu, otáčí kola, ale nemůže jet do boku)
• pokud chceme najít výslednou polohu, integrujeme přes čas
• Ackermannovo řízení
  • neholonomní
  • natáčím jednu soupravu (jako u auta)
  • v zatáčce je potřeba, aby vnitřní kolo bylo natočeno jinak než vnější kolo (tzn. nelze natáčet přímo osu, na které jsou kola – v takovém případě se kola smýkají)
  • zatáčí se posouváním tyče rovnoběžné s přední osou, ta je ke kolům připojena tyčemi, jejichž prodloužení se protínají uprostřed zadní osy („delta“?)
  • v praxi se používá složitější konstrukce
• differential steering (diferenciální řízení?)
  • neholonomní
  • zatáčím rozdílem rychlosti levého a pravého kola (jako u tanku)
  • použití v praxi
    • obecnou trajektorii nahradím sérií úseček nebo oblouků
    • musím rozumně určit $\Delta t$ – ne moc malé, abych pořád nepočítal, ale ne moc velké, abych dostal rozumné výsledky (situace: obě kola ujely stejně, ale nejdřív jedno stálo a druhé se točilo a pak naopak)
    • musím změřit vzdálenost
• omnidirectional steering
  • holonomní
  • kola mohou jet libovolným směrem
  • příklady
    • swerve/crab drive – lze otáčet kolem o 360 stupňů
    • omniwheel – kolo má po obvodu válečky, které mohou volně prokluzovat ve směru kolmém na směr otáčení kola
    • mecanum wheel – velmi podobné jako omniwheel, ale válečky jsou otočeny o 45 stupňů; když točím kolem, tak výsledný pohyb směřuje šikmo (rovněž pod úhlem 45 stupňů)
    • …
    • syncrodrive – není úplně omnidirectional, všechny kola jsou natočeny stejným směrem
  • špatná prostupnost terénem
  • jednoduchá mechanická konstrukce pro omniwheels a mecanum wheels

Elektromotory

• …
• servo motor
  • je to vlastně motor + nějaká další elektronika zajišťující zjištění pozice osy a nějaké řízení (tzv. zpětná vazba)
  • neurčujeme rychlost (otáčky), ale natočení hřídele
  • RC servo
    • otáčí se podle délky pulzů
    • má omezení – nemůže se otáčet kolem dokola (obvykle kvůli potenciometru)
    • obsahuje převodovku
    • pulzní signál má dlouhé mezery – aby se dalo ovládat více servomotorů
  • na principu servomotoru funguje třeba naklápění světel v autě
  • je možné mít i víceotáčková serva
  • RC „digitální servo“ – dva typy
    • jedno podobné jako analogové (jen elektronika uvnitř používá digitální signál, tudíž může mít hladší chod než analogové – lze ho bez problémů vyměnit s analogovým)
    • druhé komunikuje digitálně s ovladačem, je programovatelné
  • „hacknuté“ servo
    • místo potenciometru použijeme pevný odpor – řekneme servu, že je v půlce
      • někdy je potřeba doladit, aby se servo opravdu netočilo (kvůli nepřesnostem při výrobě odporů apod.)
    • takže když mu řekneme, kam se má otočit, ono se tam bude točit (ale nikdy tam nedojde)
    • tudíž místo natočení udáváme rychlost
    • u digitálních serv to nelze (rozhodně ne u druhého typu, u prvního typu někdy)

Senzory

• někdy mě zajímá jen detekce, jindy měření hodnoty
• senzory
  • lokální – taktilní (např. nárazník, měření elektrického signálu)
  • bezdotykové – měříme vzdálenost, světlo apod.
  • virtuální – měříme „vlastnosti robota“, např. proud, který jde do motoru, z toho zjistíme, že narazil na překážku → nepotřebujeme koncové senzory
• pokročilé – radar, lidar, kamera, hloubková kamera, IMU, …
• aktivní × pasivní měření
• oblíbené senzory v robotice
  • taktilní – mikrospínače, koncové spínače, „nárazníky“
  • elektrické – měření spotřeby proudu motorem, měření indukovaným proudem
  • směrové akustické, optické – měření detekcí odraženého paprsku (detekce překážek, mapování prostředí)
  • liniové senzory – směrové měření multiplexované v čase
  • kamery – zpracování obrazu
  • MEMS
• měření pomocí odrazu signálu
  • metody
    • direct TOF
      • měřím čas, jak dlouho signál letí
      • je potřeba přesně měřit čas
      • pomocí světla se malé vzdálenosti měří těžko – lepší je zvuk
    • pulsed TOF
      • přenáším pulzy
      • měřím poměr signálu, který se vrátil před a po události
    • phase-shift
      • počítám vzdálenost z fázového posunu
  • typy signálu – infračervené záření, laser, radar, ultrazvuk
  • signál se musí odrazit, jinak nic nezměřím
  • měření je aktivní
    • jsem závislý na prostředí, ve kterém měřím
    • může tam být interference s jiným senzorem stejného typu
    • je to detekovatelné nepřítelem (ve vojenském prostředí)
• měření pomocí přerušení signálu
  • pomocí brány – dvě části na sebe „svítí“, pokud signál nedoletí, tak mezi nimi něco je
  • lze detekovat odražení signálu nebo absenci odražení…
  • typicky se hodí informace o intenzitě signálu
  • někdy takhle fungují kolečka na myších (fungovaly tak kuličkové myši)
• ultrazvuk
  • přímé měření času letu signálu je možné
  • typicky měří v rozsahu 1 cm – 10 m
  • používá se neslyšitelné spektrum (vhodné jsou hodnoty kolem 40 kHz, aby to neslyšela ani zvířata)
  • měří to do kuželu, dokonce i trochu do stran a dozadu
• infračervené senzory
  • krátký dosah
  • svítí tam infra LED
  • odraz se detekuje pomocí fotorezistoru
  • PSD – měří vzdálenost až v jednotkách metrů, problém s osvětlením (horší měření venku apod.)
• laser & lidar
  • 1D, 2D, 3D
  • až 20 km
  • dnes se používají i solid-state lidary, mají víc jednotek, takže není potřeba, aby se lidar otáčel
• MEMS – micro electro mechanical systems
  • používají mikroskopické jevy
  • akcelerometry
  • gyroskopy
  • senzory tlaku
  • displeje, pumpy, motory
• odometrie
  • měření ujeté vzdálenosti
  • možnosti
    • pomocí otáček kol – ale kola můžou prokluzovat
    • pomocí otáček motoru – pozor na převodovku a na chvíle, kdy motor zabírá, ale kola se neotáčí
    • pozorováním prostředí
  • počítání
    • mechanické
    • jazýčkový spínač (reed switch)
    • induktivní a kapacitní (detekce magnetickým polem)
    • resolver, synchro (vinutí kolem motoru – generuje proud)
    • optický snímač (třeba u počítačových myší)
    • Hallův jev
    • Dopplerův jev (frekvenční posun)
    • snímání povrchu
  • enkodéry
    • relativní – říkají nám změnu měření od předchozího stavu, neříkají nám úhel
      • rate – senzor sleduje změnu mezi dvěma hodnotami (sleduje černobílý terč), frekvence změn indikuje rychlost, počet změn indikuje úhel rotace; nelze zjistit směr rotace
      • quadrature – dva senzory, snímají i směr, více možností
        • dvě stopy posunuté o půl kroku, senzory vedle sebe
        • jedna stopa, senzory posunuté o půl kroku
    • absolutní
      • binární – více senzorů v různých stopách, každý úhel odpovídá jinému binárnímu číslu, problém nastává v situaci, kdy mám nepřesné senzory
      • Grayův kód – v každém kroku se mění jeden bit
        • lze snadno sestavit (vezmu nulu, přidám sekvenci, vezmu jedničku, přidám sekvenci pozpátku)
        • je potřeba aspoň 9 stop pro 1° přesnost
      • single-track Gray code
        • N. B. Spedding ukázal pětisenzorový jednostopý kód
        • Hiltgen a Paterson ukázali 9senzorový kód (pro 360 pozic)
  • reálné enkodéry
    • na staré počítačové myši – ozubené kolečko přerušuje optický signál
    • Austria Microsystems AS5035 – magnetický, ale používá quadrature výstup
    • twist & push rotační enkodér – kovové ozubené kolečko, tři kontakty se ho dotýkají, jeden trvale, další dva vzájemně posunuté → kvadraturní signál
  • Hallův jev
    • proud protéká polovodičem, když je to v magnetickém poli, tak se proud vychyluje
    • používá se v ABS v autě
  • Dopplerův jev
    • pohybující se vysílač a přijímač, měří se fázový posun odraženého signálu
    • je jednodušší měřit rázovou frekvenci

Regulace a řízení

• u reálného motoru do hry vstupuje spousta jevů – je potřeba tomu přizpůsobovat vstup
• typicky použijeme nějakou zpětnou vazbu a podle toho budeme měnit vstup
• např. servo je lineární jen v určitém frekvenčním rozsahu
• triviálně bez feedbacku – experimentálně zjistím, jaká je skutečná maximální hodnota (v lineárním rozsahu), pak to natvrdo zapíšu do kódu
• řešení s feedbackem
  • řízení motoru nastavím na rozdíl mezi reálnou a požadovanou hodnotou (rozdíl = chyba)
  • ten rozdíl násobím ještě nějakou ladicí konstantou
• druhý pokus
  • budu upravovat řízení podle chyby (rozdílu mezi reálnou a požadovanou hodnotou)
  • = integral controller

  • nevýhody - oscilace

    • přestřelení
  • chtěl bych nepřestřelit
    • budu derivovat
    • PD regulátor (proportional + derivative controller)
• třetí pokus
  • budu přímo počítat řízení
  • ladicí konstanta bude jiná u minulých chyb než u aktuální chyby
  • proportional + integral controller
• PID controller
  • e = req_speed - cur_speed
  • sum_e = += e
  • control = P*e + I*sum_e - D*(cur_speed - last_speed)
  • parametry P, I, D jsou platné pro jeden typ procesu
• ladění parametrů
  • manuálně
  • ze zkušenosti
  • pomocí magie
  • pomocí vědy
    • Ziegler-Nichols
    • Cohen-Coon
    • Tyreus-Luyben
    • Chien-Hrones-Reswick Autotuning
  • výsledky vědeckého bádání se hodí použít – pak to obykle stačí jen trochu doladit
• rychlé manuální ladění
  • I=0, D=0
  • zvyšuju P, dokud to nezačne oscilovat
  • nastavím P na polovinu
  • ^ tohle obvykle stačí, pokud ne, tak začnu ladit další složky
    • obvykle se ladí I
    • D se používá pro tlumení nebo vyhlazení šumu
  • zvyšuju I, dokud se mi nelíbí doba trvání procesu
  • …
• pozorování: když to má být rychlé, tak to obvykle přestřelí
• Ziegler-Nichols
  • velkou roli hraje čas mezi změnou a zaznamenáním změny (= „perioda“?)
  • je potřeba najít Pc a Tc
    • Pc … kritické P, kdy to začíná oscilovat s nulovými I, D
    • Tc … perioda
• Chien-Hrones-Reswick
  • …
• pozorování: je lepší používat jednodušší přístup – někdy stačí P, PI nebo PD
• implementační problémy: nedokonalé informace (měření, rozlišení enkodéru, filtrování dat), rozsah proměnných, aritmetika (když bude akumulovaná chyba moc velká, tak může být problém s přičítáním/odčítáním)
• u boebotů nedává smysl měnit rychlost motorů vícekrát než 20× za sekundu
• implementace v reálném světě
  • mechanická – páčka, pružina, hmotnost
  • elektrická (analogová) – zesilovač, kondendzátor, odpor
  • digitální – výpočet v mikrokontrolerech FPGA, PLC, …

Řídicí systémy

• omezeny na konkrétní situaci v konkrétním čase
• starší průmyslová robotika – roboti se nepřizpůsobují okolním podmínkám (takže to vlastně nebyli roboti, ale spíše mechanická zařízení)
• robot control = sensing (načtení informací z okolí) → processing (zpracování informací) → executing (vykonání reakcí na podněty)
• konečný stavový automat (finite state machine)
  • chybí tam výstup – chování robota
• implementace FSM
  • definuju stavy jako výčtový typ
  • nastavím počáteční stav
  • implementuju přechod mezi stavy (třeba pomocí switche)
  • pozor na časování
• složitější implementace – pomocí tabulky stavů a vychodnocovacích funkcí
• Petriho síť
  • orientovaný bipartitní graf
  • vrcholy … přechody a místa
  • graf je vhodný na znázornění nezávislých událostí a synchronizace
• Grafcet
  • GRAphe Fonctionnel de Commande Etapes/Transitions
  • založen na binárních Petriho sítích
  • je vhodný pro asynchronní paralelní spouštění
• Sequential Function Chart
• Node-RED
  • low-code programování pro událostmi řízené aplikace
• implementace na střední úrovni – middleware
  • propojuje moduly na nízké úrovni, které ovládají hardware, s high level algoritmy a rozhodovacími procesy
  • např. ROS (potřebuje operační systém, na kterém by mohl běžet; poskytuje spoustu užitečných nástrojů a balíčků)
• implementace průmyslového řízení – podle technických norem
• architektury vyšší úrovně řízení
  • deliberative control
    • nejdřív se posbírají všechny indicie
    • rozhodne se, co se má dělat
    • a pak se to vykoná
    • problém – dynamické prostředí
  • SPA architektura
    • sense, plan, act
    • podobné jako předchozí
  • reaktivní řízení
    • nepřemýšlej – konej
    • tenhle princip používáme u boebotů
    • takhle funguje spousta rostlin a živočichů (mají přirozené reflexy)
    • těsný vztah mezi senzory a aktuátory
    • typicky se takové systémy popisují systémem pravidel – když se něco stane, tak něco udělej
    • minimální vnitřní stav
    • v čisté formě nemá reaktivní systém žádnou paměť, nepamatujeme si globální stav
    • pořád se používá
  • subsumption architecture
    • Rodney Brooks, firma iRobot
    • několik úrovní kontroly – vyšší úrovně řeší problémy, které nižší nezvládnou vyřešit
    • vyšší úrovně přepisujou vstupy a výstupy nižších úrovní
  • hybridní řízení
    • mysli a konej
    • reaktivita v reálném čase
    • racionální rozhodování
    • interakce obou komponent
      • reactive – okamžité potřeby
      • deliberative – dlouhodobé potřeby
    • můžou být v konfliktu – používá se třetí úroveň, která to koordinuje
  • behaviour control
    • mysli tak, jak se chováš
    • sada distribuovaných a interagujících modulů
    • je to sada jednotlivých „chování“ (behaviours)
    • behaviours ovlivňují chování robota
    • decentralizované řízení
    • jako behaviours se dají použít i neuronové sítě apod.
    • adaptabilní způsob řízení

Reprezentace prostředí, mapy

• dělení podle způsobu vytvoření mapy
  • manuální – trvá to dlouho, není přesná
  • (částečně) automatické
• podle času vytvoření – offline (předem), online (v průběhu činnosti)
• fixní/adaptivní mapa
• metrické/topologické mapy – topologické reprezentují svět jako objekty a vztahy mezi nimi
• podle úrovně abstrakce – senzorická (popis objektů podle senzorů), geometrická (popis objektů podle jejich rozměrů, hmotností apod.), topologická (objekty a jejich atributy), symbolická („tohle je židle“)
• metrické mapy mají referenční souřadnicový systém
  • objekt je charakterizován tím, jaké místo na mapě zabírá
  • příklady: turistické mapy, někdy městské mapy (ale např. všechny ulice jsou zobrazeny stejně široké)
• topologické mapy
  • neuvádějí obvykle informaci o pozici, ale pouze informace o vztazích mezi objekty
• v robotice se často používají oba přístupy, které se kombinují
• bereme v úvahu rozměry robota – nasnímané překážky tedy „rozšíříme“, aby do nich robot nenarazil (pak to může vypadat, že se chová zvláštně)
• při delším pohybu robota někdy vznikají v mapách chyby – řeší se to „uzavřením“ mapy (loop closure), které vychází z toho, že zdi na sebe navazují
• senzorická mapa
  • spojení vstupů ze senzorů
  • typickým příkladem je occupancy grid
    • pravidelná nebo nepravidelná
    • zachycuje volný prostor, překážky a neznámý prostor
  • obvykle jen částečná, ne globální
• geometrická mapa
  • objekty se skládají z geometrických primitiv (křivek, přímek, hranolů, válců, koulí)
  • problém – automatické vytvoření geometrické mapy
• topologická mapa
  • zobecněná geometrická mapa do obecného grafu
  • typické příklady
    • vrcholy … objekty, hrany … vztahy mezi nimi
    • vrcholy … objekty a vztahy mezi nimi, hrany … přiřazení objektů a vztahů
• symbolická mapa
  • pro přímou komunikaci člověk – robot
• occupancy grid / mřížka obsazenosti
  • přímý přístup
    • měření ze senzorů
    • těžké na vytváření a údržbu
  • pravděpodobnostní přístup
    • vede na bayesovské metody
  • plausibility approach (věrohodnostní přístup)
    • zachycuje více různých možností – různé úrovně jistoty
  • fuzzy přístup
    • s daty se špatně pracuje
    • „je hotel blízko pláže?“ – co je to blízko?
  • neuronové sítě, genetické algoritmy
    • problém s trénováním a neočekávanými událostmi
• roboto-centrická senzorika
  • senzory se hýbou s robotem
  • musíme data přepočítávat
• cíle lokalizace
  • abychom zjistili robotovu pozici a orientaci
    • vzhledem k mapě
    • v daném prostředí
  • někdy chceme získat pozici a orientaci jednotlivých částí robota
  • pozice + orientace = „póza robota“
• problém transformace souřadnic mezi globálním a lokálním systémem
• dělení lokalizace
  • absolutní (globální) / relativní (lokální) – relativní se typicky vztahuje k nějaké poloze v minulosti
  • pasivní / aktivní – při aktivním přístupu se při lokalizaci můžu pohybovat (např. jsem v dlouhé chodbě, nevím, ve které, tak zkusím popojet)
  • ve statickém / dynamickém prostředí
• absolutní lokalizace
  • nebere v úvahu předchozí pozici
  • obvykle technicky nebo výpočetně složitější
  • řeší situaci, kdy nemáme informaci o předchozí pozici
    • wake-up problem (robota jsme zapnuli)
    • kidnap problem (poloha robota se změnila, ale robot to neví)
  • používáme vlastnosti prostředí – landmarks (aktivní vs. pasivní)
    • aktivní – vysílají informaci, ze které lze něco zjistit
  • GPS (Navstar), Glonass, Compass (BeiDou), Galileo
• relativní lokalizace
  • měříme změnu od minule
  • problém – akumulace chyby
  • používá se odometrie a inerciální navigace
  • dead reckoning – tradiční námořní navigační postupy (směr + rychlost + čas)
  • odometrie – měření rotací kol
• typicky se setkáváme s problémy při reálné lokalizaci
• řešení reálných problémů s lokalizací
  • přesnější měření – „model based“, nejistotu eliminuju
  • nespoléhám se na to, že znám přesnou pozici robota – pravděpodobnostní lokalizace
    • pozice robota je náhodná proměnná
    • používají se principy teorie pravděpodobnosti
    • Markovovský řetězec – historie pohybu neovlivňuje budoucnost pohybu
    • odhad pózy robota je funkce $\text{Bel}:l\to\set{0,1}$
      • kde $\text{Bel}$ … belief, $l$ … pozice
    • nesnažíme se odstranit nejistotu
    • hodnoty z minulých měření kombinujeme s aktuálním měřením
    • nepotřebujeme spojitost, takže máme jistou granularitu
    • topologický graf – vrcholy = možné pozice, hrany = možné přechody
      • $\text{Bel}(l)$ odpovídá pravděpodobnosti, že je robot ve vrcholu $l$
    • Monte Carlo lokalizace
      • sledujeme množinu bodů, které mají nějakou pravděpodobnost (váhy)
      • součet vah = 1
      • algoritmus
        • predikční krok – pohnu se všemi vzorky (pokud vím, že robotovi prokluzují kolečka, tak pohnu každým vzorkem trochu jinak)
        • korekční krok – změním váhu vzorků na základě měření
        • převzorkování – upravím množinu vzorků tak, že losuju ze vzorků, přičemž vyšší váha odpovídá vyšší pravděpodobnosti vybrání (ostatní zahodím); taky bývá vhodné nějaké vzorky přidávat nebo někdy dává smysl všechny vzorky zahodit a začít znova
      • nejlepších výsledků se dosahuje se senzory, které nejsou moc nepřesné, ale ani moc přesné
      • MCL (Monte Carlo lokalizace) může kombinovat informace z více senzorů
      • pozorování
        • MCL je imunní vůči chybám v odometrii
        • MCL je imunní vůči nepřesnosti GPS
  • žádná lokalizace
    • předprogramované automaty
    • reaktivní systémy
    • evoluční algoritmy
• SLAM – simultánní lokalizace a mapování
• když známe vzdálenosti od landmarků
  • vzdálenost od dvou landmarků nám dává dvě symetrická řešení, jedno z nich typicky můžeme zahodit, protože nedává smysl
• když známe úhly k landmarkům
  • dva landmarky nám dají jeden (obvodový) úhel → máme kružnici (pokud známe pozici landmarků na mapě)
  • když máme třetí landmark, máme tři úhly (tři trojúhelníky) a dostaneme bod
• plánování cesty
  • zadání: najdi cestu ze startu do cíle nebo řekni, že cesta neexistuje
  • bereme v úvahu, jestli je cesta vůbec proveditelná, vyhýbáme se překážkám na cestě
  • zajímá nás složitost algoritmu, případně jestli najde optimální cestu
  • zajímá nás úplnost algoritmu
  • algoritmy
    • grafové
    • mřížkové / metody s potenciálovým polem
  • algoritmus nezáleží na typu mapy – lze přecházet mezi typy algoritmů
  • dělení algoritmů podle nalezeného řešení
    • přesné (exaktní)
    • aproximace
    • pravděpodobnostní řešení
  • bug algoritmy
    • žádný globální model
      • žádná mapa ani známé překážky
      • nevíme, jestli se dá vůbec dostat do cíle
    • známe pozici cíle vzhledem k pozici startu
    • máme senzory (omezené)
    • předpoklady
      • 2D statické prostředí
      • konečné parametry (tyhle všechny věci musí být konečné, aby byl algoritmus úplný)
        • lokální počet překážek
        • obvod překážky
        • tloušťka překážky
        • počet překážek, které protíná přímka
      • překážky se nedotýkají, jinak je můžeme sloučit do jedné překážky
    • Bug0
      • běž k cíli, dokud nenarazíš na překážku
      • pokud narazíš na překážku, obcházej ji, dokud nemůžeš jít zase rovně k cíli
        • je jedno, jestli budeme všechny překážky obcházet zleva nebo se budeme rozhodovat náhodně
      • robot nemá paměť, překážka ve tvaru C ho zacyklí
    • Bug1
      • řešením by bylo obcházet překážku tak dlouho, dokud nebudu blíž cíli než v místě, kde jsem do ní narazil
      • tady už potřebujeme paměť
      • hledáme místo na obvodu překážky, které je nejblíž k cíli (?)
      • je Bug1 úplný?
        • lemma 1-1: brouk se nevrací k překážce, kterou opustil
        • důkaz
          • $H_i$ … hit point, $L_i$ … leave point
          • brouk se pohybuje od startu přes H1, L1, H2, L2, …, Hn, Ln do cíle
          • …
        • lemma 1-2: brouk potká konečný počet překážek
        • důkaz: v kruhu se středem v cíli a s poloměrem odpovídajícím vzdálenosti startu a cíle je konečný počet překážek, cesty mezi Li a Hi jsou uvnitř kruhu
    • Bug2
      • máme úsečku ze startu do cíle
      • obcházíme tak dlouho, dokud tu úsečku nepotkáme znova
      • pokud se obcházením dostaneme na místo, kde už jsme byli, na dané křižovatce se příště musíme rozhodnout jinak
    • Bug2 je hladový
    • area of sight improvement
      • brouk obchází překážky kratší trasou
      • tangent bug
• nejkratší cesta
  • Djikstra
  • A*
  • D*
  • náhodné stromy
  • potential field planning
    • pustíme vodu z robota
    • cíl je prohlubeň
    • překážky jsou vyvýšené
• další úloha – bez překážek, obejít dané body
• používají se spliny, hermitovské křivky

Více robotů

• úkol je příliš komplexní pro jednoho robota
• aplikace
  • sklady
  • virtuální roje
• centralizovaná architektura
  • jeden point-of-failure
  • velká komunikační zátěž
• hierarchie
• decentralizovaná kontrola
• hybridní řízení