Wrayova diplomová práca

This error is generated automatically. I am sorry, but this page is NOT available in English. The page You see right now, is here for compatibility purpose only. I am sorry for any inconvenience. It seems You've been on Slovak only page and clicked the note on the bottom. So - do You or do You not understand Slovak? Anyway - bottom line - this page is not available in English. Do You want to return to main page in English?

Úvod

Hneď na úvod musím povedať, že moja práca nie je nič prevratné, a je to len taká veľmi hrubá demonštrácia, resp. úvod do umelej inteligencie. Síce som s tým skončil veľmi dobre na súťaži ŠVOČ a obhájil som to bez problémov pri štátniciach, ale aj tak je to podľa mňa strašne jednoduché a vždy som chcel dokázať čosi väčšie - no nepodarilo sa :) Čo už. To len aby ste náhodou od toho príliš veľa nečakali.
Možno je trošku prekvapujúce, že som si to len tak vystavil na internet, ale v tomto smere som zástancom OpenSource. Veľa ľudí robí okolo toho veľkú vedu, ale podľa mňa, keď už som to raz napísal, tak by bola škoda, keby to len tak ostalo ležať v knižnici. Vlastne - celkovo nerozumiem prečo si niektorí tie svoje výtvory strážia, ako keby boli neviem čo prevratné, a pri tom sú bežne dostupné v knižnici školy na ktorej študovali :) Asi tak 95 percent teórie v mojej diplomovej práci je odpísanej z iných publikácii, ale ak náhodou použijete niečo z mojej práce, potešíte ma ak dáte odkaz aj na mňa :) Napísal som tu k tomu aj taký nejaký dlhší pokec, lebo v diplomovej práci som mal na to len pár strán, a pritom to bolo celé o dosť zložitejšie. Mimochodom, ak sa vám to nechce čítať, linky na download sú na konci tohoto textu.

O čom moja práca je

Umelá inteligencia je presne to čo je v sci-fi filmoch, keď stroje rozprávajú, hýbu sa samé od seba a rozmýšľajú :) Potom v polke filmu ovládnu svet, ale nakoniec celé ľudstvo zachráni nejaký 10 ročný génius. Ja som si za cieľ položil čosi ZNAČNE jednoduchšie. Postaviť robota, ktorý bude "akože" rozmýšľať. Nie však úplne nad hocičím, stačí, že nájde cestu v bludisku :) Takže je to dvojkolesový vozík, ktorý naráža do stien a snaží sa doraziť do cieľa. Samozrejme, že takú "zložitú" vec som nedokázal vyriešiť sám a tak sme to spravili spolu s djMabom. Ono celkovo sa neskôr ukázalo, že ten robot je pekne tupý a chodí ako chce :) a podľa môjho názoru by celkom stačil program, na ktorom by som to demonštroval, ale v zadaní bolo zostrojiť robota. Ach jo. Na jednej strane som dnes spokojný, že som to celé tak s prehľadom obhájil a že sa to všetkým tak páčilo, ale keď si uvedomím koľko času som tomu venoval a porovnám si to s ostatnými absolventami, ktorí svoju prácu spravili s prehľadom za 3 týždne, tak mám z toho čudný pocit :) Takže rada od wraya pre budúcich diplomantov - zvoľte si čo najjednoduchšiu tému :) Samozrejme, že profesori vám budú tvrdiť, že treba robiť praktické veci, alebo aspoň dačo naprogramovať, ale fakt som si nie istý či môj dobrý pocit stojí za tie nervy čo som si s tým užil...

Ako sa mi (ne)darilo

Na úvod bolo treba postaviť robota. Takže po prehľadaní našich obydlí sme našli nejaké drevo, hračkárske kolieska a staršie cdromy kvôli motorom. Základná pomôcka každého vynálezcu je sekundové lepidlo, takže som to celé zlepil a tešil sa ako fajne rýchlo sa to podarilo. V skutočnosti bol však celý Sergej (ako sme robota pomenovali) úplne nanič. Ale vyzeral pekne :)

Sergej 1, prvý pokus o postavenie robota dopadol neúspešne...

Drevená konštrukcia nie je to pravé, je krehká, drevo má veľké trenie a vyzerá hnusne. Aspoň keď s ním robia amatéri ako ja. Krabičky od TicTacov tiež nie sú to pravé, a rozmer bol tiež len tak "od oka". Toto všetko predurčilo vznik nového robota - Sergeja Mark 2.
Sergej Mk2 to už bola úplne iná krvná skupina. Ako správny technik som si podvozok najprv navrhol, tak aby mal tie správne rozmery, a potom som ho dal kamarátovi vyrobiť. Ako správny robot, tento už bol skonštruovaný zo železa a skrutiek, a vyzeral, že dačo znesie. Slabým článkom boli akurát kolieska, lebo oproti tej železnej konštrukcii vyzerali "detsky" :)

Sergej Mk2, je to pokrok, ale stále to bolo úplne nanič...

Hlavným problémom Sergeja Mk2 neboli ani tak kolieska, ako motory. Ukázalo sa totiž, že v CD Rome, žiadne krokové motory nie sú a aj tieto boli iba nejaké motory zo striedavým budením, ak si to dobre pamätám. Povedané inak, všetka naša snaha (a že to dalo dosť práce zohnať 2 CDRomy s podobnými motormi) bola na nič, a mohli sme sa s o to väčším elánom pustiť do vývoja Sergeja Mk3.
Zohnať krokové motory vôbec nie je také ľahké ako sa na prvý pohľad zdá a nám to trvalo *poriadne* dlho. Keď sa povie, že krokový motor vhodný na konštrukciu robota sa nachádza v starších 5,25 palcových mechanikách tak to ešte neznamená, že ho obsahuje každá mechanika... Rozobral som ich približne 5 a nakoniec (a fakt to trvalo *dosť* dlho) sme mali dva krokové motory, ktoré síce vyzerali podobne, ale správali sa inak (konkrétne jeden mal dvakrát väčší krok ako druhý). Samozrejme, že sa to dá ošetriť softwareovo, ale ako sa neskôr ukázalo nie je to žiadna sranda...

Sergej Mk3, prvá funkčná verzia robota.

Sergej Mk3 mal okrem týchto "pravých" krokových motorov silonové kolesá potiahnuté gumou, a sadu snímačov pre interakciu s okolím. Do odovzdania diplomovej práce ostávalo asi 6 mesiacov, a začínalo to byť celkom dramatické... Náš diplomový vedúci bol akurát na toho pol roka, trošku bokom, a tak to začínalo byť naozaj dosť napínavé, nakoľko sme o umelej inteligencii netušili úplne nič. Bolo teda na čase začať trošku radikálnejšie, a tak sme (asi kvôli tomu stresu ako sa to blížilo) konečne rozbehali programovú časť na strane robota. Programovanie v assembleri je proste lahôdka, a tak sme sa rozhodli použiť radšej Keil. Naprogramovať mikrokontrolér je vcelku jednoduché. Posielať pár jednotiek a núl na porty a čítať nie je nič zložité - na prvý pohľad. Na druhý pohľad sa ukáže, že obyčajná jednotka z portu mikroprocesora rozsvieti diódu, ale neroztočí motor. Takže treba nejaké budiče a prevodníky úrovní (kvôli komunikácii s PC). Elektronika nie je moja silná stránka a našťastie to celé čo sa týka hardware urobil djMabo (mne ostalo tým pádom programovanie :). Je fajn keď už viete programovať v assembleri, ale je to dosť nanič, ak chcete naprogramovať mikroprocesor, a nemáte napaľovačku. Fajn - hlavne že sa darí. Na celej škole samozrejme takú napaľovačku nezoženiete, takže sme ju museli postaviť (lepšie povedané djMabo ju musel postaviť, lebo ja som zvládol akurát tak SMDčka na ňu naletovať :) Zo začiatku nechodila úplne dobre, ale neskôr sa umúdrila a podarilo sa nám na nej asi tak 200 krát preprogramovať procesor. Ďalšia vec - v prvých fázach sa nám (už sa nepamätám prečo) podarilo pár krát (asi 4) odpáliť procesor, a tak sme boli celkom častými zákazníkmi v obchode s elektrosúčiastkami :E Popri tom sme samozrejme museli rozmýšľať o bezdrôtovej komunikácii prostredníctvom infračervených diód a rádia (tú myšlienku sme neskôr v rámci stresu zavrhli :)

Hardware hotový, teraz naliať rozum

Po nespočetných hodinách strávených v škole (zatiaľ čo ostatní mali defacto prázdniny :E) sa podarilo rozbehnúť Sergeja Mk3 a nálada bola o trošku veselšia. Teraz už "len" zariadiť aby rozmýšľal. Do odovzdania diplomovej práce ostávali asi 3, alebo 4 mesiace... Sériová komunikácia v C++ Builderi je celkom jednoduchá. Celkom :) Ale nejdem preháňať, rozbehli sme to fakt pomerne rýchlo... (resp. djMabo rozbehol, musím sa priznať, že som to ešte stále dosť flákal) Prvá úloha (djMabova) bola navrhnúť optimalizáciu pohybu robota pomocou genetických algoritmov. Nič ľahšie internet je veľká vec, alebo - dajte mi názov témy, a ja sa to za týždeň nie len naučím, ale aj pochopím. No možno, čosi jednoduchšie, ale moje pochopenie genetických algoritmov sa značne líšilo od toho ako to myslel ten čo to vymyslel :) Aj napriek tomu som tam však našiel pár výborných myšlienok, a po svojom som ich implementoval do programu a zostrojil "nejaký algoritmus" (v skutočnosti tam bol pomotaný horolezec, tabu prehľadávanie, žíhanie aj genetické algoritmy :) a čo je zaujímavé - fungovalo to. Dokonca to fungovalo a nielen tak hocijako, fungovalo to omnoho lepšie ako celé genetické algoritmy... Robot zvládol (skoro) každé bludisko, a skutočne robil veci, ktoré sme mu ani nekázali (rozumej rozmýšľal po svojom :) Bol som veľmi nadšený, že sa to celé podarilo a máme mysliaceho robota, až kým sme sa s našim úspechom nepochválili našemu diplomovému vedúcemu. Bolo totiž pekné, ako to celé fungovalo, ale bohužiaľ - s genetickými algoritmami to nemalo nič spoločné, a celý môj algoritmus bol vynikajúci ale zároveň nanič. (Zaujímavý pocit, keď vymyslíte niečo nové čo aj skutočne funguje, ale povedia vám, že je to zle...)
Náš vedúci nám však našťastie vysvetlil činnosť genetického algoritmu, a bolo to aj celkom zrozumiteľné, takže som doma za necelé tri týždne naprogramoval simuláciu genetického algoritmu, na počítači. V tej chvíli som síce už videl, že veľmi účinné to nie je, ale aj tak to bolo fascinujúce sledovať "život" a "vývoj" naprogramovaných jedincov. Zistil som, že genetické algoritmy sú naozaj výborná vec, na veľa typov úloh, ale konkrétne na túto našu sa extra veľmi nehodia. Ak vás zaujíma prečo tak napíšte rovno djMabovi :) Do odovzdania diplomovej práce ostávali asi tak 2 mesiace a djMabo mal v tej chvíli prácu skoro hotovú. Takže ja som mohol konečne začať pracovať na mojej časti - expertných systémoch.

Expertné systémy

Pri expertných systémoch už situácia taká ľahká nebola, lebo výkladu našeho vedúceho som jednoducho nerozumel, a tak ostával fakt už len ten internet. Našťastie, som veľmi zhruba pochopil aj sám o čom celé expertné systémy sú a podarilo sa mi pomerne jednoducho zostaviť program, ktorý využíval informácie získané z genetických algoritmov a hľadal vďaka nim cestu bludiskom. Vlastne - bolo to viac menej to isté ako genetické algoritmy :) Veľmi spokojný som sa išiel pochváliť našemu vedúcemu ako som to rýchlo zvládol, ale samozrejme, že sa mu to veľmi nepozdávalo a tvrdil, že by tam toho malo byť viac. Keď som si premietol v hlave všetko to úsilie čo som dovtedy vynaložil, tak ma to aj celkom vytočilo. Predsa len odovzdanie diplomovky sa blíži, nemám napísaný ani riadok a mám vymýšľať nové veci... Musel som kvôli tomu aj odísť z práce a venovať sa celej diplomke ešte intenzívnejšie...
DjMabo ten už bol spokojnejší, vylaďoval iba drobné chyby (ale aj tých mal samozrejme dosť :) a tak popri tom vyrobil nového - lepšieho robota, s novými motormi a podvozkom z iného materiálu. Opäť som bol iba rád, že to celé zariadil on, lebo ja som mal plnú hlavu programovania...

Sergej Mk4, posledná verzia, ktorú sme odprezentovali aj na ŠVOČ a štátniciach. Ešte stále má problém s otáčaním a nerobí presne pravouhlé zatáčky, ale *zhruba* funguje. Joj ale som rád, že už to mám za sebou a nemusím to napravovať :) Na obrázku je ešte predposledné štádium s korkovými kolesami - ako sa ukázalo neskôr, nebol to až tak dobrý nápad.

Hlavným problémom genetických algoritmov - aspoň tých použitých v našom programe bolo to, že boli veľmi slabé a robot bol vďaka nim veľmi hlúpy. Celá ich podstata spočívala v tom, že robot sa "rozhliadol" kúsok okolo seba, zvážil si kde je cieľ a na základe tohto sa pohol nejakým smerom. Existovalo 32*4, teda 128 možností. Toto je bohužiaľ *dosť* málo, keďže skutočne originálnych bolo len tých 32 (hej hej dalo by sa naprogramovať aj viac, ale už len týchto 32 kým som vymyslel tak som mal dosť :) Keby sme si to porovnali s človekom tak by to bol človek, ktorý vie 32 vecí. Vždy sa otočí smerom k cieľu, poobzerá sa malý kúsok okolo seba (resp. pred seba) a urobí nejaký krok. V živote by takýto človek veľmi ľahko vošiel do nejakej slepej chodby, diery, bažiny, útesu... :) Proste bol poriadne tupý. Prvý môj nápad bol robota začať trochu učiť. Ak teda zistí, že nejaká vedomosť ho privedie do bažiny, tak táto vedomosť asi nebude celkom správna a teda som ju zmenil. Ešte predtým ako som chcel dačo zmeniť, bolo treba vymyslieť spôsob ako určiť, že robot sa "zacyklil". Pre človeka je to jednoduché, proste sa pozre okolo seba a vidí, že je v prd... - zacyklený. Pre program to také ľahké nie je lebo daktoré prekážky sa dajú proste obísť. (tak ako v živote podliezť, preskočiť, obísť) Aj toto som teda dosť zjednodušil (predsa len do odovzdania zostávalo nejakých 50 dní) a proste keď sa robot motal stále v rovnakej oblasti, tak asi zablúdil (zacyklil sa) a teda som nejaké gény zmenil. To slovko "nejaké" je veľmi dôležité, lebo ťažko povedať, ktoré gény spôsobili to, že sa zamotal... Povedal som si že to bude ten gén, ktorý je posledný zodpovedný za to, že sa robot zacyklil. Bolo trošku zložitejšie vymyslieť, na akú inú sa má táto informácia zmeniť, takže som to vyriešil tak, že som si povedal, že to bude buď náhodne, alebo najbližšou v poradí. Z tohoto vyplynuli vedomosti typu genotyp s náhodnou modifikáciou génov, a vedomosti typu genotyp s rotáciou génov.

V praxi to vyzeralo asi takto. Robot chcel ísť stále do cieľa, ale tie jeho jednoduché vedomosti zariadili, že už takáto jednoduchá prekážka ho zastavila. Vždy sa totiž snažil priblížiť k cieľu, a keďže to už viac nešlo tak sa vlastne vzdialil. V ďalšom kroku sa však samozrejme znova priblížil a tým pádom sa zacyklil. Genetické algoritmy (aspoň tie v tomto prípade) sú teda pekne slabé, keď si nevedia poradiť, ani s takouto jednoduchou záležitosťou :)

Prekonať túto jednoduchú prekážku nepomohla ani zmena rotáciou génov, a pri náhodnej modifikácii to vyzeralo takto. Toto zodpovedá stavu, keď sa robot priamo pri hľadaní cesty bludiskom učil, aké vedomosti sú najužitočnejšie pre bludisko tohto typu. Je to síce pekné, a takýmto spôsobom by zvládol možno každé bludisko, ale trvalo by mu to veeeeeeeeeeľmi dlho.

Povedané inak, napriek všetkému úsiliu, ktoré som venoval vývoju genetického algoritmu som si čoraz viac uvedomil, že tadiaľto cesta nepovedie, a používať iba gény (tie gény si treba predstaviť ako reakcie na isté situácie - teda robot sa "rozhliadne" okolo seba, povie si že je napríklad v situácii číslo 7 a použije gén číslo 7 a pohne sa nejakým smerom) robota do cieľa tak ľahko nedostane.
Vylepšením by bolo, keby sa robot nesnažil meniť svoje gény (ktoré djMabo už vytrénoval, takže sa dalo predpokladať, že sú veľmi kvalitné...) ale, ak sa zacyklí, tak spraví proste "niečo iné". Rozhodol som sa, že to "niečo iné" bude presun na nejaké neznáme políčko o ktorom vie, že sa do ňho dá dostať - existuje k nemu cesta, alebo povedané inak je to nezmapované políčko, ktoré susedí so zmapovaným a voľným políčkom. Podľa možností by takéto políčko malo byť čo najbližšie k cieľu. Keď sa robot dostane do tohto "dočasného cieľa" tak bude pokračovať ďalej vo svojej misii :) Avšak ukázalo sa, že niekedy voľba dočasného cieľa čo najbližšie k reálnemu cieľu, nie je veľmi šťastným riešením, lebo občas sa robot zacyklí, aj keď ide len do dočasného cieľa :) Ach jaj aj s genetickými algoritmami. Tak som sa rozhodol doplniť nové metriky pre voľbu dočasného cieľa, a naprogramoval som voľbu dočasného cieľa v prípade zacyklenia buď čo najbližšie k cieľu, čo najbližšie k robotovi, alebo tak aby bol blízko aj k cieľu aj k robotovi. Aj toto všetko však fungovalo iba vo "väčšine" prípadov, a 95 percent nie je 100 percent, takže to nebol prijateľný výsledok :) Celý tento problém vznikal najmä kvôli tomu, že algoritmus bol deterministický, a teda pri každej voľbe dočasného cieľa bolo *presne* vopred určené, ktorý cieľ si robot vybere. A práve toto spôsobovalo občas zacyklenie. Rozhodol som sa teda voľbu dočasných cieľov trošku optimalizovať.

Voľba dočasných cieľov - pokročilé metódy

Na prvý pohľad by sa mohlo zdať, že už voľba dočasného cieľa na základe metriky (čo najbližšie k cieľu, robotovi, alebo "dačo medzi") je už optimálna. Nuž faktom je, že nie je... Problém vzniká najmä pri bludiskách malých rozmerov (a tým moje demonštračné o veľkosti 11x11 štvorcov rozhodne bolo), kvôli tomu, že ak si systém povie, že hľadá cieľ ktorý je čo najbližšie k cieľu, ešte to neznamená, že takýto cieľ je jeden jediný... Trošku som to optimalizoval tým, že som začal brať do úvahy aj natočenie robota. Teda robot sa vydá k najbližšiemu cieľu, ale tak, aby sa musel čo najmenej otáčať. Aj takýchto cieľov však môže byť viac :) Ok takže som sa rozhodol, že sa robot vybere smerom k najvýhodnejšiemu cieľu, tak aby sa musel čo najmenej točiť, a ak bude takýchto cieľov viac, tak ich opäť prehodnotí podľa ďalšieho kritéria. (uff to už znie fakt zložito, ani sa mi nechce veriť, že som to vymyslel :)
Príklad. Robot nájde 10 cieľov, ktoré sú od cieľa vzdialené v euklidovskej metrike o 5 štvorcov, čo je najmenšia možná vzdialenosť do cieľa v uvažovanej situácii. Robot si zhodnotí, že je natočený na východ a ukáže sa, že ak sa nechce otáčať, tak výhodných cieľov je už len 7. Robot porozmýšľa, ktorý z nich je k nemu najbližie, a ukáže sa, že takéto ciele sú napríklad 3. Fajn, čo teraz? :) Tak teraz som už nemal na to nervy a robot si vybere cieľ náhodne... Treba povedať, že do takýchto hlbokých myšlienok sa robot dostane len málokedy, možno v jednom z 10000 rozhodovacích okamihov. Ale čo už - musí to byť premyslené do najmenších detailov.
Ešte stále tu bol však problém s tou determiničnosťou, lebo pri 1 pokuse z 10000, (to som si tipol, ale je to určite veľmi malý pomer...) v ktorom sa uplatní náhoda ťažko hovoriť o náhode... A práve kvôli tomu malému množstvu náhody sa stávalo, že robot si vybral nejaký dočasný cieľ, a nevedel sa doňho dostať. Tak si povedal že je zacyklený a vybral si dočasný cieľ (väčšinou ten istý, v lepšom prípade iný, do ktorého sa opäť nevedel dostať) a znova sa doňho nedostal a - bol proste pekne uviaznutý, a nech rozmýšľal ako chcel, nič ho nenapadlo :) Teraz nastal čas pre náhodu! Zaistil som aby si robot pamätal či sa mu podarilo dostať do dočasného cieľa, ktorý si zvolil. Ak sa mu to nepodarilo ani na 3 krát (asi 3 neviem presne akú hodnotu som zvolil) Tak si proste vybral nový dočasný cieľ úplne náhodne. Ak nedosiahol ani ten vybral si iný - opäť úplne náhodne. Toto konečne zaistilo, že robot zvládol prejsť *každé* bludisko. Povzbudený úspechom zavádzania faktoru náhody, som sa rozhodol vyskúšať, ako by to vyzeralo keby robot nebral do úvahy nejakú metriku a volil každý dočasný cieľ úplne náhodne. Ako sa neskôr ukázalo, tak toto nebol až tak dobrý nápad, ale nebol zase ani tak zlý :) Robot opäť zvládol každé bludisko, akurát mu to niekedy trvalo dlhšie.
Teraz, keď už som konečne prekonal obmedzenie genetických algoritmov a robot zvládne prejsť úplne každé bludisko, mohlo by sa zdať, že cieľ mojej práce je splnený a môžem začať pracovať na textovej časti mojej diplomovej práce (do odovzdania ostával asi mesiac a pol...) Bohužiaľ nebolo to celkom tak. Definícia expertného systému je taká, že by to mal byť systém, ktorý dokáže robiť rozhodnutia tak kvalitné ako človek - expert. Tieto moje jednoduché bludiská zvládne človek prejsť za povedzme 50 krokov (áno testoval som to aj so živými ľuďmi :) a robot to zvládol za 500 krokov, niekedy ešte viac... To je teda dosť mizerný expert. Bolo treba teda vymyslieť nejaké ďalšie, lepšie metódy.

Ďalšie metódy

Myšlienka náhody sa mi pozdávala natoľko, že som skúsil zistiť, ako by to vyzeralo, keby sa robot pohyboval úplne náhodne. Z matematického hľadiska by to znamenalo, že zvládne prejsť každé bludisko, šlo len o to, že za ako dlho... Samozrejme, že náhodný pohyb nepriniesol žiadne prekvapivé výsledky, ale aspoň som mal ďalší výsledok do tabuľky :)
Oveľa užitočnejšie sa ukázalo na chvíľu zabudnúť na celé genetické algoritmy, a zariadiť aby sa robot správal viac "pudovo". Teda nech nevymýšľa nejaké zložité stratégie, ale nech sa proste vždy pohne tak aby sa čo najviac priblížil do cieľa. Áno - samozrejme, že môže takto ľahko uviaznuť, ale to nevadí, však už som vymyslel predtým, ako sa zotaví z takejto situácie pomocou voľby dočasného cieľa :) Takže zase bol robot o čosi múdrejší, ale pri výsledku 200 a viac krokov (človek to zvládne za nejakých 50) ešte stále nemožno veľmi hovoriť o inteligencii...
Stále mi totiž chýbala jedna dôležitá vec, na ktorú som pri vývoji robota nebral ohľad. Stále som sa snažil vymyslieť nejaký nový počítačový algoritmus, čo najefektívnejší. Pri počítačoch je však jeden "problém". Keď nenaprogramujete optimálny algoritmus, ešte to vôbec nevadí, lebo aj tak dá výsledok, aj keď po dlhšom čase. Ale ani tento dlhší čas vôbec nevadí, lebo počítač počíta (rozmýšľa) omnoho rýchlejšie ako človek. Teda pri obyčajnom programovaní si človek až tak nerobí hlavu s tým nakoľko je algoritmus optimalizovaný, a čo je hlavné - pri bežnom programovaní sa postupuje logicky. Niečo také ako "možno" sa v klasickom programovaní nehodí. Všetko musí byť popísané exaktne, a v každej chvíli by malo byť možné určiť úplne presne čo ďalej. Takto však človek neuvažuje. Človek väčšinou rozmýšľa tak ako sa mu to v tej ktorej situácii hodí. A občas spraví "úplnú blbosť" a aj napriek tomu zvládne na 50 krokov, to čo môj algoritmus na 200. Hmmm - a to je pointa celých expertných systémov - napodobiť činnosť človeka.

Ako rozmýšľa človek

Človek zo zásady *nemá* nejaké špeciálne postupy na hľadanie cesty v bludisku, proste si nejaký systém väčšinou vymyslí priamo na mieste... Aspoň teda neviem o expertoch na riešenie bludísk :) Genetické algoritmy teda môžno pokojne vylúčiť. Človek sa proste tak nejak podvedome pohybuje smerom k cieľu, ale ak nejaká chodba vedie aj smerom od cieľa a vie o nej, že by mohla byť cestou do cieľa preskúma aj tú. Ak už je človek v polovici nejakej chodby tak ju väčšinou preskúma až do konca, a nevráti sa v strede cesty naspať... Ok takže v podstate sa človek hýbe tak aby sa priblížil k cieľu. Ok - robot sa bude pohybovať v smere gradientu. Ďalej preskumáva chodby. Hm toto je už ťažšie formulovať počítaču, ale ide o to, že si volí nejaké dočasné ciele čo najbližšie k nemu a snaží sa skúmať práve tie. Práve toto je dôležitá pointa - nesnažiť sa vyriešiť celý problém naraz, ale "preskúmavať" chodby. Ďalšia dôležitá skutočnosť ktorá z tohto vyplýva je tá, že ak sa snaží priblížiť do cieľov, ktoré sú k nemu relatívne blízko a najmä - určite do nich existuje cesta, ktorú už pozná, *nemôže* sa zacykliť. Samozrejme toto slovičko nemôže je trošku prehnané a robot sa s veľmi malou pravdepodobnosťou zacykliť môže, (ak si zvolí príliš náročný dočasný cieľ) ale táto pravdepodobnosť je naozaj veľmi maličká. Hm, celkom ľahko som na to prišiel, a na moje prekvapenie, skutočne to zlepšilo algoritmus, a na zvládnutie bludiska stačilo menej krokov.
Fajn čo ďalšie človek využíva? Človek detekuje slepé chodby, ak je nejaká chodba čo nikam nevedie, tak človek sa už do nej (pochopiteľne) nevráti. Fajn a teraz ako to povedať počítaču, čo je slepá chodba :)

Políčko A je slepá chodba. A dá sa to aj ľahko definovať. Všetko čo je obkolesené prekážkami z troch strán (resp 4 - tak možno mapovať aj "vnútra") je slepá chodba. Políčko B je tiež slepá chodba, ale C už nie. A definovať rozdiel medzi B a C je to čo bolo nutné vymyslieť.

Našťastie to nebolo až také zložité. Políčko A treba nejak označiť. A toto "nejak" bude značiť asi toľko, že nech doňho robot nejde, ale ak by predsa len z nejakého dôvodu musel (ešte som nevedel či to bude fungovať :) tak môže. Povedané inak, políčko A som označil, ako "políčko, ktorému sa treba vyhýbať". Fajn a Pravidlo som formuloval inak. Ak sú okolo políčka tri prekážky, alebo "políčka, ktorým sa treba vyhýbať", tak označ políčko ako "políčko ktorému sa treba vyhýbať". Znie to možno zložito, ale je to celkom jednoduché. Potom stačí pustiť algoritmus pár krát za sebou (v prvom kroku označí políčko A, v ďalšom políčko B atď) a označia sa slepé chodby. Samozrejme dôležitá podmienka je, že políčko na ktorom je robot sa nesmie označiť nijak - inak by sa robot tak nejak zabetónoval :) Ťažko povedať koľko krát za sebou je dobré tento algoritmus pustiť, takže som si iba zvolil nejakú univerzálnu konštantu, myslím, že 6 :)
Teraz to už začínalo byť celkom zaujímavé, lebo program dokáže prehľadať slepé chodby rýchlo (určite rýchlejšie ako človek) a určite sa nepomýli. Takže aj výsledky už boli približne rovnaké ako pri živých ľuďoch.
Detekcia "slepých chodieb" sa však dá dotiahnuť, ešte ďalej. Ako je totiž napísané v motte v úvode mojej diplomovej práce - V mysli začiatočníka je mnoho možností, v mysli experta je ich len pár. Čím menej možností existuje, tým je jednoduchšie sa rozhodnúť. Teda, čím viac políčok budem mať označených ako "políčko, ktorému sa treba vyhýbať" tým jednoduchšie bude nájsť cestu do cieľa, v ideálnom prípade ostane len jediná cesta bludiskom a všetko ostatné bude označené ako prekážky, alebo "políčka, ktorým sa treba vyhýbať". Takže ďalšou úlohou bolo nájsť viac takýchto políčok.

Políčko A možno označiť ako "to ktorému sa treba vyhýbať". A postačujúcou podmienkou je aby bolo políčko B voľné. V prvých dvoch prípadoch sa totiž z bodu 1 do bodu 2 dá dostať aj ak bude políčko A označené, a v treťom prípade sa z bodu 1 do bodu 2 nedá dostať, či už je políčko A voľné alebo obsadené.

Čiže: Ak políčka C sú obsadené a políčko B je voľné, potom políčko A možno označiť ako "to ktorému sa treba vyhýbať".

Práve, to čo je napísané pod predošlým obrázkom je náramne dôležitý poznatok, pretože keď som ho aplikoval do programu konečne začal robot dosahovať výsledky aspoň tak dobré, a niekedy ešte lepšie ako človek. No konečne (napriek mojim úspechom netreba zabúdať, že termín odovzdania diplomovej práce sa nezadržateľne blížil)
Aj tak som ale ešte nebol úplne spokojný, a rozmýšľal som ako viac by sa dal algoritmus (v tejto chvíli to už však prestal byť algoritmus, ale boli to skôr komplexné znalosti) vylepšiť. Vzhľadom na to, že času bolo málo ma napadlo už len jediné čo by sa dalo ešte označiť - celé "zóny, ktorým sa treba vyhýbať". Ak je totiž nejaká oblasť obkolesená či už zmapovanými, alebo nezmapovanými políčkami, tak jej vnútro nie je užitočné. Teda za dvoch podmienok. Vnútri tejto zóny sa nesmie nachádzať robot, a taktiež sa nesmie vnútri nachádzať cieľ. Pochopiteľne :) Táto skutočnosť dosť pomáha pri algoritmoch typu "náhodný pohyb" ale v tých najprepracovanejších metódach (voľba dočasných cieľov) neprináša až také zlepšenie a občas sa stalo, že sa potrebný počet krokov pri označovaní slepých zón zvýšil (pretože robot označil aj políčka, cez ktoré mohla byť cesta kratšia...) Možno však predpokladať, že pri bludiskách väčších ako je 11 x 11 štvorcov by detekcia slepých zón mala väčší význam (Najmä z časového hľadiska, pretože - čím menej možností musí robot zvažovať, tým rýchlejšie sa môže rozhodovať o ďalšom kroku)
Pár dní po "dokončení programu", pretože už som naozaj nemal náladu, ešte čosi vylepšovať, aj keď by sa to určite dalo ešte viac premakať, náš diplomový vedúci rozhodol, že by bolo zaujímavé ísť skúsiť šťastie na vedeckú súťaž. No veľmi som tej myšlienke nebol naklonený, lebo som mal pred sebou ešte písanie celej diplomovej práce, a ešte bolo treba zariadiť aby sa robot aj naozaj pohyboval, lebo simulácia na PC je jedna vec a ako to pôjde v skutočnosti je vec druhá.
Niekedy v tom čase djMabo dokončil poslednú verziu robota - Sergeja Mk4.

Posledná verzia - Sergej Mk4. Podvozok je z dosky plošného spoja (plech už bol po toľkých úpravách dosť zničený) inak žiadne výrazné zmeny. Vlastne - ešte motory sú rovnaké, a v asembleri je trošku vyladený program pre vykonávanie jednotlivých krokov. Stále sa však robot neotáča úplne presne o 90 stupňov. Bohužiaľ s tým sa už nedá spraviť nič čo je v našich silách :)

Od programu k Hardware

djMabo aj ja sme mali teda svoje programové časti hotové. Teraz išlo o to zariadiť aby program na PC komunikoval s robotom a dobre si vzájomne rozumeli :) Úplne všetko by bolo krásne jednoduché, keby v C++ Builderi existoval jednoduchý príkaz Delay. Poslal by sa príkaz robotovi, počkalo sa istý delay, robot by poslal naspäť stav snímačov, počkal by sa istý delay, program by rozhodol čo ďalej, počkal by sa istý delay, program by navrhol ďalší príkaz.
Áno takto by to bolo jednoduché, bohužiaľ - v C++ Builderi žiadny delay nie je :E Je tu však Timer a na prvý pohľad to vyzerá ako perfektná náhrada. Ovládať jeden timer sa ešte dá, dva tiež ako tak, ale v našich programoch bolo potrebné timerov dosť :) Nejdem tu rozpisovať celé to timerovanie, ale pointa je v tom, že to bol dobrý trénning na vytrvalosť a sebakontrolu :)
Druhá vec, na ktorú som si schuti zanadával boli opäť genetické algoritmy. V nich totiž občas robot urobí jeden krok, občas dva, občas sa otočí a - samozrejme všetko treba správne načasovať. Ďalšia nepríjemná vlastnosť celých genetických algoritmov bolo to, že sme ich síce mali aj ja aj djMabo rovnaké, ale ich implementácia už taká rovnaká nebola, takže ak rozbehanie genetických algoritmov u ňho trvalo 1 deň, tak u mňa nestačilo dať copy paste, ale pekne som si ich musel napísať nanovo :E Jediná pozitívna vec bol fakt, že všetky ďalšie algoritmy, ktoré som použil v mojom programe sa do robota (teda tak aby naozaj chodil) implementovali o mnoho ľahšie. Uff konečne - celé to chodilo a ostávalo už *len* napísať teoretickú časť diplomovej práce. (V skutočnosti sme obaja začali písať svoje teoretické časti už skôr, ale podstatné je že to vôbec nebolo až tak ľahké)

Písomná časť diplomovej práce

Všetci síce tvrdia, že keď robíte niečo praktické, tak napísať teoretickú časť diplomovej práce je hračka, stačí skopírovať pár odstavcov z internetu a dorobiť úvod a záver. Tak v mojom prípade (a myslím, že djMabovom tiež) to až tak ľahké nebolo. Zohnať nejakú knihu o expertných systémoch nebolo až také ľahké, a odpísať všetko z internetu - no to bolo dosť odvážne :) Po nejakom čase som zohnal jednu jedinú knižku, ktorú písal iný macher, a pre niekoho kto rieši problematiku expertných systémov necelé dva mesiace (rozumej mňa) nebolo vôbec ľahké pochopiť, že o čom to vlastne píše :) Aj tak však vznikla zaujímavá situácia - ako som tak čítal tú knižku tak som si uvedomoval, že tie veci o ktorých sa tam píše som naozaj tak vo svojom programe spravil. Fajn - aspoň som to mal teda k veci. Keď už som ako tak pochopil o čom to je tak som skopíroval pár strán textu, doplnil dačo z internetu a práca bola hotová :) Teda to som si myslel. Náš diplomový vedúci mal na to samozrejme iný názor a s prehľadom mi to poškrtal, a ak aj bola teória celkom k veci, tak úpravu práce vraj bolo treba *hodne* zlepšiť. Uff zabil som ďalších pár dní kým to bolo ako tak k svetu, a najmä - doplnil som tam pár celkom zaujímavých informácii z internetu. Našiel som totiž na dc++ pár fajn kníh a aspoň zbežne som si ich prelistoval. Samozrejme, že som veľa z nich uviedol aj v literatúre a tak moja práca začínala vyzerať ako tak k svetu (to množstvo anglických odkazov v použitej literatúre proste vzbudzovalo dobrý dojem - oponent mi neskôr povedal, že je tej literatúry málo :) Nebudem zase veľmi preháňať, podarilo sa mi to celkom v pohode dopísať a odovzdať dosť skoro pred termínom odovzadania a bol som *poriadne* spokojný, že už to mám všetko za sebou.

ŠVOČ a obhajoba

So ŠVOČkou (tak ako s veľa vecami na našej škole) bol zase trochu chaos. Myslel som, že pôjdeme s djMabom ako dvojica a urobíme prezentáciu o tom čo sme spoločne dosiahli. Deň (konkrétne 2hod) pred uzavretím prihlášok sa však ukázalo, že o mne nikto nič nevie, a teda som sa musel prihlásiť s mojou prácou sám. V duchu som si zanadával, lebo bolo evidentné, že budeme prezentovať skoro to isté, robot bude ten istý, naše programy budú tie isté a jediný rozdiel bude iba v tom ako robot rozmýšľa. Bolo síce fajn, že ten môj rozmýšľal o dosť lepšie (ale aj djMabova vec je fajn :) ale aj tak som nebol spokojný z toho, že mám ďalšiu prácu navyše. Našťastie som túto "prácu navyše" značne zredukoval :) Copy Paste z diplomky a anotácia bola hotová. Pár screenshotov z programu, nejaké obrázky tabuľka z diplomky, a aj prezentácia bola hotová. Ešte nejaké animácie a prelietajúci text a som pripravený. Pár dní pred tým som sa dozvedel, že tam budú aj zahraniční súťažiaci, tak som si to prerobil do angličtiny. Chvíľu som sa aj pohrával s myšlienkou, že aj hovoriť budem po anglicky, ale nakoniec ma môj elán prešiel, dôležité to bolo mať už celé za sebou...
ŠVOČ prebiehala skutočne veľmi v pohode. Musím povedať, že niektorí tam mali také kraviny (pri všetkej úcte) že som fakt len krútil hlavou. Už aj ten "môj vynález" som považoval za nič extra, no porota mala na to iný názor. Prvé miesto nakoniec obsadil taký poliak s databázou na PDA, druhé miesto ja a tretie djMabo. (sa mi nechelo veriť, že nám dali až dva miesta, ale asi sa im to naozaj veľmi páčilo :) Dnes mám na stene pekný diplom a dobrý pocit. Ale aj tak - ako som povedal v úvode, keby som si mal dnes vybrať, tak určite by som nechcel robiť praktickú diplomovú prácu. Je s tým *fakt* veľa starostí. Čo sa týka ŠVOČ tak to je dobrá vec, a doporučujem zúčastniť sa toho obhajoba diplomovej práce bude potom hračka.
Druhé miesto na ŠVOČ bolo zárukou toho, že diplomovú prácu obhájim bez problémov, a vôbec ma neprekvapilo keď som dostal hodnotenie od vedúceho za 1 (aj keď sa mu pár vecí nepáčilo, a možno sme spolu najlepšie nevychádzali :) a od recenzenta tiež 1. Na obhajobu pri štátniciach som sa teda nepripravoval vôbec, aj tak som si bol na 90 percent istý, že to bude zas za jedna :)
A dnes? Dnes som rád, že už je škola za mnou, a dúfam, že keď raz budem v živote niečo podobné robiť, tak za to dostanem veľa peňazí :)

Download

Tak ak vás to zaujalo tak tu si môžete stiahnuť väčšinu materiálov z mojej diplomovej práce, vrátane jej finálnej podoby, programu a zdrojových kódov. Ako som vravel, na začiatku nevadí mi to, aj tak sú voľne dostupné na priloženom CD v knižnici. Práca je v pdf iba kvôli tomu aby nezaberala toľko miesta, ak mi napíšete pošlem vám ju aj v Microsoft Word doc formáte.


Finálna podoba diplomovej práce v pdf (864 kB)
Príloha E - podrobné výsledky testov v pdf (77 kB)
Pokec na ŠVOČ v pdf (633 kB)
Prezentácie na ŠVOČ (1.48 MB)
Sergej Mk4 - aplikácia (2.33 MB)
Zdrojový kód aplikácie, aj robota (1.15 MB)