Úvod do robotiky: kartičky | uvod-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

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, …

Kinematika

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

Kinematika

manipulátor vs. robot

manipulátor – je připraven pro vykonávání dané operace
robot – je snadno přeprogramovatelný

Kinematika

manipulátor

stav jednoho kloubu popisuje jedna proměnná (joint variable $q_i$ $q_{i}$ )
- může být vícesložková
stavový vektor (joints state) $q=[q_1,q_2,\dots,q_n]$ $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}$ $R_{x, ϕ} = 100 0 cos ϕ sin ϕ 0 - sin ϕ cos ϕ$
  - 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

Kinematika

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}$ $L C S_{i - 1}$ a $LCS_i$ $L C S_{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$ $ϑ_{i}, d_{i}, a_{i}, α_{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)

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í

Mobilní zařízení (motion model)

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

Mobilní zařízení (motion model)

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

Mobilní zařízení (motion model)

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

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

Senzory

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

Senzory

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í)

Senzory

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)

Senzory

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

Senzory

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.)

Senzory

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

Senzory

MEMS – micro electro mechanical systems

používají mikroskopické jevy
akcelerometry
gyroskopy
senzory tlaku
displeje, pumpy, motory

Senzory

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í

ř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

Regulace a řízení

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)

Regulace a řízení

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

Regulace a řízení

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

Regulace a řízení

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

Regulace a řízení

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
…

Regulace a řízení

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

Regulace a řízení

Chien-Hrones-Reswick

…

Regulace a řízení

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

konečný stavový automat (finite state machine)

chybí tam výstup – chování robota

Řídicí systémy

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í

Řídicí systémy

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

Řídicí systémy

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í

Řídicí systémy

Node-RED

low-code programování pro událostmi řízené aplikace

Řídicí systémy

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ů)

Řídicí systémy

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é

Reprezentace prostředí, mapy

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é)

Reprezentace prostředí, mapy

topologické mapy

neuvádějí obvykle informaci o pozici, ale pouze informace o vztazích mezi objekty

Reprezentace prostředí, mapy

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í

Reprezentace prostředí, mapy

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

Reprezentace prostředí, 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ů

Reprezentace prostředí, mapy

symbolická mapa

pro přímou komunikaci člověk – robot

Reprezentace prostředí, mapy

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

Reprezentace prostředí, mapy

roboto-centrická senzorika

senzory se hýbou s robotem
musíme data přepočítávat

Reprezentace prostředí, mapy

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“

Reprezentace prostředí, mapy

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í

Reprezentace prostředí, mapy

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

Reprezentace prostředí, mapy

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

Reprezentace prostředí, mapy

ř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}$ $Bel : l \to {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

Reprezentace prostředí, mapy

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

Reprezentace prostředí, mapy

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

Reprezentace prostředí, mapy

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

Reprezentace prostředí, mapy

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é

Více robotů

aplikace

sklady
virtuální roje

Více robotů

centralizovaná architektura

jeden point-of-failure
velká komunikační zátěž

Úvod do robotiky

nevýhody - oscilace