Преглед на темата

  • Основно

    Затвори ги сите Прошири ги сите

    Predavatelj: doc. dr. Aleksander Sadikov (aleksander.sadikov@fri.uni-lj.si)

    Asistenta: doc. dr. Vida Groznik (vida.groznik@fri.uni-lj.si), doc. dr. Jure Žabkar (jure.zabkar@fri.uni-lj.si)

  • Kolokviji in izpiti

  • Preiskovalni algoritmi

    V tem poglavju smo najprej spoznali tako imenovane neinformirane preiskovalne algoritme, iskanje v globino, iskanje v širino in iterativno poglabljanje. Poleg same uporabnosti teh algoritmov, nam kasneje velikokrat pridejo prav koncepti, ki smo jih pri tem spoznali (npr. poglabljanje, vračanje ali uporaba iskanja v globino znotraj kompleksnejših algoritmov). Algoritme so primerjali glede na njihovo prostorsko in časovno zahtevnost in glede na optimalnost rešitve (merjene kot število korakov). V drugem delu tega poglavja smo spoznali kako koristne so lahko hevristične ocene, ki vodijo preiskovanje. Spoznali smo informirana algoritma A* in IDA* ter videli, da oba zagotavljata optimalnost rešitve (v smislu njene cene) pod pogojem, da je hevristična funkcija, ki ju vodi, dopustna. Spoznali smo tudi pomen monotone (konsistentne) hevristične funkcije za algoritem IDA*.

    Naučili smo se tudi, kako konkreten problem opišemo v t.i. prostoru stanj, da ga lahko potem rešimo s pomočjo preiskovalnih algoritmov.

    Vse pojme lahko vidite in preizkusite na primeru sveta GridWorld v Python zvezku spodaj. Zraven snemite ločeno datoteko s preprostimi implementacijami preiskovalnih algoritmov (bsearch.py), ki jo zvezek potrebuje za delovanje.

  • Igre in preiskovalni algoritmi za dva igralca

    V tem sklopu smo si pogledali pristope za igranje nasprotniških iger za dva igralca (razširljivo tudi za več igralcev). Predstavili smo dobri stari algoritem minimax, ki je še vedno osnova za marsikatero igro za katero znamo ustvariti dobro hevristično ocenjevalno fukcijo. Le-ta vodi preiskovanje enako kot pri algoritmih iz prejšnjega poglavja. V nadaljevanju smo predstavili "varno" nadgradnjo osnovnega minimax algoritma, t.j. alfa-beta rezanje. Takšno rezanje je varno, ker zagotovljeno vrne enak rezultat kot minimax, le veliko hitreje. Koliko hitreje lahko vidite v priloženem jupyter zvezku.

    Kot alternativo, ki ne potrebuje hevristične ocenjevalne funkcije, smo spoznali Monte-Carlo pristope. Z večanjem računskih zmogljivosti računalnikov so ti pristopi postali zelo močna alternativa klasičnim pristopom na osnovi minimax algoritma. Demonstrirali smo moč naključnih simulacij, več spet lahko vidite v jupyter zvezku. Preprosti Monte-Carlo pristopi pa ne izkoriščajo najbolje zmogljivosti (časa), ki so jim na voljo. Tako smo si ogledali moderno nadgradnjo MCTS (Monte-Carlo Tree Search), ki večino časa nameni zanimivim kandidatom za naslednjo potezo v igri.

    Na koncu smo si na kratko pogledali pristope AlphaZero, ki kombinirajo MCTS z nevronskimi mrežami in spodbujevalnim učenjem.

    V jupyter zvezku spodaj si lahko ogledate implementacije večine algoritmov na primeru križcev in krožcev ter jih lahko preizkusite v medsebojni igri.

  • Planiranje

    Planiranje je veja umetne inteligence, ki se ukvarja z avtomatskim načrtovanjem strategij oz. zaporedij dejanj. Dejanjem v žargonu planiranja pravimo akcije (za razliko od potez pri preiskovanju). Takšne strategije so potrebne za npr. smiselno delovanje avtonomnih robotov ali samovozečih avtomobilov. Tipično se planiranje ukvarja z visokonivojsko kontrolo, npr. v kakšnem zaporedju premikati robota med lokacijami, ne pa z nizkonivojskim nadzorom kako premakniti robota iz točke A v točko B.

    Spoznali smo STRIPS način opisa problemske domene, torej situacije in možnih akcij. STRIPS je osnova za veliko večino modernih opisnih jezikov, npr. PDDL. Situacijo opiše kot množico relacij, pri tem se omeji le na tiste relacije, ki imajo nek pomen za reševanje problema. Akcije opiše s predpogoji in učinki, slednje dostikrat delimo na tisti, ki jih akcija ustvari in tiste, ki jih poruši.

    Kot dejanski algoritem planiranja smo si pogledali planiranje z regresiranjem ciljev. Le-to izhaja iz rešitve in preiskuje katere akcije so bile potrebne, da je rešitev bila dosežena iz začetne situacije. Pri tem akcije izbira smiselno, torej vedno le tiste, ki nekaj dosežejo v smislu približevanja rešitvi.

    Vse naštete pojme smo si ogledali na praktičnem primeru igre Sokoban. Le-to si lahko predstavljamo kot avtomatizirano skladišče. Celotna koda in primeri, vključno s primerjavo s čistim preiskovanjem, je na voljo v priloženem jupyter zvezku.

  • Nadzorovano strojno učenje

    Do sedaj smo si v tem poglavju pogledali.

    Kaj je namen strojnega učenja, nekaj primerov, osnovno terminologijo in delitev strojnega učenja.

    Odločitvena drevesa, rezanje.

    Algoritem kNN (k-najbližjih sosedov).

    Ter pojme kot so šum v podatkih, kontinuizacija diskretnih atributov, manjkajoče vrednosti.