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