czech english

Barbora

pásové vozítko s barevnou kamerou a počítačem PC, 2002

Barbora byla primárně navržena pro účast na soutěži Eurobot 2002. Další (a důležitější) motivací bylo postavit univerzální podvozek, který bude sloužit jako základ pro další soutěže a výzkumné projekty. Naneštěstí jsme robota nestihli dokončit včas, takže jsme se do soutěže vůbec nekvalifikovali. I přes tento neúspěch jsme získali spoustu cenných zkušeností a podvozek úspěšně slouží už ve třetí variantě robota – Daně.

Základní informace

Řídícím centrem robota je počítač PC pro průmyslové aplikace, operačním systémem je upravený Linux. Pohon je zajištěn dvěma modelářskými bezkartáčkovými (BLDC) motory. O sledování pozice se starají čtyři optické myši. Spektrum senzorů rozšiřují dvě barevné kamery (jedna z nich je stacionární a připojena pomocí mikrovlnného přenosu) a infračervené senzory pro detekci čar. Základem systému pro manipulaci s míčky je spirálový zásobník. Řídící program mj. obsahuje MCL (Monte Carlo Localization) sledování pozice, RRTs (Rapidly-Exploring Random Trees) plánování cesty a rychlý systém zpracování obrazu založený na prahování barev.

Podvozek

Podvozek je z větší části vyroben z běžně dostupných materiálů a dílů. Především jde o díly používané v automobilovém a leteckém modelářství a také v automatizaci. Důvodem tohoto řešení bylo především snížení ceny robota a zkrácení doby vývoje. O mechanickou výrobu podvozku se postarala společnost Vakuum Praha, která úzce spolupracuje s Matematicko-fyzikální fakultou Karlovy Univerzity v Praze, kde většina členů týmu studuje. Vakuum Praha se specializuje na vakuové a nízkoteplotní systémy a jemnou mechaniku (vyvíjí se zde např. některé systémy pro družice).
Lehký a odolný podvozek je vyroben z hliníku, při pohledu zhora má zhruba čtvercový obvod o straně třicet centimetrů. Výška podvozku je dána rozměry motorů a baterií a je asi šest centimetrů.
Hybnou silou robota jsou dva bezkartáčkové (BLDC) motory vyráběné českou firmou Mega Motor. Každý tento motor má při hmotnosti 160 gramů špičkový výkon okolo 600 Wattů. Více než desetikilogramový robot díky nim dosahuje zrychlení 20ms-2 (2G). Maximální rychlost je 4ms-1. Robot je schopen jí dosáhnout na vhodném povrchu zhuba během čtvrtiny sekundy. Pro dobrou trakci a vysokou stabilitu jsme zvolili pásový pohon realizovaný pomocí průmyslových kevlarem vystužených HTD řemenů. Podobné řemeny byly použity i pro realizaci převodovek — obyčejné zubové převodovky by při omezení rozměry podvozku nebyly schopny přenést dané síly.
Nevýhodou BLDC motorů je složitost jejich řízení. Jelikož nemají komutátor, potřebují třífázové napájení s proměnnou frekvencí, nízkým napětím (12V) a velkým proudem (až 50A). Nepřítomnost komutátoru na druhou stranu přináší vysokou spolehlivost a vysoký poměr výkonu k hmotnosti a rozměrům.
Naštěstí regulátory TMM 40e-3ph vyráběné českou společností MGM-Compro byly přesně to, co jsme potřebovali. Po malé úpravě (kterou výrobce na naši žádost ochotně provedl) se dají snadno řídit po sériové lince. Namísto generování signálu ve stylu řízení serv tak nyní můžeme regulátoru poslat přímo směr a požadovaný výkon (činitel plnění PWM) a zpět se nám vrací o kolik se motor pootočil.
Zdrojem energie jsou dva desetičlánky NiCd akumulátorů. Máme tak k dispozici kapacitu 3400mAh při napětí 12V. Ta by umožnilo při maximálním odběru pohon robota po dobu dvou minut (soutěž trvá 90 sekund). Protože ale skutečný odběr je asi desetkrát menší, je kapacitní rezerva více než dostatečná. Akumulátory byly z konstrukčních důvodů řešeny jako nevyjímatelné. Nebylo tedy možné současně testovat i nabíjet. To se během testovacích jízd ukázalo jako výrazná nevýhoda. Čekání na nabití akumulátorů zapříčinilo, že testování bylo nejen nepohodlné, ale i neefektivní. Pro budoucí použití musí být kostrukce modifikována, aby umožnila výměnu akumulátorů (a tím pádem použití několika sad).

Manipulace s míčky

Dvojitá spirála z chladírenských měděných trubek se stala základem systému pro manipulaci s míčky. Tvořila zásobník, do nějž bylo možno uložit až sedm míčků. To umožnilo robotovi nasbírat co největší počet míčků a poté je roztřídit do správných košíků. Zásobník byl namontován na vrcholu podvozku tak, aby ho bylo možné v budoucnu snadno odstranit a nahradit jinou aplikační nástavbou (pro případné další soutěže či výzkum).
Míček je vždy nejprve zachycen otevřenou částí podvozku (který má tvar písmene U). Poté je zdvižen párem manipulátorů. Jejich základem jsou modelářská serva řízená obvodem 556. Dvě polohy jsou přepínány pomocí relé ovládaného z paralelního portu počítače.
Manipulátory se ukázaly být nejproblematičtějším konstrukčním subsystémem robota. Jejich realizaci jsme nechali doslova na poslední chvíli, což se ukázalo jako poměrně zásadní podcenění jejich složitosti. Ve výsledku se nám nikdy nepodařilo dosáhnout, aby fungovaly spolehlivě.
Po zdvižení míčku osm centimetrů nad podlahu se ho ujal spirálový zásobník. Vnější konstrukce zásobníku byla pevná a posun míčků zajišťoval otočný středový válec. Ten byl vyroben z hliníkové trubky a skrýval modelářský motor se dvěma planetovými převodovkami. Středový válec byl k podvozku připevněn pomocí menší trubky, která procházela jeho spodní podstavou a byla mechanicky spojena se statorem motoru. Touto trubkou bylo protaženo i napájení motoru. Naproti tomu výstupní hřídel druhé převodovky byla spojena s pláštěm válce. Po připojení napájení se tak plášť začal otáčet.

Elektronika

Hlavní řídící jednotkou robota je základní deska Advantech PCM-5864, pro průmyslové aplikace o rozměrech 20×12 cm. Jako procesor byl použit AMD K6®-2 na 500MHz. Systém dále obsahuje 128MB RAM, audio a video vstupy, 100Mb síťové připojení a sběrnici USB.
Regulátory vrací, o kolik se motory otočily od posledního čtení. Tuto informaci lze teoreticky použít jako odometrii. Kvalitu těchto dat znehodnocuje nectnost pásových vozidel — smýkání při zatáčení. Pro spolehlivější informaci o změně pozice robota jsme na sběrnini USB připojili čtyři optické myši IntelliMouse Explorer. Jejich rozlišení je 400dpi a fungují do maximální rychlosti 1.5 ms-1. Změnu polohy optická myš určuje pomocí snímání podložky 6000krát za sekundu a vyhodnocení rozdílu po sobě jdoucích snímků. Jelikož optický senzor myši nemusí být v kontaktu s podložkou, neomezuje manévrovatelnost robota. Navíc ho nerozhodí ho ani smyk nebo podkluzování, což je nectnost inkrementálních senzorů spojených s koly (nebo pohonem) robota.
Myši poskytují pouze relativní změnu pozice. Proto chyba určení pozice roste s časem. Abychom tomu předešli, je na robotovi pět reflexních fotozávor Vishay CNY-70 K detekci barvy (resp. světlosti) podložky. Na soutěži byly použity pro detekci sítě čar namalované na podložce. Jejich výstup pomáhal eliminovat kumulativní chybu relativních senzorů pomocí algoritmu MCL (Monte Carlo Localization).
Elektronika je napájena spínaným zdrojem založeným na obvodech Maxim MAX787. Hlavním významem zdroje je poskytnutí stabilního napětí nezávisle na stupni vybití akumulátorů a poklesu jejich napětí při zátěži.
Pro vyhledávání míčků je robot vybaven barevnou CMOS kamerou. Ta je připojena k počítači přes rozhraní CVBS integrované na desce. Výstup z kamery je tak téměř okamžitě k dispozici. Kromě vestavěné kamery je robot schopen přijímat videosignál prostřednictvím mikrovlnného přenosu z kamery vně robota (na soutěži v majáčku na kraji hřiště).

Struktura programového vybavení

Díky použití PC technologie jsme byli schopni nasadit operační systém Linux. Ten poskytuje svobodu v modifikaci jádra i ovladačů pro dosažení maximálního výkonu. Řízení robota je částečně implementováno přímo v jádře (časově kritické operace), zbytek (zpracování obrazu, navigace…) jsou obyčejné procesy.

Ovladače zařízení v linuxovém jádru

Při popisu začneme odspodu – ovladači zařízení v jádru systému. Ovladače se skládají z následujících modulů: tmm.o, mailbox.o, fifo.o, mice.o, ct69k.o, cvideo.o, serio.o, serport.o, elevator.o. Moduly mailbox.o and fifo.o implementují meziprocesovou komunikaci. Z uživatelského hlediska se tato primitiva chovají jako soubory, lze je otevírat a zavírat, lze z nich číst, zapisovat nebo na nich čekat na data. Narozdíl od standardních prostředků jádra operačního systému poskytují podporu multicastových zpráv (zpráv s více příjemci).
Schránka (Mailbox) je úložiště pro jednu datovou strukturu. Typicky do ní jeden proces zapíše a několik si ji přečte. Po přečtení schránky procesem se tomuto jeví jako prázdná (tzn. každý proces může přečíst uložená data pouze jednou). Pokud je schránka otevřena jako blokující, následující čtení proces zablokuje do doby, než jsou k dispozici nová data (tj. dokud "producent" do schránky znovu nezapíše).
Fronta (FIFO) je určena pro sekvenční zpracování a přístup. Při otevření pro čtení je ze začátku prázdná. Při otevření pro zápis, pokud ji jiný proces nemá otevřenou pro čtení, se chová jako „černá díra”: zahodí vše, co se do ní zapíše. V opačném případě jsou data k dispozici procesu, který ji má otevřenou pro čtení.
Ostatní moduly tvoří rozhraní na jednotlivé části robota. Řídící programy s nimi komunikují pomocí schránek, front a speciálních zařízení vytvořených těmito moduly. Zmíněné části robota jsou regulátory TMM 40e-3ph (tmm.o), optické myši IntelliMouse Explorer (mice.o), video vstup (ct69k.o, cvideo.o) a spirálový zásobník řízený prostřednictvím paralelního portu (elevator.o).

Lokalizace (sledování pozice robota)

Informace o pozici robota je počítána pomocí algoritmu MCL (Monte Carlo Localization). Relativní informace o změně pozice je získávána z optických myší. Každý pár myší poskytuje informaci o posunutí a otočení. Použili jsme čtyři myši, protože při daném nasazení se výstup ukázal celkem nespolehlivý. Myši totiž potřebují velmi přesné nastavení polohy a výšky nad podložkou (nízká hloubka ostrosti použité optiky). Problémy způsobovala i lesklá barva použitá pro čáry. Při použití čtyř myší bychom tak měli dostat šestkrát stejnou informaci (z každé z šesti dvojic), což usnadní vyfiltrování chybné informace.
Relativní informace o změně pozice je použita jako vstup pravděpodobnostního algoritmu MCL. Algoritmus spočívá ve vygenerování sady vzorků (ve stavovém prostoru) reprezentujících možnou polohu robota. Věrohodnost těchto vzorků se posuzuje podle korespondence teoretických a reálných senzorových dat. Nevěrohodné pozice jsou zahozeny, na základě věrohodných se dogenerují nové. Tento postup se opakuje po změně pozice robota a při zpracování nových senzorových dat.

Plánování cesty

Naše plánování cesty je implementací algoritmu RRTs (Rapidly-Exploring Random Trees). Rychle rostoucí náhodné stromy (RRT) jsou datové struktury a algoritmy pro efektivní prohledávání n-dimenzionálního nekonvexního prostoru. RRT jsou konstruovány inkrementálně způsobem, který efektivně minimalizuje vzdálenost náhodně vybraného bodu od stromu. RRT jsou obzvláště vhodné pro plánování cesty v prostředí, které obsahuje překážky nebo kde se vyskytují jiná omezení (na pohybové schopnosti robota, závislost plánování na rychlosti a čase…). RRT se doporučují jako technika pro generování cest bez cyklů v nelineárních systémech s omezeními na dosažitelné stavy. RRT lze intuitivně chápat jako Monte-Carlo verzi Voronoi diagramů.
Hlavním vstupem plánovače cesty je příkaz ze strategického plánovače a výstupem cesta. Modul dále používá informace o pozici robota a míčků. Cesta je posloupnost bodů. Každý bod obsahuje relativní pozici vůči předchozímu bodu, očekávanou posuvnou a rotační rychlost a čas dosažení cíle.

Řízení

Vstupem pro řídící modul (tzv. wheelman) je cesta vygenerovaná plánovačem cesty. Role řidiče je tak redukována na lineární interpolaci posunutí a otočení mezi jednotlivými body cesty. Rychlosti motorů jsou řízenou zpětnovazební smyčkou založenou na algoritmu PID. Zpětná vazba je zajištěna filtrovanými daty z šesti párů myší.

Zpracování obrazu

Srdcem modulu zpracování obrazu je klasifikace založená na prahování v barevném prostoru YUV. Výstup z kamery byl kalibrován na geometrická zkreslení a poloha míčků (relativně k robotovi) se vypočítává z pevné pozice kamery a souřadnic barevných shluků v obraze.

Sledování objektů

Úkolem modulu pro sledování objektů je filtrování výstupu zpracování obrazu za použití informace o poslední pozici sledovaných míčků. Pro sledování polohy míčků je použit algoritmus typu Monte Carlo (podobný jako pro lokalizaci). Protože míčky stejné barvy jsou nerozlišitelné, je pro včechny míčky stejné barvy použita jediná distribuce vzorků. Tento algoritmus je výpočetně náročný a jeho výkon nebyl tak dobrý, jak jsme očekávali. Experimenty ukázaly, že obyčejné průměrování dvou posledních snímků je spolehlivější a navíc méně výpočetně náročné. S ohledem na tyto výsledky byla práce na pravděpodobnostním algoritmu zastavena a použilo se průměrování.

Plánování

Modul strategického plánovače je založen na předpokladu, že robot je schopen vykonávat určité základní úkoly. Úlohou plánovače je vygenerovat posloupnost těchto akcí tak, aby maximalizoval šanci na výhru v soutěži Eurobot 2002.
Naším prvním nápadem byla „ručně kódovaná vítězná strategie” založená na použití konečného stavového automatu. Jak se ukázalo později během vývoje, tento přístup měl dva zásadní problémy:
  • automat se stával čím dál tím složitější, až jsme se nakonec shodli na tom, že navrhnout úspěšný systém tímto způsobem je prakticky nemožné
  • i kdyby to bylo možné, robot nikdy během hry nemá zcela přesnou informaci o stavu svém či celé hry
Druhý přístup je založen na diskretizaci stavového prostoru. Pro každý stav ohodnocovací funkce nejhorší možné skóre, kterého lze dosáhnout. Toto ohodnocení je založeno na předpokladu, že robot si může vybrat „nejlepší” koš a ten bránit — stát před ním a nedovojit protivníkovi z něj míčky vybrat (předpokládá se, že soupeř sesbírá všechny ostatní míčky).
Nejhorší skóre slouží k rozhodnutí, zda vybraná akce může vést ke zhoršení výsledného skóre nebo zda je možné i přes provedení akce zachovat stávající skóre (je bezpečná). Bezpečnost vykonání příkazu se počítá pro konstatní časový interval.
Výběr následující akce je založen na dvou předpokladech: akce je bezpečná a je součástí postupu, který povede ke zlepšení nejhoršího možného skóre.
Základní příkazy, které je robot schopen vykonat jsou přesuny do bodu [x,y,α] nebo vyvolání nějaké akce aplikační nástavby (otočení středového válce…). Základní akce lze kombinovat do složených akcí. Například sebrání míčku je dlouhá posloupnost příkazů, která je mnohokrát znovupoužitelná. Použitím složených akcí se strategický plán stává kompaktnějším (méně větvení). Skutečnost, že složené akce lze dekomponovat na posloupnost jednoduchých akcí umožňuje jednotné vyhodnocení bezpečnosti plánu a použítí dobře definovaného rozhraní pro jejich provádění.

Závěr a plány do budoucna

Robot Barbora byl dokončen a je je k dispozici pro další výzkum.
Naneštěstí se hardware ukázal složitější, než jsme očekávali, takže nezbyl prakticky žádný čas na odladění řídícího programu (v reálných podmínkách) nutné pro úspěch v soutěži. Přesto se ukázalo, že soutěž je výborná motivace při stavbě robota. Do budoucna očekáváme doladění software a poskytnutí experimentálních výsledků o výkonnosti systému.

Členové týmu

Vojtěch Pavlíkmechanika, elektronika, navigace, linuxové jádro
Kamil Řezáčmechanika, elektronika, řízení motorů
Zbyněk Winklerplánování, vysokoúrovňové řízeni
Martin Marešzpracování obrazu, plánování, linuxové jádro
Petr Daněčekzpracování obrazu, rozpoznávání objektů
Jan Káraplánování cesty, RRT
Jaroslav Sládeksledování objektů, shánění sponzorů
Markéta Kylouškovátlumočení, morální podpora, trička

Financování

Tento projekt by nemohl být realizován bez podpory následujících osob a organizací:
  • Smrcek, American University of Guttenberg
  • Matematicko-fyzikální fakulta Univerzity Karlovy v Praze
  • nadace Physics on Stage
  • MGM Compro
  • Loctite
  • a samozřejmě všichni členové týmu, kteří obětovali svá prasátka či jiné pokladničky

V případě dalšího zájmu o tento projekt, případně pokud máte nějaké připomínky, kontaktujte nás prosím pomocí tohoto formuláře.