Probleme de Traversare a Unui Rau Folosind Inteligenta Artificiala

INTRODUCERE

Lucrarea “Probleme de traversare a unui râu folosind inteligența artificială” are ca scop prezentarea rezolvării problemelor ca noțiune generală și ramură a Inteligenței Artificiale, înfățișarea unor exemple de probleme de traversare a unui râu cunoscute în Inteligența Artificială, elaborate de cercetătorii din domeniu de-a lungul timpului și rezolvarea într-o manieră algoritmică a acestora.

Rezolvarea algoritmică a problemelor ține de formularea și găsirea soluției problemelor, unde soluția implică, uneori în mod implicit, principiile și tehnicile care au fost elaborate pentru a asista în construirea algoritmilor care să funcționeze corect. Algoritmii au fost studiați și dezvoltați încă de la începuturile civilizației, dar, pe parcursul ultimelor decenii, volumul neașteptat de probleme de programare și cererile consecvente de programe software fiabile au dus la îmbunătățiri masive în ceea ce privește aptitudinile oamenilor de a rezolva problemele folosind algoritmi. Îmbunătățirile sunt centrate pe găsirea obiectivelor și construirea calculată a algoritmilor în mod contrar metodologiei tradiționale “ghicește și verifică”.

O problemă de traversare a unui râu reprezintă un tip de puzzle de transport, unde obiectivul este de a transporta entități de pe un mal al râului pe celălalt. Dificultatea problemei poate varia în funcție de restricțiile asupra numărului sau felului în care sunt transportate entitățile în același timp, sau în funcție de câte entități, respectiv modul în care acestea pot fi lăsate împreună pe un mal. Contextul poate varia, de exemplu, prin înlocuirea râului cu un pod.

Cele mai vechi probleme de traversare a unui râu cunoscute apar în manuscrisul “Propositiones ad Acuendos Juvenes” (traducându-se prin Probleme pentru stimularea tinerilor), scris de către Alcuin. Cele mai vechi copii ale manuscrisului datează din secolul al IX-lea și conțin trei probleme de traversare a unui râu, și anume problema vulpii, gâștei și sacului cu boabe, problema soților geloși si problema podului și torței.

Capitolul 1

[1],[4],[5],[6],[7],[8],[9],[10],[11]

CE ESTE INTELIGENȚA ARTIFICIALĂ?

1.1 Definirea inteligenței artificiale

Omul a fost supranumit homo-sapiens – omul inteligent – deoarece acesta consideră inteligența un lucru foarte important. Timp de mii de ani s-a încercat înțelegerea gândirii umane, în condițiile în care, un simplu ansamblu de materie poate percepe, întelege, prezice și manipula o lume mult mai mare și mai complicată decât sine însuși. Domeniul inteligenței artificiale, pe scurt AI, merge totuși mai departe de atât: acesta nu încearcă doar să înțeleagă entitățile inteligente, ci și să le construiască.

Inteligența artificială este unul dintre cele mai noi domenii în cadrul științei și ingineriei. Primele lucrări au început imediat după Al Doilea Război Mondial, și denumuriea propriu-zisă a luat naștere in anul 1956. Acest domeniu este preferat de majoritatea cercetătorilor întrucât, spre deosebire de alte științe unde cunoașterea a ajuns la un nivel ridicat și elaborarea de concepte noi presupune o dificultate mare, oferă posibilitatea de noi descoperiri și îmbunătățiri.

În prezent, în cadrul inteligenței artificiale se studiază o gamă largă de subdomenii, variind de la cele generale (cunoaștere și percepție), până la cele specifice, precum jocurile, demonstrarea teoremelor matematice, problema conducerii unui autovehicul pe o stradă în care apar obstacole, diagnosticarea unor maladii, automatizarea unor aparaturi, configurarea roboților etc. Deoarece inteligența artificială este aplicabilă oricărei sarcini ce implică gândirea, se poate spune că este într-adevăr un câmp de studiu universal.

Fiind un domeniu atât de vast, nu s-a putut da o definiție concretă care să cuprindă toate aspectele inteligenței artificiale. Totuși, s-a încercat definirea inteligenței artificiale urmărind cele două planuri: gândire și comportament. Sunt prezentate opt definiții bazate pe aceste două planuri, formulate de-a lungul timpului de cercetători.

Tabelul 1. Definirea Inteligenței Artificiale

Definițiile din partea de sus a Tabelului 1 reprezintă procesele de gândire și raționament, pe când cele de jos țin de comportament. Definițiile din stânga măsoara succesul în funcție de cât de asemănătoare este performanța mașinii cu cea umană, pe când cele din dreapta măsoară succesul paralel cu o unitate ideală de măsură, numită rațiune. Un sistem este rațional dacă va obține rezultatul dorit sau va avea comportamentul așteptat în funcție de datele pe care le are la un moment dat.

În istorie, toate cele patru abordări ale inteligenței artificiale au fost urmate, fiecare dintre acestea de către oameni diferiți, folosind metode diferite. O abordare bazată pe partea umană trebuie să fie într-o anumită măsură o știință empirică, incluzând observații și ipoteze despre comportamentul uman. O abordare rațională solicită o combinație de matematică și inginerie. Au existat interacțiuni între cele două grupuri, fie discreditându-se, fie ajutându-se reciproc în cele două domenii.

1.1.1 Comportamentul uman : Testul Turing

Testul Turing, propus de către Alan Turing (1950), a fost conceput să vină cu o soluție satisfăcătoare din punct de vedere operațional în ceea ce privește definirea inteligenței. Un computer va trece testul dacă un interogator uman, după ce pune o serie de întrebări scrise, nu va putea ști clar dacă răspunsurile scrise vin din partea unei persoane sau a unei mașini. Este de remarcat că pentru a programa un computer să treacă un test riguros necesită un volum suficient de mare de muncă. Computerul ar avea nevoie de următoarele abilități:

procesarea limbajului natural – pentru a-i permite să comunice cu succes într-o anumită limbă;

reprezentarea cunoștiințelor – pentru a stoca ceea ce știe sau primește din exterior;

raționamentul automat – pentru a folosi informațiile stocate ca să răspundă întrebărilor și să tragă noi concluzii;

învățare specifică mașinii – să se adapteze circumstanțelor noi și să detecteze și extrapoleze modele.

Testul Turing a evitat în mod intenționat contactul fizic direct între interogator și computer, pentru că simularea prezenței fizice a unei persoane este lipsită de importanță pentru inteligență. Cu toate acestea, asa-numitul test Turing Total include semnale video astfel încât interogatorul poate testa abilitățile de percepție ale subiectului și, de asemenea, poate “înmâna” obiecte fizice printr-un orificiu. Pentru ca un computer să treacă testul Turing total, ar avea nevoie de:

viziune computerizată – pentru a percepe obiectele;

facilități de domeniul roboticii – pentru a putea manipula obiectele și a se deplasa;

Cele șase discipline compun majoritatea domeniului inteligenței artificiale, și Turing rămâne apreciat pentru elaborarea unui test care rămâne relevant șase decenii mai târziu. Cu toate acestea, până de curând, cercetătorii au depus un efort nesemnificativ pentru a trece testul Turing, crezând că studiul principiilor care stau la baza inteligenței este mai important decât crearea unui exemplar ce posedă inteligență. Un fapt remarcabil îl reprezintă succesul în misiunea de a crea zborul artificial, odată cu folosirea tunelelor aerodinamice și studiului aerodinamicii în general de către frații Wright, în detrimentul imitării păsărilor. Lucrările inginerilor din aeronautică nu prezintă țelul câmpului lor de activitate ca “crearea unor mașinării care să zboare exact ca niște porumbei astfel încât să păcălească alti porumbei”.

1.1.2 Gândirea umană: Modelarea cognitivă

Pentru a putea afirma că un anumit program gândește ca un om, trebuie stabilite niște metode prin care se poate determina cum gândește omul. Trebuie studiate procesele efective ce au loc în mintea umană. Există trei căi prin care se poate realiza acest lucru:

introspecție – încercarea cuiva de a-și capta propriile gânduri pe măsură ce acestea apar;

experimente psihologice – observarea unei persoane în acțiune;

imagistica creierului – observarea modului de funcționare a creierului;

Odată formată o teorie precisă despre mintea umană, devine posibil ca acea teorie să fie exprimată ca un program de computer. Spre exemplu, Allen Newell și Hertbert Simon, creatorii programului “General Problem Solver”, în traducere program care rezolvă o gamă largă de probleme, prescurtat GPS, nu au fost preocupați de abilitatea programului de a rezolva problemele corect. Mai degrabă, aceștia au urmărit pașii raționamentului programului în rezolvarea problemelor și i-au comparat cu raționamentul subiecților umani în rezolvarea acelorași probleme. Câmpul interdisciplinar al științei cunoașterii adună laolaltă modele computerizate din inteligența artificială și tehnici experimentale din psihologie pentru a construi teorii precise și testabile ale minții umane.Știința cunoașterii este în mod necesar bazată pe investigația experimentală a indivizilor umani sau animali.

La începuturile inteligenței artificiale exista o confuzie între abordări: un anumit cercetător putea susține că un algoritm se descurcă bine cu o anumită sarcină, fiind așadar un model bun de comportament uman, sau invers. În prezent, abordările sunt delimitate clar, nemaiexistând confuzii și permițând atât inteligenței artificiale, cât și științei cunoașterii, să se dezvolte mai rapid.

1.1.3 Gândirea rațională: Legile gândirii

Filosoful grec Aristotel a fost unul dintre primii gânditori care au încercat să codifice “gândirea corectă”, ceea ce reprezintă, evident, procese irefutabile ale rațiunii. Silogismele sale au oferit modele pentru structuri rationale care furnizau mereu concluzii corecte atunci când premisele date erau corecte. Aceste legi ale gândirii au fost presupuse a guverna procesul gândirii și, astfel, studiul lor a dat naștere domeniului științific numit logică.

Logicienii secolului al XIX-lea au dezvoltat o serie de notații specifice pentru enunțurile legate de toate felurile de obiecte din lume și relațiile dintre acestea. În anul 1965, existau deja programe care, în principiu, puteau rezolva orice problemă expusă în notația logică și care să aibă soluție ( în cazul în care problema nu avea o soluție, programul ar fi intrat într-o buclă infinită). Logicienii din prezent speră să dezvolte în continuare, în cadrul inteligenței artificiale, anumite programe pentru a crea sisteme inteligente.

În cadrul abordării bazate pe legile gândirii există două obstacole principale. În primul rând, preluarea cunoștințelor informale și transformarea acestora în termenii formali de care este nevoie în notația logică, nu este o sarcină ușoară, mai ales atunci când cunoștințele nu sunt 100% sigure. În al doilea rând, există o diferență mare între a rezolva o problemă “în principiu” și a o rezolva în mod practic. Chiar și problemele care conțin câteva sute de fapte pot epuiza resursele unor computere obișnuite, decât daca nu există o îndrumare în ceea ce privește ordinea în care se execută pașii raționamentului. Deși cele două obstacole se aplică oricărei încercări de a construi sisteme de calcul rationale, acestea au apărut initial în domeniul logicii.

1.1.4 Comportamentul rațional: Agentul rațional

Un agent este ceva ce acționează (termenul agent provine din latinescul agere, care înseamnă a face). Desigur, orice program pe computer face ceva, dar agenții implementați pe computer sunt construiți pentru a face ceva mai mult: a acționa în mod independent, a percepe mediul în care se află, a persista o perioadă mai lungă de timp, a se adapta la schimbări și a crea și urmări scopuri. Un agent rațional este ceva ce acționează în așa manieră încât să obțină cel mai bun rezultat, sau, dacă există incertitudini, să obțină cel mai bun rezultat posibil.

În abordarea bazată pe legile gândirii, accentul este pus pe deducții corecte. A face deducții corecte reprezintă uneori o parte a activității agentului rațional, deoarece o cale de a se comporta rațional este să raționeze logic până la concluzia că o acțiune dată va duce la îndeplinirea scopului și apoi să acționeze în baza acelei concluzii. Pe de altă parte, deducțiile corecte nu definesc întru totul raționamentul; în unele situații nu există un lucru demonstrat a fi corect de făcut, dar ceva trebuie totuși făcut. Există, de asemenea, căi prin care un agent se poate comporta rațional, dar despre care nu se poate spune că implică deducții. Spre exemplu, a trage rapid mâna de pe o plită încinsă este un act reflex mai eficient decât o acțiune mai lentă, dedusă după o gândire atentă.

Toate aptitudinile necesare pentru testul Turing permit, de asemenea, unui agent să acționeze rațional, reprezentarea cunoștințelor și rațiunea permit agenților să ia decizii bune. Omul are nevoie să genereze propoziții clare în limbajul natural pentru a exista într-o societate complexă, are nevoie să învețe nu numai pentru știință, dar și ca să-și îmbunătățească abilitatea de a genera comportamente eficiente.

Abordarea agentului rațional are doua avantaje față de celelalte abordări. Pe de-o parte, este mai generală decât abordarea legilor gândirii, deoarece deducțiile corecte sunt doar una dintre cele câteva mecanisme posibile pentru a obține raționalitatea. Pe de altă parte, este mai maleabilă pentru dezvoltările științifice decât abordările bazate pe comportamentul uman sau gândirea umană. Standardul raționalității este foarte bine definit matematic și complet general și poate fi “despachetat” pentru a genera modele de agenți care să-l îndeplinească în mod dovedit. Comportamentul uman, pe de altă parte, este bine adaptat pentru un anumit mediu și este definit oarecum de totalitatea lucrurilor făcute de oameni în general. Ținând cont de principiile generale ale agenților raționali și de componentele necesare construirii lor, este observabil faptul că, în ciuda simplității aparente cu care problema poate fi definită, o varietate enormă de obstacole pot apărea la rezolvarea ei.

Un lucru important de reținut este faptul că ideea de a obține raționalitatea perfectă, adică a lua mereu decizia corectă, nu este un lucru realizabil în mediile complicate. Cerințele computaționale devin foarte ridicate.

1.2 Influențe asupra inteligenței artificiale

Inteligența artificială este o disciplină foarte tânără. Alte discipline precum filosofia, neurobiologia, biologia evoluționistă, economia, științele politice, sociologia, antropologia, ingineria de control și multe altele au studiat inteligența pentru o perioadă mai îndelungată. Influențele asupra inteligenței artificiale sunt foarte numeroase, astfel încât numai câteva exemple vor fi prezentate, definind o serie de întrebări ce pun în legătură un domeniu cu domeniul inteligenței artificiale.

Filosofie

Pot fi folosite regulile formale pentru a trage concluzii valide?

Cum apare mintea dintr-un creier fizic?

De unde vine cunoașterea?

Cum duce cunoașterea la acțiune?

Aristotel (384 – 322 î.H) a fost primul care a formulat un set precis de reguli care guvernează partea rațională a minții. El a dezvoltat un sistem informal de silogisme pentru raționament adecvat, care, în principiu, permiteau generarea de concluzii în mod mecanic, pornind de la un set de premise. Mult mai târziu, Ramon Lull (1315), a avut ideea că un raționament folositor poate fi îndeplinit de către o entitate mecanizată. Wilhelm Leibniz (1646-1716) a construit un aparat mecanic cu scopul de a efectua operații pe concepte, în locul numerelor, dar domeniul său era limitat. S-a speculat că mașinile ar putea face nu numai calcule, dar să fie și capabile să gândească și să acționeze independent. Acest fapt este demonstrat ca fiind posibil, odată cu apariția roboților capabili să poarte o conversație, rudimentară ce-i drept, sau să se deplaseze într-un mediu cu obstacole.

Fiind dată o minte fizică ce manipulează cunoștințe, următoarea problemă o reprezintă sursa cunoștințelor. David Hume (1711-1776), prin lucrarea Tratat asupra naturii umane (Hume, 1739), a propus principiul inducției: regulile generale sunt obținute prin expunerea la asocieri repetate între elementele lor. Mai târziu a fost dezvoltată doctrina pozitivismului logic. Această doctrină susține că toate cunoștințele pot fi caracterizate prin teorii logice conectate, eventual, la enunțuri de observație care corespund datelor inițiale de tip senzorial. Astfel, pozitivismul logic combină raționalismul cu empirismul. Cartea lui Carnap, Structura logică a lumii (1928), definește o procedură de calcul explicită pentru extragerea cunoștințelor din experiențe elementare. A fost probabil prima teorie a minții văzute ca proces computațional.

Ultimul element al minții din punct de vedere filosofic îl reprezintă conexiunea dintre cunoaștere și acțiune. Acest aspect este vital pentru inteligența artificială, întrucât inteligența necesită acțiuni, alături de rațiune. Mai mult, doar prin întelegerea modului în care acțiunile sunt justificate, se poate întelege modul în care se construiește un agent ale cărui acțiuni sunt justificabile (sau raționale). Aristotel, în lucrarea sa De Motu Animalum, susține că acțiunile sunt justificate de o conexiune logică între obiective și cunoașterea rezultatului unei acțiuni.

Matematică

Care sunt regulile formale necesare pentru a trage concluzii valide?

Ce poate fi calculat?

Cum raționăm bazându-ne pe informații nesigure?

Filosofii au marcat unele dintre ideile fundamentale ale inteligenței artificiale, dar saltul la o știință formală a cerut o formalizare matematică în trei arii fundamentale: logică, calcul și probabilitate.

Ideea de logică formală poate fi identificată încă din timpul filosofilor Greciei antice, dar dezvoltarea ei matematică a început cu adevărat odată cu munca lui George Boole (1815-1861), care a conturat detaliile logicii propoziționale, sau logicii Boole (Boole, 1847). Alfred Tarski (1902-1983) a lansat o teorie de referință care arată felul în care pot fi asociate obiectele dintr-o schemă de tip logic cu cele din lumea reală. Următorul pas era să se determine limitele a ceea ce putea fi făcut folosind logica și calculul.

Teoria incompletitudinii, aparținând lui Gödel, demonstrează că în orice teorie formală la fel de puternică precum aritmetica Peano (teoria elementară a numerelor naturale), există afirmații adevărate asupra cărora nu se poate decide nimic, în sensul că nu au nici o dovadă în cadrul teoriei. Asta l-a motivat pe Alan Turing (1912-1954) să încerce să găsească exact care funcții sunt calculabile. Teza elaborată de Church și Turing, care susține că o mașină Turing (Turing, 1936) este capabilă să calculeze orice funcție calculabilă, este în general acceptată. Turing de asemenea a demonstrat că există funcții pe care nici o mașină Turing nu le poate calcula. Un exemplu foarte bun îl reprezintă faptul că nici o mașină nu poate spune în mod general dacă un program dat va returna un rezultat în mod sigur sau va rula într-o buclă infinită.

Pe lângă logică și calcul, a treia mare contribuție a matematicii în inteligența artificială este teoria probabilității. Italianul Gerolamo Cardano (1501-1576) a fost primul care a lansat ideea de probabilitate, descriind-o în termeni de eventuale deznodământuri ale jocurilor de noroc. În anul 1654, Blaise Pascal (1623-1662), într-o scrisoare adresată lui Pierre Fermat (1601-1665), a arătat cum poate fi prezis viitorul unui joc de noroc neterminat și cum să atribuie plăți medii pariorilor. Probabilitatea a devenit rapid o parte neprețuită a tuturor științelor cantitative, ajutând la abordarea măsurătorilor nesigure și teoriilor incomplete.

Economie

Cum ar trebui luate deciziile pentru a maximiza profitul?

Cum poate fi maximizat profitul atunci când oamenii din jur nu cooperează?

Economia ca știință a apărut în 1776, atunci când folosoful scoțian Adam Smith (1723-1790) a publicat lucrarea O anchetă privind natura și cauzele averii națiunilor. Smith a fost primul care a tratat economia ca pe o știință, bazându-se pe ideea că economia poate fi văzută ca un ansamblu de agenți care doresc să-și maximizeze propria situație economică.

Teoria deciziilor, care combină teoria probabilității cu teoria utilității, oferă un cadru formal și complet pentru deciziile (economice sau nu) făcute cu incertitudine, asta fiind valabil în cazurile în care descrierile probabilistice surprind în mod corespunzător mediul celui care ia deciziile. Acest lucru este potrivit pentru economiile mari, unde fiecare agent trebuie să ignore acțiunile altor agenți ca indivizi. Pentru economiile mici, situația este mai mult ca un joc: acțiunile unui jucător pot afecta în mod significant utilitatea altuia (fie în mod pozitiv sau negativ).

Munca în economie și în cercetarea operațională au contribuit mult în definirea noțiunii de agenți raționali, dar pentru mulți ani inteligența artificială a evoluat pe o cale complet separate. Un motiv îș reprezintă complexitatea evidentă de a face decizii rationale. Herbert Simon (1916-2001) a demonstrat că modelele bazate pe satisfacere (luarea deciziilor care sunt suficient de bune, în locul calculării laborioase a unei decizii optime) ofereau o descriere mai bună a comportamentului uman (Simon, 1947). Începând cu anii 1990, interesul reapărut în ce privește tehnicile decizional-teoretice pentru sistemele bazate pe agenți raționali (Wellman, 1995).

Capitolul 2

[1],[3]

AGENȚI INTELIGENȚI

Conceptul de raționalitate poate fi aplicat unei mari varietăți de agenți care operează în orice mediu. Faptul că unii agenți se comportă mai bine decât alții conduce la ideea de agent rațional, acela care se comportă cât mai bine cu putință. Performanța unui agent depinde de natura mediului în care se află, unele medii fiind mai dificile pentru acesta decât altele.

2.1 Aspecte generale

Un agent poate fi văzut ca o entitate care percepe mediul în care se află prin intermediul senzorilor și care acționează în acel mediu prin intermediul efectorilor. Un agent uman are ochi, urechi, cât și alte organe care acționează ca senzori, alături de mâini, picioare, corzi vocale și altele, care se comportă ca efectori în relația cu mediul. Un agent software, în schimb, primește comenzi de la tastatură, fișiere, pachete de rețea, etc, ca date senzoriale de intrare și se acționează asupra mediului în care se află prin afișarea unor rezultate pe un ecran, scriere de fișiere sau trimitere de pachete în rețea.

Se definește termenul de percepție, care se referă la informațiile percepute de către un agent într-un mediu, la orice moment dat. Secvența percepțiilor agentului reprezintă o istorie completă a tuturor informațiilor pe care agentul le-a perceput de-a lungul activității sale. Astfel, decizia unui agent la un anumit moment poate depinde de întreaga secvență a percepțiilor până la momentul curent, dar nu va depinde de lucuri pe care acesta nu le-a perceput încă. Specificând modalitatea de acțiune a unui agent pentru fiecare secvență de percepții posibilă, se caracterizează, în mare, rolul său.

Fig. 2.1 Agentul simplu

Matematic, comportamentul unui agent poate fi descris de funcția agent, care pune în legătură orice percepție cu o anumită acțiune. Poate fi imaginată încadrarea acestei funcții agent într-un tabel care să descrie orice agent, pentru o mare majoritate a agenților. Cu toate acestea, ar fi imposibil de realizat datorită dimensiunilor; ar ajunge la o lungime infinită. Un astfel de tabel ar putea fi realizat doar punând o limită asupra lungimii secvențelor de percepții care vor fi alese. Având la dispoziție un agent experimental, se poate construi un tabel prin explorarea tuturor secvențelor de percepții posibile și înregistrarea acțiunilor executate de agent ca răspuns. Tabelul reprezintă o caracterizare externă a agentului, pe când, intern, funcția-agent asociată unui agent artificial va fi implementată într-un program-agent. Cele două noțiuni nu trebuiesc confundate, întrucât funcția reprezintă o descriere matematică abstractă, pe când programul reprezintă o implementare concretă, care va rula într-un sistem fizic (mașină de calcul,etc).

Pentru a ilustra aceste idei, se va considera exemplul lumii aspiratorului. Simplitatea acestei lumi este suficient de mare încât pot fi prezentate toate acțiunile efectuate de aspirator și, de asemenea, fiind o lume imaginară, se pot adăuga o serie de variații. Mediul acestui exemplu este constituit din două locații, pătratul A și pătratul B. Agentul aspirator va percepe în ce pătrat se află și dacă este mizerie sau nu în acel pătrat. În funcție de aceste date, el poate alege să se miște în partea dreaptă, în partea stângă, să aspire mizeria sau să nu facă nimic. O funcție foarte simplă pe care să se bazeze comportamentul agentului este următoarea: dacă pătratul curent este murdar, atunci agentul va aspira, altfel, se va muta în celălalt pătrat.

Fig. 2.2 Lume cu două locații a unui agent-aspirator

Tabelul 2.1 Tabelarea funcției unui agent simplu pentru lumea agentului aspirator din Fig. 2.2

O tabelare parțială a unei funcții agent este prezentată în Tabelul 2. Urmărind acest tabel, se poate observa că majoritatea agenților dintr-o lume a agenților-aspirator pot fi definiți doar prin adăugarea în diferite feluri a acțiunilor în partea dreaptă a tabelului. Cu toate acestea, se pune următoarea întrebare: ce definește un agent ca fiind bun sau slab, inteligent sau lipsit de inteligență.

2.2 Comportamentul agenților

Un agent rațional este un agent care va face ceea ce trebuie. Conceptual vorbind, asta înseamnă că fiecare intrare în tabelul funcției agent va fi completată în mod corect. Evident, a face ceea ce trebuie este mai important decât contrarul, dar trebuie definit conceptul de a face ce trebuie. Se pun în discuție consecințele acțiunilor unui agent. Atunci când un agent este plasat într-un mediu, acesta va genera o secvență de acțiuni în funcție de percepțiile pe care le are. Această secvență de acțiuni va face mediul să treacă printr-o secvență de stări. Dacă secvența este acceptabilă, atunci agentul s-a comportat bine. Acest lucru este surprins de o măsură a performanței, care evaluează orice secvență de stări ale mediului dată.

Este important să se facă distincția înre stările mediului și stările agentului. Dacă s-ar defini succesul în funcție de opinia agentului despre propria performanță, atunci un agent ar atinge raționalitatea perfectă doar amăgindu-se că performanța sa a fost perfectă. În mod evident, nu există o măsură a performanței fixă pentru toate sarcinile și agenții posibili. Se va elabora una în funcție de circumstanțe. Considerând exemplul agentului aspirator cu două locații, s-ar putea măsura performanța acestuia în funcție cantitatea de mizerie curățată într-un interval de douăsprezece ore. În cazul acesta, un agent rațional și-ar maximiza această măsură a performanței prin curățarea mizeriei, apoi aruncarea acesteia pe podea și curățarea ei din nou, ducând la un ciclu de acest gen. O măsură a performanței mai potrivită ar fi răsplătirea agentului pentru faptul că podelele sunt curate. Rezultând ca o regulă generală, este mai potrivit ca măsura peformanței să fie elaborată în funcție de schimbările care se doresc într-un mediu, decât în funcție de modul în care s-ar dori ca agentul să se comporte.

Cu toate acestea, chiar și atunci când principalele probleme sunt evitate, încă rămân niște aspecte ce trebuiesc rezolvate. Urmărind exemplul de mai sus, cu agentul aspirator ce efectuează acțiuni în intervalul de douăsprezece ore, noțiunea de „podea curată” poate fi interpretată ca o curățenie medie în timp. Dar această curățenie medie poate fi atinsă în mod egal de către doi agenți diferiți, unul dintre ei muncind la intensitate normală, dar pe tot intervalul de timp, pe când celălalt să curețe mai repede, dar să ia pauze mai mari. Acest exemplu poate avea implicații filosofice adânci. Poate fi comparat cu alegerea dintre o viață riscantă, constituită din suișuri și coborâșuri, sau o viață banală, dar sigură. O altă situație asemănătoare este alegerea dintre o economie unde toată lumea trăiește într-o sărăcie moderată, sau o economie unde unii trăiesc în bogăție, pe când alții sunt foarte săraci. Se definesc în continuare principalele caracteristici care determină modul în care se va comporta un agent.

2.2.1 Raționalitatea

La un anumit moment, raționalitatea depinde de patru lucruri:

Măsura performanței care definește criteriul succesului.

Cunoașterea inițială a mediului de către agent.

Acțiunile pe care un agent le poate face.

Secvența actualizată de percepții a agentului.

Aceste aspecte duc la o definire a rolului unui agent rațional: pentru orice secvență de percepții posibilă, un agent rațional ar trebui să aleagă acțiunea care va maximiza măsura peformanței sale, tinând cont de acea secvență de percepții și de orice cunoștințe încorporate ale agentului.

Reluând exemplul agentului aspirator, se cunoaște faptul că acesta va curăța un pătrat dacă este murdar, sau se va muta în celălalt pătrat în caz contrar. Pentru a stabili dacă acest agent este într-adevăr un agent rațional, va trebui definită măsura performanței, ce se știe despre mediu și acțiunile pe care agentul le va face în funcție de cunoștințele pe care le primește de la mediu:

Măsura performanței va acorda un punct recompensă pentru fiecare pătrat curat la un anumit pas, pe parcursul a 100 de pași executați în timp.

Se cunoaște felul în care arată mediul, dar locația de pornire și unde este mizeria rămân informații necunoscute. Pătratele curate rămân curate și acțiunea de aspirație va curăța pătratul curent. Acțiunile stânga și dreapta vor muta agentul în stânga sau în dreapta, exceptând cazul în care aceste acțiuni ar scoate agentul din mediul în care se află. În acest caz, agentul va rămâne pe loc.

Singurele acțiuni disponibile, deci, sunt Stânga, Dreapta, Aspiră.

Agentul va percepe în mod corect locația în care se află și dacă în acea locație se află mizerie.

În aceste condiții se poate spune că agentul este într-adevăr rațional. Performanța așteptată de la acesta este cel puțin la fel de bună ca a oricărui alt agent. Se poate observa cu ușurință că același agent poate deveni irațional în circumstanțe diferite. Un exemplu care dovedește acest lucru este cazul în care, odată ce toată mizeria a fost curățată, agentul va oscila neputincios între cele două locații. Dacă măsura performanței sale ar include o penalitate de un punct pentru fiecare acțiune Stânga sau Dreapta, atunci agentul ar fi unul slab. Un agent bun în cazul acesta nu ar face nimic odată ce s-ar asigura că toate pătratele sunt curate. Dacă pătratele devin iarăși murdare, agentul ar trebui să verifice ocazional și să le curețe dacă este nevoie. Dacă mediul este necunoscut, agentul trebuie să exploreze în loc să rămână la cele două pătrate A și B.

2.2.2 Omnisciența, învățarea și autonomia

Este important să se facă distincția între raționaliate și omnisciență. Un agent omniscient știe rezultatul efectiv al acțiunilor sale și poate acționa în consecință; omnisciența rămâne totuși o calitate imposibilă în lumea reală. Se consideră un exemplu în care două persoane sunt depărțite de o stradă și una dintre ele dorește să ajungă la cealaltă . Nu există trafic și agentul-persoană care dorește să traverseze nu este ocupat cu altă acțiune. În mod rațional, acesta alege să traverseze strada. Între timp, se prăbușește un avion pe acea stradă, iar agentul este distrus. Faptul că agentul a ales să traverseze nu a fost un lucru irațional în condițiile date, dar acest exemplu demonstrează că raționalitatea nu înseamnă perfecțiune.

Raționalitatea maximizează performanța dorită, pe când perfecțiunea maximizează performanța efectivă. Astfel, se dovedește a fi imposibil de realizat un agent inteligent ale cărui acțiuni se vor dovedi mereu a fi cele corecte. În consecință, definirea raționalității nu necesită omnisciență, deoarece o alegere rațională depinde numai de secvența percepțiilor actualizată. Pe de altă parte, se dorește ca un agent să nu întreprindă acțiuni slabe din punct de vedere al inteligenței. Dacă un agent nu se va uita în ambele direcții înainte de a traversa o stradă aglomerată, secvența percepțiilor sale ar fi prea sumară și agentul ar putea fi călcat. Mai mult, un agent rațional ar alege acțiunea de a privi în ambele părți, chiar înainte de a începe să traverseze. Acest lucru ar maximiza performanța așteptată. A face acțiuni pentru a modifica percepțiile viitoare, fapt care se numește adunare de informații, reprezintă un aspect important al raționalității.

Un agent rațional trebuie nu numai să adune informații, dar și să învețe cât mai multe din percepțiile sale. Configurația inițială a agentului ar putea conține cunoștințe inițiale mărunte despre mediu, dar pe măsură ce acesta capătă experiență, acele cunoștințe vor fi modificate și îmbunătățite. Există cazuri extreme în care mediul este cunoscut complet încă de la început. În acest caz, agentul nu trebuie să perceapă sau să învețe, trebuie doar să acționeze corect. Acest tip de agent este unul fragil.

O altă caracteristică a unui agent inteligent este autonomia. Un agent rațional ar trebui să învețe ce poate astfel încât să poată compensa pentru cunoștințele inițiale parțiale sau incorecte. Practic, rareori se cere autonomie completă încă de la început. Dacă agentul a avut foarte puțină experiență, sau deloc, acesta ar fi trebuit să acționeze la întâmplare doar dacă designerul nu l-ar fi sprijinit. Așa cum evoluția a înzestrat animalele cu mecanisme care să le permită să supraviețuiască până dobândesc suficientă cunoaștere, este de preferat ca un agent să aibă, de asemenea, o serie de cunoștințe inițiale cât și abilitatea de a învăța. Acumulând suficientă experiență, comportamentul unui agent rațional poate deveni efectiv independent de cunoștințele sale primare. Astfel poate fi construit un singur agent rațional pentru o multitudine de medii.

2.3 Mediul de sarcină al agenților

Următorul pas în construirea unui agent, după definirea conceptului de raționalitate, îl reprezintă identificarea mediului de sarcină. Mediul de sarcină practic reprezintă problema a cărei soluție va fi oferită de agenții inteligenți. Definirea acestor medii de sarcină se poate face în mai multe moduri, determinând maniera în care se va obține un program cât mai adecvat pentru agentul rațional. Acesta poate fi definit ca ansamblul format din măsura performanței, mediul în care se află agentul, senzorii și efectorii agentului. Pentru a realiza un agent de succes, acest mediu de sarcină trebuie definit cât mai complet cu putință. Se consideră ca exemplu un pilot automat de automobil. Acțiunea de a conduce în acest caz este extrem de flexibilă, datorită combinațiilor de situații care pot apărea.

În primul rând, se pune problema măsurării performanței pilotului automat. Printre calitățile pe care ar trebui să le aibă se numără consumul eficient, condusul în siguranță, minimizarea timpului până la destinație, minimizarea sau evitarea completă a încălcării regulilor de circulație. Desigur, unele dintre cerințe pot intra în conflict, iar în acest caz se vor face compromisuri pentru o eficiență maximă.

Următorul aspect îl reprezintă mediul în care se află pilotul. Acesta va trebui să conducă pe o multitudine de tipuri de drumuri, de la drumuri rurale, urbane, până la autostrăzi cu multe benzi, sau poate merge pe șosele cu obstacole asemenea gropilor, traficului intens, animalelor, pietonilor, semnelor de circulație, etc.

Pentru a putea acționa, un agent ar trebui să aibă o serie de senzori care să-i permită interacțiunea cât mai eficientă cu mediul. În cazul pilotului automat, printre aceștia s-ar număra una sau mai multe camere video, pentru a putea observa drumul, senzori de distanță pentru a aprecia distanța față de celelalte automobile, de teren pentru a evita eventualele obstacole, etc.

Efectorii, ca în cazul celor disponibili unui pilot uman, sunt controlul accelerației, al direcției și al frânei. De asemenea, ar fi nevoie de o modalitate pentru ca pilotul automat să comunice cu pasagerul, și eventual cu orice alt pilot automat.

Mediile de sarcină care pot fi definite în inteligența artificială sunt foarte numeroase. Cu toate acestea, se pot defini o serie de cazuri pentru a caracteriza mediile de sarcină. Aceste cazuri vor determina în mare măsură designul cel mai potrivit pentru un agent. Se va face în continuare o paralelă între diferite tipuri de medii:

Medii complet vizibile sau medii partial vizibile – dacă senzorii unui agent îi vor oferi acestuia posibilitatea de a percepe starea completă a mediului în orice moment de timp, atunci mediul este complet vizibil. Un mediu de sarcină este efectiv complet vizibil dacă senzorii detectează toate aspectele care contează pentru alegerea acțiunii. Acesta este de preferat pentru agent, întrucât agentul nu va fi nevoit să rețină în memorie o anumită stare pentru urmări mediul. Pe de altă parte, un mediu poate deveni partial observabil dacă agentul are senzori ce nu oferă percepții corecte sau complete. Dacă agentul nu are senzori deloc, mediul va deveni imposibil de observat.

Medii cu agent singular sau medii multi-agent – distincția dintre aceste două medii este evidentă. Spre exemplu, un agent care rezolvă o integramă fără ajutor se va situa într-un mediu cu agent singular, pe când un agent care joacă șah se va afla într-un mediu multi-agent. Construirea agenților în mediile multi-agent diferă de cea în cazul mediilor cu agent singular. În cazul unui pilot automat, reprezentând un agent ce se află într-un mediu multi-agent, evitarea coliziunilor va mări performanța tuturor agenților prezenți în mediu, acest mediu putând fi definit ca un mediu multi-agent partial cooperant. Mediile multi-agent pot fi și partial competitive, deoarece, luând cazul pilotului automat, un agent poate ocupa un singur loc de parcare. Astfel, comunicarea în mediile multi-agent poate fi interpretată ca un comportament rational. În unele medii multi-agent competitive, un comportament aleator poate fi considerat rational, întrucât va elimina piedicile puse de prezicerea acțiunilor.

Medii deterministe sau medii stocastice – dacă următoarea stare ce urmează a fi explorată este complet determinată de starea curentă și de acțiunea executată de către agent, atunci mediul se numește determinist, altfel, acesta se numește mediu stocastic. În principiu, un agent nu va avea probleme în ceea ce privește nesiguranța dacă mediul în care se află este complet vizibil și determinist. Pe de altă parte, dacă mediul este parțial observabil, atunci acesta poate fi considerat stocastic. Situațiile reale sunt atât de complexe, încât este imposibil să se contorizeze toate aspectele neobservate. Din punct de vedere practic, ele trebuie să fie tratate ca medii stocastice. În cazul mediului pilotului automat, mediul este cu siguranță stocastic, întrucât pilotul nu poate prezice cu exactitate comportamentul celorlalți piloti (mediu multi-agent),cât și faptul că oricând poate interveni o defecțiune. În schimb, mediul agentului-aspirator așa cum a fost descris anterior este un mediu determinist, dar unele modificări precum apariția la întâmplare a mizeriei în oricare pătrat poate transforma mediul într-unul stocastic. Un mediu este nesigur dacă acesta nu este nici complet vizibil, nici determinist. Diferența dintre un mediu stocastic și un mediu nedeterminist este dată de faptul că, în cazul mediilor stocastice, incertitudinea acțiunilor este măsurată folosind probabilități, pe când în mediile nedeterministe, acțiunile sunt caracterizate de consecințele lor posibile, dar nu se ține cont de probabilități.

Medii episodice sau medii secvențiale – într-un mediu de sarcină episodic, experiența agentului este împărțită în episoade. În fiecare episod, acesta înregistrează o percepție și efectuează o singură acțiune. Este foarte important de știut că episodul următor nu va depinde de acțiunile făcute în episoadele anterioare. De exemplu, un agent care este conceput să descopere elementele nepotrivite pe o linie de producție va decide acțiunea asupra elementului care este inspectat fără să țină cont de acțiunile precedente. Mai mult de atât, acțiunea executată asupra unui element din linia de producție nu determină dacă următorul element este defect sau nu. În mediile de sarcină secvențiale, decizia curentă ar putea afecta toate deciziile viitoare. În cazul jocului de șah, deciziile luate pe termen scurt pot avea consecințe pe termen lung. În consecință, mediile episodice sunt mai simple decât cele secvențiale, deoarece agentul nu trebuie să anticipeze acțiuni în viitor.

Medii statice sau medii dinamice – dacă mediul se schimbă în timp ce agentul decide asupra acțiunii pe care o va face, atunci mediul este unul dinamic pentru agent, altfel, este static. Mediile statice sunt mai ușor de utilizat, întrucât agentul nu trebuie să observe mediul sau să țină cont de timp când decide asupra unei acțiuni. Mediile dinamice, pe de altă parte, vor întreba agentul ce acțiune a ales; dacă acesta nu a ales nici o acțiune, se presupune că a decis să nu facă nimic la acel moment. Dacă mediul însuși nu se schimbă odată cu trecerea timpului, dar performanța agentului se schimbă, mediul poate fi numit semi-dinamic.

Medii discrete sau medii continue – această diferență se aplică stării mediului, modului în care timpul este gestionat și ansamblului de percepții și acțiuni ale agentului. Pentru a lămuri asupra acestei diferențe, se pun în discuție cele două medii de sarcină: jocul de șah și pilotul automat. Mediul jocului de șah are un număr finit de stări distincte (excluzând jocurile cu ceas). Percepțiile și acțiunile agentului constituie, de asemenea, un set de tip discret. Pilotul automat, în schimb, reprezintă o problemă în care stările și timpul sunt vaori de tip continuu.

Medii cunoscute sau medii necunoscute – în mediile cunsocute, consecințele (sau probabilitățile consecințelor pentru mediile stocastice) sunt date pentru toate acțiunile posibile. Evident, dacă mediul este nescunoscut, agentul va fi nevoit să îl descopere pentru a putea lua deciziile bune. Este important de precizat faptul că distincția dintre mediile cunoscute sau necunoscute și mediile complet vizibile sau partial vizibile nu înseamnă același lucru. Spre exemplu, într-un joc de cărți se pot cunoaște regulile, dar cărțile să fie ascunse la un moment dat. Mediul este, în acest caz, cunoscut, dar parțial vizibil. Un alt exemplu îl reprezintă un joc pe computer, unde monitorul poate arăta starea completă a jocului, dar nu se cunoaște funcționalitatea butoanelor, reprezentând o situație unde mediul este necunoscut, dar complet vizibil.

2.4 Tipuri de agenți inteligenți

Principala provocare pentru inteligența artificială este să creeze programe de dimensiuni mici care, în limitele existente, să producă un comportament rational în detrimentul tabelării agenților. Se definesc patru tipuri de programe agent care înglobează principiile care stau la baza majorității sistemelor inteligente.

2.4.1 Agentul reflex simplu

Cel mai simplu tip de agent este agentul reflex simplu. Acest tip de agent selectează acțiunile în baza percepției curente, neținând cont de percepțiile anterioare. De exemplu, agentul-aspirator a cărui funcție este tabelată în Tabelul 2.1 este un agent reflex simplu, deoarece decizia ia în calcul doar locația curentă și dacă acolo există sau nu mizerie.

Se observă faptul că programul-agent este foarte mic, comparative cu tabelarea funcției-agent. Evident, reducerea atât de mare a dimensiunilor are loc datorită ignorării istoricului percepțiilor, care scade numărul posibilităților de la la doar 4. O altă cauză a reducerii dimensiunilor este aceea că dacă locația curentă este murdară, acțiunea nu depinde de locație.

Comportamentul agentului reflex simplu poate apărea și în medii mai complexe. Dacă un șofer s-ar afla la bordul unui efineile automat și un alt efineile din fața acestuia ar frâna, semnalând această acțiune prin becuri, răspunsul normal al șoferului ar fi să observe acest lucru și să apese frâna. Cu alte cuvinte, e nevoie de prelucrarea datelor vizuale pentru a efine condiția “Automobilul din față frânează”. Asta va declanșa o conexiune în programul agentului cu acțiunea frânează. O astfel de conexiune se numește regulă de tip condiție-acțiune scrisă într-un program-agent astfel:

dacă mașină-din-față-frânează atunci acționează-frâna

Astfel de conexiuni apar și la oameni, unele având legătură cu răspunsurile dobândite prin învățare (condusul), sau reprezentând reflexe înnăscute (clipitul când ceva se apropie de ochi).

Fig 2.5 Schema unui agent reflex simplu

În figura 2.5 este prezentat un agent reflex simplu într-o formă schematică, arătând cum regulile de tip condiție-acțiune îi permit agentului să facă legătura între percepții și acțiuni. Programul-agent prezentat în figura 2.6 este de asemenea foarte simplu. Funcția INTERPRETEAZĂ-INTRARE va genera o descriere abstractă a stării curente bazate pe percepție, și REGULĂ-ADECVATĂ va returna prima regulă din setul de reguli care se potrivește cu descrierea stării curente.

Cu toate că agenții reflecși simpli au avantajul că sunt simpli, aceștia se dovedesc a fi destul de limitați ca inteligență. Agentul din figura 2.6 va funcționa doar dacă poate lua o decizie corectă pe baza percepției curente, mediul fiind obligatoriu complet vizibil.

2.4.2 Agentul reflex bazat pe model

Cea mai bună modalitate de a rezolva problema mediilor partial vizibile este ca agentul ia în calcul partea mediului pe care nu o poate vedea în momentul curent. Asta ar însemna ca agentul să memoreze o stare înternă care depinde de istoricul percepțiilor și care reflectă cel puțin o parte din aspectele neobservate ale stării curente.

Actualizarea informațiilor stării interne pe măsură ce timpul trece va necesita două tipuri de cunoaștere spre a fi implementate în programul-agent. În primul rând, sunt necesare informații despre cum evoluează mediul în mod independent de agent. Spre exemplu, un automobil ce dorește să depășească va fi mai aproape decât a fost cu un moment înainte. În al doilea rând, e nevoie să se cunoască modul în care acțiunile agentului vor afecta mediul. Această cunoaștere a modului în care “funcționează” mediul, se numește un model al mediului. Agentul care utilizează un astfel de model se numește agent bazat pe model.

Fig. 2.7 Agentul reflex bazat pe model

Figura 2.7 reprezintă schema unui agent reflex bazat pe model cu stare internă și arată modul în care percepția curentă este combinată cu starea internă precedentă pentru a genera descrierea stării curente, bazându-se pe modelul mediului din punctul de vedere al agentului. Programul-agent este prezentat în figura 2.8. Partea importantă a programului o reprezintă funcția ACTUALIZEAZĂ-STARE, care este responsabilă pentru definirea noii stări interne. Detaliile despre cum modelele și stările sunt reprezentate variază în funcție de tipul de mediu și de tehnologia folosită în construirea agentului.

Indiferent de tipul de reprezentare folosit, este rareori posibil ca un agent să determine starea curentă a unui mediu parțial observabil în mod exact. Astfel, agentul nu va mai cunoaște exact cum este mediul în momentul actual, ci va trebui să ghicească în cel mai bun mod. De exemplu, un pilot automat care are în fața căruia a oprit un automobil mare (un tir spre exemplu), poate doar să presupună ce a cauzat oprirea automobilului din fată. Incertitudinea stării curente poate fi imposibil de evitat, dar agentul va trebui să ia totuși o decizie.

2.4.3 Agentul bazat pe obiective

A avea detalii despre starea curentă a mediului nu este mereu suficient pentru a lua o decizie. De exemplu, la o intersecție, un pilot automat poate vira la stânga, la dreapta, sau poate merge în față. Decizia corectă, în acest caz, depinde de locația unde agentul trebuie să ajungă. Altfel spus, agentul are nevoie de anumite informații despre obiectivul său, informații care descriu situațiile convenabile (de exemplu, faptul că a ajuns la o destinație). Programul-agent poate combina aceste informații cu modelul (asemenea aceluia folosit în cazul agentului-reflex bazat pe model) pentru a alege anumite acțiuni și a-și atinge obiectivul.

Fig. 2.9 Agentul bazat pe obiective

Uneori alegerea unei acțiuni în baza obiectivelor este simplă, ca atunci când satisfacerea obiectivului rezultă din efectuarea unei singure acțiuni. Alteori, însă, acest lucru este mai complicat. De exemplu, atunci când pilotul automat consideră secvențe întregi de acțiuni pentru a găsi o modalitate să îndeplinească obiectivul. În acest caz, căutarea și planificarea sunt ramuri ale inteligenței artificiale care se ocupă cu găsirea secvențelor de acțiuni potrivite pentru a îndeplini obiectivul agentului.

Luarea deciziilor în acest fel este diferită de regulile condiție-acțiune din cazul agenților reflecși prin faptul că ia în calcul viitorul. În designul agenților reflecși, acest lucru nu este reprezentat explicit, deoarece regulile încorporate vor conecta percepțiile cu acțiunile în mod direct. Un agent reflex va frâna dacă vede becurile de frână aprinse. Un agent bazat pe obiective ar putea raționa faptul că, dacă automobilul din față are becurile de frână aprinse, va încetini. Astfel, tinând cont de modul în care evoluează mediul, singura acțiune care ar duce la îndeplinirea obiectivului de a nu lovi alte automobile, ar fi să frâneze.

Cu toate că agentul bazat pe obiective pare mai puțin eficient, acesta este mai flexibil întrucât cunoștințele pe care se bazează luarea deciziilor sunt reprezentate explicit și pot fi modificate. Dacă în mediul agentului ar ploua la un anumit moment, agentul ar putea actualiza cunoștinele sale despre cum să acționeze în mod eficient frânele în acel mediu. Acest lucru ar schimba în mod automat și restul comportamentelor relevante din punct de vedere al vremii pentru a se potrivi noilor condiții. În cazul agentului-reflex, ar trebui rescrise toate regulile de tip condiție-acțiune. Astfel, comportamentul agentului bazat pe obiective poate fi ușor modificat, prin specificarea unu alt obiectiv. Regulile agentului reflex funcționează doar pentru un singur obiectiv, ele trebuind modificate complet pentru un obiectiv nou.

2.4.4 Agentul bazat pe utilitate

Pentru un agent, a avea doar obiective nu este de ajuns pentru a genera un comportament de calitate în majoritatea mediilor. De exemplu, multe secvențe de acțiuni vor duce pilotul automat la destinație, astfel îndeplinind obiectivul; cu toate acestea, unele dintre ele sunt mai rapide, oferă mai multă siguranță sau sunt mai ieftine. Obiectivele oferă doar o distincție rudimentară între situațiile fericite și nefericite. O măsură a performanței mai generală ar permite compararea mai multor stări ale mediului în funcție de utilitatea agentului în acele stări.

Se cunoaște faptul că o măsură a performanței va atribui un scor pentru orice secvență de stări ale mediului dată, pentru a putea distinge ușpr între modalitățile mai mult sau mai puțin convenabile de a ajunge la o destinație în cazul pilotului automat. Funcția de utilitate a unui agent reprezintă o internalizare a măsurii performanței. Dacă funcția de utilitate internă și măsura performanței externă se află în concordanță, atunci un agent care alege să maximizeze utilitatea sa, va fi rațional, conform măsurii performanței sale externe.

Asemenea unui agent bazat pe obiective, agentul bazat pe utilitate are multe avantaje în ceea ce privește flexibilitatea și învățarea. Mai mult de atât, în unele cazuri, obiectivele pot fi inadecvate, dar un agent bazat pe utilitate tot va lua o decizie în mod rațional. În primul rând, în cazul obiectivelor care intră în conflict, dintre care doar unele pot fi indeplinite (viteza și siguranța în cazul pilotului automat), funcția de utilitate va specifica alegerea potrivită. În al doilea rând, dacă există o serie de obiective pe care agentul dorește să le îndeplinească, niciunul dintre acestea neputând fi atins cu certitudine, utilitatea va pune la dispoziție o modalitate prin care șansa de reușită să fie pusă în balanță cu importanța obiectivelor.

Observarea parțială a mediului și nesiguranța sunt omniprezente în lumea reală, astfel încât luarea de decizii se face cu incertitudine. Un agent rațional bazat pe utilitate va alege acțiunea care maximizează utilitatea rezultatului așteptat. În general, orice agent rațional ar trebui să se comporte ca și cum ar deține o funcție de utilitate a cărei valoare returnată să încerce s-o maximizeze.

Fig. 2.10 Agentul bazat pe utilitate

În figura 2.10 este prezentată schematic structura unui agent bazat pe utilitate. Acesta folosește un model al mediului, alături de o funcție de utilitate care determină stările sale preferate dintre stările mediului. Apoi se va alege acțiunea care conduce la cea mai bună utilitate așteptată, această utilitate fiind calculată făcând media tuturor stărilor rezultat, ponderată de probabilitatea ca o anumită acțiune să ducă la un rezultat.

Pentru ca un agent bazat pe utilitate să fie eficient, el trebuie să modeleze și să urmărească mediul în care se află, sarcini care au necesitat un volum mare de cercetări asupra percepției, reprezentării, raționării și învățării. Alegerea modului de acțiune care să maximizeze utilitatea agentului este de asemenea o sarcină dificilă, fiind necesari algoritmi ingenoși pentru a îndeplini acest lucru. Chiar și cu acești algoritmi, raționalitatea perfectă este imposibil de atins în practică, datorită complexității de calcul pe care o impune.

2.4.5 Agentul care învață

Până acum au fost explicate diverse programe-agent, având la dispoziție numeroase metode pentru a selecta o acțiune. Mai există o categorie de programe-agent, programele care „prind viață”. În lucrarea sa faimoasă, Turing (1950) ia în considerare ideea de a programa efectiv mașinile sale inteligente manual. Presupunând ce volum de muncă ar necesita acest lucru, acesta afirmă: “O metodă mai expeditivă este de dorit ”. Metoda propusă de el este să construiască mașini capabile să învețe, iar apoi să le învețe el însuși. În multe domenii ale inteligenței artificiale, aceasta este metoda preferată pentru a crea sisteme de ultimă generație. Învățarea are avantajul de a permite agentului să opereze într-un mediu inițial necunoscut și să devină mai competent decât îi permiteau cunoștințele sale inițiale.

Fig. 2.11 Agentul care învață

Un agent care învață poate fi împărțit în patru componente conceptuale, așa cum este ilustrat schematic în figura 2.11. Cea mai importanță distincție se face între elementul de învățare, care este responsabil să facă îmbunătățiri, și elementul de performanță, care este responsabil să selecteze acțiuni externe. Elementul de performanță reprezintă agentul, așa cum a fost prezentat în exemplele anterioare: primește percepții și decide ce acțiuni să facă. Elementul de învățare folosește feedback de la secțiunea critic în legătură cu modul în care se comportă agentul și determină cum va fi modificat elementul de performanță pentru a se comporta mai bine pe viitor.

Designul elementului de învățare depinde foarte mult de designul elementului de performanță. În încercarea de a construi un agent care să învețe să facă un anumit lucru, prima întrebare nu este cum va învăța să îl facă, ci mai degrabă de ce tip de element de performanță va avea nevoie pentru a face acel lucru, îndată ce a învățat cum. Având la dispoziție un anumit design al agentului, pot fi construite mecanisme de învățare pentru a îmbunătăți fiecare parte a agentului.

Criticul îi va transmite elementului de învățare cât de bine se descurcă agentul respectând un standard de performanță fixat. Criticul este necesar, deoarece percepțiile singure nu oferă nici o indicație în ceea ce privește succesul agentului. De exemplu, un program de șah ar putea primi o percepție conform căreia a dat șah mat, dar are nevoie de un standard de performanță pentru a ști că acest lucru este un lucru bun; percepția în sine nu oferă această informație. Este important ca standardul de performanță să fie fixat. Conceptual, acesta poate fi interpretat ca fiind în exteriorul agentului întru totul, deoarece agentul nu trebuie să-l modifice pentru a se potrivi prorpiului comportament.

Ultima componentă a agentului este generatorul de probleme. Acesta este responsabil cu sugerarea acțiunilor care vor conduce la experiențe noi și informative. Dacă elementul de performanță ar acționa după bunul plac, acesta ar face în continuu acțiunile cele mai bune în baza a ceea ce știe. Dar agentul trebuie să exploreze într-o anumită măsură și să facă unele acțiuni aflate sub optim pe termen scurt, pentru a descoperi acțiuni mai bune pe termen lung. Sarcina generatorului de probleme este să sugereze aceste acțiuni de explorare.

Pentru a concretiza designul general al agentului care învață, se consideră exemplul pilotului automat. Elementul de performanță va consta în orice colecție de cunoștințe și proceduri pe care le folosește pilotul în acțiunile de conducere. Pilotul va condce folosind acest element de performanță. Criticul observă lumea și transmite informații către elementul de învățare. De exemplu, pilotul automat virează brusc de-a lungul a trei benzi de circulație,iar criticul observă limbajul nepotrivit al celorlalți piloți. Din această experiență, elementul de învățare este capabil să formuleze o regulă care spune că acțiunea pilotului a fost una greșită. Astfel, elementul de performanță este modificat prin instalarea noii reguli. Generatorul de probleme poate identifica anumite zone ale comportamentului care necesită îmbunătățiri și poate sugera experimente, asemenea frânării pe diferite suprafețe de carosabil în diferite condiții.

Elementul de învățare poate face modificări oricăror componente de învățare care apar în diagramele celorlalți agenți (Fig. 2.5, 2.7, 2.9, 2.10). Cele mai simple cazuri implică învățarea direct din secvența percepțiilor. Observarea perechilor de stări succesive ale mediului poate permite agentului să învețe cum evoluează mediul, iar observarea rezultatelor acțiunilor sale îi poate permite agentului să învețe ce rezultat au acțiunile sale. De exemplu, dacă pilotul automat aplică o anumită presiune pe frână în timp ce conduce pe un drum umed, va afla curând cât de mult a frânat. Evident, aceste două sarcini de învățare sunt mult mai dificile dacă mediul este parțial observabil.

Pe scurt, agenții au o varietate de componente, acele componente putând fi reprezentate în multe feluri în cadrul programului-agent, generând astfel o multitudine de metode de învățare. Există, totuși, un punct comun. Învățarea la agenții inteligenți poate fi rezumată ca fiind un proces de modificare a fiecărei componente a agentului pentru a aduce componentele într-un acord mai strâns cu feedback-ul disponibil, îmbunătățind astfel performanța generală a agentului.

CAPITOLUL 3

[1],[2],[12]

REZOLVAREA PROBLEMELOR

FOLOSIND CĂUTĂRI

În cel mai simplu caz în care un agent trebuie să ia o decizie, acesta are la dispoziție un model bazat pe stări ale mediului, fără incertitudini și având obiective de îndeplinit. Agentul poate determina modul în care pot fi îndeplinite obiectivele, căutând în spațiul stărilor mediului o cale de a ajunge din starea curentă, într-o stare obiectiv. Se poate găsi o secvență de acțiuni care vor atinge scopul propus chiar înainte ca agentul să facă vreo acțiune în mediu.

Această problemă poate fi abstractizată la o problemă matematică de găsire a unui drum, pornind de la o stare inițială, către o stare obiectiv. Un aspect foarte important îl reprezintă faptul că aceste stări pot fi reprezentate ca noduri ale unui graf, noduri ce conțin informații despre fiecare stare. Reprezentarea spațiului stărilor sub formă de graf pune la dispoziție o serie de metode de căutare prin care soluția poate fi găsită, metode ce vor fi explicate mai târziu.

În capitolul precedent s-a pus în discuție funcționarea agenților inteligenți. Cei mai simpli agenți sunt agenții reflecși, ale căror acțiuni se bazează pe o legătură directă între stări și acțiuni disponibile. Acest tip de agenți nu pot funcționa bine în mediile în care aceste legături sunt prea numeroase pentru a putea fi memorate și ar necesita foarte mult timp pentru a fi învățate. Agenții bazați pe obiective, în schimb, iau în considerare acțiunile viitoare și oportunitățile oferite de consecințele lor.

3.1 Agenți care rezolvă probleme

Urmează a fi definit un tip de agent bazat pe obiective numit agent care rezolvă probleme. Agenții care rezolvă probleme folosesc reprezentări atomice, care presupun faptul că stările mediului sunt considerate ca întregi, fără o structură internă vizibilă pentru algoritmii care rezolvă probleme. Agenții bazati pe obiective care folosesc reprezentări mai avansate, precum cele factorizate sau structurate, sunt supranumiți agenți de planificare.

Agenții inteligenți urmăresc să-și maximizeze măsura peformanței. Îndeplinirea acestui lucru este întrucâtva simplificată dacă agentul poate adopta un obiectiv și urmări îndeplinirea acestuia. Se consideră un agent în orașul Arad, România, bucurându-se de o vacanță. Măsura performanței agentului conține mulți factori: acesta dorește să viziteze obiectivele principale, să învețe limba, să facă poze, să evite cheltuirea excesivă, să evite alcoolul, etc. Problema deciziei este una complexă, implicând multe compromisuri și citirea atentă a ghidurilor.Presupunând că agentul are la dispoziție un bilet nerambursabil pentru ziua următoare de la București către țara din care a venit, este evident că acesta va adopta obiectivul de a ajunge la București. Seriile de acțiuni care nu îl vor duce la timp în București vor fi respinse fără alte considerații, simplificând astfel cu mult problema luării deciziilor. Scopurile ajută la organizarea comportamentului prin limitarea obiectivelor pe care agentul încearcă să le îndeplinească, astfel micșorând numărul acțiunilor pe care le ia în considerare. Formularea scopului, bazată pe informațiile curente și pe măsura performanței agentului, reprezintă primul pas în rezolvarea problemelor.

Scopul este definit ca fiind un set de stări ale mediului, acele stări în care scopul este îndeplinit. Sarcina agentului este aceea de a găsi o modalitate să acționeze, în prezent și în viitor, astfel încât să atingă o stare satisface scopul. Înainte de asta, trebuie să decidă ce fel de acțiuni și stări ar trebui luate în considerare. Dacă agentul ar lua în calcul acțiuni precum “mergi în față un centimetru” sau “virează un grad către stânga”, atunci acesta nu ar atinge obiectivul de a ajunge la București niciodată, deoarece la acel nivel de detaliu, incertitudinea mediului ar fi prea ridicată, și pașii soluției ar fi prea numeroși.

Formularea problemei reprezintă procesul prin care se decide ce acțiuni și stări vor fi luate în considerare, pentru un scop dat. Pentru exemplul prezentat anterior, acțiunile agentului vor reprezenta trecerea de la un oraș mare către altul. Prin urmare, fiecare stare va corespunde unui anumit oraș.

Fig. 3.1 Hartă simplificată a drumurilor unei părți a României

Scopul agentului din exemplu este de a conduce până la București. Acesta ia în calcul următoarea locație în care să conducă, pornind din Arad. Există trei drumuri care pleacă din Arad : către Sibiu, Timișoara și Zerind. Niciunul dintre acestea nu va atinge scopul, iar agentul nu va ști ce drum să urmeze, doar dacă nu este deja obișnuit cu geografia României. Cu alte cuvinte, agentul nu va ști care acțiune este cea mai bună, deoarece nu are informații despre starea care rezultă din luarea fiecărei acțiuni. Dacă mediul este necunoscut, atunci agentul este nevoit să facă o acțiune în mod aleator.

Presupunând, totuși, că există o hartă a României, aceasta îi va furniza agentului informații despre stările în care poate ajunge și despre acțiunile pe care le poate face. Agentul poate folosi aceste informații pentru a considera etapele următoare ale unei călătorii ipotetice prin cele trei orașe, încercând să găsească o călătorie care duce eventual la București. Odată ce s-a găsit un drum pe hartă de la Arad la București, agentul își poate îndeplini scopul prin executarea acțiunilor de codus care corespund etapelor călătoriei. În general, un agent, având la dispoziție doar câteva opțiuni imediate ale căror valori sunt nescunoscute, poate decide ce va face prin examinarea mai întâi a acțiunilor viitoare ce duc la stări cu valori cunoscute.

Pentru moment, se presupune că mediul este observabil, astfel încât agentul va avea mereu informații despre starea curentă. De asemenea, se consideră că fiecare oraș de pe hartă va avea un semn care indică prezența sa piloților care ajung în oraș. Mediul este discret, întrucât în orice stare dată, există doar un număr finit de acțiuni pe care agentul le poate face. Acest lucru este evident pentru agentul din România, întrucât orice oraș este conectat la un număr mic de alte orașe. Se presupune, de asemenea, că mediul este cunoscut, astfel încât agentul cunoaște stările ce rezultă din fiecare acțiune (o hartă precisă este suficientă pnetur a îndeplini această condiție în problemele de navigație). În final, mediul este considerat a fi determinist, ceea ce înseamnă că fiecare acțiune va avea exact un singur rezultat. În condiții ideale (este și cazul agentului din România), dacă agentul alege să conducă din Arad în Sibiu, va ajunge obligatoriu în Sibiu. Cu toate acestea, condițiile nu sunt întotdeauna ideale.

Se poate deduce că soluția oricărei probleme poate fi reprezentată de o secvență fixată de acțiuni. Dar, în general, poate fi o strategie de divizare ce sugerează diferite acțiuni în viitor, în funcție de percepțiile primite. De exemplu, agentul poate decide să conducă de la Arad la Sibiu, și apoi la Rîmnicu Vîlcea, dar, de asemenea, ar trebui să aibă un plan în eventualitatea în care ajunge accidental la Zerind în loc de Sibiu. Din fericire, dacă agentul cunoaște starea inițială și mediul este cunoscut și determinist, acesta va ști exact unde se află după efectuarea primei acțiuni și percepția primită. Din moment ce decât o singură percepție este posibilă după prima acțiune, soluția poate specifica o singură acțiune următoare, și așa mai departe.

Procesul de găsire a unei secvențe de acțiuni ce duc la îndeplinirea scopului, se numește căutare. Un algoritm de căutare primește, ca intrare, o problemă, și returnează o soluție sub forma unei secvențe de acțiuni. Odată ce o soluție este găsită, acțiunile pe care le recomandă pot fi efectuate. Această etapă se numește etapa de execuție.

În figura 3.2 este prezentat programul unui agent simplu care rezolvă probleme. Acesta va formula inițial un scop și o problemă de rezolvat, va căuta o secvență de acțiuni care ar putea rezolva acea problemă și va executa acele acțiuni, pe rând. Când va încheia acest proces, va formula un alt scop si algoritmul se va relua.

Se observă faptul că, în timp ce agentul va executa secvența de acțiuni oferită de soluție, acesta va ignora percepțiile atunci când alege o acțiune, deoarece știe dinainte care vor fi acestea. Faptul că agentul își desfășoară activitatea fără să observe mediul, necesită destulă siguranță. Acest lucru este denumit de teoreticienii controlului sistem în buclă deschisă, deoarece ignorarea percepțiilor încalcă bucla dintre agent și mediu.

3.2 Definirea problemelor

Alături de exemplul agentului ce călătorește în România, se va considera și problema canibalilor și misionarilor,problemă în care trei canibali și trei misionari trebuie să traverseze un râu în siguranță, pentru a putea ilustra mai clar pașii necesari în definirea unei probleme. Problema canibalilor și misionarilor va fi explicată mai pe larg puțin mai târziu.

O problemă poate fi definită formal prin intermediul a cinci componente:

Starea inițială din care pornește agentul. Pentru agentul care călătorește în România, folosit ca exemplu mai sus, aceasta poate fi descrisă ca Oraș(Arad). În cazul problemei canibalilor și misionarilor, starea inițială poate fi definită ca un nod având următoarele caracteristici: Start (3, 3, 0, 0, mal). Primele două valori reprezintă numărul de canibali și misionari de pe malul stâng, următoarele două valori reprezintă, evident, numărul canibalilor și misionarilor de pe malul drept. Variabila “mal” va sugera malul curent (pe care se află barca).

O descriere a acțiunilor posibile pe care agentul le poate face dintr-o anumită stare s. ACȚIUNI(s) returnează setul de acțiuni care poate fi executat din starea s. Se spune că aceste acțiuni sunt aplicabile în s. De exemplu, din starea Oraș(Arad), acțiunile aplicabile sunt {Mergi(Sibiu), Mergi(Timișoara), Mergi(Zerind)}. Pentru problema canibalilor și misionarilor, acțiunile posibile sunt Traversează (C), Traversează (M), Traversează (CC), Traversează (MM), Traversează (CM). Aceste acțiuni sugerează faptul că, la un moment dat, pot traversa râul fie un canibal, un misionar, doi canibali, doi misionari sau un canibal și un misionar. Din aceste acțiuni se deduce automat faptul că barca nu poate călători singură și că nu pot fi mai mult de două persoane în barcă în același timp.

O descriere a ceea ce face fiecare acțiune; denumirea acestei activități este model de tranziție. Acest model de tranziție este specificat printr-o funcție REZULTAT(s,a), ce returnează o stare ca urmare a executării acțiunii a în starea s. Se definește, de asemenea, noțiunea de succesor, care se referă la orice stare ce poate fi atinsă dintr-o stare dată, executând o singură acțiune.De exemplu:

REZULTAT(Oraș(Arad),Mergi(Zerind))=Oraș(Zerind).

Considerând starea inițială și acțiunea în care traversează râul un canibal, funcția rezultat va arăta în felul următor:

REZULTAT(Start(3, 3, 0, 0, mal_stâng), Traversează(C))=Nod(2, 3, 1, 0, mal_drept).

Se observă că în partea stângă, numărul canibalilor a scăzut cu unul, în timp ce în partea dreaptă, a crescut cu unul. De asemenea, malul curent s-a schimbat. Este foarte important ca la fiecare pas să se respecte condiția problemei (în cazul problemei canibalilor și misionarilor, condiția este ca numărul misionarilor să nu fie mai mic decât cel al canibalilor la un anumit moment, indiferent de mal).

Împreună, starea inițială, acțiunile și modelul de tranziție, definesc în mod implicit spațiul stărilor problemei. Acest spațiu al stărilor formează un graf în care nodurile reprezintă stări și legăturile dintre noduri reprezintă acțiuni (Harta României prezentată în figura 3.1 poate fi văzută ca un graf al spațiului stărilor, dacă fiecare legătură între noduri reprezintă acțiunea de a merge dintr-un oraș în altul, în ambele sensuri). Un traseu în spațiul stărilor reprezintă o secvență de stări conectată printr-o secvență de acțiuni.

Testarea obiectivului, care determină dacă o anumită stare este starea-obiectiv. Uneori, se dă un set explicit de stări-obiectiv posibile, caz în care testul verifică dacă starea curentă se află printre acestea. Scopul agentului din România este dat de setul cu o singură stare {Oraș(București)}.Pentru problema misionarilor și canibalilor, starea-obiectiv este reprezentată de nodul Nod(0, 0, 3, 3, mal_drept). Acest nod sugerează faptul că toți canibalii și misionarii au trecut pe malul drept. În unele cazuri, scopul este specificat printr-o proprietate abstractă, în locul unui set de stări. De exemplu, în jocul de șah, scopul este de a atinge o stare numită “șah mat”, stare ce presupune ca regele adversarului să fie în șah și să nu poată scăpa.

O funcție de cost a traseului ce atribuie un cost numeric fiecărui traseu. Agentul care rezolvă probleme va alege o funcție a costului ce reflectă propria măsură a performanței. Pentru agentul care dorește să ajungă la București, timpul este foarte important, astfel încât costul unui traseu poate reprezenta timpul necesar traversării sale, sau lungimea sa în kilometri. Pentru problema canibalilor și misionarilor, costul poate fi reprezentat de numărul de traversări ale râului necesare pentru a ajunge în starea finală.

Aceste cinci elemente definesc o problemă și pot fi unite într-o singură structură de date ce reprezintă intrare pentru un algormit de rezolvare a problemelor. Soluția reprezintă secvența de acțiuni care duce de la starea inițială la starea obiectiv. Calitatea soluției este măsurată de funcția de cost a traseului, iar o soluție optimă va avea cel mai mic cost.

3.3 Căutarea soluțiilor

Odată cu formularea problemelor, următoarea etapă o reprezintă rezolvarea lor. Știind faptul că o soluție este, de fapt, o secvență de acțiuni, un algoritm de căutare va funcționa considerând diverse secvențe de acțiuni posibile. Problema poate fi transformată fie într-un graf, fie într-un arbore, considerând starea inițială ca fiind rădăcina arborelui, nodurile reprezentând stări din spațiul stărilor și arcele reprezentând acțiuni.

După ce a fost transpusă într-un graf, rezolvarea problemei se va face pe baza acestui graf. Pornind de la nodul ce reprezintă starea inițială, primul pas este testarea acestuia pentru a afla dacă reprezintă o stare obiectiv (în mod evident, acest lucru ar fi ilogic, dar testarea nodului de pornire este importantă pentru cazurile menite să păcălească, în care starea inițială și cea obiectiv coincid ). Pasul următor reprezintă luarea în considerare a mai multor acțiuni posibile. Acest lucru se face prin expandarea nodului ce reprezintă starea curentă prin aplicarea acțiunilor corecte asupra acesteia. Se va genera, astfel, un nou set de stări.

Fig. 3.3 Căutarea într-un graf

Pentru agentul turist, expandarea nodului rădăcină Oraș(Arad) va genera trei noduri-copil: Oraș(Sibiu), Oraș(Timișoara) și Oraș(Zerind). Nodul Oraș(Arad) este considerat, în mod automat, nodul-părinte al celor trei noduri generate. Pentru a continua căutarea, trebuie ales un nod-copil pentru a deveni noul nod-părinte (Figura 3.4).

Fig. 3.4 Exemplu de căutare într-un arbore

Esența căutării, în cazul agentului din România, constă în urmărirea unei opțiuni și păstrarea celorlalte pentru cazul în care opțiunea aleasă prima dată nu va conduce la o soluție. Nodurile ce nu au noduri-copil se numesc frunze. Totalitatea nodurilor-frunze ce pot fi expandate la un anumit moment formează frontiera. Expandarea nodurilor din cadrul frontierei continuă până când, fie este găsită o soluție, fie nu mai există alte stări care să fie expandate. Algoritmul general de căutare într-un arbore este prezentat în figura 3.5. Structura algoritmilor de căutare este asemănătoare cu structura acestui algoritm, diferența constând în alegerea următoarei stări ce va fi expandată, acest lucru reprezentând strategia de căutare.

În cadrul algoritmilor prezentați în Figura 3.5 și Figura 3.6, frontiera reprezintă o listă ce va conține nodurile nevizitate ce urmează a fi expandate. Este important de precizat rolul listei nodurilor explorate. Aceasta vine ca o îmbunătățire a algoritmului de căutare într-un arbore (Figura 3.5). În cadrul algoritmului de căutare într-un graf (Figura 3.6), lista nodurilor explorate reprezintă o structură de date ce diferă în funcție de strategia de căutare, și care ajută la eliminarea drumurilor redundante, astfel: ultimele noduri generate care sunt identice cu nodurile generate anterior (cele din frontieră sau din lista nodurilor explorate) nu vor mai fi adăugate la frontieră, în schimb, vor fi eliminate. Un drum redundant reprezintă o cale mai costisitoare de a ajunge la o stare obiectiv. În cadrul drumurilor redundante se pot încadra și drumurile ce conțin bucle (vizitarea unei stări în mod repetat).

3.3.1 Structura unui algoritm de căutare

Algoritmii de căutare necesită o structură de date pentru a înregistra informațiile arborelui de căutare ce se construiește. Această structură va defini, pentru fiecare nod n al arborelui, patru elemente:

n.STARE: starea din spațiul stărilor căreia îi corespunde nodul;

n.PĂRINTE: nodul din arborele de căutare care a generat nodul n;

n.ACȚIUNE: acțiunea care a fost aplicată părintelui pentru a genera nodul n;

n.COST-DRUM: costul, reprezentat în mod tradițional printr-o funcție y(n), pentru drumul de la starea inițială la nodul n, indicat de pointerii părinților.

Având la dispoziție componentele unui nod-părinte, se pot afla foarte ușor componentele unui nod-copil, așa cum se observă în algoritmul din figura 3.7.

Odată cu generarea nodurilor, este necesară o modalitate de stocare a acestora. Nodurile trebuie stocate în frontieră într-o manieră care să permită algoritmului de căutare să aleagă cu ușurintă următorul nod pentru a fi expandat, în funcție de strategia de căutare utilizată. Pentru a stoca nodurile, se folosesc în general trei structuri de date: coada, stiva și coada cu prioritate. Alegerea uneia din cele trei structuri de date se face în funcție de strategia de căutare folosită de algoritm. Operațiile principale sunt inserarea, extragerea sau accesarea unui element. Descrierea acestor structuri de date se va face în cadrul metodelor de căutare în care sunt folosite.

3.3.2 Criterii de performanță

Înainte de a trece la implementarea unui anumit algoritm de căutare, trebuie luate în considerare o serie de criterii de performanță ce vor influența alegerea unui anumit algoritm. Evaluarea unei strategii de căutare se face având în vedere patru caracteristici:

Completitudine – proprietatea algoritmului de a găsi o soluție, în mod garantat, atunci când aceasta există

Complexitate temporală – timpul necesar pentru a găsi o soluție

Complexitate spațială – memoria necesară pentru a putea face căutarea

Optimalitate – proprietatea unui algoritm de a găsi o soluție optimă

Complexitatea spațială și temporală se consideră în funcție de dificultatea problemei date. Dacă graful ce reprezintă spațiul stărilor este dat în mod explicit ca intrare pentru programul de căutare, complexitățile se determină în funcție de dimensiunea grafului. În schimb, în inteligența artificială, graful este reprezentat de obicei implicit de către starea inițială, acțiunile și modelul de tranziție și este de multe ori infinit. Din această cauză, complexitatea se exprimă pe baza a trei elemente:

b – factorul de ramificare, sau numărul maxim de succesori pentru fiecare nod;

d – adâncimea nodului-obiectiv cu cel mai mic cost;

m – adâncimea maximă a spațiului stărilor (poate fi infinită);

Timpul este deseori măsurat în funcție e numărul de noduri generate în timpul căutării, iar spațiul în funcție de numărul maxim de noduri stocate în memorie. Pentru a evalua eficiența unui algoritm de căutare, se poate lua în considerare doar costul căutării, care depinde în principal de complexitatea temporală, dar poate conține și informații despre memoria folosită, sau se poate folosi costul total, care combină costul căutării cu un cost pentru soluția găsită.

3.3.3 Strategii de căutare neinformată

O problemă determină graful și obiectivul, dar nu determină ce cale va fi aleasă din frontieră. Sarcina aceasta revine unei strategii de căutare. O strategie de căutare va specifica ce drumuri vor fi alese din frontieră.

Diferite tipuri de strategii vor fi obținute prin modificarea modului în care selectarea drumurilor din cadrul frontierei este implementată. Aceste strategii de căutare se numesc neinformate (sau căutări oarbe), întrucât nu au informații suplimentare despre stările ce nu apar în definiția problemei.

Activitatea unei strategii de căutare neinformată presupune doar generarea succesorilor și distingerea unei stări-obiectiv de o stare normală. Toate strategiile de căutare se deosebesc prin ordinea în care nodurile sunt expandate.

Există mai multe strategii de căutare neinformată, dar vor fi explicate mai detaliat doar căutarea în lățime și căutarea în adâncime, celelalte strategii reprezentând cazuri particulare ale acestora. Tipuri de strategii de căutare:

căutarea în lățime

căutarea în adâncime

căutarea în adâncime limitată

căutarea de cost uniform

căutarea prin adâncire iterative

căutarea bidirecțională

3.3.3.1 Căutarea în lățime (Breadth-First Search)

Căutarea în lățime reprezintă o strategie simplă prin care nodul rădăcină este expandat primul, apoi toate nodurile-succesor ale acestuia, apoi succesorii acestor noduri și așa mai departe. Toate nodurile aflate la o anumită adâncime vor fi expandate în arborele de căutare, înainte care orice nod de la următorul nivel să fie expandat.

Acest tip de căutare reprezintă o instanță a algoritmului general de căutare într-un graf, prezentat în figura 3.6, unde nodul nevizitat cu cea mai mică adâncime este ales pentru a fi expandat. Pentru a realiza acest lucru, algoritmul de căutare va utiliza o structură de date numită stivă (FIFO queue), pentru frontieră. Astfel, nodurile noi (care au întotdeauna o adâncime mai mare decât părinții lor) vor fi adăugate la sfârșit, iar nodurile vechi, având o adâncime mai mică, vor fi expandate primele.

Figura 3.8 prezintă algoritmul în pseudocod pentru căutarea în lățime. Se observă faptul că testarea obiectivului în cazul fiecărui nod se face atunci când nodul este generat, și nu când acesta este ales pentru a fi expandat. De asemenea, algoritmul va elimina orice drum nou către un nod care aparține deja frontierei sau listei nodurilor vizitate. Astfel, căutarea în lățime va furniza mereu cea mai scurtă cale către fiecare nod din frontieră. Urmează analiza acestei strategii de căutare în funcție de cele patru criterii de performanță.

În ceea ce privește completitudinea, căutarea în lățime este completă, cu condiția ca factorul de ramificare b să fie finit. Căutarea în lățime va găsi eventual nodul obiectiv la o anumită adâncime finită d (adâncimea soluției cu cel mai mic cost așa cum a fost definită anterior), după generarea tuturor nodurilor mai puțin adânci. Se observă faptul că, odată ce un nod-obiectiv a fost generat, este evident că acesta este nodul obiectiv cu cea mai mică adâncime, întrucât toate nodurile cu o adâncime mai mică au fost deja testate pentru a verifica obiectivul și au picat testul. Cu toate acestea, nodul-obiectiv cel mai puțin adânc nu este neapărat soluția cea mai optimă; căutarea în lățime este optimă doar în cazul în care costul drumului este o funcție nedescrescătoare a adâncimii nodului. O astfel de situație are loc atunci când toate acțiunile au același cost.

Din punct de vedere al complexității, eficiența căutării în lățime scade. Considerând un arbore uniform unde fiecare stare are b succesori. Pe primul nivel, rădăcina va genera b noduri, fiecare dintre acestea generând la rândul lor alte b noduri și așa mai departe. Considerând că soluția se află la adâncimea d (în cel mai rău caz reprezentând ultimul nod generat la acel nivel), atunci numărul total de noduri generate va fi:

Complexitatea temporală este deci O(). În cazul în care testarea obiectivului s-ar face atunci când nodurile sunt alese pentru expandare și nu atunci când sunt generate, toate nodurile aflate la adâncimea d ar fi expandate înainte ca nodul-obiectiv să fie găsit, iar în acest caz, complexitatea temporală ar fi O(). Întrucât, în cazul căutării în lățime, fiecare nod expandat este păstrat în memorie, complexitatea spațială va fi de ordinul O().

Tabelul 3.1 Exemplu de complexitate spațială și temporală pentru b=10

O complexitate exponențială de forma O() este îngrijorătoare, așa cum sugerează exemplul din Tabelul 3.1. Pentru un factor de ramificare b=10, o putere de procesare de un milion de noduri pe secundă și o memorie de aproximativ o mie de biți alocată fiecărui nod, datorită complexității exponențiale, căutarea soluției pentru o adâncime mai mare de 12 devine inaccesibilă. Cu toate că, la adâncimea 12, timpul necesar căutării ar putea fi acceptabil pentru o problemă importantă, nici un computer obișnuit nu ar dispune de memoria necesară pentru a îndeplini această sarcină.

Algoritmul de căutare în lățime este optim dacă există o soluție aflată la o adâncime mică și costul fiecărui pas este 1. Dacă toate soluțiile unei probleme se află la o adâncime mare, algortimul devine ineficient datorită complexității.

Fig. 3.9 Căutarea în lățime

În figura 3.9 este exemplificată strategia de căutare în lățime pe un arbore. Nodurile vor fi expandate crescător, în funcție de indicii asociați lor în figură.

3.3.3.2 Căutarea în adâncime (Depth-First Search)

Această strategie de căutare presupune expandarea celui mai adânc nod din frontieră, la momentul curent. Căutarea va merge până la cel mai adânc nivel al arborelui de căutare, unde nodurile nu mai au succesori. Dacă nu este găsită soluția, se va reveni la următorul cel mai adânc nod care mai are succesori neexplorați.

Implementarea se face în aceeași manieră ca în cazul căutării în lățime, singura diferență constând in faptul că pentru căutarea în adâncime se folosește, ca structură de date pentru frontieră, coada. Acest lucru presupune faptul că nodul generat cel mai recent va fi ales pentru a fi expandat. Astfel, se va selecta cel mai adânc nod neexpandat, întrucât, la pasul precedent, părintele acestuia avea adâncimea cea mai mare. Urmează analiza eficienței strategiei în funcție de cele patru criterii de performanță.

În ceea ce privește completitudinea strategiei, aceasta depinde de anumite aspecte. În cazul în care căutarea în adâncime se face pe un graf (figura 3.6),aceasta va fi completă într-un spațiu al stărilor finit, deoarece într-un graf se evită trecerea prin aceeași stare în mod repetat și se evită drumurile redundante, expandându-se eventual toate nodurile. În versiunea căutării într-un arbore (figura 3.5), în schimb, strategia de căutare nu este completă datorită ciclurilor care pot apărea, sau cazurilor în care spațiul stărilor este infinit. Algoritmul poate fi modificat pentru a verifica dacă o stare nouă există deja în drumul de la rădăcină până la starea curentă, evitând astfel buclele infinite, dar acest lucru este valabil doar dacă spațiul stărilor este finit, și nu se evită apariția drumurilor redundante. Orice versiune a algoritmului căutării în adâncime va eșua în cazul în care spațiul stărilor este infinit, dacă drumul ales de algoritm nu conține nici o soluție și este infinit.

Complexitatea temporală este de forma O() și poate deveni foarte mare dacă m(adâncimea maximă a spațiului stărilor) este mult mai mare decât d (adâncimea nodului-obiectiv cu cel mai mic cost). Avantajul căutării în adâncime față de cea în lățime, îl reprezintă complexitatea spațială. Pentru căutarea pe un graf, nu există nici nu avantaj, dar, în cazul căutării pe un arbore, se va stoca doar un singur drum de la rădăcină până la un nod-frunză, împreună cu nodurile-copil ale fiecărui nod din drum, rămase neexpandate. Odată ce un nod a fost expandat și nu este un nod-obiectiv, acesta poate fi eliminat din memorie, odată ce toți descendenții săi au fost explorați. Pentru un spațiu al stărilor cu factorul de ramificare b și adâncimea maximă m, complexitatea spațială va fi de forma O(bm). Considerând exemplul din Tabelul 3.1, dacă nodurile aflate la aceeași adâncime ca nodul-obiectiv nu au succesori, pentru adâncimea d = 16, ar fi nevoie de doar 156 kb, față de 10 eb, ca în cazul căutării în lățime, de ori mai puțin.

În funcție de criteriile definite mai sus, căutarea în lățime nu este considerată optimă, în principal pentru faptul că eșuează într-un spațiu al stărilor infinit.

Fig. 3.10 Căutarea în adâncime

În figura 3.10 este exemplificată strategia de căutare în adâncime pe un arbore. Nodurile vor fi expandate crescător, în funcție de indicii asociați lor în figură.