Mouse in Maze with robot E-Puck

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.

Plné znenie pravidiel súťaže je možné nájsť na http://www.robotika.sk/contest/2011/umouse.php

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

Keďž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ôvodov 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 rozmery 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ž zdieľajú 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 rozmery 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ť.

Algoritmus

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. Nájdi 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 cieli.

Problémy s druhou vrstvou

Napriek počítadlu krokov motorov, nie je možné považovať tieto dáta za presné na určovanie pozície robota. Toto patrilo medzi náš najväčší 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.

Výsledok

Vyššie uvedené problémy sa nám nepodarilo úplne vyriešiť. Kvôli tomu sa často (hlavne pri väčších bludiskách) stáva, že robot narazí do steny, pretože je vychýlený a zachytí nesprávnu informáciu pri získavaní perceptu.

Zdrojové 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

Rady ostatným, ktorí chcú programovať robota E-puck

Ako začať

• Je potrebné nainštalovať najnovšiu verziu MPLAB IDE http://www.microchip.com/Microchip.WWW.SecureSoftwareList/secsoftwaredownload.aspx?device=en019469&lang=en&ReturnURL=http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=1406&dDocName=en019469&part=SW007002#

• Taktiež treba nainštalovať najnovšiu verziu kompilátora MPLAB C Compiler for dsPIC DSCs http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=1406&dDocName=en535363

• E-book getting started: http://www.e-puck.org/index.php?option=com_phocadownload&view=category&id=5:tutorials&Itemid=38

  POZOR! Jedná sa o starú verziu, niektoré veci treba robiť ináč, dobrým zdrojom je tento link, na ktorom je popísané, čo konkrétne je uvedené nesprávne v príručke Getting Started: http://ssr.wikidot.com/cs198-e-pucks/

• Aby sa program dal kopírovať cez Bluetooth do robota, je potrebné nainštalovať Tiny Bootloader. Inštalačný súbor je spomínaný aj v návode uvedenom vyššie "tinybld198". Je ho možné stiahnuť zo stránky http://www.etc.ugal.ro/cchiculita/software/tinyblddownload.htm kde treba kliknúť na odkaz Download Tiny PIC Bootloader.

• EpuckMonitor - umožňuje ovládať robota cez GUI. Program nie je úplne funkčný, obsahuje veľa chýb. Nepodarilo sa nám zobraziť obraz z kamery, zakaždým to zmrzlo. http://www.e-puck.org/index.php?option=com_phocadownload&view=file&id=46:epuckmonitor&Itemid=38

• Kompletné knižnice a vzorové programy (pre aktuálnu verziu MPLAB IDE) http://www.e-puck.org/index.php?option=com_phocadownload&view=file&id=42:e-puck-svn-snapshot&Itemid=38

Užitočné zistené fakty o robotovi

• Robot má selektor na výber až z 16tich módov. Keďže v robotovi môže byť nahraný len jeden program je vhodné využiť tento selektor v programe tak, že na začiatku programu (po resete robota) sa prečíta poloha selektora a v závislosti od nej sa vykoná jedna z procedúr. Môžeme teda naprogramovať program, ktorý bude emulovať, že robot obsahuje X rôznych programov.

• Step counter (počítadlo krokov kolies) ráta kroky do záporných hodnôt, ak je rýchlosť záporná - robot cúva, alebo zabáča. 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ť. Raz sa môže otočiť o väčší raz o menší uhol. Je to spôsobené nepresným mechanickým vyhotovením kolies a šmykmi, ktoré robot dostáva pri rýchlom striedaní rôznych pohybov.

• 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

Fotky nášho robota

E-puck s pridaným extra kompasom

E-puck - inside

E-puck - zvyšok jeho častí

Iné fotky

E-puck

E-puck

E-puck