Bazele Logice ale Inteligentei Artificiale

Facultatea de Automatica si Calculatoare, Sectia Calculatoare, Directia C4

Titular curs: Prof. dr. ing. Adina Magda Florea


Continut
Evaluare
Teme 1999-2000
Bibliografie

Continut

CAPITOLUL 1 Teoria logica
1.1 Abordarea semantica a teoriei logice
1.2 Abordarea sintactica a teoriei logice
1.3 Demonstratie si deductie
1.4 Consistenta si completitudine

CAPITOLUL 2 Demonstrarea teoremelor in logica cu predicate
2.1 Modelul Herbrand
2.2 Principiul rezolutiei si completitudinea rezolutiei
2.3 Teoreme cu egalitate
2.4 Strategii rezolutive
2.5 Strategia rezolutiei liniare cu clauze ordonate
2.6 Utilizarea euristicilor in demonstrare

CAPITOLUL 3 Problema satisfacerii restrictiilor (CSP)
3.1 Cadrul logic al problemei satisfacerii restrictiilor
3.2 Utilizarea satisfacerii restrictiilor in interpretarea desenelor
3.3 Clasa CSP rezolvabile in timp polinomial
3.4 Imbunatatirea timpului de rulare al CSP
3.5 Problema satisfacerii partiale a restrictiilor

CAPITOLUL 4 Rationament nemonoton.
4.1 Ipoteza lumii inchise
4.2 Rationament implicit
4.3 Ierarhii taxonomice
4.4 Sisteme de mentinere a consistentei datelor (TMS)
4.5 Sisteme de mentinere a consistentei datelor bazate pe presupuneri (ATMS)

CAPITOLUL 5 Logica actiunii. Planificare
5.1 Sistemul GPS
5.2 Planificare liniara. Sistemul STRIPS
5.3 Planificare neliniara. Sistemul TWEAK

CAPITOLUL 6 Rationament inductiv
6.1 Invatarea utilizand macrooperatorii
6.2 Invatare bazata pe explicatii si generalizarea bazata pe explicatii
6.3 Spatiul versiunilor

CAPITOLUL 7 Logica sistemelor multi-agent
7.1 Logici sententiale ale increderii
7.2 Multimi de lumi posibile
7.3 Cunostinte de grup
7.4 Modelul BDI
7.5 Comunicare, interactiune si protocoale intre agenti
 

Evaluare
Pentru tema de casa de semestru punctajul este de 2p (2,5 p pentru rezolvari de exceptie).
Pentru activitatea la laborator si temele de casa saptamanale punctajul este de 2p.
Pentru tezele (teorie si probleme) de la examen punctajul este de 7p
Total 11p (11.5p).

Teme de semestru 1999-2000
Se alege una din urmatoarele 5 teme. Tema se preda in ultimul laborator de BLIA. Programul se aduce pe discheta si se prezinta cu explicatii si rulare pe mai multe cazuri de test. Se vor include comentarii explicative in program. Se vor explica, sub forma de comentarii in program, structurile de date utilizate. Se recomanda o scriere modulara si o rezolvare eficienta.

TEMA Nr. 1
Sa se implementeze in LISP un demonstrator de teoreme in logica implicita a lui Poole. Pentru documentare se citeste fisierul Word DefaultPoole.doc.

TEMA Nr. 2
Sa se scrie un interpretor al unui subset al limbajului Prolog in LISP. Interpretorul admite clauze Prolog care pot contine constante simbolice, variabile, marcate prin ?x, si liste cu un singur nivel. Programul va avea functii (sau macrodefinitii) de adaugare unui fapt sau regula in baza de date si de demonstrare a unui scop cu afisarea instantierilor realizate prin satisfacerea scopului. Se vor afisa intotdeauna toate solutiile care au satisfacut scopul.

Exemple posibile de utilizare
(ad (prieten maria dan))
(ad (prieten ana dan))
(ad (cunoaste gelu ?x) (prieten ?x dan))
(demo (cunoaste ?x ?y))
?x=gelu, ?y=maria
?x=gelu, ?y=ana
(ad (member ?x (?x . ?rest)))
(ad (member ?x (?y . ?rest)) (member ?x ?rest))
(demo (member a (a b c)))
yes

TEMA Nr. 3
Sa se implementeze in LISP un sistem bazat pe cunostinte de tip tabla (blackboard system). In sistem exista o multime de surse de cunostinte - SC (agenti) dotate cu o baza de cunostinte (BC) proprie (locala) si un set propriu de reguli de productie. Aplicarea regulilor de productie se face pe baza faptelor din BC cat si pe baza faptelor inferate de alte surse de cunostinte din sistem. Comunicarea de fapte inferate intre SC se face prin intermendiul unei structuri de date comune, numita blackboard. Fiecare SC stie care sunt faptele de interes pentru comunitate si, de indata ce le obtine, le scrie pe structura de tip tabla. De asemenea, un SC stie care sunt faptele din reguli pe care le poate deduce pe baza setului propriu de reguli cat si cele care vor fi deduse de celelalte SC din sistem. Astfel, aplicarea unei reguli care se bazeaza si pe fapte ce vor fi deduse de alte SC din sistem poate fi facuta numai dupa ce aceste fapte au fost produse si scrise pe blackboard.

Se va defini limbajul de reguli (o versiune fara variabile, deci inclusa in logica cu propozitii), strategia de control de aplicare a regulilor de catre SC si mecanismele de sicronizare pentru acces la tabla.

TEMA Nr. 4
Sa se implementeze in LISP problema pescuitului rational. Mai multe companii detin nave de pescuit, fiecare nava avand o anumita capacitate de a prinde peste – mica (C) si mare (L). Navele pot fi trimise la pescuit intr-o serie de amplasamente marine, acestea fiind de 2 tipuri – langa coasta unde pot pescui nave mici (de tip C) si in larg unde pot pescui nave mari (de tip L). Trimiterea unei nave in larg costa c1, langa coasta c2, si mentinerea in port c3, cu c1>c2>>c3, ci de tip bani. O cantitate de peste pescuita PP produce o cantitate de bani B=PP*ct (cu ct o constanta a problemei).
In fiecare din locurile de pescuit pestele trebuie sa se regenereze (inmulteasca) dupa pescuit. Intr-un interval de timp T o cantitate de peste R se inmulteste cu coeficientul R*CF (CF – constanta care depinde de locul de pescuit – in larg mai mare sau langa coasta mai mic) si nu se poate inmulti decat daca R>Rmin, unde Rmin este cantitatea minima de peste care asigura inmultirea, aceasta fiind de asemenea dependenta de locul de pescuit.

Companiile au ca scop obtinerea unui profit maxim. In acelasi timp, o pescuire intensiva pentru profit poate duce la lipsa pestelui si a posibilitatii de regenerare, si, implicit, la scaderea profitului companiilor care nu mai au ce pescui.

Se cere sa se gaseasca:
A – toate solutiile care asigura mentinerea resurselor de peste la cel putin nivelul de regenerare pentru o durata de N intervale de timp si sa se calculeze profitul global al companiilor in acest caz.

B – o solutie in care nu se impune mentinerea restrictiei de neepuizare a resurselor si in care acestea pot (si sunt) epuizate dupa M < N intervale de timp. Sa se calculeze profitul global in acest caz.

TEMA Nr. 5
Sa se implementeze in LISP o problema de planificare in lumea blocurilor in care actiunile pot fi executate de o multime de agenti. Fie o masa cu o dimensiune nelimitata si o multime de blocuri de aceeasi marime, etichetate cu numele (A, B, ..) si tipul lor (T1, T2, ..). Exista mai multe blocuri din fiecare tip O stare a lumii este una din combinatiile posibile ale blocurilor plasate unul peste altul sau pe masa (la asezarea blocurilor unul peste altul nu conteaza tipul acestora).

Actiunile posibile ale agentilor sunt:
 stack(A,B) – aseaza A peste B daca s-a luat A si B liber
 put(A) – plaseaza A pe masa daca s-a luat A
 get(A) – apuca (ia) A daca A liber (A poate sa fie sau pe masa sau peste un alt bloc B)
Fiecare agent poate executa toate actiunile indicate dar numai pentru anumite tipuri de blocuri (la limita, pentru nici un tip sau pentru toate tipurile – se sugereaza includerea a cate 1 agent si pentru aceste 2 cazuri).

A – se cere sa se sintetizeze toate planurile posibile pentru trecerea dintr-o stare initiala Si in una finala Sf (stare scop), Si si Sf fiind definite la nivelul global al sistemului. Se va testa progarmul si pentru un caz in care problema nu are solutie.

B – Fiecare agent are definite propria lui stare initiala si stare finala (scop) dar, in functie de tipurile de blocuri pe care le poate actiona, este sau nu capabil sa-si atinga scopul. Fiecare agent are o lista cu ceilalti agenti din sistem si, pentru fiecare agent, tipurile de blocuri pe care acesta le poate muta. Se cere, pentru fiecare agent Ai din sistem, sa se sintetizeze un plan de atingerea scopului, in care agentul Ai:
          B1 –apeleaza la cati mai putini (alti) agenti pentru realizarea scopului si, a doua varianta,
          B2 -  apeleaza la cati mai multi agenti care au nevoie, in planurile lor, de actiuni ale lui Ai si, eventual, minimizeaza numarul de agenti care nu au nevoie de actiunile de care Ai este capabil.

Bibliografie