Multirobotická kooperativní inspekce

Multirobotická kooperativní inspekce prostˇredí

Diplomová práce

Multirobotická kooperativní inspekce prostˇredí Diplomová práce Intelligent and Mobile Robotics Group Gerstner Laboratory for Intelligent Decision Making and Control Czech Technical University in Prague

15/06/2009

laboratory

Gerstner Jan Maˇcák, 2009

Gerstner Laboratory - Intelligent and Mobile Robotics Group

1 / 11


Diplomová práce

Pˇrehled - obsah a cíle práce Pojmy • inspekce prostˇredí - optimální projetí známé mapy s cílem

ˇ rit každý bod volného prostoru nameˇ • multirobotická - robotu˚ bude více než jeden • kooperativní - roboty budou spolupracovat

Motivace • hledání pˇredmet ˇ u, ˇ ˚ zranených lidí • hlídání budov

Cíle práce • rˇešení inspekˇcní úlohy • využití harmonických funkcí pˇri plánování cesty mob. robotu • experimentální oveˇ ˇ rení výsledku˚ laboratory



2 / 11

Pˇrístup k ˇrešení


Diplomová práce

ˇ Rešení inspekˇcní úlohy

• Známá mapa • Volný prostor je reprezentován ˇ jako polygon s derami.

Dekompozice na podproblémy • nalezení meˇ ˇ ricích míst, • úloha Art Gallery Problem,

• plán navštívení meˇ ˇ ricích míst, • úloha Multiple Traveling Salesmen Problem, • plánování cesty.

laboratory



3 / 11



Diplomová práce





laboratory



3 / 11



Diplomová práce





laboratory



3 / 11



Diplomová práce

Plánování cesty • Cesta = spojnice bodu˚ ležící celá ve volném prostoru • Kritéria • délka, • hladkost, • bezpeˇcnost. • Prohledávání volného prostoru — cˇ asto oblast v R n . • Vzhledem k mohutnosti množiny nelze prohledat kompletneˇ • náhodné vzorkování prostoru a detekce kolize, • diskretizace prostoru.

laboratory



4 / 11



Diplomová práce

Harmonická funkce • cesta je dána gradientem této funkce • splnuje ˇ Laplaceovu rovnici

∆f = 0, ∆ =

n X ∂2 ∂xk2 k =1

• extrémy pouze na hranici oblasti • modelování pˇrekážek okrajovými

podmínkami • Dirichlet - f (x, y ) = g ∂u • Neumann - ∂n =g

ˇ 3D vizualizace prub ˚ ehu harmonické funkce

Nevýhody • težké ˇ získat ˇrešení analyticky - nutno použít metod numerické matematiky laboratory



5 / 11


Pˇrehled výsledku˚

Diplomová práce

Numerické metody ˇ Metoda konecných diferencí • soustava linerárních rovnic nad pravidelnou symetrickou sítí

ˇ Metoda konecných prvku˚ • soustava lineárních rovnic

nad libovolnou oblastí pokrytou koneˇcnými prvky triangulace

Výhody a nevýhody MKD MKP

tvar oblasti – +

více dimenzí + –

složitost + –

Popis okrajovými podmínkami Dirichlet Neumann Smíšený

omezení výpoˇcetní pˇresností ˇ singularita, špatná podmínenost netrpí žádným z omezení laboratory



6 / 11


Diplomová práce


Generování cesty • gradientní algoritmus

1000 4

• varianty • cesta po vrcholech • cesta po koneˇcných

800 700

prvcích ˇ zjemnováním triangulace 1080 204

15 9

10

500 400 8 300 200

277 57

16

600

• iterované hledání

∆ t [ms]

3

900

15070 5815

5

7 6

12 13

11 14

17

100 01 200

2 400

600

800

1000

1200

1400

cesty z vybraných bodu˚ prostoru

ˇ Hodnotami okrajových podmínek lze ovlivnovat vzdálenost, ve které bude robot míjet pˇrekážku. laboratory



7 / 11


Diplomová práce


Pˇrínosy harmonické funkce • Cesta na zobecnené ˇ místo • Rozložení složité mapy • Prostˇredí s více cíli 1000 4

3

900 800 700

16 9

600

15 10 17

500 400 8 300

5

7 1812 6 13

11 14

200 100 01 200

2 400

600

800

1000

1200

1400 laboratory



8 / 11


Diplomová práce


Pˇrínosy harmonické funkce • Cesta na zobecnené ˇ místo • Rozložení složité mapy • Prostˇredí s více cíli

1000 4

3

800

600

1000 4

3

800 16 9

400 5

8

15 10

17

7 12 6 13

600

16 9

400

11 14

5

200

8

15 10

17

7 12 18 17 6 13

11 14

200

01 500

1000

2 1500

01 500

1000

2 1500 laboratory



8 / 11


Diplomová práce


Pˇrínosy harmonické funkce • Cesta na zobecnené ˇ místo • Rozložení složité mapy • Prostˇredí s více cíli

1000 4

3

800

18 16 9

600 400

5 200 01 200

Jan Maˇcák, 2009

8

15 10

7 6

12 13

19

11 14

17 2 400

600

800

1000

1200

1400


laboratory

Gerstner

8 / 11


Diplomová práce

Výsledky experimentu˚

Zhodnocení kvality cest • Cesta získaná využitím harmonické funkce oproti cesteˇ získané

ohodnocením triangulace Dijkstrovým algoritmem: • lépe obtéká pˇrekážky, • je prum ˇ eˇ o 15 % delší, ˚ ern • má menší maximální kˇrivost, je proto v praxi lépe realizovatelná. 1000 4

vAPF [m/s]

3

1

900 800

ωAPF [rad/s] vSP [m/s]

0.8

700

16

15 9

10

ωSP [rad/s]

0.6

600 500

0.4 400 8 300 200

5

7 6

12 13

11

0.2

14

17

0 100 01 200

400

600

800

1000

1200

1400

2

1600

−0.2

0

500

1000

1500 t[s]

2000

2500

3000

laboratory



9 / 11


Diplomová práce

Výsledky experimentu˚

ˇ Rešení inspekˇcní úlohy 5000

5000

4500

4500

4000

4000

3500

3500

3000

3000

2500

2500

2000

2000

1500

1500

1000

1000

500

500

0

0 0

500

1000

1500

2000

2500

3000

3500

4000

0

500

1000

1500

2000

2500

3000

3500

4000

• Celková délka cest ˇrešení je o 6 % vetší ˇ než nejmenší možná. • Celkový cˇ as realizace inspekce je o 3 % kratší než realizace

inspekce s nejkratšími cestami. • Cesta dle harmonické funkce mení ˇ smer ˇ po malých krocích, a

proto nemusí robot v zatáˇckách výrazneˇ zpomalovat. laboratory



10 / 11


Shrnutí

Diplomová práce

Shrnutí inspekˇcní úloha ˇrešena dekompoziˇcním pˇrístupem, implementovány dveˇ metody pro aproximaci ˇrešení PDE, cesty plánovány využitím harmonického potenciálu, identifikovány další zajímavé možnosti využití harmonických funkcí pˇri plánování pohybu, • provedeno srovnání výsledku˚ s jinými plánovacími pˇrístupy, • úspešn ˇ eˇ proveden reálný experiment. • • • •

laboratory



11 / 11

Multirobotická kooperativní inspekce

Recommend Documents