MoRoUS
Mozek, Robotika, Umělá inteligence SŠ korespondenční Seminář
MoRoUS je nov´ y korespondenˇ cn´ı semin´ aˇ r pro vˇsechny stˇredoˇskol´aky, kter´e zaj´ım´a umˇ el´ a inteligence, mozek ˇci robotika. Organiz´atoˇri ˇ semin´aˇre jsou pˇrev´aˇznˇe studenti FEL CVUT. • • • • •
M´ aˇs r´ ad logick´e u ´lohy, tvoˇr´ıˇs r´ ad nˇeco nov´eho? Zaj´ım´ a Tˇe, jak se dˇeti nauˇc´ı mluvit a rozumˇet? A jak to nauˇcit robota? Jak naj´ıt nejkratˇs´ı cestu mˇestem? Jak to, ˇze se dok´ aˇzeme pohybovat a jak je ˇr´ızen pohyb u robota? • Jak se rozhodujeme a jak pl´ anujeme? • Jak nacpat co nejv´ıc vˇec´ı do mal´eho batohu? • Jak se ˇs´ıˇr´ı davem panika ˇci nadˇsen´ı? Pˇrenes se s n´ ami do roku 2129 na planetu Mu vzd´ alenou pouh´ ych 12 svˇeteln´ ych let od Zemˇe, kter´ a je obydlen´ a pouze roboty, a spolu s n´ami a profesorem Morousem pojd’ nal´ezt na tyto a mnoh´e dalˇs´ı ot´ azky odpovˇed’.
Co Tˇ eˇ cek´ a? • 3 s´ erie zad´ an´ı bˇ ehem roku (v z´ aˇr´ı, v prosinci a v u ´noru), v kaˇzd´em z nich najdeˇs 4 u ´lohy a tak´e t´em´ atka, kter´ a lze ˇreˇsit bˇehem cel´eho roku. • 4-denn´ı soustˇ redˇ en´ı na konci roku, kde dostaneˇs moˇznost vyzkouˇset si, jak Tvoje ˇreˇsen´ı funguj´ı pˇr´ımo v re´ aln´ ych robotech ˇci datech z nemocnic, ale hlavnˇe Tˇe ˇcekaj´ı ˇ ctyˇ ri dny pln´ e z´ aˇ zitk˚ u, her, pˇ redn´ aˇ sek a zaj´ımav´ ych lid´ı. • Ceny pro nejlepˇ s´ı ˇ reˇ sitele a nezapomenuteln´ y pocit z v´ıtˇezstv´ı :-D
Se spoustou u ´ loh si nev´ım rady. . . Nevˇeˇs hlavu, urˇcitˇe v tom nebudeˇs s´ am. Staˇc´ı, kdyˇz poˇsleˇs ˇreˇsen´ı jen nˇekter´ ych u ´loh nebo jejich ˇc´ ast´ı, i ty mohou rozhodnout.
Aktu´aln´ı informace a zad´an´ı najdeˇs na naˇsich webov´ ych str´ank´ach
http://morous.felk.cvut.cz Sledovat n´ as m˚ uˇzeˇs tak´e na Facebooku Morous – korespondenˇcn´ı semin´ aˇr https://www.facebook.com/seminarmorous
Robotika, Umělá inteligence MoRoUS Mozek, SŠ korespondenční Seminář
P´ıˇse se rok 2129 a na planetˇ e Mu ob´ıhaj´ıc´ı kolem hvˇ ezdy sluneˇ cn´ıho typu vzd´ alen´ e pouh´ ych 12 svˇ eteln´ ych let od Zemˇ e, ˇ zije obyvatelstvo ne zcela nepodobn´ e lidsk´ emu. Na prvn´ı pohled byste jak´ ekoli rozd´ıly hledali jen velmi tˇ eˇ zko, nebot’ vypadaj´ı t´ emˇ eˇr stejnˇ e jako lid´ e a i jejich chov´ an´ı je velmi podobn´ e. Jedin´ y rozd´ıl je v tom, ˇ ze nam´ısto srdce maj´ı pod svou k˚ uˇ z´ı ukryt´ y samonab´ıjec´ı zdroj energie. Jedn´ a se o spoleˇ cnost sest´ avaj´ıc´ı z robot˚ u, kter´ a nejen, ˇ ze spolu komunikuje a vypad´ a jako lid´ e, ale dok´ aˇ ze b´ yt i sama sobˇ estaˇ cn´ a ve vytv´ aˇren´ı nov´ ych bytost´ı“. ” Jedin´ y ˇ clen spoleˇ cnosti, kter´ y vznikl pˇrirozenou cestou a kter´ emu v lev´ e polovinˇ e tˇ ela bije skuteˇ cn´ e srdce a v ˇ zil´ ach prot´ ek´ a krev, je prof. Morous, kter´ y pˇr´ıˇst´ı rok oslav´ı sv´ e 150. narozeniny. Vˇ ek se na star´ em p´ anovi projevuje st´ ale v´ yraznˇ eji a asi i proto, ˇ ze tuˇs´ı, ˇ ze mu ˇ casu uˇ z pˇr´ıliˇs nezb´ yv´ a, ˇ ım hloubˇ tr´ av´ı nyn´ı mnoh´ e hodiny nad pap´ırem a sepisuje sv´ e pamˇ eti. C´ eji se noˇr´ı do minulosti, t´ım v´ıc se rozpom´ın´ a na sv´ eu ´trapy a probl´ emy, se kter´ ymi se musel bˇ ehem konstrukce a v´ yvoje robot˚ u pot´ ykat. Mnohdy si ani nem˚ uˇ ze pˇresnˇ e rozpomenout, jak kter´ y probl´ em kdysi ˇreˇsil. Pojd’te s n´ım proj´ıt tuto strastiplnou cestu a pomoci mu vzpomenout si na ˇreˇsen´ı probl´ em˚ u, se kter´ ymi se musel vypoˇr´ adat.
3. s´ erie 2014/2015 Term´ın odesl´an´ı 3. s´erie: 5. 4. 2015 Vzpom´ınkov´ a kniha u ´spˇeˇsnˇe pokraˇcovala a prof. Morous pˇrid´aval dalˇs´ı a dalˇs´ı kapitoly. Nyn´ı se zamyslel nad d˚ uleˇzit´ ym probl´emem, kter´ ym byla v´ yroba a distribuce zdroj˚ u po planetˇe. Hned od zaˇc´ atku bylo jasn´e, ˇze vˇsechny suroviny, kter´e pˇrivezl sebou ze Zemˇe nebudou dostaˇcovat pro plynul´ y pr˚ ubˇeh zabydlov´an´ı planety. Z toho d˚ uvodu museli co nejrychleji vybudovat s´ıt’ silnic, zjistit dostupn´e zdroje na planetˇe a tak´e se zapojit do obchodu s meziplanet´ arn´ımi plavidly, kter´e obˇcas na planetˇe zastavovaly. Vˇetˇsina tˇechto probl´em˚ u byla d´ıky velmi inteligentn´ım robot˚ um dobˇre ˇreˇsiteln´ a, i kdyˇz se samozˇrejmˇe na zaˇc´ atku pot´ ykali s jist´ ymi obt´ıˇzemi. . .
1. u ´ loha (20. bod˚ u) Profesor se rozpom´ınal na znaˇcn´e probl´emy pˇri tˇr´ıdˇen´ı a rozvozu z´asob, kter´e se opakovaly mnoho mˇes´ıc˚ u, neˇz se podaˇrilo naj´ıt uspokojiv´ y automatick´ y syst´em. Z´ asoby byly urˇceny do tˇr´ı mˇest a bal´ıky byly oznaˇceny poˇc´ateˇcn´ımi p´ısmeny jejich jmen: L, A a P. Vzhledem k tomu, ˇze ruˇcn´ı tˇr´ıdˇen´ı bylo sice pˇresn´e, ale nepraktick´e a pomal´e, bylo pˇri st´ ale se zvˇetˇsuj´ıc´ım objemu dod´avek nutn´e navrhnout linku pro jejich automatick´e tˇr´ıdˇen´ı. Profesor si vzpom´ınal, ˇze pozice adresn´ıho ˇst´ıtku na bal´ıku byla pˇredem d´ ana a probl´emem tedy bylo pouze rozpoznat dan´e p´ısmeno. Ke sn´ım´ an´ı byla pouˇzita jednoduch´ a kamera o rozliˇsen´ı 8×6 pixel˚ u (obrazov´ ych bod˚ u), rozliˇsuj´ıc´ı stupnˇe ˇsedi (0 – ˇcern´ a, 1 – b´ıl´ a). Po prvn´ıch testech bylo zˇrejm´e, ˇze u ´loha 2
Robotika, Umělá inteligence MoRoUS Mozek, SŠ korespondenční Seminář
nebude tak snadn´ a, jak se myslelo. Data obsahovala znaˇcn´ y ˇsum a m´alokdy se body p´ısmene trefily pˇresnˇe do pixel˚ u kamery. Vzorov´ a p´ısmena vypadala n´asledovnˇe (viz obr´ azek 1):
Obr´ azek 1: Vzorov´ a p´ısmena na bal´ıc´ıch Zat´ımco re´ alnˇe nasn´ıman´ a p´ısmena vypadala sp´ıˇse takto (viz obr´azek 2):
Obr´ azek 2: Skuteˇcn´ a p´ısmena na bal´ıc´ıch 1. Navrhnˇete, jak´ ym zp˚ usobem byste chytˇre slouˇcili informaci obsaˇzenou v jednom obr´ azku do jednoho ˇc´ısla (tzv. pˇr´ıznaku) tak, aby co nejl´epe postihovalo rozd´ıly mezi p´ısmeny A a L. Pozn.: jeden obr´azek je vlastnˇe pole 8×6 ˇc´ısel z rozsahu h0, 1i. 2. Navrhnˇete obdobn´ y pˇr´ıznak jako v pˇredchoz´ım bodˇe tak, aby dobˇre rozliˇsoval mezi p´ısmeny A a P. 3
Robotika, Umělá inteligence MoRoUS Mozek, SŠ korespondenční Seminář
hodnota X h0; 0, 2) h0, 2; 0, 4) h0, 4; 0, 6) h0, 6; 0, 8) h0, 8; 1i
poˇc. v´ yskyt˚ uvA 10 6 3 1 0
poˇc. v´ yskyt˚ uvL 1 0 3 7 9
poˇc. v´ yskyt˚ uvP 4 8 4 3 1
Tabulka 1: V´ ysledky pozorov´ an´ı pˇr´ıznak˚ u
3. Nyn´ı zkuste vymyslet jeden pˇr´ıznak, kter´ y by rozliˇsoval mezi vˇsemi tˇremi p´ısmeny. Jak dobˇre mysl´ıte, ˇze by fungoval? 4. Pomohlo by v pˇredchoz´ım bodˇe pˇrid´ an´ı dalˇs´ıho pˇr´ıznaku? Bylo by moˇzn´e pouˇz´ıt vaˇse pˇr´ıznaky z bod˚ u 1 a 2? Profesor Morous si nemohl v˚ ubec vzpomenout, jak obr´azky z kamery nakonec pˇrepoˇc´ıtali do pˇr´ıznak˚ u, ale vˇedˇel, ˇze nakonec mˇeli pomˇernˇe dobr´ y pˇr´ıznak X. Dalˇs´ım krokem bylo, ˇze ruˇcnˇe roztˇr´ıdili 20 bal´ık˚ u od kaˇzd´eho druhu a pro kaˇzd´ y zjistili hodnotu X, kterou nav´ıc pro jednoduchost rozdˇelili do pˇeti interval˚ u. V´ ysledky sv´ ych pozorov´ an´ı zapsali do tabulky podobn´e tabulce 1. 5. Pokud tedy pˇriˇsel bal´ık a syst´em ho ohodnotil hodnotou X = 0, 27, do kter´eho mˇesta byste jej poslali, aniˇz byste se d´ıvali na jeho oznaˇcen´ı? 6. Pokud byste d´ ale vˇedˇeli, ˇze bal´ıky do A jsou dvakr´at ˇcastˇejˇs´ı neˇz do L a tˇrikr´at ˇcastˇejˇs´ı neˇz do P, do kter´eho mˇesta byste poslali bal´ık s hodnotou X = 0, 51, aby pravdˇepodobnost chyby (tj. odesl´ an´ı bal´ıku na ˇspatnou adresu) byla co nejniˇzˇs´ı?
2. u ´ loha (20. bod˚ u) S´ıt’ cest na planetˇe se stala pˇr´ıliˇs rozs´ ahlou a jiˇz nebylo v robot´ıch sil´ach ji celou udrˇzovat (viz pˇr´ıklad z minul´e s´erie). Bylo zbyteˇcn´e, aby mezi dvˇema m´ısty vedla v´ıce neˇz jedna cesta. Profesor se tedy chv´ıli zad´ıval do mapy silnic a pˇrebyteˇcn´e silnice zakr´ atko vyˇskrtal. Pak se na chv´ıli zamyslel, p´ar z nich zase zp´atky pˇrikreslil a vymazal jin´e. Ted’ je to ide´ aln´ı,“ pomyslel si. ” Na obr´ azku 3 je pˇr´ıklad, jak takov´ a mapa silnic na planetˇe m˚ uˇze vypadat, ale skuteˇcn´ a s´ıt’ se m˚ uˇze liˇsit. Je tedy potˇreba vymyslet ˇreˇsen´ı tak, aby fungovalo pro ˇ libovolnou situaci. Cern´ e teˇcky jsou d˚ uleˇzit´ a m´ısta, spojnice mezi nimi zn´azorˇ nuj´ı cesty (silnice) a ˇc´ıslo u nich popisuje jejich d´elku. 4
Robotika, Umělá inteligence MoRoUS Mozek, SŠ korespondenční Seminář
Obr´ azek 3: Vzorov´ y pˇr´ıklad mapy silnic na planetˇe 1. Jak ze vˇsech cest vybrat takov´e, aby v´ ysledn´ a s´ıt’ silnic byla spojit´a (tj. aby existovala trasa mezi libovoln´ ymi dvˇema body) a aby neobsahovala zbyteˇcnˇe mnoho cest (tj. aby mezi vˇsemi m´ısty byla pouze jedna takov´a trasa)? 2. Jak zmˇenit postup, aby souˇcet d´elek vˇsech vybran´ ych silnic byl co nejmenˇs´ı?
3. u ´ loha (20. bod˚ u) Profesor Morous se hned od zaˇc´ atku snaˇzil, aby novˇe obydlen´a planeta prosperovala a tˇeˇzila i z meziplanet´ arn´ıho obchodu. Snaˇzil se proto co nejl´epe vyuˇz´ıt jej´ı pˇr´ırodn´ı zdroje a v tov´ arn´ ach, kter´e na planetˇe vybudoval, nechal podle peˇcliv´ ych propoˇct˚ u vyr´ abˇet produkty, kter´e byly tehdy ˇz´ adan´e v cel´em zn´am´em vesm´ıru. Na planetˇe Mu se nach´ az´ı tov´ arna, ve kter´e jsou vyr´abˇeny lodˇe, auta a letadla. • V tov´ arnˇe maj´ı k dispozici 100 ks plastu, 130 ks ˇzeleza, 130 ks dˇreva, 100 ks skla a 30 ks drahokam˚ u. • Hodnota vyroben´e lodˇe je 30, auta 30 a letadla 50 MpC (Meziplanet´arn´ı Coin).
5
Robotika, Umělá inteligence MoRoUS Mozek, SŠ korespondenční Seminář
Na v´ yrobu lod´ı, aut a letadel je potˇreba n´ asledujic´ı poˇcet kus˚ u jednotliv´ ych surovin: • auto: 2 ˇzeleza, 1 sklo, 1 plast • letadlo: 1 drahokam, 1 sklo, 1 plast, 1 ˇzelezo • lod’: 3 dˇreva, 1 sklo, 1 ˇzelezo. 1. Kolik kus˚ u kter´eho v´ yrobku maj´ı roboti vyrobit, aby maximalizovali zisk? (Pˇredpokl´ adejte, ˇze prodaj´ı vˇse, co vyrob´ı.) 2. Kolik kus˚ u surovin jim z˚ ustane na skladˇe? 3. Je ˇreˇsen´ı jednoznaˇcn´e? 4. Suroviny, kter´e z˚ ustanou na skladˇe, je moˇzn´e prodat meziplanet´arn´ım vozidl˚ um, kter´e obˇcas na planetˇe zastavuj´ı. V´ ykupn´ı cena plastu je 2, dˇreva a skla 4, ˇzeleza 5 a drahokam˚ u 9 MpC. Jak´e je nyn´ı nejlepˇs´ı ˇreˇsen´ı?
4. u ´ loha (20. bod˚ u) Nˇejakou dobu se profesor pot´ ykal s probl´emem jak co nejefektivnˇeji vyhled´avat na povrchu planety jednotliv´e suroviny. Ty se nach´ azely ˇcasto tˇesnˇe pod povrchem ˇci pˇr´ımo na povrchu. Dle toho, jak´ a surovina se pod povrchem nach´azela, liˇsily se i vlastnosti povrchu nad n´ı. Nakonec se mu d´ıky vyuˇzit´ı r˚ uzn´ ych senzor˚ u um´ıstˇen´ ych na tˇele robot˚ u podaˇrilo, ˇze byli schopni jednoduˇse detekovat, jak´a surovina se nach´az´ı pod povrchem. Roboti maj´ı na tˇele um´ıstˇeny jednotliv´e senzory: kameru, detektor zvuku, elektronick´ y nos, elektronick´ y detektor chuti a tlakov´e senzory. Povrch se dle suroviny uloˇzen´e pod n´ım mohl liˇsit v n´asleduj´ıc´ıch vlastnostech: barva povrchu, zvuk vydan´ y po naˇsl´ apnut´ı, pevnost povrchu, v˚ unˇe a chut’ zeminy. Na zkuˇsebn´ıch vzorc´ıch se podaˇrilo namˇeˇrit data zaznamenan´a v tabulce 2. 1. Pomoc´ı kter´eho ze senzor˚ u dok´ aˇzete nejl´epe rozliˇsit, jak´a surovina bude pod povrchem? V kolika procentech budete pˇri pouˇzit´ı tohoto senzoru u ´spˇeˇsn´ı? Jak jste nastavili hodnoty hranic pro odliˇsen´ı surovin? Pokuste se ˇreˇsen´ı zakreslit. 2. Spoˇctˇete, v kolika procentech pˇr´ıpad˚ u dok´ aˇzete spr´avnˇe urˇcitˇe povrch, pokud vyuˇzijete samostatnˇe jednotliv´e senzory (kameru, audio z´aznam, elektronick´ y nos, elektronick´ y jazyk a tlakomˇer). 3. Je mezi senzory nˇejak´ y, kter´ y n´ am pˇri naˇsich mˇeˇren´ı nedal ˇz´adnou informaci o tom, jak´ a surovina je pod povrchem? 6
Robotika, Umělá inteligence MoRoUS Mozek, SŠ korespondenční Seminář
ˇ mˇeˇreni C. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Surovina Uhl´ı Drahokamy ˇ Zelezo ˇ Zelezo Drahokamy Uhl´ı Uhl´ı ˇ Zelezo Uhl´ı ˇ Zelezo Uhl´ı Drahokamy Drahokamy ˇ Zelezo Drahokamy
El. nos 1 2 1 4 3 2 1 4 1 4 2 3 3 4 3
El. jazyk 1 2 5 4 1 3 2 2 5 3 4 3 5 1 4
Kamera 3 3 4 4 3 3 3 4 4 4 4 3 3 4 3
Audio 3 2 2 2 2 3 3 2 3 2 3 2 2 2 2
Tlakov´e s. 5 2 1 2 3 4 4 5 5 1 5 2 2 4 3
Tabulka 2: Zkuˇsebn´ı vzorky
4. Jak se zmˇen´ı u ´spˇeˇsnost rozliˇsen´ı surovin, pokud pouˇzijete kombinaci dvou ˇci v´ıce senzor˚ u? Existuje nˇejak´ a kombinace senzor˚ u, kter´a jiˇz bude robot˚ um dostaˇcovat pro rozliˇsen´ı surovin pod povrchem (pro dan´e mˇeˇren´ı)? Pokuste se vizualizovat vaˇse ˇreˇsen´ı a do grafu (2D ˇci 3D) zakreslete hranice, kter´e jste pro odliˇsen´ı typ˚ u surovin pouˇzili.
7
Robotika, Umělá inteligence MoRoUS Mozek, SŠ korespondenční Seminář
T´ em´ atko T´em´ atka m˚ uˇzete odes´ılat v pr˚ ubˇehu cel´eho roku. Je jen na v´as, jestli k nˇemu nap´ıˇsete program, nakresl´ıte obr´ azkov´e ˇreˇsen´ı, vyrob´ıte ˇreˇsen´ı v re´alu, ˇci jen pop´ıˇsete sv´e myˇslenky. Pokuste se vˇzdy ale pˇrij´ıt s nˇejak´ ym sv´ ym n´apadem a dobˇre ho zd˚ uvodnˇete.
T´ em´ atko ˇ c. 1: Rozhovor s robotem (20 bod˚ u) Jak byste otestovali, zda se bav´ıte s robotem, nebo s ˇclovˇekem? Zamyslete se, co dˇel´a ˇclovˇeka skuteˇcnˇe ˇclovˇekem. Kdy pˇri rozhovoru pozn´ ate, ˇze v´am odpov´ıd´a stroj? Jak´e vˇeci je dnes nejsloˇzitˇejˇs´ı vyrobit a kter´e naopak ani do robot˚ u vkl´adat nechceme?
Kam pos´ılat ˇ reˇ sen´ı? Aˇz budeˇs m´ıt ˇreˇsen´ı hotov´e, poˇsli n´ am pros´ım cel´ a sv´a ˇreˇsen´ı, vˇcetnˇe vˇsech n´akres˚ u, progr´ amk˚ u, prostˇe vˇse co by n´ am usnadnilo opravov´ an´ı Tv´e u ´lohy. Staˇc´ı, kdyˇz poˇsleˇs ˇreˇsen´ı jen nˇekter´ ych u ´loh nebo jejich ˇc´ ast´ı. ˇ sen´ı pos´ılej nejl´epe e-mailem na adresu
[email protected], Reˇ nebo poˇstou (ˇreˇsen´ı kaˇzd´e u ´lohy v tomto pˇr´ıpadˇe napiˇs na samostatn´ y pap´ır A4) na adresu Korespondenˇcn´ı semin´ aˇr Morous, ˇ Katedra kybernetiky FEL CVUT, Karlovo n´ amˇest´ı 13, 121 35 Praha Eda, Eva, Honza, K´ aja, Martin, Mirek, Ondra, Petr, Radek a Terka 8
