Sisteme de Productie - Inteligenta Artificiala

Obiective

Durata: 2 ore

1. Definitia sistemelor de productii

In 1972, Newell si Simon prezinta un model al rationamentului uman, fiind precursorii uneia dintre paradigmele de baza ale inteligentei artificiale, si anume sistemele de productie.

Un sistem de productii este un model matematic avand o importanta particulara in inteligenta artificiala, atat pentru implementarea algoritmilor de cautare cat si pentru modelarea rezolvarii umane a problemelor.

Dupa definitia data de Brownston (1985), un sistem de productii consta din:

1. O multime finita de reguli de productie, denumita baza de reguli. Aceste reguli sunt numite simplu productii. O productie este o pereche ordonata (conditie, actiune), adeseori notata

conditie -> actiune,

a carei interpretare este urmatoarea:

Daca conditie este indeplinita ATUNCI se poate executa actiune.

Partea din regula, care contine conditia, specifica acele criterii care trebuie sa fie indeplinite pentru ca regula sa fie aplicata, deci ca actiunea pe care aceasta o mentioneaza sa aiba loc.

2. Memoria de lucru (working memory) continand piese de cunoastere (declarativa sau factuala), memorate nerestrictiv intr-o colectie denumita context. Contextul reprezinta starea curenta a procesului de rezolvare a unei probleme. La debutul acestui proces, contextul este initializat cu datele initiale ale problemei. Daca conditia unei reguli este satisfacuta de piesele de cunoastere din context, se spune ca regula respectiva este aplicabila. Multimea regulilor aplicabile poarta denumirea de multime conflictuala.

3. Strategia de control sau ciclul de corespondenta (sau recunoastere, selectie) si actiune, intelegand prin acesta algoritmul care face posibila functionarea sistemului de productii, algoritm care consta, de obicei, din urmatorii pasi :

Corespondenta (selectia). Sunt selectionate toate regulile din baza de productii pentru care s-au gasit piese de cunoastere in contextul actual al problemei care satisfac partea de conditie (conditia poate fi unificata cu o clauza din contextul problemei). Multimea acestor reguli astfel selectate se numeste multime conflictuala deoarece regulile acestei multimi intra intr-o competitie din care una singura va fi declansata.

Rezolvarea conflictului. Daca prin procesul de corespondenta se obtin mai multe reguli aplicabile, atunci se elimina mai intai acele reguli care produc replici ale unor simboluri (elemente) deja existente in context (astfel se evita ciclurile), iar apoi regulile ramase se ordoneaza potrivit unor strategii de rezolvare a conflictelor de prioritate si, astfel, se selecteaza regula care va fi declansata. Rezolvarea conflictului se poate face simplu prin selectarea primei reguli aplicabile care nu produce un ciclu sau prin utilizarea unei functii euristice.

Actiunea. Se executa partea de actiune a regulii declansate. Daca nu exista productii (reguli) aplicabile (multimea conflictuala e vida), sistemul de productie se opreste. Evident, executia unei astfel de reguli va modifica corespunzator contextul problemei.

Reluarea ciclului. Se reseteaza toate productiile selectate (multimea conflictuala) si se reia ciclul de la faza de corespondenta folosindu-se contextul modificat in ciclul anterior. Daca un ciclu nu produce actiuni, sistemul se opreste. Oprirea mecanismului interpretativ poate avea loc si ca urmare a executarii unei productii la care partea de actiune specifica oprirea.

Un sistem de productie, simplist implementat, nu este prevazut cu o strategie de revenire (backtracking) din asa numitele situatii 'dead-end'. De aceea, utilizarea sistemelor de productii la implementarea unor algoritmi de rezolvare a problemelor trebuie facuta in conexiune cu utilizarea unor algoritmi de cautare 'depth-first', 'breadth-first' sau, mult mai elegant, 'best-first', strategia de rezolvare a conflictului fiind 'euristica' pentru implementarea acestuia din urma.

Exemplu. Functionarea unui sistem de productii poate fi usor ilustrata facand apel la un exemplu simplu si anume rearanjarea in ordine alfabetica a simbolurilor unui sir de caractere.

Productii

1. ba -> ab

2. ca -> ac

3. cb -> bc

Sirul (contextul) initial: cbaca

Trasarea algoritmului de rearanjarea a caracterelor sirului initial este ilustrata in tabelul de mai sus.

Ideea utilizarii productiilor apartine apartine lui Post (1943), care a propus un model bazat pe reguli de productie ca o teorie formala a calculului. Ideea are la baza formalismul gramaticilor generative introduse de N. Chomsky, in special gramaticile contextuale. Aplicatii interesante ale sistemelor de productie apar in lucrarile lui Newell si Simon de la Carnegie Institute of Technology. De asemenea, ideea sistemelor de productii sta la baza algoritmilor Markov si a masinilor Turing.

Pentru familiarizarea cu acest concept, de o importanta majora in inteligenta artificiala, sunt prezentate in continuare doua exemple.

Exemplul 5-1. Spatiul de stari generat de un 8-puzzle este destul de complex pentru a prezenta interes, astfel incat acesta este un exemplu frecvent utilizat in inteligenta artificiala. In cele ce urmeaza este prezentata solutia acestei probleme utilizand un sistem de productii.

Pentru simplitatea solutiei, se va presupune din nou ca patratelul liber (negru) este mutat si nu piesele.

Starea initiala Goal

Productii

Contextul contine starea goal -> Halt

Patratelul negru nu este sus -> muta patratelul negru in sus

Patratelul negru nu este in stanga -> muta patratelul negru la stanga

Patratelul negru nu este in dreapta -> muta patratelul negru la dreapta

Patratelul negru nu este jos -> muta patratelul negru in jos

Contextul (Memoria de lucru) contine configuratia curenta

Strategia de control

1. Incearca fiecare productie in ordine;

2. Evita ciclurile;

3. Opreste-te daca ai ajuns la Goal.

Dupa cum se poate constata din analiza punctelor 1 si 2 ale strategiei de control a cautarii, rezolvarea conflictului se realizeaza prin alegerea primei reguli (productii) care nu produce un ciclu. Aceasta este una dintre cele mai simple strategii de rezolvare a conflictului. Implementarea unui astfel de algoritm trebuie sa se faca impunand o conditie de limitare a adancimii, altminteri algoritmul se va 'pierde' in investigarea unor drumuri foarte lungi sau va descoperi o solutie deloc optimala (problema la descrierea algoritmului 'depth-first'). Evident, o implementare simplista, fara un procedeu de revenire (backtracking), poate usor devia de la solutia problemei.

Exemplul 5-2. Problema traseului calului de sah este de asemenea un exemplu des utilizat in inteligenta artificiala pentru sublinierea unor aspecte importante privind implementarea sistemelor de productie.

Pentru inceput, se considera o tabla formata din 3×3 patratele. Tot pentru simplitate cele 9 patratele se vor numerota cu cifrele arabe de la 1 la 9, si nu cu o pereche de tip (C,L) notatie utilizata uzual in jocul de sah.

Regulile de productie vor reprezenta in acest caz mutarile egale ale calului de sah si anume:

1 Calul este in paratelul 1 -> Muta calul in patratelul 8

2 Calul este in paratelul 1 -> Muta calul in patratelul 6

3 Calul este in paratelul 2 -> Muta calul in patratelul 9

4 Calul este in paratelul 2 -> Muta calul in patratelul 7

5 Calul este in paratelul 3 -> Muta calul in patratelul 4

6 Calul este in paratelul 3 -> Muta calul in patratelul 8

7 Calul este in paratelul 4 -> Muta calul in patratelul 9

8 Calul este in paratelul 4 -> Muta calul in patratelul 3

9 Calul este in paratelul 6 -> Muta calul in patratelul 1

10 Calul este in paratelul 6 -> Muta calul in patratelul 7

11 Calul este in paratelul 7 -> Muta calul in patratelul 2

12 Calul este in paratelul 7 -> Muta calul in patratelul 6

13 Calul este in paratelul 8 -> Muta calul in patratelul 3

14 Calul este in paratelul 8 -> Muta calul in patratelul 1

15 Calul este in paratelul 9 -> Muta calul in patratelul 2

16 Calul este in paratelul 9 -> Muta calul in patratelul 4

Memoria de lucru va contine starea curenta existenta pe tabla si starea de goal. Rezolvarea conflictului presupune si in acest caz alegerea primei productii care nu produce o bucla. Strategia de control este simpla constand in aplicarea regulilor pana la atingerea pozitiei de goal, caz in care algoritmul ia sfarsit. De asemenea, strategia de control ar trebui sa implementeze mecanismul de backtracking. In aceste conditii, modul in care sistemul de productii determina solutia problemei este ilustrat in tabelul urmator.

Strategia de control sau ciclul de recunoastere si actiune se poate implementa utilizand o procedura recursiva Path(X,Y), unde X reprezinta pozitia initiala a calului de sah, iar Y pozitia in care acesta trebuie mutat.

procedure Path(X,Y)

begin

if X=Y then halt

else begin

Corespondenta:

alege dintre productii pe cele a caror parte de

conditie poate fi unificata cu regula move(X,Y)

Rezolvarea conflictului:

alege din multimea conflictuala prima productie a

carei aplicare nu produce mutarea calului intr-un

patratel anterior vizitat (excluderea ciclurilor)

fie move(X,Z) productia selectata

Actiunea: % declansarea productiei move(X,Z)

muta calul in patratelul Z

X := Z

stocheaza in memoria de lucru informatia ca patratelul

Z a fost vizitat

%

path(Z,Y)

afiseaza(Z)

end

end;

Implementarea procedurii precedente intr-un limbaj de calcul al predicatelor (respectiv Prolog) este foarte simpla, aceasta constand in scrierea a doua clauze, un fapt si o regula:

X path(X,X).

X, Y path(X,Y) Z move(X,Z) (been(Z)) assert(been(Z)) path(Z,Y).

Dupa cum se poate constata regula path este recursiva. Pentru prevenirea ciclurilor in baza de date se adauga, utilizand in acest scop predicatul assert cate un fapt been(Z) de fiecare data ce un nod Z este intalnit in procesul de cautare.

Cum initial X=1 si Y=2, subgoal-ul move(X,Z) este unificat cu prima regula din baza de reguli si anume productia move(1,8), variabila Z fiind instantiata cu 8. Cum calul nu a fost inca plasat in patratelul 8, regula respectiva este selectata si declansata. Actiunea regulii consta in actualizarea starii curente X:=Z=8 si stocarea in memoria de lucru a informatiei ca patratelul 8 a fost vizitat. Procedura apelandu-se recursiv, acest procedeu se reia pana la atingerea starii Y=2. Trebuie remarcat faptul ca este esential ca subgoal-urile regulii path sa fie executate in ordinea in care acestea apar in corpul regulii.

2. Controlul cautarii in sistemele de productie

Modelul sistemelor de productie ofera cateva mecanisme prin care proiectantul unui astfel de sistem poate interveni dirijand procesul de cautare: selectia modului de cautare data-driven sau goal-driven, structura regulilor de productie si strategia de rezolvare a conflictului.

2.1. Selectia modului de cautare: data-driven sau goal-driven

In cautarea Data-driven (directa) se incepe de la descrierea initiala a problemei (o secventa de axiome, simptomele unei boli, o colectie de date ce trebuie interpretate etc.) si se deduc noi cunostinte din aceste date. Deducerea noilor cunostinte este consecinta aplicarii unor reguli de inferenta logica, efectuarea unor mutari in cazul jocurilor sau, in general, aplicarea unor operatori de tranzitie starii curente a problemei. Noua stare, rezultata in urma aplicarii operatorului de tranzitie, va fi adaugata bazei de cunostinte a problemei in cauza.

Descrierea precedenta accentueaza oportunitatea utilizarii sistemelor de productie pentru implementarea proceselor de cautare. Contextul (sau memoria de lucru) va fi construit din datele presupuse a fi adevarate (ipoteze) si cele deduse ca fiind adevarate prin utilizarea unor productii in ciclurile precedente.

O productie este selectata daca conditia acesteia este unificata cu un fapt din contextul problemei. Aplicarea (declansarea) unei reguli are ca efect executia actiunii asociate, actiune care va avea drept efect modificarea contextului (memoriei de lucru), prin modificarea unor informatii sau adaugarea unor informatii noi.

Fig. 5.1

In tabelul de mai jos este ilustrat modul de cautare al grafului AND/OR ilustrat in figura 1 si descris prin productiile urmatoare:

1. p q goal

2. r s p

3. w r q

4. t u q

v s

6. start v r q

Observatie. Graful de mai sus nu este cunoscut a priori, ci este generat in procesul de cautare.

Dupa cum se poate constata din analiza datelor din tabelul de mai sus, s-a utilizat o strategie simpla de rezolvare a conflictului si anume alegerea/selectarea acelei reguli aplicabile care a fost cel mai putin recent utilizata sau nu a fost utilizata deloc.

In varianta data-driven productiile sunt de forma CONDITIE ACTIUNE si anume daca conditia este satisfacuta de elementele din memoria de lucru se poate efectua actiunea respectiva. In aceasta situatie, cand productiile sunt implicatii logice si actiunea adauga noi informatii in memoria de lucru, actul de aplicare a unei reguli este, de fapt, modus-ponens. Aplicarea unei astfel de reguli genereaza un nou nod al grafului AND/OR cercetat.

Un sistem de productie poate fi implementat si prin utilizarea unei metode goal-driven de cautare. Pentru exemplificare, sa consideram secventa de reguli de productie de mai jos, reguli care genereaza graful AND/OR alaturat.

1. p q goal

2. r s p

3. w r p

4. t u q

v s

6. start v r q

In aceasta situatie o productie CONDITIE ACTIUNE este aplicabila daca actiunea acesteia poate fi unificata cu un element din memoria de lucru. Aplicarea unei reguli implica adaugarea conditiei regulii respective informatiilor din memoria de lucru. Procesul de cautare se opreste cand in baza de date se gaseste un fapt echivalent cu datele initiale ale problemei. Trasarea acestui algoritm, pe cazul exemplului propus, este ilustrata in tabelul urmator.

Analizand tabelul de mai sus se constata ca strategia de rezolvare a conflictului este aceeasi cu cea utilizata in cautarea data-driven.

2.2.Controlul cautarii prin intermediul strategiei de rezolvare a conflictului

Dupa cum s-a specificat mai sus, sistemele de productii permit implementarea unor functii euristice pentru rezolvarea conflictului. In cele ce urmeaza sunt prezentate principiile utilizate pentru implementarea strategiilor generale de rezolvare a conflictului. Evident, eficienta procesului de cautare nu este aceeasi daca se implementeaza o strategie eficienta de rezolvare a conflictului sau se alege cea mai simpla dintre ele: selectarea primei reguli care nu conduce la un ciclu.

Cele mai reprezentative aspecte care trebuie avute in vedere la implementarea unei strategii generale de rezolvare a conflictului sunt urmatoarele:

Refractia. Daca o regula a fost aplicata, aceasta nu mai poate fi aplicata pana ce contextul in care aceasta regula a fost aplicata nu s-a modificat (rolul refractiei este de a evita ciclurile).

Recentitatea Sunt preferabile acele reguli ale caror conditii sunt unificate cu cele mai recente fapte adaugate in memoria de lucru (se influenteaza continuarea unei anumite linii de rationament).

Specificitatea. O regula mai specifica este preferabila in raport cu una generala. O regula este mai specifica decat alta regula daca partea de conditie a regulii respective este mai restrictiva decat a celeilalte.

REZUMAT

Un sistem de productii consta dintr-o multime finita productii, reguli de forma conditie -> actiune, si o baza de date (memoria de lucru) care contine starea curenta a problemei (contextul).

Sistemele de productii au urmatoarea strategie de control, aplicabila in fiecare ciclu de executie: a) se testeaza conditiile productiilor din baza de cunostinte si se formeaza multimea conflictuala (a regulilor aplicabile, ale caror conditii sunt indeplinite de datele din context); b) se selecteaza regula care va fi declansata (la un ciclu se executa o singura regula, selectata din multimea conflictuala dupa o strategie anterior stabilita); c) se executa partea de actiune a regulii declansate, ceea ce conduce la modificarea contextului problemei.

Se reseteaza toate productiile selectate (multimea conflictuala) si se reia ciclul de la faza de corespondenta folosindu-se contextul modificat in ciclul anterior. Daca un ciclu nu produce actiuni, sistemul se opreste. Oprirea mecanismului interpretativ poate avea loc si ca urmare a executarii unei productii la care partea de actiune specifica oprirea (in general, la gasirea solutiei).

PROBLEME PROPUSE

Problema 1. Sa se obtina prin metoda sistemelor de productii ordonarea alfabetica a sirului de caractere: cabbcba

Productii

1. ba -> ab

2. ca -> ac

3. cb -> bc

Sirul (contextul) initial: cabbcba.

Problema 2. Sa se rezolve problema 8-puzzle din figura de mai jos utilizand un sistem de productii.

Starea initiala Goal

Productii

Contextul contine starea goal -> Halt

Patratelul negru nu este sus -> muta patratelul negru in sus

Patratelul negru nu este in stanga -> muta patratelul negru la stanga

Patratelul negru nu este in dreapta -> muta patratelul negru la dreapta

Patratelul negru nu este jos -> muta patratelul negru in jos

Contextul (Memoria de lucru) contine configuratia curenta

Strategia de control

1. Incearca fiecare productie in ordine;

2. Evita ciclurile;

3. Opreste-te daca ai ajuns la Goal.

TEST DE AUTOEVALUARE

Ce este o productie:

a.       Pereche ordonata (conditie, actiune) .

b.      Pereche ordonata (actiune, conditie).

c.       Pereche neordonata.

In cazul unei multimi conflictuale:

a.       Regulile acestei multimi intra intr-o competitie din care toate vor fi declansate.

b.      Regulile acestei multimi intra intr-o competitie din care una va fi declansata .

c.       Regulile componente se vor declansa fara competitie.

In cazul metodei goal-driven, o productie e aplicabila daca:

a.       Conditia acesteia nu poate fi unificata cu un element din context.

b.      Actiunea acesteia poate fi unificata cu un element din memoria de lucru.

c.       Conditia acesteia poate fi unificata cu un element din memoria de lucru.

Ce reprezinta contextul?

a.       Starea curenta a procesului de rezolvare a unei probleme.

b.      Starea anterioara a procesului de rezolvare a unei probleme.

c.       Starea viitoare a procesului de rezolvare a unei probleme.

Prin declansarea unei reguli are loc:

a.       Se opreste neconditionat programul.

b.      Se reia ciclul fara modificarea contextului.

c.       Executarea partii de actiune din corpul regulii.

Strategia de cautare pornind de la descrierea initiala a problemei poarta denumirea de:

a.       Data-driven.

b.      Goal-driven.

c.       Open-driven.

Raspuns

1. a 3. b c

2. b 4. a 6. a

v v v