O mikromyších, lidech a závodech v bludišti

Malá robotická myš zvládne bludiště za pouhých šest sekund. Každý rok se po celém světě soutěží v nejstarším robotickém závodě. Cíl je jednoduchý: dostat autonomní mikromyš co nejrychleji na konec bludiště. Ten, kdo skončil druhý, prohrál o 20 milisekund. Konkurence se však vyostřila.

V roce 1952 sestrojil matematik Claude Shannon elektronickou myš jménem Theseus, která dokázala vyřešit bludiště. Trik, díky němuž byla myš inteligentní, se skrýval v počítači zabudovaném do samotného bludiště, tvořeného telefonními reléovými spínači.

Myš byla v podstatě jen magnetem na kolečkách, který následoval elektromagnet ovládaný polohou reléových spínačů. Claude nyní prozkoumává bludiště pomocí poměrně složité strategie pokusů a omylů. Když najde správnou cestu, zaznamená si informace do paměti.

„Claude Shannon je jeden z největších mužů století. Bez něj by nic z toho, co dnes známe, neexistovalo. Celá digitální revoluce začala s ním.“ – _{Coughlin, Kevin (February 27, 2001). „Bell Labs digital guru dead at 84— Pioneer scientist led high-tech revolution“}

Theseus je často označován za jeden z prvních příkladů strojového učení. Ředitel společnosti Google nedávno řekl, že inspiroval celý obor umělé inteligence. O 25 let později redaktoři Institutu elektrotechnických a elektronických inženýrů neboli IEEE zavětřili soutěž o elektronickou myš, neboli le mouse electronique, jak se nechali slyšet. Byli nadšeni.

V roce 1977 přilákalo vyhlášení soutěže IEEE Amazing Micro-Mouse Maze Contest přes 6 000 účastníků, ale počet úspěšných soutěžících rychle klesal.

Nakonec se do finále v roce 1979 dostalo jen 15 účastníků. V té době však již soutěž vzbudila dostatečný zájem veřejnosti a dostala se do celostátního vysílání večerních zpráv.

Je jedno, co to bylo, mohly to být koňské dostihy, mohly to být automobilové závody, mohly to být myší závody,
Pokud v sobě máte alespoň špetku soutěživosti, chtěli byste vyhrát, ne?

Stejně jako skutečná myš musí být i Micromouse plně autonomní. Žádné připojení k internetu, žádné GPS ani dálkové ovládání, a žádné šťouchání, které by jí pomohlo se odlepit. Na šasi myši se musí vejít veškerá výpočetní technika, motory, senzory a napájecí zdroj.

Výška myši není omezena, ale pravidla nepovolují šplhání, let ani žádné formy spalovacího pohonu, takže například raketový pohon nepřipadá v úvahu.

Samotné bludiště je čtverec o straně asi tři metry, rozdělený stěnami na chodby o šířce pouhých 18 centimetrů. A v roce 2009 byla představena kategorie Micromouse poloviční velikosti s myškami menšími než 12 a půl centimetru na každé straně a s cestičkami o šířce pouhých devět centimetrů.

Konečné uspořádání bludiště je odhaleno až na začátku každé soutěže, poté už soutěžící nesmějí kód ve svých myších měnit.

Tři velké soutěže, All Japan, Taiwan a APEC v USA, obvykle omezují dobu, po kterou se myši v bludišti pohybují, na sedm nebo deset minut a myši mohou od startu k cíli proběhnout pouze pětkrát.

Pokud tedy strávíte hodně času hledáním, je to penalizace. To dává smysl. Strategií většiny myší Micromouse je tedy strávit první běh pečlivým poznáváním bludiště a hledáním nejlepší cesty k cíli a zároveň neztrácet příliš mnoho času. Pak využijí zbývající pokusy ke sprintu po této cestě, aby dosáhli co nejrychlejšího času běhu.

Hládání cesty skrze bludiště

Řešení bludiště může znít docela jednoduše, i když je důležité si uvědomit, že díky tomu, že místo očí má jen několik infračervených senzorů, je pohled zevnitř bludiště mnohem méně zřetelný než ten, který vidíme shora. Přesto můžete jednodušší bludiště vyřešit i se zavřenýma očima.

Pokud položíte jednu ruku podél jedné stěny, dostanete se nakonec na konec většiny běžných bludišť. A přesně to si uvědomili i někteří původní soutěžící. A poté, co si naprosto jednoduchá myš sledující stěnu odnesla v prvním finále zlato, byl cíl bludiště posunut dál od okrajů a byly přidány volně stojící stěny, které by jednoduchou myš sledující stěnu nechaly hledat věčně.

Vaším dalším instinktem může být proběhnout bludištěm a všímat si každého rozcestí. Kdykoli se dostanete do slepé uličky nebo smyčky, můžete se vrátit na poslední křižovatku a zkusit jinou cestu.

Pokud vaše poslední odbočka doleva nikam nevedla, vrátíte se na tuto křižovatku a místo toho se vydáte doprava. Tuto strategii si můžete představit jako strategii, kterou může použít tvrdohlavá myš, která vběhne co nejhlouběji do bludiště a vrátí se zpět, až když už nemůže jít dál.

Tato strategie hledání, známá jako hledání do hloubky, nakonec myš dovede k cíli. Problém je v tom, že to nemusí být nejkratší cesta, protože myš se otočí zpět, jen když to potřebuje, takže mohla přehlédnout zkratku, kterou nikdy nezkusila.

Sourozenec tohoto vyhledávacího algoritmu, hledání podle šířky, by našel nejkratší cestu. Při této strategii myš běží po jedné větvi křižovatky, dokud nedosáhne další, a pak se vrátí zpět, aby zkontrolovala cestu, kterou přeskočila, a teprve potom se přesune na další vrstvu křižovatek.

Myš tedy kontroluje každou možnost, na kterou dosáhne, ale všechno to couvání znamená, že se cesty opakují mnohokrát. V tomto okamžiku trvá i prohledání celého bludiště často kratší dobu.

Tak proč to prostě neudělat? Pečlivá myš by mohla prohledat všech 256 políček bludiště a otestovat každou odbočku a roh, aby se ujistila, že že určitě našla nejkratší cestu. Ale ani tak důkladné prohledávání není nutné. Místo toho se nejoblíbenější strategie Micromouse od všech těchto technik liší.

Flood fill algoritmus

Jedná se o vyhledávací algoritmus známý jako flood fill. Plánem této myši je optimistické cestování bludištěm, a to tak optimistické, že při první cestě nemá její mapa bludiště vůbec žádné stěny.

Jednoduše si nakreslí nejkratší cestu k cíli a vyrazí. Když jejich optimistický plán nevyhnutelně narazí na zeď, která na jejich mapě nebyla, jednoduše si ji označí a aktualizují novou nejkratší cestu k cíli. Běží, aktualizují, běží, aktualizují, stále se blíží k cíli.

Pod kapotou algoritmu je to, co si mikromyš vyznačuje na mapě, vzdálenost od každého čtverce v bludišti k cíli. Aby myš cestovala optimisticky, sleduje stopu klesajících čísel až k nule.

Kdykoli narazí na zeď, aktualizuje čísla na mapě tak, aby odrážela novou nejkratší vzdálenost k cíli. Tato strategie sledování číselné cesty nejmenšího odporu dala algoritmu flood fill jeho název.

Proces se podobá zaplavení bludiště vodou a aktualizaci hodnot na základě průtoku. Jakmile myš dosáhne cíle, může vyhodnotit cestu, kterou prošla, a získat řešení bludiště.

Může se však ohlédnout zpět a představit si ještě kratší, neprobádanou cestu, kterou mohla jít. Micromyš ještě nemusí být spokojená s tím, že našla nejkratší cestu. Tento algoritmus sice nezaručuje nalezení nejlepší cesty na první průchod. Využívá toho, že myš se musí vrátit na start, aby mohla začít další běh.

Pokud tedy myš považuje svůj návrat za novou cestu, může zpáteční cestu využít také k prohledání bludiště. Mezi těmito dvěma pokusy, které jsou oba optimalizovány tak, aby našly nejkratší cestu od startu k cíli, je velmi pravděpodobné, že ji myš objeví. A myš to udělá efektivně, přičemž často ponechá nepodstatné oblasti bludiště zcela nedotčené.

Flood fill algoritmus nabízí inteligentní i praktický způsob, jak může mikromyš nejkratší cestu bludištěm. Jakmile existovala jasná strategie hledání nejkratší cesty a jakmile se mikrokontroléry (jak jinak, když mikromyš :) ) a senzory potřebné k její realizaci staly běžnými, někteří lidé se domnívali, že soutěž vyčerpal.

V článku publikovaném v časopise IEEE, na konci 80. let se psalo, že se soutěž Micromouse přežila. „Problém byl vyřešen a nepřinášel žádné nové výzvy.“ Nic nebylo tak daleko od pravdy, jako toto tvrzení. Vývoj a pokrok mikromiší, že stále platí bondovské „Nikdy neříkej nikdy“, a neustále se lze posouvat kupředu a zvedat laťku.

V soutěži All Japan Micromouse Competition 2017 našly obě myši na bronzovém a stříbrném místě nejkratší cestu k cíli, a když ji našly, dokázaly ji urazit za 7,4 sekundy.

Vítězná myš Červené komety (Red Comet od Masakazu Utsunomiya) však dokázala něco úplně jiného. Všichni se vydali nejkratší cestou k cíli. Cesta, kterou šla Red Comet je o celých pět a půl metru delší. To proto, že Red Comet ve skutečnosti nehledá nejkratší cestu, ale nejrychlejší cestu.

A vyhledávací algoritmus Červené komety přišel na to, že tato cesta má méně zatáček, které ji zpomalují. Takže i když cesta plýtvala, vyhrála o 131 milisekund.

Rozdílné cesty při soutěži jsou nyní častější než jiné a dokonce i samotný dojezd do cíle zůstává obtížný, ať už kvůli záhadnému algoritmu, nebo zvláštnosti fyzického bludiště.

Mikromyš se nechová vždy tak, jak byste očekávali. Problém Micromouse není zdaleka vyřešen, protože se nejedná pouze o softwarový nebo hardwarový problém, ale o obojí. Je to problém robotiky.

Red Comet nevyhrál proto, že by měl lepší vyhledávací algoritmus nebo že by měl rychlejší motory. Jeho chytrost vycházela z toho, jak spolu mozek a tělo myši spolupracovaly. Ukázalo se tedy, že řešení bludiště není problém.

Nikdy to nebyl problém, že? Ale ve skutečnosti jde o navigaci a o rychlou jízdu. Každý rok jsou roboti menší, rychlejší a lehčí. Inovací je stále dost. A v Japonsku existuje malá skupina obdivovatelů, kteří se zabývají stavbou Micromouse o čtvrtinové velikosti.

Soutěže, které se na první pohled jevily jako vyřešené existují i jinde. Například skok do výšky byl olympijskou disciplínou od roku 1896, přičemž závodníci v průběhu desetiletí zdokonalovali své skoky pomocí variant, jako jsou nůžky, západní kotoul a roznožka, s klesajícími výsledky. V podstatě na skocích nebylo co vylepšit.

Ale jen do okamžiku než se pružné vypolstrované doskočiště stalo v soutěžích standardem. Dick Fosbury v roce 1968 přepsal limity tím, že se stal prvním olympionikem který přeskočil tyč obráceně, po zádech. Nyní téměř každý skokan do výšky provádí takzvaný Fosburyho flop.

Kdyby se v 80. letech soutěžení mikromyší zastavilo, soutěž by přišla o vlastní Fosburyho flopy, dvě inovace, které zcela změnily způsob závodů mikromyší.

Vždyť ve sportu, kde si závodníci mohou dovolit jakoukoli modernizaci, se toho může hodně změnit. První „Fosburyho flop“ v Micromouse neměl nic společného s technologií.

Byl to prostě způsob, jak myslet mimo vyjeté koleje. Dříve každá myš při nárazu zpomalila a otočila se vpravo nebo vlevo a tak to šlo od zdi ke zdi. S myší Mitee 3 se však vše změnilo.

Myš Mitee 3 tak poprvé implementovala diagonály. A to se ukázalo jako mnohem lepší nápad, než si všichni skutečně mysleli. A protože je to super, a super obtížné, návrháři bludišť teď často vkládají do bludišť diagonály.

Aby bylo možné využít diagonály, muselo se šasi myši zmenšit na šířku menší než 11 centimetrů, respektive na pouhých pět centimetrů u poloviční velikosti Micromouse.

Změnit se musely i senzory a software myši. Při jízdě mezi rovnoběžnými stěnami stačí udržovat stejnou vzdálenost mezi levým a pravým infračerveným snímáním. Úhlopříčka však vyžaduje zcela nový algoritmus, který myš v podstatě vede, jako by měla nasazené klapky na očích.

Za normálních okolností, pokud jdete podél stěny nebo něčeho podobného, většinu času vidíte stěnu po celou dobu. A tak vám to pomáhá se navádět a vy víte, kdy z ní vystupujete.

Ale v diagonální situaci vidíte, jak se na vás řítí stěny. A pokud se jen trochu vychýlíte ze směru, zachycení o roh je mnohem méně šetrné než smyk o zeď. Diagonály jsou i dnes jedním z největších zdrojů havárií v závodech.

Ale na oplátku se členitá dráha zatáček mění v jednu úzkou rovinku. V dnešní době je téměř každá soutěžní myš navržena tak, aby toto riziko podstupovala. Zavedení diagonál otevřelo prostor pro ještě více nápadů.

Přibližně ve stejné době myši uplatňovaly podobné strategie i při zatáčení. Namísto zastavení a otáčení se dvěma pravotočivými zatáčkami mohla myš provést jediný obloukovitý obrat.

Bludiště už nebylo jen mřížkou čtvercových chodeb. S tolika dalšími možnostmi, které bylo třeba zvážit, se vymýšlení nejlepší cesty stalo složitějším než kdykoli předtím. Ale odměna byla dramatická. To, co dříve představovalo řadu zastavení a rozjezdů, se nyní mohlo stát jediným plynulým hadovitým pohybem.

Zcela se změnil způsob, jakým se myš pohybovala se v bludišti. Dostupná technologie se v průběhu let také vylepšovala. Vysoká a těžkopádná ramena, která sloužila k vyhledávání stěn, nahradila menší soustava infračervených senzorů na palubě myši.

Přesné krokové motory byly vyměněny za stejnosměrné motory. Ty poskytují větší výkon při menších rozměrech a hmotnosti. Původně se používaly servomotory, jejich pootočení odpovídalo počtu impulsů, které dostaly a zpětně se z nich dala číst poloha hřídele.

Dnes se veškeré otáčení se provádí na základě digitálního gyroskopu, protože je mnohem spolehlivější. Ne na základě počítání a čtení impulsů z kol nebo motorů. Původně gyroskopy vznikly hlavně pro navádění, pro udržení směru nebo navádění raket, ale ve své digitální podobě se používají v každém mobilním telefonu. Je to jako kdybyste u sebe měli kompas. To to přidalo myším další orientační smysl.

Ale i přes všechna mechanická vylepšení zůstal největší fyzikální problém myší po desetiletí nevyřešen. Kola prokluzovala a rychlost myší limitovaly smyky, které dostávaly v zatáčkách.

Na závodech vidíte, že každý závodník má v ruce roli lepicí pásky. Tato páska neslouží k opravám ani k opětovnému připevnění upadlých dílů. Slouží k tomu, aby se z kol mezi jednotlivými koly sbírala smítka prachu.

Při rychlosti a přesnosti, s jakou se tito roboti pohybují, stačí malá změna tření k tomu, aby zničila celou jízdu. Pokud chcete při rychlé jízdě zatočit, potřebujete dostředivou sílu, která vás urychlí a hlavně vás v zatáčce udrží.

A čím rychleji se pohybujete, tím větší sílu potřebujete, abyste se udrželi na trati. Proto mají závodní tratě i silnice zatáčky s náklonem. Náklon přidává složku normálové síly, která stačí k vytvoření dostředivé síly potřebné k udržení dráhy. To umožňuje projet zatáčku bez smyku.

Závodní myši se v tomto nijak neliší od aut, ale v bludišti nemohou mít ani náklony v zatáčkách. Už jen proto, že jejich trasa není pevně daná, poloměry a křivky zatáčení určuje algoritmus. Jak se myši stávaly rychlejšími a rychlejšími, počátkem roku 2000 už nebyla jejich limitujícím faktorem rychlost, ale její kontrola.

Musely mít nízko nastavené těžiště a v zatáčkách zpomalovat, aby nenarazily do zdi, nepřevrátily se nebo nevyletěli z trati. Na rozdíl od závodních aut však v pravidlech nebylo nic, co by soutěžícím Micromouse bránilo tento problém vyřešit sestrojením zcela nového mechanismu.

Druhý „Fosburyho flop“ byl téměř považován za trik, když ho myš Mokomo08 poprvé použila v soutěži. Ta myš neroztáčela jen své motory, ale roztáčela i vrtuli. A zatímco létání nad stěnami je proti pravidlům, v pravidlech není nic proti tomu, aby se myš přisávala k zemi, aby neklouzala.

Dave Otten byl první člověk, který na mikromyš nasadil ventilátor. Použil ventilátor s potrubím, ale nebylo to příliš účinné, vyfukovaný vzduch nedokázal vyvinout dostatečný tlak, aby přitlačil myš k dráze. Ale šlo o vykročení správným směrem a myši se dnes v zatáčkách přicunou k dráze jako hubice vysavače.

V měřítku myši Micromouse stačí podtlakový ventilátor, často jen sestavený z dílů ručních dronů, aby vytvořil sílu směrem dolů, která je pětinásobkem hmotnosti myši. Myši dnes dokáží zatáčet s dostředivým zrychlením blížícím se 6G. To je stejné jako u vozů F1.

S přidaným řízením přisávání se konstruktérům podařilo posunout rychlostní limity. Myši se mohou se řítit rychlostí až sedm metrů za sekundu, rychleji, než dokáže běžet většina lidí.

Každá z funkcí, které jsou nyní standardní součástí moderní Micromouse, byla kdysi experimentem a nikdo neví jaký bude dalším „Fosburyho flop“.

Než se čtyřkolové myši staly standardem, trvalo to 22 let – od vítězství v soutěži All Japan v roce 1988. Stále se však experimentuje se šestikolovými a osmikolovými konstrukcemi, všesměrovým pohybem, a dokonce i s počítačovým viděním. Jaká bude další změna paradigmatu?

Pokud chcete s Micromouse začít, musíte se starat nejen o počet koleček, o podtlakové ventilátory a úhlopříčky. Je to dokonalá kombinace všech hlavních disciplín, které potřebujete pro robotiku a inženýrství a programování, vestavěné systémy, to vše zabalené do jednoho dostupného balíčku, který můžete dělat ve svém obývacím pokoji a nepotřebujete k tomu laboratoř.

Přijdete k tomu, protože jste zvědaví, a pak si řeknete: „To bych mohl udělat. To nevypadá tak těžce.“ A pak jste opravdu odsouzeni. Když vás to vtáhne, stane se z toho pořádná cesta. V jádru je Micromouse jen o myši, která se snaží vyřešit bludiště.

Po téměř padesáti letech jde o jednoduchý problém, který je ale dobrou připomínkou toho, že nic takového jako jednoduchý problém neexistuje.

Autor: RN

---

https://www.technologyreview.com/2018/12/19/138508/mighty-mouse

https://micromouseonline.com/micromouse-book/history/