Tvorba map v roboticerobotika/prednasky/2014...Mapa Motivace Metricka´ mapa Topologicka´ mapa...

Robotika

Tvorba map v robotice

25. brezna 2013

Ing. Frantisek Burian

MapaMotivace

Metricka mapa

Topologicka mapa

Tvorba mapy

Navigace v mape

Pomocnealgoritmy

Mapa v pojetı mobilnı robotiky

Mapa je strojove citelny popis prostredı, ktery lze vyuzıt k lokalizacia navigaci robotu naprıc tımto prostredım.

• Metricka mapa (2D zobrazenı)• Topologicka mapa (teorie grafu)

MapaMotivace

Metricka mapa

Topologicka mapa

Tvorba mapy

Navigace v mape

Pomocnealgoritmy

Metricka mapa

• Ukladany kartezske souradnice vyznacnych bodu• Narocne na presnost merenı, sum senzoru• Lze jednoduse provadet sebelokalizaci

[Hans P. Moravec - Robot Evidence Grids]

MapaMotivace

Metricka mapa

Topologicka mapa

Tvorba mapy

Navigace v mape

Pomocnealgoritmy

Topologicka mapa

• Ukladany vzajemne vztahy vyznacnych bodu• Lze jednoduse provadet navigaci podel bodu

A B

CD

E

F

3

4.2

6.2

1

2.5 3.5

2

3

1

• Uzly• Hrany

Mapa

Tvorba mapyModel sveta

Bayesuv klasifikator

Model senzoru

Prıklad

Mrızka obsazenosti

Prıklady hotove mapy 3D

Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Model sveta

Realny (metricky) svet je slozen z ruzne obsazenych oblastıM.

Hledame zpusob, jakym lze vyjadrit obsazenost tohoto sveta.

• Pravdepodobnost obsazenosti• Moznost obsazenosti (odds ratio)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Model sveta - Pravdepodobnostnı model

Necht’ p(MO) oznacuje ppst. obsazenosti bunky.

p(MO) =

0, pokud je dana oblast sveta neobsazena (M = E)

0.5, pokud o dane oblasti nemame informaci1, pokud je dana oblast obsazena (M = O)

Dale necht’ p(ME) oznacuje ppst. volnosti (pruchodivosti) bunky.Ze zakonu statistiky muzeme psat:

0 < p(MO) < 1 0 < p(ME) < 1

Nakonec uzavreme skupinu jevu do celistve skupiny1

p(MO) + p(ME) = 1

Mapou obsazenosti rozumıme hodnoty obou velicin p(MO) a p(ME)

1Pro ucely jednodussıho pochopenı, existujı i jine modely, kde toto nemusı platit.

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Model sveta - Model moznostı

Vyjadreme moznost, kterou ma bunka, ze je obsasena takto:

O(M) =p(MO)

p(ME)

O(M) =

0, pokud je dana oblast sveta neobsazena (M = E)

1, pokud o dane oblasti nemame informaci∞, pokud je dana oblast obsazena (M = O)

Mapou obsazenosti rozumıme hodnoty pouze jedne veliciny O(M)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Bayes - Odvozenı

p(A) p(B)

S

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Bayes - Odvozenı

p(A) p(B)

p(AB)

S

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Bayes - Odvozenı

p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Bayes - Odvozenı

p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

p(B|A) =p(AB)

p(A)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Bayes - Odvozenı

p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

p(B|A) =p(AB)

p(A)

p(A|B)p(B) = p(AB) = p(B|A)p(A)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Bayes - Odvozenı

p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

p(B|A) =p(AB)

p(A)

p(A|B)p(B) = p(AB) = p(B|A)p(A)

p(A|B) =p(B|A)p(A)

p(B)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Bayes - Odvozenı

p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

p(B|A) =p(AB)

p(A)

p(A|B) =p(B|A)p(A)

p(B)

novainformace

predchozıinformace

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Bayes - Odvozenı

p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

p(B|A) =p(AB)

p(A)

p(A|B) =p(B|A)p(A)

p(B)

novainformace

modelsenzoru

predchozıinformace

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Bayes - Odvozenı

p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

p(B|A) =p(AB)

p(A)

p(A|B) =p(B|A)p(A)

p(B)

novainformace

modelsenzoru

predchozıinformace

pravdepodobnostmerenı

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Bayes - Odvozenı

p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

p(B|A) =p(AB)

p(A)

p(A|B) =p(B|A)p(A)

p(B)=likelihood · prior

evidence

novainformace

modelsenzoru

predchozıinformace

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Bayes - Odvozenı

p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

p(B|A) =p(AB)

p(A)

novainformace

modelsenzoru

predchozıinformace

p(A|B) =p(B|A)p(A)

p(B|A)p(A) + p(B|A)p(A)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Moznost obsazenosti (odds ratio)

p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

p(B|A) =p(AB)

p(A)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

p(B|A) =p(AB)

p(A)

O(A|B) =p(A|B)

p(A|B)=

p(B|A)p(A)p(B|A)p(A)

= λ(B|A)O(A)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

p(B|A) =p(AB)

p(A)

O(A|B) =p(A|B)

p(A|B)=


= λ(B|A)O(A)

novainformace

predchozıinformace

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


p(A) p(B)

p(AB)

S

p(A|B) =p(AB)

p(B)

p(B|A) =p(AB)

p(A)

O(A|B) =p(A|B)

p(A|B)=


= λ(B|A)O(A)

novainformace

modelsenzoru

predchozıinformace

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Prıklad - pravdepodobnostnı vypocet

L

x

p(L|MO)

p(L|ME)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


L

x

p(L|MO)a

p(L|ME)a

a

p(L|MO)

p(L|ME)

1. Init: p(MO)a = 0.5, p(ME)a = 0.52. Merenı1 (L1): p(L1|MO)a = 0.22, p(L1|ME)a = 0.65p(L1)a = p(L1|MO)ap(MO)a + p(L1|ME)ap(ME)a = 0.22 · 0.5 + 0.65 · 0.5 = 0.43

p(MO|L1)a =p(L1|MO)a · p(MO)a

p(L1)a=

0.22 · 0.50.435

= 0.25

p(ME |L1)a =p(L1|ME)a · p(ME)a

p(L1)a=

0.65 · 0.50.43

= 0.75 = 1− p(MO|L1)a

V bode a je prekazka s pravdepodobnostı p(O)a=25%

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


L

x

p(L|MO)a

p(L|ME)a

a

p(L|MO)

p(L|ME)

1. Init: p(MO)a = p(MO|L1)a = 0.25, p(ME)a = p(ME |L1)a = 0.752. Merenı2 (L2): p(L2|MO)a = 0.22, p(L2|ME)a = 0.65p(L2)a = p(L2|MO)ap(MO)a + p(L2|ME)ap(ME)a = 0.22 · 0.25 + 0.65 · 0.75 = 0.54

p(MO|L2)a =p(L2|O)a · p(MO)a

p(L2)a=

0.22 · 0.250.54

= 0.10

p(ME |L2)a =p(L2|ME)a · p(ME)a

p(L2)a=

0.65 · 0.750.54

= 0.90 = 1− p(MO|L2)a

V bode a je prekazka s pravdepodobnostı p(O)a=10%

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


L

x

p(L|MO)

p(L|ME)

x

p(M

O|Ln)

p(MO)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


L

x

p(L|MO)

p(L|ME)

x

p(M

O|Ln)

p(MO)

p(MO|L1)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


L

x

p(L|MO)

p(L|ME)

x

p(M

O|Ln)

p(MO)

p(MO|L1)

p(MO|L2)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


L

x

p(L|MO)

p(L|ME)

x

p(M

O|Ln)

p(MO)

p(MO|L1)

p(MO|L2)

p(MO|L3)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Prıklad - Moznostnı vypocet

L

x

p(L|MO)

p(L|ME)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


L

x

p(L|MO)a

p(L|ME)a

a

p(L|MO)

p(L|ME)

1. Init: O(M)a =0.5

0.5= 1

2. Merenı1 (L1): λ(L1|M)a =0.22

0.65= 0.33

O(M|L1)a = λ(L1|M)a ·O(M)a = 0.33 · 1 = 0.33

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


L

x

p(L|MO)a

p(L|ME)a

a

p(L|MO)

p(L|ME)

1. Init: O(M)a = O(M|L1)a = 0.33

2. Merenı2 (L2): λ(L2|M)a =0.22

0.65= 0.33

O(M|L2)a = λ(L2|M)a ·O(M)a = 0.33 · 0.33 = 0.10

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


L

x

p(L|MO)

p(L|ME)

x

O(M|Ln)

O(M)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


L

x

p(L|MO)

p(L|ME)

x

O(M|Ln)

O(M)

O(M|L1)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


L

x

p(L|MO)

p(L|ME)

x

O(M|Ln)

O(M)

O(M|L1)

O(M|L2)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


L

x

p(L|MO)

p(L|ME)

x

O(M|Ln)

O(M)

O(M|L1)

O(M|L2)

O(M|L3)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Mrızka obsazenosti (Occupancy grid)

• Cely svet disjunktne metricky (ekvidistantne) rozdelıme na oblasti

◦ 1D: ekvidistantnı useky

◦ 2D: ekvidistantnı ctvercova mrız

◦ 3D: ekvidistantnı krychlova mrız

• Kazde bunce priradıme pravdepodobnost p(O) = 0.5

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy


• Cely svet disjunktne metricky (ekvidistantne) rozdelıme na oblasti◦ 1D: ekvidistantnı useky




Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy






Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy






Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy






Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Krok 1. - Sebelokalizace

Zjistıme polohu a smer senzoru (sebelokalizace)• 1D: S = (Sx, Ssgn)

• 2D: S = (Sx, Sy, Sϕ)

Sϕ

• 3D: S = (Sx, Sy, Sz, Sθ, Sψ, Sϕ)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Krok 2. - Projekce merenı

Zmerıme senzory okolı robotu• 1D: M = (L, σ)

• 2D: M = (L, σα, σβ)

• 3D: M = (L, σα, σβ, σγ)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Krok 3. - Aplikace Bayese na mrızku

• Zjistıme bunky ktere merenı ovlivnilo• Pro kazdou bunku spocıtat model senzoru◦ Pro pravdepodobnostnı model p(L|MO) a p(L|ME)◦ Pro moznostnı model λ(L|M)

• Pro kazdou bunku mapy aplikovat bayese◦ Pro pravdepodobnostnı model p(MO|L) a p(ME |L)◦ Pro moznostnı model O(M|L)

• 1D: M = (L, σ)

• 2D: M = (L, σα, σβ)

• 3D: M = (L, σα, σβ, σγ)

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Prıklady mapy 2D

Prekazka

Neznamo

Volno

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Prıklady mapy

Mapa



Model senzoru

Prıklad

Mrızka obsazenosti


Vyskova mapa

Navigace v mape

Pomocnealgoritmy

Vyskova mapa

• Occupancy Grid obsahuje prılis mnoho informacı pro navigaci vexterieru

• Pro navigaci v exterieru je lepsı ukladat informaci o vysceterenu/prekazky v dane mape.

• Z vyskove mapy (vrstevnice) lze vysledovat prujezdnost vozidla aprekazky

Mapa

Tvorba mapy

Navigace v mapeMotivace

Potencialove pole

Mrızka obsazenosti

Graf viditelnosti

Prımkova dekompozice

Trojuhelnıkovadekompozice

Pomocnealgoritmy

Kudy tudy ?

A

B

?

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Potencialove pole

A

B

• 1. Vezmeme mapu

• 2. Vytvorıme potencial cıle• 3. Pricteme potencial objektu• 4. Najdeme cestu se stale klesajıcım gradientem

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Potencialove pole

A

B

• 1. Vezmeme mapu• 2. Vytvorıme potencial cıle

• 3. Pricteme potencial objektu• 4. Najdeme cestu se stale klesajıcım gradientem

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Potencialove pole

A

B



Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Potencialove pole

A

B



Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Potencialove pole

A

B

• 1. Vezmeme mapu• 2. Vytvorıme potencial cıle• 3. Pricteme potencial objektu

• 4. Najdeme cestu se stale klesajıcım gradientem

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Potencialove pole

A

B

• 1. Vezmeme mapu• 2. Vytvorıme potencial cıle• 3. Pricteme potencial objektu• 4. Najdeme cestu se stale klesajıcım gradientem

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Mrızka obsazenosti

A

B

• 1. Vezmeme mapu

• 2. Namapujeme na ni rastr obsazenosti• 3. Vytvorıme spoje mezi neobsazenymi vrcholy• 4. Nalezneme nejkratsı cestu pres neobsazene vrcholy

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Mrızka obsazenosti

A

B

• 1. Vezmeme mapu• 2. Namapujeme na ni rastr obsazenosti

• 3. Vytvorıme spoje mezi neobsazenymi vrcholy• 4. Nalezneme nejkratsı cestu pres neobsazene vrcholy

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Mrızka obsazenosti

A

B

• 1. Vezmeme mapu• 2. Namapujeme na ni rastr obsazenosti• 3. Vytvorıme spoje mezi neobsazenymi vrcholy

• 4. Nalezneme nejkratsı cestu pres neobsazene vrcholy

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Mrızka obsazenosti

A

B

• 1. Vezmeme mapu• 2. Namapujeme na ni rastr obsazenosti• 3. Vytvorıme spoje mezi neobsazenymi vrcholy• 4. Nalezneme nejkratsı cestu pres neobsazene vrcholy

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Graf viditelnosti

A

B

• 1. Vezmeme mapu

• 2. Najdeme vrcholy vsech objektu v mape• 3. Spojıme vrcholy, ktere jsou videt• 4. Nalezneme nejkratsı cestu pres hrany

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Graf viditelnosti

A

B

• 1. Vezmeme mapu• 2. Najdeme vrcholy vsech objektu v mape

• 3. Spojıme vrcholy, ktere jsou videt• 4. Nalezneme nejkratsı cestu pres hrany

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Graf viditelnosti

A

B

• 1. Vezmeme mapu• 2. Najdeme vrcholy vsech objektu v mape• 3. Spojıme vrcholy, ktere jsou videt

• 4. Nalezneme nejkratsı cestu pres hrany

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Graf viditelnosti

A

B

• 1. Vezmeme mapu• 2. Najdeme vrcholy vsech objektu v mape• 3. Spojıme vrcholy, ktere jsou videt• 4. Nalezneme nejkratsı cestu pres hrany

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B

• 1. Vezmeme mapu

• 2. Najdeme vrcholy vsech objektu v mape• 3. Spojıme nejblizsı vrcholy, ktere jsou videt

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B


• 3. Spojıme nejblizsı vrcholy, ktere jsou videt

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B

• 1. Vezmeme mapu• 2. Najdeme vrcholy vsech objektu v mape• 3. Spojıme nejblizsı vrcholy, ktere jsou videt

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B

• 4. Pulıme polygony, v nutnosti pulıme delsı stranu

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B

• 4. Pulıme polygony, v nutnosti pulıme delsı stranu

• 5. Vytvorıme graf pres stredy prımek• 6. Najdeme nejkratsı cestu

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B

• 4. Pulıme polygony, v nutnosti pulıme delsı stranu• 5. Vytvorıme graf pres stredy prımek

• 6. Najdeme nejkratsı cestu

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B

• 4. Pulıme polygony, v nutnosti pulıme delsı stranu• 5. Vytvorıme graf pres stredy prımek


Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B

• 4. Pulıme polygony, v nutnosti pulıme delsı stranu• 5. Vytvorıme graf pres stredy prımek• 6. Najdeme nejkratsı cestu

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy

Trojuhelnıkova dekompozice

A

B

• 1. Vezmeme mapu

• 2. Najdeme vrcholy vsech objektu v mape• 3. Spojıme nejblizsı vrcholy, ktere jsou videt

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B


• 3. Spojıme nejblizsı vrcholy, ktere jsou videt

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B

• 1. Vezmeme mapu• 2. Najdeme vrcholy vsech objektu v mape• 3. Spojıme nejblizsı vrcholy, ktere jsou videt

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B

• 4. Optimalizujeme stejne jako v predchozım prıpade

Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B

• 4. Optimalizujeme stejne jako v predchozım prıpade• 5. Vytvorıme graf pres teziste trojuhelnıku


Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B

• 4. Optimalizujeme stejne jako v predchozım prıpade• 5. Vytvorıme graf pres teziste trojuhelnıku


Mapa

Tvorba mapy


Potencialove pole

Mrızka obsazenosti

Graf viditelnosti



Pomocnealgoritmy


A

B

• 4. Optimalizujeme stejne jako v predchozım prıpade• 5. Vytvorıme graf pres teziste trojuhelnıku• 6. Najdeme nejkratsı cestu

Mapa

Tvorba mapy

Navigace v mape

Pomocnealgoritmy

Hledanı nejkratsı cesty vgrafu

Nejkratsı cesta v grafu (Dijkstra)

S B

C D

E

F

G

H

I

E

Mapa

Tvorba mapy

Navigace v mape

Pomocnealgoritmy



S B

C D

E

F

G

H

I

E

0

Mapa

Tvorba mapy

Navigace v mape

Pomocnealgoritmy



S B

C D

E

F

G

H

I

E

0 1

1 1

Mapa

Tvorba mapy

Navigace v mape

Pomocnealgoritmy



S B

C D

E

F

G

H

I

E

0 1

1 1

2

2

2

2

Mapa

Tvorba mapy

Navigace v mape

Pomocnealgoritmy



S B

C D

E

F

G

H

I

E

0 1

1 1

2

2

2

2

3

3

Mapa

Tvorba mapy

Navigace v mape

Pomocnealgoritmy



S B

C D

E

F

G

H

I

E

0 1

1 1

2

2

2

2

3

3

Mapa

Tvorba mapy

Navigace v mape

Pomocnealgoritmy



S B

C D

E

F

G

H

I

E

0 1

1 1

2

2

2

2

3

3

Mapa

Tvorba mapy

Navigace v mape

Pomocnealgoritmy



S B

C D

E

F

G

H

I

E

0 1

1 1

2

2

2

2

3

3

Mapa

Tvorba mapy

Navigace v mape

Pomocnealgoritmy



S B

C D

E

F

G

H

I

E

0 1

1 1

2

2

2

2

3

3

S B

C D

E

F

G

H

I

E

S-D-I-E

Dekuji za pozornost

25. brezna 2013

Ing. Frantisek Burian

Date post:	07-Mar-2021
Category:	Documents
Upload:	others
View:	1 times
Download:	0 times

Tvorba map v roboticerobotika/prednasky/2014...Mapa Motivace Metricka´ mapa Topologicka´ mapa...

Documents