proiecte

Examenul de Inteligen Artificial

Universitatea "Al.I.Cuza"

Facultatea de Informatic

Sesiunea mai 2001

Proiecte

Grupul de proiecte ROBO ndrumtor Dan CristeaSe are n vedere proiectarea unui sistem a crui comportare s fie similar cu activitatea unui robot capabil a se orienta n spaiu. "Robotul" va primi o hart (cuprinznd planul unui etaj al unei cldiri), va fi plasat ntr-un anumit punct i i se va indica un alt punct n care trebuie s ajung. Un alt tip de activiti vizeaz trasarea unor sarcini mai complexe, ca de exemplu plasarea mai multor obiecte n diverse puncte ale cldirii i indicarea unei configuraii finale a acestor obiecte. Robotul n acest caz va trebui s-i planifice micrile n vederea realizrii planului, dup care va trece la execuia lui. Deplasarea robotului va fi facilitat de existena unui radar plasat pe robot care-l va ajuta s descopere configuraia locurilor pe care le viziteaz, pentru a le compara cu harta i a-i verifica astfel poziia n plan la fiecare moment.

Resurs comun iniial dar actualizabil:

"harta" reprezentnd planul cldirii.

Resurse comune permanent actualizate:

"cldirea" o alt hart reprezentnd situaia real a cldirii. ntre "hart" i "cldire" pot exista diferene datorate existenei unor obstacole (sau spargerii unor ui);

"poziia" reprezentnd poziia real a robotului n cldire.

Cele ce urmeaz reprezint o descriere sumar i aproximativ a arhitecturii acestui sistem. Corecii pot oricnd fi operate de voi, cu condiia ca rezultatul s fie superior celui imaginat de mine, din cel puin unul din urmtoarele puncte de vedere: mai elegant, mai general (adic permite luarea n calcul a mai multor posibiliti de comportament ale robotului). Nu m intereseaz o simplificare a arhitecturii descrise care s duc la o execuie mai eficient pentru unele cazuri dar care s micoreze generalitatea.

O arhitectur posibil a acestui sistem ar vedea urmtoarele module i interaciuni n comunicarea dintre ele:

ROBO1 sistemul radar

Numr studeni: 2

Se va construi un modul capabil a simula rspunsul radarului plasat pe robot, cnd robotul se gsete n cldire ntr-un anumit loc i are o anumit orientare. Simularea va avea la baz cldirea, care este o hart a crei form va fi aproximativ egal cu cea memorat de robot (harta). Cldirea va fi sursa rspunsurilor radarului la impulsurile emise reprezentnd distana pn la cel mai apropiat obstacol n direcia "nainte" fa de plasarea robotului. Diferenele care pot interveni ntre hart i cldire va reprezenta diferena dintre plan i realitatea la acel moment. Aceste diferene snt generate de: greeli de reprezentare pe hart, obstacole ce se afl la un moment dat n calea robotului, modificri n constituia cldirii.

Modulul va primi n intrare o poziie n plan i o direcie i va ntoarce o distan (ce reprezint rspunsul radarului la spotul de raze emis).

ROBO1 va comunica cu comparatorul hart-cldire.

ROBO2 sistemul de comparare hart-cldire

Numr studeni: 4

Se va construi un modul capabil a lua decizii asupra configuraiei terenului comparativ cu harta memorat.

Intrare: harta memorat (harta), o poziie, o direcie reprezentnd orientarea spre nainte a robotului

Ieire: o decizie a ncadrrii n hart i a locului unde se afl robotul, respectiv a apariiei unui obstacol.

Comportamentul sistemului de comparare poate fi diferit funcie de punctul n care se afl robotul fa de un perete, sau de un obstacol aflat n cale. El trebuie s aplice euristici car s decid c n anumite cazuri diferenele constatate snt nesemnificate i pot proveni din erori de apreciere ale radarului, ori aproximaii ale hrii, pe cnd n alte cazuri, cnd erorile snt mari ele pot provini din existena unor obstacole.

ROBO2 va trebui s comunice cu radarul, creierul i sistemul de readucere n plan.

ROBO3 sistemul de generare a planului

Numr studeni: 4

Se va construi un modul capabil a genera un plan de micare a robotului. Pentru generarea planulu pot fi luate n considerare mai multe strategii de cutare ntr-un spaiu al strilor. n acest caz fiecare membru al echipei se poate ocupa de implementarea unei strategii anume, putnd rezulta astfel un numr de module de planificare interanjabile. Se pot folosi coduri realizate de studeni din anii precedeni.

Intrri: punctul n cldire n care se afl robotul (START) i punctul n plan n care se dorete el a ajunge (FINI).

Ieiri: un plan, reprezentnd un ir de micri ce trebuiesc executate pentru deplasarea de la START la FINI.

Resurse: harta actualizat de creier.

Planificatorul comunic cu creierul i cu sistemul de readucere n plan.

ROBO4 sistemul de readucere n plan

Numr studeni: 4

n cazul unui incident, care aici ar putea consta n apariia neateptat a unui obstacol pe traseu, robotul ar trebui s fie capabil s plaseze din nou n plan starea curent sau, n cazuri extreme, s recalculeze planul. Modulul trebuie deci s implementeze diagrama triangular (v. cursul) pe care s decid dac noua stare se gsete n planul vechi i deci se sare n acea stare a vechiului plan, sau nu exista n planul vechi, caz n care va apela la planificator pentru calcularea unu nou plan.

Comunicaii: cu planificatorul i comparatorul hart-teren, de unde trebuie s primeasc informaii despre obstacole.

ROBO5 sistemul mecanic

Numr studeni: 2

Acest modul simuleaz sistemul de naintare i de rotire al robotului. n principiu, robotul nainteaz astfel: tie c se afl ntr-un anumit punct i trebuie s execute o micare pe o distan dat ntr-o anumit direcie, sau s execute o rotire de un anumit unghi. Ca urmare el va face un numr de pai n acea direcie sau va executa o rotire. Sistemul mecanic este cel care "propulseaz" robotul spre nainte cu un pas. Acest lucru se va manifesta printr-o actualizare a poziiei reale a robotului n "cldire" dac comanda a fost de micare nainte, sau a orientrii sale dac comanda a fost de rotire cu un anumit unghi.

Comunicaii: cu creierul, cu sistemul de vizualizare pe hart i cu sistemul de vizualizare a ceea ce vede robotul.

ROBO6 sistemul de vizualizare a perspectivei de deasupra

Numr studeni: 3-4

Modului va plasa ntr-o fereastr "cldirea" i poziia robotului n ea, dintr-o perspectiv de "deasupra". Aceasta reprezint situaia REAL.

O alt fereastr, n aceeai perspectiv va figura "harta" i poziia robotului pe hart. Aceasta reprezint situaia IMAGINAT de robot, proiecia n mintea robotului a realitii i plasarea lui ntr-nsa.

n marea parte cele dou configuraii trebuie s coincid, dar din compararea celor dou imagini un observator ar trebui s neleag motivele pentru care robotul se neal n anumite cazuri, prin luarea unor decizii greite, sau msura n care imaginea sa asupra realitii difer de cea real.

Odat cu deplasarea sau rotirea robotului aceast imagine se va schimba corespunztor.

Comunicri: cu creierul pentru proiectarea viziunii imaginare, cu sistemul de micare i generatorul de evenimente externe pentru actualizarea imaginii reale.

ROBO7 sistemul de vizualizare din perspectiva ochilor robotului

Numr studeni: 4

Modului va plasa ntr-o fereastr ceea ce "vede" robotul prin intermediul radarului su ntr-un unghi de G (parametru) grade stnga i dreapta fa de direcia "nainte".

Odat cu deplasarea sau rotirea robotului aceast imagine se va schimba corespunztor.

Comunicare: cu radarul, posibil i cu creierul.

ROBO8 creierul

Numr studeni: 4-5

"Creierul" este sistemul care integreaz informaiile primite de la diversele module pe care le are la dispoziie. El tie c se poate baza pe urmtoarele module:

ROBO2: comparatorul hart/teren care i confirm sau infirm plasarea ntr-un anumit punct, ct i existena unor obstacole (sau modificri ale configuraiei cldirii). Acest sistem obine deciziile prin folosirea lui ROBO1: ochi sistemul radar;

ROBO3: un generator de plan (n realitate tot o parte a creierului, pe care preferm s o vedem ca o component separat a sistemului);

ROBO5: picioare sistemul mecanic care propulseaz robotul nainte un pas, sau l rotete ntr-o parte cu un anumit unghi.

Dac la un anumit moment n faa robotului apare un obstacol, acesta trebuie s fie capabil a-l ocoli. Ca urmare "creierul" va afla de la ROBO2 c n fa are un obstacol i va intra ntr-o faz de scanare a terenului pentru a afla forma obstacolului. Cnd realizeaz c are suficient informaie asupra formei i plasamentului obstacolului n hart, va plasa obstacolul pe hart i va apela ROBO3 pentru o actualizare a planului.

"Creierul" trebuie gndit ca un fel de rege care acioneaz legat la ochi. El cere i obine de la sclavii si orice informaie de care are nevoie, comand anumite sarcini i ateapt rezultatul execuiei lor, pentru ca pe baza corelrii tuturor acestor informaii s hotrasc ce va face la fiecare moment n vederea realizrii planului primordial. n anumite situaii "creierul" poate decide abandonarea temporar a planului curent pentru realizarea unui plan auxiliar, care s ajute realizrii planului major. De exemplu, robotul poate intra ntr-un subplan de "scanare" a unui obstacol, pe care apoi s-l plaseze pe hart.

"Creierul" actualizeaz cu informaii "imaginea virtual" afiat de ROBO6. El nu poate i nu trebuie s cunoasc "imaginea real". Plasarea n realitate este o consecin a interaciunilor mecanice ale robotului cu lumea, iar acestea reprezint un rezultat al reprezentrii lumii n mintea sa.

ROBO9 sistemul de generare a evenimentelor externe

Numr studeni: 3-4

Utilizatorul trebuie s poat interveni n planul cldirii pentru a face modificri, constnd din plasarea de obstacole, sau deschiderea unor ui. Modificrile se fac interactiv n fereastra care prezint situaia din teren n perspectiva de deasupra.

Comunicri: cu modulul de afiare a perspectivei de deasupra (n fereastra situaiei REALE).

Grupul de proiecte IURES ndrumtor Dan Cristea

Se dorete realizarea unui sistem capabil a purta un dialog n limba romn cu un utilizator asupra unui univers de discurs precizat. Pentru exemplificarea funcionrii sistemului vom considera o aplicaie la un domeniu al discursului limitat la lumea cuburilor (ca cel din curs). Fie o mini-reea semantic ca cea din figura de mai jos:

i ntrebrile:

(I1): Ce culoare are cubul alpha?(I2): Din ce material e fcut gamma?(I3): Ce corpuri snt verzi?(I4): Care snt corpurile galbene?Bibliografie: Tufi, Tecuci&Cristea, "LISP", Ed. Tehnic, Bucureti, 1987, vol. II.

Proiectul are urmtoarele componente:

IURES1 editorul bazei de cunotine

Nr. studeni: 4 (5 dac interfaa este grafic)

Intrare: comenzi textuale sau grafice

Ieire: mesaje de eroare sau de confirmare a construciilor cerute, construcii grafice care simuleaz vizual o reea semantic.

Resurs: lips sau o reea deja construit (salvat ntr-o sesiune anterioar). Reeaua are o reprezentare n memorie i se configureaz prin dialogul cu utilizatorul. La sfritul dialogului reeaua trebuie salvat ntr-un fiier de unde s poat fi recuperat.printr-o comand (load ...). Fiierul batch construit trebuie s conin o secven de comenzi de atribuire a proprietilor pe simboluri.

Modulul trebuie s fac posibil construirea interactiv a bazei de cunotine, ca o reea semantic descriptiv. Reeaua va fi structurat pe dou niveluri: reeaua semantic conceptual (RSCon) i reeaua semantic referenial (RSRef). Nodurile trebuie unite prin relaii, care snt de dou tipuri: taxonomice (ierarhice) ISA (eventual inversa acesteia INST) i semantice, specifice domeniului. O caracteristic a funcionrii modulului trebuie s fie posibilitatea de a face modificri asupra unei reele deja construite. Se va puncta privilegiat o realizare n care construcia/editarea se realizeaz grafic.

Numele nodurilor lexicalizate trebuie s fie rdcini ale cuvintelor prin care ne putem referi la conceptul sau instana corespunztoare. Nodurilor crora nu le corespund intrri lexicale snt simboli generai cu funcia (gensym).

IURES2 modul de analiz morfo-lexical

Nr. studeni: 2

Intrare: o ntrebare n limba romn (care, n principiu, trebuie s aparin domeniului de discurs pentru care a fost construit baza de cunotine).

Ieire: un ir de rdcini de cuvinte numit form normal.

Astfel, pentru intrrile (I1) (I3), ieirile ar trebui s fie, respectiv:

(I1-fn): culoare cub alpha?(I2-fn): material gamma?(I3-fn): corp verde?(I4-fn): corp galben?Resurs: reeaua semantic ca depozitor de informaie lexical (numele nodurilor) i un dicionar de sinonime. Acest dicionar trebuie creat ca un fiier text de perechi de rdcini de cuvinte. Prile drepte ale acestor perechi snt nume de noduri lexicalizate din reeaua semantic.

Un cuvnt din intrare este cutat nti n dicionarul de sinonime prin intermediul unei funcii de recunoatere a unei rdcini ntr-un cuvnt. Dac este gsit acolo pe coloana din stnga, sinonimul lui aflat pe coloana din dreapta este ntors respectiv un nod din reea. Dac nu este gsit acolo, reeaua semantic este interogat (pentru toate rdcinile posibile ale cuvntului). Cea mai lung rdcin astfel gsit este ntoars, sau nici o urm n irul de ieire, n caz contrar.

Pentru exemplul nostru, dicionarul ar trebui s cuprind intrrile:

culori culoare; pentru a recunoate formele de plural are substantivului culoare, n care se manifest alternana fonetic oa ( ocolora culoare; pentru a face fa ntrebrilor de genul: Cum e colorat alpha?verzi verde

; pentru a recunoate formele de plural are adjectivului verde, n care se manifest alternana fonetic d ( zIURES3 modul de preprocesare semantic

Nr. studeni: 2

Intrare: forma normal lsat de modulul IURES2 de procesare morfo-lexical

Ieire: o form intermediar "pre-semantic" (v. "Lisp" pag. 207-208)

Resurs: reeaua semantic RSCon + RSRef

Sarcina acestui modul este de descoperire a categoriile funcionale ale cuvintelor din forma normal. O sarcin a modului const n identificarea conceptelor i instanelor de concept amintite n ntrebare. Pentru exemplele enunate, aceste forme snt:

(I1-preSem): (CONC culoare) (CONC cub) (INST alpha CONC cub)?(I2-preSem): (CONC material) (INST gamma CONC cub)?(I3-preSem): (CONC corp) (INST verde CONC culoare)?(I4-preSem): (CONC corp) (INST galben CONC culoare)?Practic are loc o adnotare a cuvintelor filtrate rmase n irul de intrare prin prisma reelei semantice. Astfel, (I1-preSem) precizeaz apartenena cuvntelor culoare i cub la clasa CONCEPT i a cuvntului alpha la clasa INSTAN, ca i faptul c aceasta este o instan a conceptului cub .a.m.d.

IURES4 modul de procesare semantic

Nr. studeni: 2

Intrare: forma pre-semantic lsat de modulul IURES3 de preprocesare semantic

Ieire: o form ce pune n eviden relaiile semantice ce unesc conceptele amintite n ntrebare


ntr-o prim faz, acest modul trebuie s elimine informaia redundant din perechile concept instan n care instana aparine conceptului: (CONC c) (INST i CONC c) ( (INST i CONC c).

Apoi modulul trebuie s gseasc cile de relaii semantice ce unesc conceptele din ntrebare:

(I1-Sem): (CONC culoare) are-culoare-1 (INST alpha CONC cub)?(I2-Sem): (CONC material) e-fcut-din-1 (INST gamma CONC cub)?(I3-Sem): (CONC corp) are-culoare (INST verde CONC culoare)?(I4-Sem): (CONC corp) are-culoare (INST galben CONC culoare)?IURES5 modul rezolvitor de problem

Nr. studeni: 2

Intrare: forma semantic a ntrebrii lsat de modulul IURES4 de procesare semantic

Ieire: o form ce evideniaz instanele regsite n RSRef pe cile de relaii semantice puse n eviden din interpretarea la nivel conceptual a ntrebrii


(I1-Rez): (INST galben CONC culoare)

(I2-Rez): (INST fier CONC material)(I3-Rez): (INST gamma CONC corp)

(I4-Rez): (INST alpha beta CONC corp)

Idea, a crei finalizare este dat n exemplul (I1-Rez), este ca plecnd din nodul instan alpha al conceptului cub (INST alpha CONC cub) pe o cale de relaii invers dect cea descris, respectiv (are-culoare-1)-1 = are-culoare s se regseasc o instan a nodului culoare galben, n acest caz.

IURES6 modul verbalizator

Nr. studeni: 2

Intrare: rspunsul furnizat de modulul IURES5 ca i forma intermediar a problemei furnizat de modulul IURES4

Ieire: o propoziie coerent i corect gramatical care s verbalizeze acest rspuns

Resurs: informaii de verbalizare ataate reelei semantice RSCon

Astfel, din

(I1-Sem): (CONC culoare) are-culoare-1 (INST alpha CONC cub)?i

(I1-Rez): (INST galben CONC culoare)

trebuie generat exprimarea:

Culoarea cubului alpha este galben.

Din

(I2-Sem): (CONC material) e-fcut-din-1 (INST gamma CONC cub)?i

(I2-Rez): (INST fier CONC material)trebuie generat exprimarea:

Materialul din care este fcut cubul gamma este fierul.

sau

Cubul gamma este fcut din fier.

.a.m.d.

Grupul de proiecte INFERENTE ndrumtor Dan CristeaSe dorete construcia unui sistem capabil a propaga inferene "de bun sim". Textul care urmeaz descrie parial problema. Cteva proiecte legate ntre ele pot fi imaginate. Ca text ajuttor, putei consulta si cursul de inferene n reele semantice.

Sistem inferenial pe reele semantice evenimeniale

Nr. de studeni: 4

Punctaj: 50

S se proiecteze un sistem inferenial utiliznd o reprezentare prin reele semantice evenimeniale. Iat cteva exemple:

John loves Mary:

Bill says X to John:

O regul se poate reprezenta ca un eveniment inferenial:

ntr-un proces inferenial, ori de cte ori un eveniment peste care se potrivete partea ANT a unui eveniment inferenial este detectat, un nou eveniment care e dat de instanierea prii CON a lui trebuie creat. Partea ANT a unui eveniment inferenial lucreaz ca un demon pattern. El este n general adormit dar apariia unui eveniment de tip A l trezete, fcndu-l s verifice dac satisface pattern-ul (ev4 n figur). n caz afirmativ, un eveniment de tip B dat de o instaniere a lui ev5 este creat i procesul se propag mai departe. n astfel de reele timpul este o component important, apariia unor anumite evenimente fcndu-se la anumite momente de timp. Sistemul ar trebui s raporteze toate apariiile de noi evenimente.

S se arate cum se poate dezvolta un proces inferenial ntr-o astfel de reea n care se cunosc premizele:

John is a man.

Bill is a man.

Mary is a woman.

John is very believable (if a person X says to John Y then John believes Y).

Any man is a person.

Any woman is a person.regulile:

Every man that loves a woman and believes that that woman loves him is happy.

Every man that loves a woman and believes that that woman loves another man is unhappy.

i apariiile de evenimente (la anumite momente de timp):

t1: John loves Mary.

t2>t1: Mary says to John that she loves John.

t3>t2: Bill said to John that Mary loves Bill.S se imagineze mecanisme de pstrare a consistenei reprezentrii. Spre exemplu, sistemul ar trebui s nu permit existena simultan a unor perechi de evenimente (John e fericit, John e nefericit).

Reeaua semantic va fi construit cu editorul de reele semantice evenimeniale iar deducerea proprietilor motenite v va fi dat de modulul de motenire n reele semantice.

Editor de reele semantice evenimeniale

Nr. studeni: 4

Punctaj: 50

S se scrie un program editor cu ajutorul cruia s se poat construi interactiv o reea semantic. Lucrul cu editorul se va face cu predilecie ntr-o manier grafic, prin operaii cu mouse-ul (click, drag-and-drop etc.). De exemplu pentru a defini un concept: click dreapta n spaiul de lucru, selectarea meniului de creare concept dintr-o fereastr float care se deschide, urmat de completarea unor informaii ntr-o fereastr de dialog. Stabilirea relaiilor dintre obiecte: drag-and-drop n spaiul de lucru a unui obiect de tip RELAIE, care se va lega de cele dou obiecte/instane ntre care trebuie stabilit relaia. Reeaua construit se salveaz. O sesiune de lucru cu editorul poate fi ntrerupt i reluat alt dat.

Proiecte cu care va trebui s colaborai: motenirea proprietilor, sistem inferenial pe reele semantice evenimeniale.

Motenirea proprietilor

Nr. studeni: 2

Punctaj: 45

Descriei un algoritm de motenire a proprietilor ntr-o reea semantic descriptiv (un sistem ierarhic nemonoton cu multipl motenire). Sistemul va rezolva contradiciile prin adoptarea unui algoritm de prioriti (nti-n-adncime, stnga-dreapta, ca cel din CLOS). Programul va trebui s lucreze pe o reea construit cu editorul de reele semantice. Este recomandabil ca proiectul de inferene n reele semantice s utilizere modului dv. pentru toate proprietile motenite.

ochi

picioare

comparare hart-teren

imagine virtual

imagine real

creier

planificator

evenimente externe

perspectiv ochi

readucerea n plan

e-fcut-din

e-fcut-din

e-fcut-din

are-culoare

are-culoare

lemn

fier

verde

rou

galben

are-culoare

e-fcut-din

culoare

material

gamma

Reeaua semantic referenial

Reeaua semantic conceptual

beta

alpha

cub

obiect

cilindru

corp

LOVER

evenimente

cu to love

John

BELOVED

person

Mary

ev1

LOVER

BELOVED

SPEAKER

HEARER

person

SAID-THING

evenimente

cu to say

John

SPEAKER

HEARER

Bill

ev1

SAID-THING

X

evenimente

infereniale

evenimente

de tip A

evenimente

de tip B

ev3

ev4

ev5

ANT

CON

orice eveniment

proiecte

Documents