Difference between revisions of "Mouse in Maze with robot E-Puck"

From RoboWiki
Jump to: navigation, search
(→‎Stratégia robota)
(→‎Prehľadávanie)
Line 35: Line 35:
 
Vhodnými funkciami dokážeme s takouto reprezentáciou pohodlne pracovať. Rozhranie tvorí funkcia mazeCell, ktorá pre políčko so súradnicami [x, y] vráti údaje o stenách susediacich s týmto políčkom a funkcia addPercept, ktorá na aktuálnu pozíciu robota pridá do poľa dáta o stenách, ktoré momentálne robot vidí. Taktiež treba brať do úvahy fakt, že robot vidí percept zrotovaný v závislosti od jeho rotácie a pred doplnením dát percept správne otočiť.
 
Vhodnými funkciami dokážeme s takouto reprezentáciou pohodlne pracovať. Rozhranie tvorí funkcia mazeCell, ktorá pre políčko so súradnicami [x, y] vráti údaje o stenách susediacich s týmto políčkom a funkcia addPercept, ktorá na aktuálnu pozíciu robota pridá do poľa dáta o stenách, ktoré momentálne robot vidí. Taktiež treba brať do úvahy fakt, že robot vidí percept zrotovaný v závislosti od jeho rotácie a pred doplnením dát percept správne otočiť.
  
−
== Prehľadávanie ==
+
=== Pseudokód ===
 +
# Získaj aktuálny percept a ulož ho do reprezentácie.
 +
# Spusti prehľadávanie do šírky (v pamäti) a zastav ho na políčku, ktoré obsahuje aspoň jednu takú hranu, o ktorej ešte nevieme, či je to stena. (Vďaka prehľadávaniu do šírky dostaneme najbližšie také políčko)
 +
# Ak také políčko existuje, rekonštruuj cestu k tomuto políčku, choď po nej a skoč na krok 1.
 +
# Ak také políčko neexistuje, skoč na krok 5.
 +
# Spusti prehľadávanie do šírky (v pamäti) a zastav ho na políčku [0, 0] (štart).
 +
# Rekonštruuj cestu a choď po nej.
 +
# Najdi v reprezentácií súradnice cieľa.
 +
# Ak cieľ existuje, spusti prehľadávanie do šírky (v pamäti) a zastav ho na súradniciach cieľa.
 +
# Ak sa podarilo dostať prehľadávaním do šírky do cieľa, rekonštruuj cestu a choď po nej.
 +
# Robot je v ciely.
  
 
== Užitočné zistené fakty o robotovi ==
 
== Užitočné zistené fakty o robotovi ==

Revision as of 23:31, 26 April 2011

E puck - devices

Myš v bludisku

Príklad bludiska

Problém myši v bludisku spočíva v zostrojení a naprogramovaní (v našom prípade sme pracovali už so zostrojeným robotom) robota, ktorý je schopný prejsť bludiskom za čo najkratší čas.

Bludisko pozostáva z mriežky zloženej zo štvorcov s rozmermi 18cm x 18cm. Počet štvorcov v mriežke je maximálne 16 x 16. Steny bludiska sú 5cm vysoké a 1,2cm hrubé. Celé bludisko je ohraničené stenami, vďaka čomu sa nemôže stať, že by ho robot opustil. Štart bludiska sa nachádza vždy v jednom zo štyroch rohov a cieľ tvorí štvorica štvorcov, medzi ktorými nie sú steny (2 x 2).

Robot môže prejsť bludisko viacej krát, ráta sa vždy najkratší čas, za ktorý sa robotovi podarilo prejsť zo štartu do cieľového štvorca.

Základné informácie o robotovi E-puck

E-puck je robot s open-source hardwareom. Podstava robota je kruhového tvaru s priemerom 7cm. Výška robota je 5cm a hmotnosť dosahuje 200g. Disponuje 8kB RAM a 144kB FLASH pamäťami, Bluetooth modulom, ôsmimi IR senzormi, 3D akcelerometrom, tromi mikrofónmi, reproduktorom, farebnou VGA kamerou, 2 krokovými motormi s prevodom 50:1, vďaka ktorému je možné pohybovať s robotom rýchlosťou 13cm/s. Robota je možné programovať v jazyku C.

Viacej informácií o robotovi je možné nájsť na http://en.wikipedia.org/wiki/E-puck_mobile_robot

Stratégia robota

Kedže robot môže prejsť cez bludisko viacej krát a dôležitý je najkratší čas, rozhodli sme sa, že vhodnou stratégiou bude najprv namapovať a zapamätať si celé bludisko, vrátiť robota na štartovacie políčko, nájsť najkratšiu cestu do cieľa a ísť po nej.

Abstrahovanie problému do diskrétneho sveta

Z dôvodou zjednodušenia testovania programu sme rozdelili problém do dvoch vrstiev.

Prvá vrstva zanedbáva fyzikálne vlastnosti spojitého sveta a pristupuje k riešeniu problému myši v bludisku ako keby sa robot nachádzal v diskrétnom priestore. Robot má teda v tejto reprezentácií celočíselné súradnice [0, 0] - [15, 15] a 4 rôzne otočenia (hore, dole, vľavo a vpravo). Pre každé políčko v štvorcovej sieti je pre každú z jeho 4 hrán (hornú, spodnú, ľavú a pravú) jasne určené, či sa na tejto hrane nachádza stena, nenachádza stena, alebo či robot ešte nevie o výskyte steny.

Druhá vrstva je adaptérom, ktorý umožňuje reálnemu robotovi, ktorý sa nachádza v spojitom priestore pracovať s diskrétnym dátovým modelom. Zabezpečuje vrátenie relevantných údajov o vyskytujúcich sa prekážkach na aktuálnej pozícií robota, otočenie robota o uhol +-90 stupňov a presunutie robota medzi dvomi susediacimi políčkami.

Celá logika (algoritmus) sa teda nachádza v prvej vrstve a teda je k nej možné napísať testy. Vďaka nim sme prvú vrstvu vyladili na počítači bez nutnosti zložitého debugovania programu bežiaceho na robotovi.

Reprezentácia bludiska

Reprezentácia bludiska

Keďže vieme maximálne rozmeri bludiska, stačí nám na jeho reprezentáciu statické dvojrozmerné pole. Na reprezentáciu jednej možnej steny potrebujeme 2 bity (00 - nevieme o stene, 01 - nachádza sa tam stena, 02 - nenachádza sa tam stena). Keby sme si pre každé políčko mali pamätať 4 steny, potrebovali by sme teda 16 x 16 x 4 x 2 = 2048 bitov. Nie je to však nevyhnutné. Niektoré políčka totiž zdielajú tú istú spoločnú stenu. Ak si budeme pamätať každú stenu práve raz a vynecháme hranice bludiska, o ktorých vieme, budeme potrebovať 15 x 16 x 2 x 2 = 960 bitov.

Pre zjednodušenie implementácie používame pole bajtov o veľkosti 15 x 16. Jedným bajtom reprezentujeme 2 steny - jednu vodorovnú so súradnicami [x, y] a jednu zvislú so súradnicami [y, x]. Namapovanie jednotlivých stien na súradnice pola je znázornené na nasledujúcom obrázku. Zobrazené bludisko ma pre zjednodušenie rozmeri 5 x 5.

Vhodnými funkciami dokážeme s takouto reprezentáciou pohodlne pracovať. Rozhranie tvorí funkcia mazeCell, ktorá pre políčko so súradnicami [x, y] vráti údaje o stenách susediacich s týmto políčkom a funkcia addPercept, ktorá na aktuálnu pozíciu robota pridá do poľa dáta o stenách, ktoré momentálne robot vidí. Taktiež treba brať do úvahy fakt, že robot vidí percept zrotovaný v závislosti od jeho rotácie a pred doplnením dát percept správne otočiť.

Pseudokód

  1. Získaj aktuálny percept a ulož ho do reprezentácie.
  2. Spusti prehľadávanie do šírky (v pamäti) a zastav ho na políčku, ktoré obsahuje aspoň jednu takú hranu, o ktorej ešte nevieme, či je to stena. (Vďaka prehľadávaniu do šírky dostaneme najbližšie také políčko)
  3. Ak také políčko existuje, rekonštruuj cestu k tomuto políčku, choď po nej a skoč na krok 1.
  4. Ak také políčko neexistuje, skoč na krok 5.
  5. Spusti prehľadávanie do šírky (v pamäti) a zastav ho na políčku [0, 0] (štart).
  6. Rekonštruuj cestu a choď po nej.
  7. Najdi v reprezentácií súradnice cieľa.
  8. Ak cieľ existuje, spusti prehľadávanie do šírky (v pamäti) a zastav ho na súradniciach cieľa.
  9. Ak sa podarilo dostať prehľadávaním do šírky do cieľa, rekonštruuj cestu a choď po nej.
  10. Robot je v ciely.

Užitočné zistené fakty o robotovi

  • Robot má selektor na výber až 16tich módov, naraz v ňom ale môže byť nahraný len jeden program, teda nahraním nového programu sa prepíše pôvodný. Tento selektor sa však dá využiť v programe tak, že po výbere inej pozície a resetovaní, bude robot robiť niečo iné. Teda si môžme naprogramovať program, ktorý sa bude "tváriť", že obsahuje X rôznych programov a bude volať funkcie podľa aktuálnej pozície selektora.

  • Step counter(rátač krokov kolesa) ráta kroky do záporných hodnôt, ak je rýchlosť záporná (teda robot cúva), treba s tým rátať pri ohraničujúcich podmienkach.

  • Aj napriek step counteru nie je možné presne odsledovať koľko sa robotovi podarilo reálne prejsť, teda napr. raz sa môže otočiť o väčší raz o menší uhol. Toto patrilo medzi náš jediný veľký problém, pretože robot sa čoskoro vychýlil a začal narážať. Používanie senzorov, na vyhýbanie sa stenám, situáciu veľmi nezlepšilo, pretože robot chodil ešte krivšie a nepredvídateľnejšie. V našom poslednom kóde je verzia pohybu pri ktorej postupne zrýchľuje a spomaľuje, čo robotovi presnosť zvýšilo, ale na úkor rýchlosti.

  • Pozície led diód a senzorov na vzdialenosť nie sú umiestnené priamo nad sebou, čo je trochu nepraktické pri testovaní senzorov za pomoci rozsvietenia diód. Použiteľný je aj index 8, ktorý prestaví všetky led diódy naraz.

    E-puck - náčrt pozícií diód
    E-puck - náčrt pozícií senzorov

Pravidlá súťaže

http://www.robotika.sk/contest/2011/umouse.php

Ako začať

Naše výsledné kódy

V ZIP archíve sú dva programy. Maze je implementácia prechodu bludiskom. BTcom slúži ako demonštrácia posielania dát z robota do PC cez bluetooth. Táto ukážka posiela dáta získané cez I2C z kompasu. Media:MazeAndBTCompass.zip

Video nášho robota

Our Photos

E-puck s pridaným extra kompasom
E-puck - inside
E-puck - zvyšok jeho častí

Photos

E-puck
E-puck
E-puck
Retrieved from "https://wiki.robotika.sk/robowiki/index.php?title=Mouse_in_Maze_with_robot_E-Puck&oldid=5738"