czech english
Robotika.cz » Průvodce » {CleanBug}

CleanBug

Autor: Martin Dlouhý, 2009-11-18
algoritmus uklízecí cesty pro jednoduché automaty

Hledání uklízecí cesty, někdy nazývané pokrývací cesty, je poměrně častá úloha pro mobilní roboty. Pokusíme se zde rozšířit základní úlohu pro jednoduché deterministické automaty s omezenou pamětí s tím, že o uklízeném prostoru nebudeme mít žádné předběžné informace.

Motivace

Jak již název napovídá, aplikace uklízecí cesty je v první řadě pro automatické domácí vysavače, vytírací a leštící automaty. Co možná už zřejmé není, že se vlastné jedná o pokrývací cestu a můžete tímto způsobem např. hledat miny, sekat zahradu nebo sbírat golfové míčky na tréningovém hřišti.
Robotické vysavače stejně jako robotické sekačky už nějaký čas na trhu jsou. Jejich algoritmy typicky využívají náhodné procházky, o které lze dokázat, že dáte-li robotu dostatek času, bude prostor s vysokou pravděpodobností uklizen/posekán.
V tomto článku se však s pravděpodotnostním řešením nespokojíme. Chceme algoritmus, který 100% projde všechny dostupné pozice a nevynechá jedinou. Pokud zůstane nějaký kout neuklizený, tak vám to asi nebude tak vadit jako kdyby na poli zůstala zapomenutá mina. To je asi přesvědčivá úloha, kdy se s pravděpodobností nespokojíte.

Deterministické uklízení

Lze sestavit deterministický algoritmus na dokonalé uklizení místnosti, který by používal jen pár registrů jako Bug algoritmy? Odpověď je ano, i když první řešení se vám asi příliš líbit nebude. Na druhou stranu robot o svém prostředí zatím vůbec nic neví a jak ho bude poznávat, tak si toho moc nebude pamatovat, takže úloha to rozhodně triviální není.

Definice robota

Pro zjednodušení budeme předpokládat kruhového robota, který se dokáže otočit na místě a celým svým tělem pokrývá/uklízí prostor. Po překážkách budeme požadovat, aby byly statické a s konečným obvodem. Náš robot bude vybaven senzory pro detekci kolize s překážkou a algoritmem objíždění. Konečně, jako u bug algoritmů, robot bude znát v každém okamžiku svoji absolutní pozici.

Pokrytí prázdného prostoru

Začneme ve velkém prázdném prostoru. Jak ho uklidit, když ještě neznáme ani jeho hranice? Asi vás napadne nějaké postupné šrafování, nebo vzor orby na poli, ale oboje se typicky drží nějaké strany a o ní náš robot zatím nic neví. Pro startovní pozici někde uprostřed místnosti se asi jako nejlepší jeví spirála, která s každým půlkruhem naroste o velikost robota (viz obrázek).

Překážky

Co si má robot počnout, pokud při uklízení po spirále z předešlého odstavce narazí na překážku? Zkusíme upravený algoritmus Bug1:
  1. vydej se po spirále
  2. pokud narazíš na překážku označ si tento bod H (hit point) a obcházej překážku
  3. monitoruj nejbližší další bod na spirále (označ jej L = leave point) a ujetou vzdálenost
  4. po návratu do H zvol kratší cestu zpět do L
  5. pokud nebyl nalezen žádný leave point KONEC - místnost je uklizena
  6. GOTO 1
Nyní se pokusíme odhadnout maximální možnou délku cesty pomocí algoritmu CleanBug1:

P < D + 1.5 ∑i nipi/2

kde D je vzdálenost ujetá po spirále a odpovídá ploše místnosti/průměr robota, pi jsou obvody jednotlivých překážek a násobící faktor ni odpovídá počtu průsečíků spirály s i-tou překážkou.

CleanBug2 s pamětí

Pokud budeme analyzovat chovaní CleanBug1, tak zjistíme, že nejvíce času algoritmus stráví objížděním (znovuzmapováním) překážek, které mají mnoho průsečíků s naší spirálou. Stačí mu sice pamatovat si dvě souřadnice (hit point a leave point) a dvě vzdálenosti (aktuální ujetá vzdálenost od hitpointu a vzdálenost od leave pointu), ale překážku musí vždy 1.5x objíždět. Co kdyby si robot mohl zapamatovat např. 100 pozic/vzdáleností?
  1. vydej se po spirále
  2. pokud narazíš na překážku označ si tento bod H (hit point)
  3. pokud máš H v poznámkové paměti s odpovídajícím L a směrem, použij je k objetí překážky a vymaž je z poznámkové paměti a GOTO 1
  4. obcházej překážku a monitoruj průsečíky se spirálou. Podle směru průsečíku si je zapisuj jako další H nebo L = leave point + ujetou vzdálenost do poznámkové paměti
  5. pokud dojde místo v poznámkové paměti odmaž nejvzdalenější body na spirále
  6. po návratu do H zvol kratší cestu zpět do L
  7. pokud nebyl nalezen žádný leave point KONEC - místnost je uklizena
  8. GOTO 1
Pokud má robot dostatek paměti, tak při prvním objezdu může zmapovat všechny přejezdy tj. dalši Hitpointy a Leave pointy. Odpovídající páry a doporučený směr dalšího objíždění pak je třeba analyzovat při dokončení objezdu mapované překážky.

CleanBug3 se znalostí prostředí

Co kdyby jste CleanBug2 s dostatečnou pamětí znova pustili v úplně stejném prostředí ze stejného startu? Nešlo by to v druhém průchodu uklidit ještě „chytřeji”?
Z dat, co nám nasbíral CleanBug2, máme vlastně graf cest (hran) a křižovatek (vrcholy, průsečíky). Hodilo by se nám projít všechny hrany grafu, tj. hledáme Eulerův tah (jednotažky, nakreslení domečku jedním tahem). Pro Eulerův tah bychom ale potřebovali, aby všechny vrcholy měli sudý stupeň. V našem grafu ale jak na potvoru všechny vrcholy (s vyjímkou startu) mají stupeň 3. Je třeba tedy některé hrany zdvojit, což můžeme jednoduše udělat pro každou překážku zvlášť — zdvojíme každou druhou hranu.
Pro vyhledání trasy lze použít algoritmus „lepení uch”. Jede, dokud nedorazí na křižovatku, kde už jsou všechny hrany použité. Pak vybere libovolný vrchol na cestě, kde ještě nějaké hrany zbývají a pak přilepí další „ucha”.

Závěr

V tomto článků jsme ukázali příklad deterministického automatu se znalostí své pozice, který dokáže spolehlivě pokrýt předem neznámé prostředí. Ukázali jsme i vylepšení, pokud má robot k dispozici větší paměť případně informace z předešlého uklízení. Příjde vám to příliš jednoduché? Zkuste najít lepší algoritmus, který např. bude realizovat optimalizaci CleanBug3 ještě před dokončením prvního mapování …
Pokud se Vám něco z toho článku přišlo špatně nebo Vám některá část přišla méně srozumitelná, můžete se nám ozvat pomocí našeho kontaktního formuláře.

Pošlete email redakci.
Všechny materiály, které máme k dispozici, jsou již součástí článku, na který reagujete (tj. pokud tam tedy není např. plánek na stavbu, je to proto, že nic takového nemáme).

Vaši zprávu se bohužel nepodařilo odeslat, ale můžete nám napsat sami na adresu

Vaše zpráva byla úspěšně odeslána

Pro odeslání formulář je třeba mít zapnutý javascript.