Naslov predmeta: Poglobljeni algoritmi preiskovaja in planiranja
Metode preiskovanja in planiranja so bistvene komponente številnih sistemov umetne inteligence na področjih, kot so: programiranje robotov, reševanje kombinatoričnih problemov, strojno učenje, interpretacija senzorskih informacij in igranje iger. V zadnjih dveh desetletjih so se pojavili mnogi sofisticirani algoritmi preiskovanja in planiranja, ki niso del osnovnih predmetov iz umetne inteligence.
Ta predmet predstavi izpopolnjene algoritme za naslednje paradigme reševanja problemov: preiskovanje prostora stanj, simbolično preiskovanje, planiranje na onovi sredstev in ciljev ter planiranje v negotovih domenah. Predmet vključuje projekte na teme po izbiri študentov, npr. v kombinatorični optimizaciji ali programiranju robotov, lahko tudi v povezavi s študentovimi doktorskimi raziskavami.
VSEBINA
Pregled osnovnih preiskovalnih algoritmov. Prostor stanj, neinformirano in informirano preiskovanje, hevristično preiskovanje in algoritem A*
Kako lahko hevristike kreiramo avtomatsko? Poenostavljanje problemov z abstrakcijo, hierarhične abstrakcije, hierarhični algoritem A*, baze vzorcev
Prostorsko učinkovite verzije A*. Preiskovanje z linearno prostorsko zahtevnostjo, A* z iterativnim poglabljanjem (IDA*), določanje pragov v IDA*, rekurzivno hevristično iskanje, transpozicijske tabele
Hevristično preiskovanje ob pomnilnih in časovnih omejitvah. SMAG in sorodni algoritmi, preiskovanje v realnem času, RTA* in njegove različicem učenje z LRTA*
Simbolično hevristično preiskovanje. Izboljšana prostorska učinkovitost s predstavitvijo množic stanj z Boolovimi spremenljivkami; algoritmi simboličnega hevrističnega preiskovanja, simbolični A*
Reševanje problemov z zadoščanjem omejitev. Zadoščanje omejitev, konsistentnostni algoritmi, strategije preiskovanja, reševanje NP-težkih problemov
Agentno/robotsko planiranje nalog. Predstavitev stanj in akcij, princip sredstev in ciljev; planirni grafi, SATPLAN, delno urejeno planiranje; hierarhično planiranje; več-agentno planiranje
Odločanje v domenah z negotovostjo. Planiranje in izvajanje planov ob prisotnosti napak in nepričakovanih dogodkov; markovski odločitveni procesi
