GolfBot

GolfBot je robot založený na platforme LEGO NXT a jeho úlohou je autonómne hrať zjednodušenú verziu golfu. GolfBot bol vytvorený ako projekt pre predmet Algoritmy pre AI robotiku. GolfBot počas hrania využíva údaje z kamery a pomocou polynomiálnej regresie sa učí správne hýbať a odpaľovať loptu.

Golfbot

Úloha

Na hracej ploche je vyznačený bod, symbolizujúci dieru, na ktorý robot musí dostať loptu čo najnižším počtom úderov. Je teda potrebné vytvoriť program pre robota, ktorý bude robota navigovať k lopte tak, aby bol schopný vystreliť správnym smerom. Robot pritom potrebuje korigovať silu úderu tak, aby lopta zostala na cieľovom bode, nakoľko je diera iba namaľovaná a lopta nezapadne dnu.

Realizácia

Hracia plocha Golfbota. Nad robotom je na tyči zavesená kamera.

Konštrukcia robota

Robot je zložený zo súčiastok LEGO MINDSTORMS. Má dva nezávislé motory napojené na pásy, čo mu umožňuje okrem pohybu vpred a zatáčania aj otáčanie na mieste. Vpredu má jednoduchú pálku na odpaľovanie loptičky a na jeho vrchnej strane je kartón s farebnými markermi pre snímanie jeho polohy kamerou. Motory ovláda riadiaca kocka NXT, ktorá prijíma príkazy od riadiaceho počítaču cez USB rozhranie.

Riadiaci počítač a kamera

Informáciu o polohe robota a lopty počítač získava z externého snímača Kinect, ktorý je umiestnený zhruba 2m nad zemou. Z tejto polohy počítač následne určí ďalšiu akciu pre robota a cez USB mu daný príkaz pošle. Po vykonaní tohoto príkazu oznámi robot počítaču správu o úspechu.

Implementácia

Pohyb robota

Pohyb robota ovláda NXT kocka podľa pokynov od riadiaceho počítaču. NXT kocka čaká v cykle na príkazy, ktoré po prijatí vykoná a po každej splnenej akcii oznámi jej ukončenie.

Robot prijíma štyry druhy rozkazov

• choď dopredu N dĺžkových jednotiek
• otoč sa na mieste o N rotačných jednotiek
• vystreľ silou N
• ukonči program

počítač jednotky pohybu, streľby a otočenia nepozná a musí sa experimentálne naučiť ako sa robot chová. Použitím tohoto prístupu sa stráca potreba presnej ručnej kalibrácie konštánt a je možno meniť loptu, jazdný povrch a vzdialenosť kamery bez potreby zmeny nastavení programu.

Navigácia

Akcia robota sa volí čisto reaktívne podľa polohy lopty, cieľa, robota a jeho natočenia.

Výber akcie vyzerá približne nasledovne:

1. Ak si tesne za loptou správne sa natoč a vystreľ
2. Ak si v oblasti za loptou, choď bližšie k nej
3. Ak si v oblasti pred loptou choď do oblasti za ňou tak, aby si do nej nenarazil

Použitím týchto pravidiel môžeme vytvoriť motorovú schému, podľa ktorej sa robot bude hýbať.

Schéma navigácie Golfbota. Červený kruh vyjadruje loptu, modrý jamku a zelený chcenú polohu robota - polohu, z ktorej chce robot strieľať.

Učenie

Po každej vykonanéj akcii robot vypočíta zmenu a spolu s parametrom príkazu si ju pre každú akciu uloží. Z týchto dát potom aproximuje polynomiálnou regresiou funkcie pohybu a streľby. Všetky tieto funkcie by mali byť s naším robotom spojité a takmer lineárne a preto nám na aproximáciu regresia postačuje.

• Dáta regresie
• 

  Regresia streľby lopty na cieľ.

• 

  Regresia rotácie robota.

Na obrázku regresie streľby si možno všimnúť, že nafitovaná funkcia neprechádza počiatkom. Tento fakt je zapríčinený konštrukciou pálky, ktorá pri akejkoľvek nenulovej sile pohne loptičkou aspoň o svoju dĺžku.

Spracovanie obrazu

Prepojenie s kamerou a určovanie orientačných bodov

Obraz sme získavali pomocou Kinectu pre XBox 360. Máme dve triedy, Kinect (odvodená od edu.ufl.digitalworlds.j4k.J4KSDK) a Camera (implementuje Runnable).

Hlavný program spúšťa vlákno kamery, ktoré následne pri inicializácii spustí vlákno kinectu v móde J4KSDK.COLOR. Inštancii tredy Kinect je potom poslaná referencia na kameru. Trieda Kinect prekrýva metódu udalosti onColorFrameEvent, ktorá nastáva po zosnímaní farebného obrazu kinectom, pričom tento obraz posiela inštancii kamery cez referenciu volaním jej verejnej metódy setImageFromKinect.

Hlavné vlákno kamery vykonáva cyklicky tieto akcie:

Najprv sa otestuje, či existuje snímka z kamery.

• Ak nie, ukončí iteráciu cyklu a pokračuje ďalšou iteráciou.
• Ak áno:
  1. Vytvorí si novú kópiu obrázku (pre účely spracovania).
  2. Aplikuje gaussovo rozmazanie pracovného obrázka z polomerom 3px.
  3. Skonvertuje obrázok z farebného formátu BGR do LAB.
  4. Pomocou prahovania, nájdeniu najväčšieho spojitého komponentu a priemerovania x, y pozícií pixelov najväčšieho spoločného komponentu nájde stredy kruhových značiek a lopty.
  5. Určia sa polohy cieľa (stred obrázka), lopty (oranžová značka na obrázku), polomer lopty a pozicia robota.
  6. Spočíta sa uhol natočenia robota (podľa zelenej a modrej značky).
  7. Vykreslia sa získané body do náhľadového obrázka.
  8. Hlavné vlákno programu je notifikované o dokončení cyklu kamery (teda sú spočítané potrebné body pre ďalšiu fázu programu hlavného vlákna).

Rozmazanie obrázku gaussiánom

Pre lepší výsledok hľadania najväčšieho spojitého komponentu prahovaním je vhodné jemne rozmazať obrázok na to, aby sme zničili malé medzery v maske vytvorenéj prahovaním, ktoré by mohli rozdeliť spojité objekty na viacero komponentov.

Na rozmazanie obrázka (blur) je použítý rozmazávací algoritmus, využívajúci aproximáciu gaussovej funkcie, ktorý dokáže pracovať v lineárnom čase. Použili sme port algoritmu z JavaScriptu z blogu Ivana Kuckira, nájsť ho je možné na stránke Fastest Gaussian Blur (in linear time) (jedná sa o algoritmus 4 na tejto stránke).

Keďže algoritmus počíta s tým, že obrázok je tvorený poľom bajtov, kde jeden bajt reprezentuje jeden pixel, bolo nutné obrázok rozdeliť na tri obrázky, ktoré reprezentovali jeho červenú, zelenú a modrú farebnú zložku samostatne. Potom, ako algoritmus rozmazania dokončil svoju prácu na každom z týchto rozdelených obrázkov, bolo treba ich opätovne spojiť do jedného obrázka. Na toto nám slúžia metódy separateColor a putColor.

Prevod z RGB do LAB

Keďže zosnímaný obrázok z kamery je vo formáte, kde jeden pixel je určený štyrmi bajtmi s významom: Blue, Green, Red a posledný je vždy nulový (hodnota 0), pričom tieto hodnoty sú v rozsahu od 0 do 255, je treba najprv každý pixel preformátovať do tvaru RGB, kde každá hodnota je float s hodnotou od 0 do 1. Na to máme metódu getPixel s následným predelením každej zložky hodnotou 255.

Každý pixel je potom vložený do statickej metódy triedy CIELab s názvom fromRGB, ktorá vráti hodnotu pixelu vo formáte farieb LAB. Trieda CIELab na prevod z RGB do LAB ešte používa medzikrok, kde každý RGB pixel prevedie do formátu XYZ, z ktorého následne vytvorí LAB formát.

Prahovanie

Prahovanie používame na získanie masky informácií o prítomnosti farebnej informácie v LAB formáte v spracovávanom obrázku. Tento algoritmus (metóda prahuj(float[] from, float[] to)) dostáva minimálnu a maximálnu hodnotu prahu farby v LAB formáte a v obrázku zisťuje, pre každý pixel, či je v rozsahu tejto hodnoty alebo nie je. Ak pixel v rozsahu je, dostane výstupná maska na pozícii pixelu hodnotu 1, v opačnom prípade je použitá hodnota 0.

int[] o = new int[potrebná veľkosť]
for každé x
   for každé y
      if pixel na x a y je medzi from a to
         zapíš do o 1
      else
         zapíš do o 0
return o

Najväčší spojitý komponent

Výstupom z prahovania je maska obsahujúca nuly a jednotky, na pozíciách, kde bola zistená vhodná farba. Algoritmus nájdenia najväčšieho spojitého komponentu prehľadáva pôvodnú masku, v prípade nájdenia hodnoty jedna spustí prehľadávanie do šírky, pričom každý susedný pixel (v každom z 8 smerov) označí hodnotou N. N začína na hodnote 2 a je zvyšovaný po dokončení označenia komponentu, tento číselný údaj je vpisovaný do vstupnej masky. Tento komponent sa hľadá metódou int flood(int px, int py, int[] in, int n), ktorá dostáva súradnice prvého bodu komponentu, masku a číselné označenie komponentu, označí komponent a spočíta počet pixelov v tomto komponente, ktorý následne vráti.

Každý komponent je zapísaný do HashMap, kde kľúč je číslo komponentu a hodnota je počet pixelov v komponente. Po nájdení všetkých komponentov sa určí najväčší z nich a maska sa opäť preznačí na hodnoty 0 a jednoa takto:

• Ak pixel má hodnotu čísla najväčšieho komponentu, bude nastavený na hodnotu 1.
• Ak pixel má inú hodnotu, bude nastavený na 0.

Metóda hľadajúca najväčší spojitý komponent má názov najSpoj.

Určenie stredu a AABB ohraničenia komponentu

Na získanie stredu a AABB ohraničenia komponentu sa používa metóda drawX. Metóda dostáva masku s určeným najväčším spojitým komponentom, pričom pre každý pixel, ktorého hodnota je rovná 1, je pozícia pixelu x a y pripočítaná k ceľkovému súčtu. Rovnako sú pre každé x a y upravené hodnoty premenných maxX, minX, maxY a minY. Výsledný stred je vypočítaný ako pomer súčtu x ku počtu pixlov a súctu y k počtu pixlov.

Výsledok spracovania obrazu a navigácie. V ľavej časti sú označené nájdené body a v pravej je fialovou farbou označený bod, do ktorého chce robot smerovať, aby obišiel loptu.

int[] stred = new int[6]
long sx = 0, sy = 0
int maxX = 0, maxY = 0, minX = width, minY = height, pocet = 0
for každý x
   for každý y
      if pixel x,y patrí komponentu
         sx += x, sy += y, pocet++
         maxX = max(maxX, x)
         maxY = max(maxY, y)
         minX = min(minX, x)
         minY = min(minY, y)
if pocet je 0
   return stred
stred[0] = round(sx / pocet)
stred[1] = round(sy / pocet)
stred[2] = minX
stred[3] = minY
stred[4] = maxX
stred[5] = maxY
return stred

Záver

Skonštruovali sme robota, ktorý samostatne hrá upravenú verziu golfu a vďaka jeho schopnosti učiť sa dokáže po krátkom čase postupne zvyšovať svoju úspešnosť. Ďalej sme implementovali jednoduchý lokalizačný a navigačný systém využitím známych postupov a algoritmov.

Problémy, nedostatky riešenia a návrhy na ich opravu

Konštrukcia robota bola obdĺžníková a pri otáčaní pri lopte robot občas zavadil o loptu. Riešiť tento problém udržiavaním väčšieho odstupu od lopty bolo nedostatočné, lebo robot potom nedosiahol pálkou na loptu. Opraviť tento neduh by bolo možné vytvorením lepšieho odpaľovacieho systému s dlhším dosahom, zmenou tvaru robota alebo vylepšením navigačného algoritmu tak, aby sa k lopte približoval zhruba v smere ktorým chce streliť.

Nepodarilo sa nám zpojazdniť priamu komunikáciu cez Bluetooth, preto bol na komunikáciu použitý USB kábel, ktorý bolo treba držať, aby sa na ňom robot nezasekol pri otáčaní.

Farebné značky boli na robotovi prichytené nepresne a bránili v prístupe k NXT kocke, čo spôsobilo drobné nepresnosti pri pohybe a streľbe.

Pálka bola dostatočne presná, no pri maléj sile sa loptička mohla vrátiť pod pálku a zaseknúť sa tam. Pri vyšších silách sa už chovala bezproblémovo.

Pri testovaní sa nám osvedčilo obmedziť robotove pohyby na kratšie úseky pohybu, lebo odhad z regresie mal rezervy a pri dlhom pohybe vpred a povedzme 10% chybe uz mal robot vyššiu tendenciu narážať do lopty. Pridaním trackovania polohy počas chôdze by sa dal implementovať skoršie zastavenie, alebo ďalším riešením by bola zlepšená navigácia, ktorá by sa do chceného bodu nehrnula priamo, ale by robota najprv priblížila a až potom kratšími pohybmi upresnila polohu na chcenú.

Video

V ukážke robot udrie dva razy slabo, pričom mu pomáha človek(neúspešne) nohou aby sa mu vracajúca lopta nezasekla pod pálku. Keďže zmeny pozície lopty po strele boli malé, robot začne strieľať silnejšie a ďalej naháňa loptu a snaží sa ju dostať na cieľ.

Zdrojové kódy

Zdrojové kódy pre PC aplikáciu ovládajúcu robota.

Zdrojový kód pre NXT kocku robota.