F A K U L T A I N F O R M A T I K Y
P O S U D E K O P O N E N T A B A K A L Á Ř S K É P R Á C E Masarykova univerzita
N á z e v p r á c e : Navigace bludištěm pomocí prohledávám stromu metodou Monte Carlo
Autor p r á c e : Ján Petrák
P r á c e se z a b ý v á a p l i k a c í z n á m é h o a l g o r i t m u M o n t e Carlo Tree Search ( M C T S ) na p r o b l é m p r o c h á z e n í b l u d i š t ě m . V p r á c i j s o u d i s k u t o v á n y n á s l e d u j í c í o t á z k y : Jak s p r á v n ě reprezentovat b l u d i š t ě z hlediska m i n i m a l i z a c e č a s u v ý p o č t u ? Jak nastavit hyperparametry M C T S v z h l e d e m ke kvalitě v ý s l e d k u i č a s u v ý p o č t u ? Jak modifikovat z á k l a d n í M C T S algoritmus pro efektivnější ř e š e n í b l u d i š ť z d a n é h o benchmarku?
P r a k t i c k á část p r á c e je z a l o ž e n a n a p o u ž i t í n á s t r o j e AI-Toolbox s t í m , že výše u v e d e n é modifikace M C T S algoritmu jsou provedeny v p ř í s l u š n ý c h č á s t e c h onoho toolboxu. Student e v i d e n t n ě pochopil, jak M C T S v praxi funguje, a o v l á d l A I - Toolbox na d o s t a t e č n é úrovni, aby byl schopen takové modifikace u d ě l a t . D o s a ž e n é v ý s l e d k y jsou p o m ě r n ě z a j í m a v é z e j m é n a s o h l e d e m na to, že v e l k á část z n i c h se o b t í ž n ě d o h l e d á v á v existující l i t e r a t u ř e ( t é m ě ř k a ž d ý u ž i v a t e l učících a l g o r i t m ů řeší n a s t a v e n í h y p e r p a r a m e t r ů , ale m á l o k d o o nich do detailu píše v p u b l i k a c í c h ) . Text p r á c e je v e l m i d l o u h ý , což je č á s t e č n ě z p ů s o b e n o z a ř a z e n í m v e l k é h o m n o ž s t v í m e n š í c h tabulek, které mohly být a g r e g o v á n y a p o t é p ř e s u n u t y do přílohy.
N i c m é n ě celkově je text čitelný a obsahuje zajímavé p o s t ř e h y týkající se ř e š e n ý c h p r o b l é m ů . Z hlediska prezentace bych pouze v y t k n u l p ř e t ě ž o v á n í slova „ s p a r s e " , k t e r é se objevuje v m i n i m á l n ě dvou z a m ě n i t e l n ý c h v ý z n a m e c h .
Po k r á t k é m ú v o d u (kapitola 1) následuje kapitola 2 s r o z u m i t e l n ě popisující for
malizaci bludišť p o m o c í Markovových r o z h o d o v a c í c h p r o c e s ů a popisuje algoritmus M C T S . Součástí t é t o kapitoly je i prezentace metod AI-Toolboxu, kterou považuji za z b y t e č n ě technickou a odsunutelnou do přílohy. Zde se v textu objevuje n a s t a v e n í 0.99 pro discount factor. Autor tvrdí, že je tato hodnota d o s t a t e č n ě blízká 1 a tedy v h o d n ě aproximuje „ u n d i s c o u n t e d " sumu o d m ě n . A l e j e tomu s k u t e č n ě tak? Cesty v bludištích m o h o u být z a t r a c e n ě d l o u h é .
Kapitola 3 se z a b ý v á v h o d n o u v o l b o u reprezentace b l u d i š t ě . A u t o r p o r o v n á v á dva p ř í s t u p y k v ý p o č t u p ř e c h o d ů : V ý p o č e t p ř e d s p u š t ě n í m M C T S a v ý p o č e t p ř e c h o d ů za b ě h u . Autor objektivně analyzuje klady a z á p o r y obou přístupů, v p o d s t a t ě n e m á m co vytknout. V p ř í p a d ě v ý p o č t u p ř e d e m se autor z a b ý v á r e p r e z e n t a c í vy
p o č t e n ý c h p ř e c h o d ů . Zde d o c h á z í k závěru, že reprezentace p o m o c í řídkých matic je v ý h o d n á , s čímž nelze nesouhlasit.
Kapitola 4 obsahuje d e t a i l n í e x p e r i m e n t á l n í v y h o d n o c e n í r ů z n ý c h n a s t a v e n í n ě k t e r ý c h p a r a m e t r ů M C T S . Navíc přináší originální heuristiky pro jejich n a s t a v e n í . Celkově je tato kapitola j e d n í m z h l a v n í c h p ř í n o s ů p r á c e . Trochu m i zde c h y b í explicitní j e d n o d u c h é p ř í k l a d y b l u d i š ť , n a n i c h ž j e d n o t l i v é heuristiky selhávají.
Autor se drží bludišť z benchmarku, diskutuje e x p e r i m e n t á l n í výsledky, ale o d h a l e n í
Oponent: doc. RNDr. Tomáš Brázdil, Ph.D.
1
slabin na m i n i m a l i z o v a n ý c h p ř í k l a d e c h by h o d n o t u t é t o p r á c e v ý z n a m n ě zvýšilo.
N i c m é n ě vzhledem k tomu, že se j e d n á o b a k a l á ř s k o u práci, považuji p r e z e n t o v a n é výsledky za n a d s t a n d a r d n í .
Kapitola 5 popisuje sadu heuristik pro zlepšení s a m o t n é h o M C T S na bludištích.
Heuristiky jsou to v e s m ě s j e d n o d u c h é , ale jejich k o m b i n a c í lze e v i d e n t n ě d o s p ě t k v y l e p š e n í v ý s l e d k ů . A u t o r o p ě t celkem s r o z u m i t e l n ě shrnuje d o s a ž e n é v ý s l e d k y a p ř e h l e d n ě prezentuje heuristiky.
Celkově se d o m n í v á m , že student odvedl velké m n o ž s t v í kvalitní p r á c e a navr- zhuji z n á m k u A .
Brno 16. č e r v n a 2019 Tomáš Brázdil
2
