| Seznam |
| Téma: | Srovnání algoritmů pro hlídačův problém a problém pokrytí |
|---|---|
| Katedra: | Katedra kybernetiky |
| Vedoucí: | IMR |
| Vypsáno jako: | Diplomová práce, Bakalářská práce, Semestrální projekt |
| Popis: | • Problém hlídačovy cesty spočívá v nalezení optimální (tj. nejkratší nebo nejrychlejší) trasy v polygonálním prostředí s dírami, která garantuje vizuální pokrytí celého prostředí (tj. hlídač po projití výsledné trasy uvidí všechny body prostředí). Standardní formulace problému uvažuje bodového hlídače se všesměrovým zorným polem a neomezeným poloměrem viditelnosti. Oproti tomu robotická formulace uvažuje kruhový robot s poloměrem r a omezeným poloměrem viditelnosti senzoru d, což vede na koncept tzv. d-viditelnosti: robot vidí daný bod právě tehdy, pokud úsečka spojující tento bod se středem robotu neprotíná překážku a je kratší než hodnota d.
• Pokud bychom uvažovali d = r, tj. robot vidí jen “pod” sebe, potom se hlídačův problém redukuje na variantu problému pokrytí, anglicky coverage planning problem. Coverage planning je široká kategorie specifických problémů a algoritmů. Výhoda algoritmů pokrytí je jejich relativní jednoduchost ve srovnání s algoritmy pro hlídačův problém, protože neuvažují d-viditelnost. Nevýhoda je, že pro d >> r, coverage planning nezaručuje 100% vizuální pokrytí. Navzdory podobnosti těchto dvou problémů zatím nevíme o žádném jejich srovnání v literatuře. • Cílem práce bude pro různé hodnoty r a d experimentálně srovnat algoritmus pro hlídačův problém, který bude studentovi poskytnut, s vhodným algoritmem pokrytí. Kritéria pro srovnání budou procento pokrytí, délka výsledné trasy a výpočetní čas. Součástí práce bude rešerše algoritmů pokrytí, výběr vhodného algoritmu pro srovnání, jeho implementace a experimentální ověření. • Téma je vhodné pro softwarově a algoritmicky zaměřené studenty. • Nabízím aktivní přístup k vedení práce. • Kontakt: jan.mikula@cvut.cz • Web: http://imr.ciirc.cvut.cz/People/Jan • Laboratoř: http://imr.ciirc.cvut.cz/Lab/Lab • IMR CIIRC ČVUT |