Inteligenta Artificiala - UPB 2020-2021
Se foloseste A* pentru a se gasi drumul de lungime minima intre 2 puncte dintr-un sistem de coordonate carteziene. Nu exista costuri la trecerea dintr-o celula in alta, iar euristicile folosite sunt distanta euclidiana si cea Manhattan.
Daca se elimina sqrt() din distanta euclidiana, pare ca algoritmul se
comporta mai bine, dar asta e o pura intamplare, din moment ce fara sqrt()
euristica nu mai e admisibila. De fapt, explorand mai putine stari, algoritmul
ar putea ajunge la un rezultat gresit daca ar fi rulat pentru o problema mai
complexa
Se foloseste un arbore SI/SAU pentru a se modela comportamentul unui aspirator nedeterminist intr-un spatiu 1D, unde celulele pot fi fie curate, fie murdare. Nedeterminismul consta in faptul ca atunci cand aspiratorul curata o celula, exista 2 posibilitati:
- Celula era curata
$\Rightarrow$ aceasta se poate ramane curata sau se poate murdari - Celula era murdara
$\Rightarrow$ aceasta va fi curatat, dar se poate ca si celula din dreapta sa fie curatata
Reprezinta o decizie. In fiecare stare, sunt maxumum 3 actiuni posibile: Left,
Right, Clean. Fiii unui nod SAU reprezinta efectele acestor decizii,
daca ar deveni actiuni. Deci daca oricare dintre ele duce la o stare de succes
(in care toate celulele sunt cu siguranta curate), atunci si nodul poate duce
la o stare de succes.
Reprezinta o actiune in sine. Pentru actiunile de miscare (Left, Right), are
un singur fiu, noua pozitie in care ajunge aspiratorul. Pentru actiunea Clean,
nedeterminismul aspiratorului inseamna ca pentru a fi siguri ca acest nod duce
la o stare de succes, e nevoie ca ambele situatii care se pot obtine in urma
acestei actiuni (descrise mai sus) sa duca la succes, pentru ca nu stim care
scenariu se va intampla in cazul unei functionari a aspiratorului.
La final se creeaza un plan de actiune, un fel de algoritm care descrie deciziile aspiratorului in functie de mediu (curatenia celulelor).
Se implementeaza un algoritm generic de rezolvare a unei probleme de satisfacere a constrangerilor care admite un numar dat de abateri de la constrangerile date. Algoritmul folosit este un BKT clasic care nu mai viziteaza nodurile de pe o ramura atunci cand numarul de abateri de la constragneri de pe aceasta depaseste numarul minim global gasit pana in acel moment, deoarece ce pe acea ramura nu mai se poate gasi o asignare de variabile cu un cost mai mic decat minimul curent.
Se implementeaza algoritmul Monte Carlo Tree Search pe un joc de connect 4
Se foloseste algoritmul Robinson pentru a se realiza unificarea a doua formule, pe baza unui dictionar de substitutii (care se completeaza pe parcursul algoritmului).
Bine ca de data asta putem sa alegem singuri cum reprezentam datele...
Se utilizeaza rezolutia pentru a demonstra propozitii.
Se demonstreaza o serie de teoreme (implicatii) folosind forward chaining.
Teoremele sunt formulate in FNC si se folosesc functiile implementate in
laboratoarele anterioare (unify() si substitute()) pentru a aplica un set
de fapte unor premise, astfel incat sa se obtina noi fapte.
In lab e implementat algoritmul Graphplan care creeaza o planificare de actiuni cu scopul de a ajunge la o anumita stare. Starile sunt definite ca o lista de predicate. Algoritmul se bazeaza pe 2 notiuni:
Sunt predicate care se contrazic (de ex.: A si ~A). Aceste predicate nu pot
face parte din aceeasi stare.
Sunt actiuni care au cel putin unul dintre preconditii sau efecte in mutex. Aceste actiuni nu se pot executa simultan.
Pe baza mutecsilor descrisi mai sus, se creeaza o lista de actiuni posibile, una de actiuni aflate in mutex (au oricare dintre premise sau efecte in relatie de mutex), alta de efecte ale actiunilor antementionate si inca una cu efectele aflate in mutex.
Niste tractoare scarboase de rezolvat pe hartie. Calcule chioare de probabilitati si nimic mai mult. Nu merita sa ajunga pe Git...
Se implementeaza reguli care reduc dimensiunea factorilor (tabelelor de probabilitati) din nodurile unei retele bayesiene.
Un join intre 2 factori prin care se inmultesc probabilitatile liniilor care fac match.
Se elimina o variabila dintr-un factor adunand valorile intrarilor unde variabila respectiva are valori opuse (se poate ignora pentru ca se considera si cazul in care e adevarata si cel in care nu).
Daca observam ca o variabila are o anumita valoare, putem elimina intrarile cu valoarea opusa din toti factorii in care apare variabila.
Se implementeaza si se compara performantele algoritmilor DFID, IDA*,
LRTA* si Branch and Bound. Se
afieseaza caile gasite de agent de la starea initiala pana la cea finala,
costurile gasite de acesta pentru fiecare stare explorata, precum si timpii si
memoria utilizata in cadrul fiecarui algoritm.
Se implementeaza un algoritm de rezolvare a nivelurilor din jocul "Game about Squares". Se foloseste algoritmul Best First ce foloseste euristica euclidiana, impreuna cu doua strategii de eliminare a starilor ce nu pot duce la o stare castigatoare.
Se foloseste algoritmul Naive Bayes pentru a clasifica articole de stiri dupa domeniul acestora. Acelasi algoritm este folosit si pentru rezumarea acestor articole. Rezumatele sunt create de catre model selectand unele propozitii din articolul initial. Se antreneaza si se compara rezultatele obtinute atat cu monograme cat si cu bigrame.