Inteligenta Artificiala

Observatie: in cazul in care pentru un tip de mutare nu se precizeaza in mod clar costul, se va considera costul 1.

Observatie: Pe lângă program se va uploada și o documentație în format pdf cu informațiile cerute mai jos. Se poate face și în Google docs punând linkul către ea într-un comentariu pe primul rând al programului

Barem comun

Linkuri utile

• https://repl.it/@IrinaCiocan/cautare-BFDFDFI-complet#main.py
• https://repl.it/@IrinaCiocan/uniform-cost-search#main.py
• https://repl.it/@IrinaCiocan/a-star#main.py
• https://replit.com/@IrinaCiocan/a-star-optimizat#main.py
• https://replit.com/@IrinaCiocan/ida-star#main.py
• https://repl.it/@IrinaCiocan/problemablocurilor#main.py (E implementat cu BF si A*)
• https://replit.com/@IrinaCiocan/8-puzzle#main.py
• https://repl.it/@IrinaCiocan/exemplu-afisare-timp-folosit (cum calculam timpul de executie a unei secvente de cod)
• https://repl.it/@IrinaCiocan/problema-canibalilor-si-misionarilor#main.py
• https://repl.it/@IrinaCiocan/exemplu-iterare-prin-folder
• http://irinaciocan.ro/inteligenta_artificiala/python-comprehensions.php la secțiunea cu argumentele programului, respectiv timeout
• http://irinaciocan.ro/inteligenta_artificiala/cum-rezolvam-o-problema.php modul general de abordare a unei probleme

Barem (punctajul e dat in procentaje din punctajul maxim al temei; procentajul maxim este 100%):

1. (5%)Fișierele de input vor fi într-un folder a cărui cale va fi dată în linia de comanda. În linia de comandă se va da și calea pentru un folder de output în care programul va crea pentru fiecare fișier de input, fișierul sau fișierele cu rezultatele. Tot în linia de comandă se va da ca parametru și numărul de soluții de calculat (de exemplu, vrem primele NSOL=4 soluții returnate de fiecare algoritm). Ultimul parametru va fi timpul de timeout. Se va descrie în documentație forma în care se apelează programul, plus 1-2 exemple de apel.
2. (5%) Citirea din fisier + memorarea starii. Parsarea fișierului de input care respectă formatul cerut în enunț
3. (15%) Functia de generare a succesorilor
4. (5%) Calcularea costului pentru o mutare
5. (5%) Testarea ajungerii în starea scop (indicat ar fi printr-o funcție de testare a scopului). Atenție, acolo unde nu se precizează clar în fișierul de intrare o stare finală înseamnă că funcția de testare a scopului doar verifică niște condiții precizate în enunț. Nu se va rezolva generând toate stările finale posibile fiindca e ineficient, ci se va verifica daca o stare curentă se potrivește descrierii unei stări scop.
6. (15% = 2+5+5+3 ) 4 euristici:
   • (2%) banala
   • (5%+5%) doua euristici admisibile posibile (se va justifica la prezentare si in documentație de ce sunt admisibile)
   • (3%) o euristică neadmisibilă (se va da un exemplu prin care se demonstrează că nu e admisibilă). Atenție, euristica neadmisibilă trebuie să depindă de stare (să se calculeze în funcție de valori care descriu starea pentru care e calculată euristica).
7. (10%) crearea a 4 fisiere de input cu urmatoarele proprietati:
   1. un fisier de input care nu are solutii
   2. un fisier de input care da o stare initiala care este si finala (daca acest lucru nu e realizabil pentru problema, aleasa, veti mentiona acest lucru, explicand si motivul).
   3. un fisier de input care nu blochează pe niciun algoritm și să aibă ca soluții drumuri lungime micuță (ca să fie ușor de urmărit), să zicem de lungime maxim 20.
   4. un fisier de input care să blocheze un algoritm la timeout, dar minim un alt algoritm să dea soluție (de exemplu se blochează DF-ul dacă soluțiile sunt cât mai "în dreapta" în arborele de parcurgere)
   5. dintre ultimele doua fisiere, cel putin un fisier sa dea drumul de cost minim pentru euristicile admisibile si un drum care nu e de cost minim pentru cea euristica neadmisibila
8. (15%) Pentru cele NSOL drumuri(soluții) returnate de fiecare algoritm (unde NSOL e numarul de soluții dat în linia de comandă) se va afișa:
   • numărul de ordine al fiecărui nod din drum
   • lungimea drumului
   • costului drumului
   • timpul de găsire a unei soluții (atenție, pentru soluțiile de la a doua încolo timpul se consideră tot de la începutul execuției algoritmului și nu de la ultima soluție)
   • numărul maxim de noduri existente la un moment dat în memorie
   • numărul total de noduri calculate (totalul de succesori generati; atenție la DFI și IDA* se adună pentru fiecare iteratie chiar dacă se repetă generarea arborelui, nodurile se vor contoriza de fiecare dată afișându-se totalul pe toate iterațiile
   • între două soluții de va scrie un separator, sau soluțiile se vor scrie în fișiere diferite.

   Obținerea soluțiilor se va face cu ajutorul fiecăruia dintre algoritmii studiați:

   • Pentru studenții de la seria CTI problema se va rula cu algoritmii: BF, DF, DFI, UCS, A* (varianta care dă toate drumurile), A* optimizat (cu listele open și closed, care dă doar drumul de cost minim), IDA*.
   • Pentru studenții din seriile Mate-Info și Informatică, problema se va rula cu algoritmii: BF, DF, DFI, A* (varianta care dă toate drumurile), A* optimizat (cu listele open și closed, care dă doar drumul de cost minim), IDA*.
   Pentru toate variantele de A* (cel care oferă toate drumurile, cel optimizat pentru o singură soluție, și IDA*) se va rezolva problema cu fiecare dintre euristici. Fiecare din algoritmi va fi rulat cu timeout, si se va opri daca depășește acel timeout (necesar în special pentru fișierul fără soluții unde ajunge să facă tot arborele, sau pentru DF în cazul soluțiilor aflate foarte în dreapta în arborele de parcurgere).
9. (5%) Afisarea in fisierele de output in formatul cerut
10. (5%+5%) Validări și optimizari. Veți implementa elementele de mai jos care se potrivesc cu varianta de temă alocată vouă:
    • Validare: verificarea corectitudinii datelor de intrare
    • Validare: găsirea unui mod de a realiza din starea initială că problema nu are soluții. Validările și optimizările se vor descrie pe scurt în documentație.
    • Optimizare: găsirea unui mod de reprezentare a stării, cât mai eficient
    • Optimizare: găsirea unor condiții din care sa reiasă că o stare nu are cum sa contina in subarborele de succesori o stare finala deci nu mai merita expandata (nu are cum să se ajungă prin starea respectivă la o stare scop).
    • Optimizare: implementarea eficientă a algoritmilor cu care se rulează programul, folosind eventual module care oferă structuri de date performante.
11. (5%) Comentarii pentru clasele și funcțiile adăugate de voi în program (dacă folosiți scheletul de cod dat la laborator, nu e nevoie sa comentați și clasele existente). Comentariile pentru funcții trebuie să respecte un stil consacrat prin care se precizează tipul și rolurile parametrilor, căt și valoarea returnată (de exemplu, reStructured text sau Google python docstrings).
12. (5%) Documentație cuprinzând explicarea euristicilor folosite. În cazul euristicilor admisibile, se va dovedi că sunt admisibile. În cazul euristicii neadmisibile, se va găsi un exemplu de stare dintr-un drum dat, pentru care h-ul estimat este mai mare decât h-ul real. Se va crea un tabel în documentație cuprinzând informațiile afișate pentru fiecare algoritm (lungimea și costul drumului, numărul maxim de noduri existente la un moment dat în memorie, numărul total de noduri). Pentru variantele de A* vor fi mai multe coloane în tabelul din documentație: câte o coloană pentru fiecare euristică. Tabelul va conține datele pentru minim 2 fișiere de input, printre care și fișierul de input care dă drum diferit pentru euristica neadmisibilă. În caz că nu se găsește cu euristica neadmisibilă un prim drum care să nu fie de cost minim, se acceptă și cazul în care cu euristica neadmisibilă se obțin drumurile în altă ordine decât crescătoare după cost, adică diferența să se vadă abia la drumul cu numărul K, K>1). Se va realiza sub tabel o comparație între algoritmi și soluțiile returnate, pe baza datelor din tabel, precizând și care algoritm e mai eficient în funcție de situație. Se vor indica pe baza tabelului ce dezavantaje are fiecare algoritm.
13. Doar pentru studenții de la seria CTI (Bonus 10%) pentru implementarea Greedy și analizarea acestuia împreună cu ceilalți algoritmi.
14. Doar pentru studenții de la seria CTI (Bonus 10%) pentru fiecare dintre următoarele optimizări pentru cazul în care se cere o singură soluție (deci în program veți avea un if care verifică dacă numărul inițial de soluții cerut era 1):
    1. la BF să se returneze drumul imediat ce nodul scop a fost descoperit, și nu neapărat când ajunge primul în coadă
    2. la UCS+A* (bonusul ar fi 10%+10% dacă se face pt ambele) să nu avem duplicate ale informației din noduri în coadă. În cazul în care tocmai dorim să adăugăm un nod în coadă și vedem că există informația lui deja, păstram în coadă, dintre cele 2 noduri doar pe cel cu costul cel mai mic
15. Bonus (5%) Dacă faceți mai multe euristici admisibile dar diferite ca idee (cu alt mod de abordare a calculării).
16. (Bonus 5%) implementare proprie (rescriere completă față de exemplele de la laborator)
17. (Bonus 15-20%) Adăugarea unei interfețe grafice care să simuleze drumul cu ajutorul unei animații (de exemplu, făcută în pygame).

Tema nu se puncteaza fara prezentare. Se va da o nota pe prezentare de la 1 la 10 in functie de cat de bine a stiut studentul sa explice ce a facut. Punctajul temei se va inmulti cu nota_prezentare/10. Astfel, daca cineva stie sa explice doar jumatate din ce a facut, primeste jumatate din punctaj; daca nu stie nimic primeste 0.

Temele copiate duc la anularea notei atat pentru cel care a dat tema cat si pentru cel care a copiat, iar numele studentilor cu aceasta problema vor fi comunicate profesorului titular de curs.