Introducció a la intel-ligencia artificial # Introducción a la inteligencia artificial

Algoritmos # Màquina intel-ligent. Representació del coneixement. Logica. Algorismes

  • Enviado por: Alberto Seco
  • Idioma: catalán
  • País: España España
  • 26 páginas
publicidad

INTRODUCCIÓ A LA INTEL.LIGÈNCIA ARTIFICAL

TEMA 1: INTRODUCCIÓ A LA IA

TEMA 1: INTRODUCCIÓ A LA IA

Definició de la IA

# Segons en Robert Schank la IA te dos objectius:

  • Construir una màquina intel-ligent

  • Investigar la naturalesa de la intel-ligència.

En Schank dóna cinc característiques:

  • Comunicació, es a dir, si no hi ha comunicació vol dir que no hi ha intel-ligència.

  • Coneixement intern.

  • Coneixement sobre el món.

  • Objectius i plans.

  • Creativitat.

# En Luc Steels la defineix com “el camp científic dedicat a comprendre el fenònem de la intel-ligència”, usant la definició d'Allen Newell que caracteritza la intel-ligència en els següents termes:

  • Comportament flexible en funció de l'entorn.

  • Exhibir comportament adaptatiu, racional, orientat a objectius.

  • Operar en temps real.

  • Operar en un entorn molt ric, complex i detallat. Percebre la gran quantitat de canvis de l'entorn, utilitzar grans quantitats de coneixement i controlar un sistema motor de molts graus de llibertat.

  • Utilitzar símbols i abstraccions.

  • Utilitzar llenguatge, naturals i artificials.

  • Aprendre de l'entorn.

  • Adquirir capacitats a través del desenvolupament.

  • Viure autònament dins d'una comunitat.

  • Mostrar consciència de sí mateix.

# En Patrick Winston diu que la IA és l'estudi dels càlculs que fan possible percebre, raonar i actuar.

# L'Elaine Rich la defineix com l'estudi de com fer que els orinadors facin coses que, per ara, les persones fan millor.

# En el llibre d'Edicions UPC es defineix la IA com l'intent de:

  • Comprendre els mecanismes que poden donar lloc a una conducta denominada intel-ligència.

  • Produir màquines intel-ligents (programació d'ordinadors o construcció de màquines tals com robots).

  • Com avaluar el comportament intel-ligent d'un programa?

    Al 1950 Allan Turing va proposar un test que consistia en que una persona (observador) fa unes preguntes i li responen una altra persona i una màquina en habitacions diferents, i l'observador ha decidir en quina habitació es troba la persona. La màquina intenta fer-se passar per la persona i aquesta passa el test quan ha aconseguit enganyar un nombre considerable de vegades al/s observador/s. Aquest test només es basa en el comportament verbal, es a dir, només en la comunicació.

    Arees d'aplicació de la IA

    Tasques d'interació amb el món (nen).

    • Percepció (Visió i Parla).

    • Llenguatge natural (comprensió, Generació i Traducció).

    • Raonament de sentit comú.

    • Moviment (navigation, robots).

    Tasques formals (a l'escola).

    • Jocs (escacs, backgammon, go, trencaclosques).

    • Matemàtiques (geometria, lògica, Integració simbòlica, derivació automàtica de programes).

    Tasques d'expert (a la Facultat)

    • Engnyeria (disseny, detecció de falles).

    • Diagnòstic mèdic.

    • Anàlisi financera.

    • Anàlisi científica.

    Historia de la IA

    Gestació:

    1820 Màquina de Babbage

    1920 Màquina de Torres Quevedo

    1945 Maquina de Von Neumann (ENIAC)

    1948 Principios de Cibernètica (Vienner)

    1950 Ideas de Shanon sobre automatització d'escacs.

    Naixement i infancia (fins 1968):

    · Cerca en espais d'estats.

    · Generació i proba.

    · Cerca heurística

    • Programar per jugar a les dames.

    1956 Conferencia de Dartmoth, euforia incial amb promeses exagerades (en 10 anys, campió mundial d'escacs), sobreestimació capacitat de cerca.

    1957 Programar per jugar a escacs.

    1958 General Problem Solver.

    1960 Principi de resolució.

    1963 Resolució d'integrals.

    1965 Primers projectes de Robótica. Anys dificils: desacredit per les promese incumpleses. La conclusió es que la cerca sola és impracticable, i hi ha una necesitat de coneixement. S'abandonen les xarxes neuronals, tras Minsky i Papert.

    Desenvolupament (fins 1977):

    · Xarxes semàtiques.

    · Regles

    · Formalismes lògics.

    · Sistemes de producció.

    · Frames

    · planificació.

    1968 Dendral: síntesi d'estructures moleculars. Macsyma: càlcul simbólic.

    1970 Scholar. J. Carbonell.

    1972 Planner, Hewitt.

    1973 Primers ptototipus de SE.

    173 Mycin, Shortliffe, Buchanan, Clancey.

    1974 Sophie, Brown, Burton

    1975 Frames: Minsky.

    1976 Teiresias, Davis.

    Reconeixement extern (fins 1980):

    1977 KRL, Bobrow, winograd

    1978 Prospector, Duda

    1980 Xsel, Xcon, McDermott. Papel del coneixement, multiplicitat de representacions,.

    Representació del coneixement: tema estrella de la IA.

    Popularització dels sistemes experts.

    Necesitat de l'aprenentatge automàtic.

    Xarxes neuronals: reanudació tras Hopfield.

    Robótica i agents autónoms.

    1981 Emycin, Van Melles, Shortliffe, Buchanan.

    1982 Reactor, Nelson.

    Tècniques d'IA

    Ja hem vist la primera tècnica que va ser la de Turing, despres va apareixer ELIZA, que el va crear Weizembaum que vol simular el tipus de conversa que es te quan es parla amb un psicoanalista.

    • Eliza és el mateix que el test de Turing? En Turing l'observador sap que una de les respostes és d'una màquina, enc anvi amb Eliza és la propia màquina.

    • Tenim el problema de reconeixement del llenguatge natural: es a dir, que tenim un text i fem preguntes i obtenim unes respostes, si el sistema dona respostes despres de tenir el text, vol dir que ha comprés el text i per tant que te una certa intel-ligència.

    • També tenim el Pattern matching: que conisteix en que tenim una frase i es fa una pregunta sobre aquesta frase.

    Pere ha comprat un llibre vermell.

    Que ha comprat Pere? un llibre vermell

    Per cada patro tenim una resposta i si hi ha algun cas en que no te patro, llavors escogeix respostes a l''tzar. Aquest sistema és en el que es basa ELIZA.

    • T.L.N: tractament del llenguatge natural, per solucionar el tractament de llenguatge natural tenim:

    • Gramàtiques

    • Lexicons (diccionaris)

    Frase 1: acció: compra Individu 3: objecte 5:

    Temps: passat instancia persona instancia llibre

    Agent: individu 3 nom: Pere color: vermell

    Objecte: objecte 5

    Amb aquest metode s'afegeix un coneixement abstracte

    Encara ens caldria afegir mes coneixement de sentit comú i això s'aconsegueix amb els scripts.

    TEMA 2: REPRESENTACIÓ DEL CONEIXEMENT

    Introducció

    Per representar el coneixement necessitem dels esquemes de representació, els cuals estan compostos per:

    • Estructures de dades.

    • I procediments o funcions.

    Normalment del coneixement parlarem de dos entitats:

    • Mon o domini del problema.

    • Representació del mon.

    Aquestes dues entitats han d'estar molt relacionades, ja que volem la millor representació possible que puguem obtenr del món. La representació es pot fer per tant amb un o més esquemes. Aquesta representació sempre serà incompleta, ja que sino seriem en el mon del problema.

    El coneixement te unes característiques que el fan irrepresentable totalment:

    • En molts cassos la informció es voluminosa.

    • Hi ha moltes modificacions.

    • El coneixement es complex .

    Per tant hem de buscar les parts rellevants del món.

    Els sistemes basats en el coneixement són els sistemes que es basen en una representació del coneixement per resoldre els problemes que li poguin apareixer. Les característiques d'aquests sistemes, serien basicament:

    • Adequació de la representació: l'esquema de representació ha de ser suficient per representar el problema i poder resoldre'l.

    • Adequació de la inferència: a partir de coneixements es voldria obtenir altres coneixements (cas de la lògica, en concret les premises).

    • Eficiència en la inferència: si la resposta triga molt en donar-se pot ser que en alguns sistemes ja sigui massa tard per aplicar-la, perque s'havia d'haver fet abans.

    • Eficiència/comoditat en l'adquisició: que els mecanismes dels sistemes per representar el coneixement s'assemblin més als mecanismes que utitza l'expert per representar la informació.

    Tipus de coneixement

    Els diferents tipus de coneixement que podem represnetar són:

    • Coneixement relacional simple: aquest es compon per les taules que contenen els registres d'una base de dades.

    • Heretable/ taxonòmic: tenim una representació de conceptes a varis nivells.

    Permeten repartir la informació als diferents nivells. I cambiant la informació d'un d'aquests nivells quedan actualitzats tots els nivells per sota sense haver de ser modificats aquests.

    Com podem veure, aquest coneixement es compon de conjunts i d'elements, aquests últims són les entitats reals, i els conjunts conjunts d'aquestes entitats reals.

    Existeixen dos tipus de crelacions:

    · ES-UN (inclusió ").

    · INSTANCIA DE (pertany ").

    • Coneixement inferible: tipus particular del coneixement procedimental.

    Home (Socrates)

    "x: home (x) ! mortal (x)

    • Coneixement procedimental: és el coneixement de com calcular els valors, es adir, te una funció de càlcul relacionada. Per exemple: l'edat va cambiant en funció de la data de naixement i per tant s'ha d'anar calculant. Per tant l'edat no es consideraría un atribut sino com una funció que pren la data actual i la data de naixement i dona l'edat.

    Exemple: Relacions de familia.

    Maria és cosina de l'Anna

    Cosina s'ha de traduir als sis termes que tenim, unes possibles traduccions són:

    Maria

    Filla

    -Germa

    -Mare

    De l'Anna

    Filla

    -Germana

    -Mare

    Filla

    -Germà

    -Pare

    Filla

    -Germana

    -Pare

    Tenim quatre representacions i a partir de cada cas obtenim un resultat diferent. Una solució es agrupar els termes primitius i així obtenim una únca representació

    Cosina !

    Fill

    Germà

    Mare

    Filla

    Germana

    Pare

    Respas de lógica de predicats

    • 1.-Formalització dels predicats.

    • 2.-Manipulació, en concret posar els predicats en forma claussular.

    • 3.-Resolució.

    Problema 1

    • A John, le gusta todo tipo de comida.

    • 1.-"x: (comida (x) ! gusta (John, x))

    • 2.-¬ comida (x) " gusta (John, x) _1

    • Las manzanas son comida.

    • 1.-comida (manzanas) ! "x: (manzana(x) ! comida(x))

    • 2.-comida (manzanas)_2

    • El pollo es comida.

    • 1.-comida (pollo)

    • 2.-comida (pollo)_3

    • Cualquier cosa que alguien come y no muere es comida.

    • 1.-"x: ("y: come (y, x) " ¬muere (y)) ! comida (x)

    • 2.-"x: ("y: come (y, x) " ¬muere (y)) ! comida (x)

    " "x: (¬("y: come (y, x) " ¬muere (y)) " comida (x))

    " "x: ("y: ¬come (y, x) " muere (y)) " comida (x))

    " "x "y: (¬come (y, x) " muere (y) " comida (x))

    ¬come (y, x) " muere (y) " comida (x)_4

    • Bill come cacahuetes y no ha muerto.

    • 1.-come (Bill, cacahuetes) " ¬muere (Bill)

    • 2.-come (Bill, cacahuetes)_5

    ¬muere(Bill)_6

    • Sue come todo lo que Bill come.

    • 1.- "x: (come (Bill, x) ! come (sue, x))

    • 2.- ¬come (Bill, x) " come (Sue, x)_7

    Resolució: premisas U {¬C} " ð on C és la conclusió. La regla de la resolució és la següent:

    A" B

    ¬A" C

    B " C

    Demostrar que:

    C = gusta (John, cacahuetes)

    ¬gusta (John, cacahuetes) 1

    x/cacahuetes

    ¬comida(cacahuetes) 4

    x/cacahuetes

    ¬come (y, cacahuetes) " muere(y) 6

    y/Bill

    ¬come (Bill, cachueste) 5

    ð

    Amb la resolució també es poden respondre les preguntes que demanen de donar algun nom, i no només a preguntes requereixen d'una resposta afirmativa o negativa.

    Sistemes de regles de producció

    Els sistemes de producció són semblants a les representacions lògiques, però no són iguals.

    La representació lògica és el que s'anomena representació declarativa, que vol dir, que en el coneixement que representa estan definits els objecetes però en canvi no esta definit com es manipulen els objectes:

    Ax1) A ! B

    Representació lògica

    Ax2) A

    Els sistemes de regles són una representació procedimental, a més de definir els objectes, també explica el tipus d'execució que es pot fer sobre el coneixement. Es tracta la reprresentació lògica com un programa.

    Exemple:

    L1: gat (Buffy)

    L2: gat (Lissy)

    L3: animaldomestic (Dina)

    L4: "x: gat(x) ! animaldomesstic(x)

    Animaldomestic (x) x! variable de sortida

    No sabem el valor de x perque no sabem com executar el programa.

    Si suposem accés seqüèncial : x= Dina

    Canviem L4 per L3 i tenim que x=Buffy.

    En els sistemes de produccions tenim dos components:

    • Fets: els fets són afirmacions i en cap moment tindrem negacions.

    • Implicacions

    • A ! B

      A

      Modus ponens “cap endavant”

      B

      No podem utilitzar el modus ponens cap enrera, pero si podem fer una lectura cap enrera.

      A ! B ; per obtenir unaB hem d'obtenir una A

      A ! B

      Objectiu B

      Modus ponens “cap enrera”

      Objectiu A

      Modus ponens cap endavant

      Els tipus de coses que necessitem pel modus ponens cap endavant:

      • Fets: s'agrupen en base de fets, tots afirmacions

      • Regles: base de regles

      • Mecanisme de control, s'aparellen en due parts:

      · Mecanisme d'inferència: varia tot el conjunt del modus ponens possibles cap endavant que podria fer. Si no troba cap MP el sistema s'atura. Si hi ha diverses posibilitats necessitarem un mecanisme per escollir-ne alguna. Crea el conjut de conflictes (aplicacions que hi ha)

      · Mecanisme de resolució de conflicte: escolleix el MP que farà servir entre tots els possibles.

      Cap endavant les regles s'assemblen a l'estructura condicional

      Les condicions i accions s'evaluen sobre les variables o contingut de la memoria.

      En aquest sistema s'evaluen sobre la base de fets (BF) i es modifica l'anomenada base de fets.

      A ! B

      A avalua cert segons la BF

      A ! B " Base de regles (BR)

      A " BF

      Executar B

      Afegir B a la BF

      A " B ! C i A " B ! C no passa res pero el següent cas te un tractament dierents:

      ¬ A ! B no pot passar i per tant no s'accepta

      Però amb la hipotesi del mon tancat si s'acceptaria. La hipotesi del món tancat diu que durant el funcionament del sistema podem fer l'hipotesi de que tota afirmació estarà a la BF.

      ¬ A ! B

      A " BF

      En cada moment A es cert o fals però no pot ser cert i fals en el mateix moment.

      B

      Tenim el criteri de refracció que diu que en el conjunt de conflictes no es consideren activacions que ja s'han fet.

      Modus ponens cap enrera

      En aquest tipus de sistema de producció també necessitem el descrit a l'apartat anterior (MP cap endavant) però amés necesitem la llista d'objectius a assolir.

      • Fets: base de fets

      • Regles: base de regles

      • Llista d'objectius a assolir.

      • Mecanismes de control

      En aquest cas l'execució s'atura quan no tenim cap objectiu més que assolir.

      A

      Objectiu A, B, C

      Objectiu B, C

      En aquest cas tenim unes restricions sintactiques:

      • A ! B, on B només pot ser un “fet” afirmat.

      • No podem tenir coses com: A ! B " C, però en canvi podem fer coses d'aquest estil:

      A ! B

      A ! C

      • No podem tenir coses com: A ! B " C, tenim com objectiu, però no podem afirmar que al tenir A tindrem B ja que podriem tenir C.

      A " B " C ! D

      A ! C

      B ! C

      Objectiu D

      A " B ! C

      Objectiu A, B, C

      ¬ A ! B

      Objectiu B

      Els objectius són de la bae de fets o a la part dreta i per tant es pot prohibir aquesta situació o tratar-lo de forma diferent.

      Aquesta forma és lasegüent:

      Objectiu ¬ A

      Negació per fallida:

      Objectiu ¬ A pero plantegem Objectiu A, en aquest cas podem succeir dues coses:

      • que aconseguim validar aquest predicat, i per tant voldrà dir que hem fracasat al obtenir ¬ A.

      • O que no ho aconseguim demostrar, i per tant voldrà dir que hem aconseguit l'objectiu ¬A.

      Ca enrera manifesten l'actiu canviant els objectius i no els fets com fa el sistema cap endavant. En cap enrera el mecanisme de resolució de conflictes pot fer backhacking, es a dir, que pot replantejar-se decissions no presses abans.

      Representacions estructurades

      Xarxes semantiques

      Les xarxes semàntiques són sistemes de representació declaratiu encara que hi han xarxes amb coneixement procedimental.

      La idea de les xarxes semàntiques es semblant a un diccionari. Quillian volia representar el significatde les paraules i es d'on surt l'idea de diccionari.

      Una xarxa equival a un graf etiquetat amb els nodes i arcs. Els concpetes són als nodes i la definició són les diverses connexions amb els altres nodes.

      Hi ha autors que a les xarxes semàntiques les anomenen xarxes associatives.

      Els node represneten:

      • Conceptes

      • Individus: objectes concrets del nostre domini.

      • Accions

      • Valors de propietats dels individus.

      Els arcs representen relacions (la relació que hi ha entre indivuds i conceptes) atributs, etc.

      Exemple:

      · Canari: ocell que canta i de color groc.

      · Ocell: animal vertebrat, amb ales i que pot volar.

      Les relacions poden ser de dos tipus: " es_un i " instcnia de.

      En principi nomes es poden expresar relacions bnaries amb les xarxes semàtiques, però una relació de qualsevol cardinalitat es pot expressar en funció de relacions binaries.

      Una relació binaria te l'esquema següent:

      Exemple de transformació d'una relció qualevol a una relació binaria: resultat (equiplocal, equipVis, golsl, golsev)

      El sou de Joan es de 100000 ptas

      El sou de Joan es més gran que el de Pere.

      En el primer exemple tenim n valor concret (100000) i a l'altre no (sou-j). El node de 10000 ptes pot existir sense la resta de la xarxa peque 100000 sempre seran 100000 els cobri o no, en Joan. En canvi el node sou-j depen de la xarxa. Per tant depenent de la epresentació tindrem nodes que els haurem de tenir sempre i noes objectius que poden existir en una altra xarxa.

      Mecanismes d'inferencia de les xarxes semàntiques

      Pàgina 6 de les transparencies.

      A la figura 3 s'organitzen els concpetes de forma jerarquica (forma d'arbre) on cada nivel de l'arbre es caracteritza pel grau d'especificació. Hi ha dos tipus de relacions:

      • Taxonòmiques: instancia_de. És una connexió entre els diferents conceptes.

      • Particulars: defineixen els atributs dels conceptes.

      Els concpetes inferiors hereten els atributs dels conceptes superiors a ells.

      A la figura 5 tenim la represnetació d'un arc. Un arc te tres blocs:

      A la figura 7 es vol simular una frase en una xarxa semàtica. El verb és el centre de la xarxa i està unit a tots els objectes de la frase. Seria com analitzar les frases (distingir subjecte, verb, objecte directe, objecte indirecte, etc.)

      A la figura 8 tenim els grafs de dependencia concpetual. La frase es redueix a elements atomics, seria el llenguatge assembler de les frases.

      A la figura 1 (pàgina 7) es vol intentar representar predicats en lògica. Les operacions (", ", ¬) necessitaran altres nodes que apuntin a les accions que afecten.

      A la figua 7.7 (pàgina 8) es vol definir subparts de les xarxes. Això permet treballar amb quantificadors.

      Sistemes de frames

      Les etiquetes de les xarxes semàntiques són objectes no estructurats.

      Els frames són xarxes semàtiques sobre objectes estructurats (tuples, registres...). És la definició d'un objecte estructurat on cada objecte estructurat es basa en una sèrire d'slots.

      Un slot és un objecte estructurat en base a una serie de facets.

      Un facet és un objecte amb “valor” que s'anomena fillers.

      Les estructures no estan aïllades, estan relacionades. hi ha dos tipus de relacions:

      • Taxonòmiques: relacions es_un (inclusió) i instancia_de (pertinença). Permeten el raonament per herencia.

      • Usuari: s'han de definir i les definicions són estructurades.

      Podem trobar un exemple a la pàgina 5 de les transparencies.

      L'herencia no és copia sino consulta. EL frame consulta a un frame superir però la característica no és copia al frame consultor, sino que es manté al frame superior i només es pot consultar

      La descripció de frames, slots i relacions es troba a les pagines següents:

      Fotocopia 1

      Descripció de les relacions, frames, i slots.

      Fotocopia 2

      Un demon es un una funció que s'activa sense cridar-les. Te condicions d'activacions sobre el valor associat a un slot. Sobre un valor podem preguntar, per un frame i slot concret, quin valor te. Si te definit el valor el retorna, si no el té definit i el demon esta en if_needed llavors s'executa una funció per calcular quin valor hauria de tenir. Si el demon està a if_added s'executaria aun assignem un valor a un slot concret. I si fos if_remove s'executaria la funció quan esborresim un valor.

      L'herencia indica si l'slot es pot heretar o no. Les definicions d'herencia es defineixen en dos parts: per les taxonòmiques i per les relacions d'usuari.

      Existeixen diferents tipus de slots en funció de l'herencia, aquests tipus de slots són:

      • Slots membres: slots que s'apliquen a les instancies de les classes.

      • Slots propis: són els que no interessa que s'heretin.

      Les relacions definides per l'usuari sempre estan definides entre les instancies.

      Herència

      L'herència consisteix en trobar valors en d'altres frames quan el frame sobre el qual es fa la consulta no té cap valor (per l'slot). L'herència no es còpia sino que només es pot consultar.

      Per trobar els valors a travès de l'herència tenim unes prioritats: primer es busca el facet valor i si no es troba es buscaria en el facet demon. Aquesta prioritat descrita és la prioritat dins del frame.

      Les diferents formes de poder combinar les prioritats dintre la jeràrquia i les prioritats dintre del frame ens dona dos tipus d'herència:

      Aquest dos ordres de cerca d'un valor en l'herència només es pot utilitzar en relacions d'usuaris si aquestes són transitives.

      Que passa quan hi ha diferents camins per anar per l'herència? (herència multiple)

      Eli.vola=NO

      Ara hi ha dos possibles camins d'herència. Per solucionar el problema no hi ha criteris generals per solucionar l'herència multiple.

      Un criteri podria ser escolir el camí de longitud més curta:

      Aquest camí te longitud 1

      Aquest camí te longitud 2

      Però el primer camí podria tenir una lonmgitud més gran que el segon i el resultat seria incorrecte. I si els dos camins tinguessin la mateixa longitud encara no sabriem quin escollir.

      El que no seria lògic seria triar el camí vermell ja que pel camí blau anem a un frame que està per sota del frame al que arribem pel camí vermell. No és lògic utilitzar els casos generals per definir casos excepcionals que defineix ja el valor que volem pel nostre frame.

      Aquest és el criteri de la distancia inferencial:

      • 1 pas: fer el conjunt dels frames des dels quals podem arribar a un valor *.

      • 2 pas: filtre, el.liminar del conjunt els frames tals que en el conjunt hi ha un altre frame tal que podria heretar el valor deinit en el primer frame. Conjunt verd discontinu.

      • 3 pas: Si la cardinalitat de l'slot és N llavors no hi ha cap problema. En canvi si la cardinalitat de l'slot es 1 tenim dos casos. Primer cas si la cardinalitat del conjunt es 1 llavors tot està correcte, però en canvi, el segon cas, si la cardinalitat del conjunt és més gran que 1 llavors el criteri no decideix.

      Un altre criteri seria que si ens pot arribar un valor per un camí despreciem els altres camins.

      Els scripts

      Els scripts pretenn solucionar el problema del coneixement del sentit comú. Són un sistema de frames especialitzats per respondre al sentit comú.

      A la pagina 12 de les transparencies trobem un exemple d'script

      Anàlisi comparatiu de les representacions

      Càlcul de predicats (CP)

      Sintctics

      Sistemes de producció (SP)

      Xarxes semàntiques (XS)

      Orientats a la semàntica

      Frames (F)

      Scripts (S)

      CP

      SP

      XS/F

      Adequació expressiva

      No hi ha valors per defecte.

      Manca d'estructures

      Negociaó per fallada

      Dificil representar

      lleis generals

      (negació?)

      Adequació inferencial

      Principi de resolució

      Modus Ponens

      Herència

      (taxonomica)

      Eficiència inferencial

      Pobre

      Ús de meta-regles

      Procediments

      Eficiència en l'adquisició

      Pobre

      Regular

      Lleis generals

      Coneixement heurístic

      Coneixement taxonòmic

      La inferència

      TEMA 3: RESOLUCIÓ DE PROBLEMES

      Introducció

      La cerca sobre un espai d'estats es un bon metode per fer inferència sobre problemes (resolució de problemes).

      La metodologia que seguirem serà:

      • Formular el problema.

      • Determnar la insrtancia de l'esquema de cerca òptim.

      • Implementar.

      La IA vol dissenyar engings informàtics amb un comportament intel-ligent en un entorn complexe. El disseny d'engings infomàtics equival a dissenyar un programa. I el comportament intel.ligent equival a:

      • Fixar un objectiu

      • Més assolir l'objectiu: aquest objectiu es pot assolir de forma reactica (sensors, reacció a cada configuració -estat- percebuda de l'entorn) o de amb una certa planificació.

      Amb la planificació tenim un objectiu, la situació actual, el pla que seguirem (seqüències d'accions, precondcions, efectes ...) i una funció de cost (associada a cada acció).

      Per exemple un robot podria anar directament provant fins a arribar al lloc desitjat o ve primer mirar per on podria anar i despres començar el viatge.

      Exemple: tenim dues gerres una de 3 litres i una altre de 5 litres i volem obtenir 4 litres exactes.

      Això es el que s'anomea Espai d'estats.

      Els components d'un problema són:

      • Estat. Configuració possible de l'entorn en el que em trobo resolent el problema.

      En l'exemple: Estat = <xp, xg> on xp" {0,1,2,3} i xg"{0..5}

      • Espai d'estats: conjunt de tots els estats per un problema

      • Condició d'objectiu: xg=4

      • Estat inicial : <0,0>

      • Operadors: estat ! estat. Per cada operaxdor tindrem les precondicions i els efectes.

      Per exemple: prec: xp<3 efecte: xp=3

      • Funció de cost: estat * operador ! R

      • Solució: que es compon d'un estat objectiu, una seqüència d'operadors de l'estat inicial a l'estat objectiu, de tots els estats objectius i totes les seqüències. En els dos primers casos poden obtenir la solució optima (per això haurem de disposar d'una mena de funció de cost).

      Formulació

      Exemple: problema de les 8 reines

      Podem codificar el problema amb:

      • Una taula de [8,8] de booleans.

      • [<, >, <, >, ...., <, >]

      x1 y1 x2 y2 x8 y8

      Ens quedem amb la segona formulaci´:

      Els elemnts bàsics que intervindran en el disseny d'esquemes algorísmics:

      • Un estat és un conjunt de parells.

      • Condició d'objectiu: "i, j: i"j: xi"xj " yi"yj " |yi-yj|"0 ""i: xi, yi " {1,...8}

      • Estat inicial {<?,?>, <?,?>, ....}

      • Operadors: col.locar reina (l, i, j)

      Pre "k (xk,yk)" (?,?), xk"i yk"i; |xk-i|"|yk-j|

      Efecte xl=i, yl=j.

      • Solució: un estat objectiu

      Cerca no informada

      Els components d'un algorisme de cerca són:

      • Comprovar l'objectiu. Funció es_estat_objectiu: estat ! booleà.

      • Generar_successors: estat ! {estati} tal que són estats pels quals eisteix un operador tal que la precondició és satisfeta per l'estat anterior.

      • Estrategia de cerca: selecciona_estat: {estat} x estratregia ! estat

      • Solució: d'estat a un estat o a un camí (estat inicial, estat).

      Esquema comú dels algorismes de cerca

    • Associar a l'estat inicial un node incial.

    • Aplicar al node inicial tots els operadors posibles (expandir elnode).

    • Associar a tots els fills generats un punter al pare.

    • Comprovar si algun dels fills és un nde terminal.

    • Si no hem trobat un node terminal, un cop tractats els fills repetits, integrar els fills generats a la llista de pendents (ordre segons estratègia de cerca).

    • Seleccionar un nou node a ser expandit i repetir 3, 4, 5, 6

    • Si arribem a un node terminal final, s retorna al node inicial a través del punters i així obtenim el camí solució (seqüència d'operadors).

    • Si es compleixen les condicions de control d'acabament i no hem arribat a un node terminal final, s'atura el procès sense solució. Les condicions d'acabament poden ser: la no generació de nodes nous al fer l'expansió de nodes i per tant s'arriba a tenir la llista de nodes pendents d'explorar buida, o l'arribada a una profunditat màxima, o l'ús del temps màxim de CPU inicialment previts, o...

    • Funció cerca_general (problema, estratègia) retorna solució o buit

      Inicialitzar (problema, estat_inicial)

      Bucle

      Si generar_successors (problema, actual)=" llavors retorna buit

      Sino estat_actual ! selecciona_estat (genera_successors (problema.actual, estrategia)

      Si es_estat_objectiu (estat_actual) llavors retorna solució (estat_actual)

      Fsi

      Fsi

      Fbucle

      ffució

      Una altra versió d'aquest algorisme de cerca general podria ser el següent:

      Funció cerca_general (problema, estrategia) retorna solució o fallada

      Espai ! inicialitació_espai (problema, estat inicial)

      Mentre cert

      Si no es pot expandir cap node (espai) llavors retorna fallada

      Actual ! escollir_node_per_expandir (estrategia)

      Si satisfa_condició_objectiu (actual) ! retorna actual

      Fsi

      Espai ! expandir_node (espai, actual)

      Fmentre

      Ffunció

      Aquests dos algorisme implementen una cerca cega o desinformada i el que és util és la cerca informada.

      Per poder fer una cerca informada necessitem declarar un tipus estructurat per indicar la informació a partir de la qual podem guiar la cerca.

      Tipus

      Problema es tupla estat_inicial: estat

      Es_objectiu?:funció estat!bool

      Operadors: cjt_de (operadors)

      F_cost: funció estat x operador ! R

      Ftipus

      Ara la cerca general es pot fer de la següent forma:

      Funció cercageneral (problema, fencuar) retorna solució o fallada

      Var

      Actual: estat

      Oberts: supercua (estat)

      Fvar

      Oberts !encuar (supercua.crea, problema, estat_inicial)

      Mentre cert

      Si supercua.buida?(oberts) ! ret fallada

      Actual ! desencuar(oberts);

      Si problema.es_objectiu?(actual) ! ret atual

      Fsi

      Oberts ! fencuar(oberts, expandir(actual, problema.operadors));

      Fmentre

      Ffunció

      Les estrategies que es poden seguir són el recorregut en amplada o en fondaria, i els algorismes es poden trobar a les trasparencies pagina 14.

      Amplada

      En amplada tenim una funció fencuar

      fencuar: encuar_al_darrera

      Aquesta funció garanteix que recorrem el nostre espai d'estats d'una forma sistemàtica. Ens garantirà completessa si existeix la solució (" solució ! segur que la trobem)

      Amplada prioritària

      OBERTS: llista de nodes als que s'ha arribat i encara no s'han expandit.

      TANCATS: llista de nodes ja examinats.

      INICIAL: descripció de l'estat inicial.

      FINAL: descripció de l'estat final.

      NODE_ACT: descripció de l'estat actual.

      FILLS: llista que conté els nodes fills de l'estat actual.

      OBERTS ! INICIAL

      TANCATS ! NULL

      NODE_ACT ! INICIAL

      Associar un punter buit a INICIAL

      mentre ¬buit(OBERTS) " (NODE_ACT<>FINAL) fer

      OBERTS ! OBERTS - NODE_ACT

      TANCATS ! NODE_ACT + TANCATS

      FILLS ! expandir (NODE_ACT)

      FILLS ! FILLS - TANCATS

      FILLS ! FILLS - OBERTS

      Associar a cada element de FILLS un apuntador a NODE_ACT

      si algun_final (FILLS) llavors

      NODE_ACT ! el_fil (FILLS)

      sino OBERTS ! OBERTS + FILLS

      NODE_ACT ! cap (OBERTS)

      fsi

      fmentrs

      si NODE_ACT = FINAL llavors

      proporcionar la seqüència solució.

      sino

      informar de que no existeix solució

      fsi

      A tots aquests algorismes, en lloc d'usar comparatius podriem usar un predicat del tipus:

      final (NODE_ACT)

      Fondaria

      Fondaria Aquest algoritme no te completessa.

      En aquest algorisme tenim dos variants:

      • Fondaria limitada: fondaria on tindrà un màxim de node per baixar. (l = #_nodes -1). Si hi ha solució el camí que porta a la solució no pot tenir més de l passos.

      • Fandaria iterativa (ID): aquesta fondaria es vàlida en arbres on no hi hagin moltes solucions.. qui anem provant per nivells de nodes. En aquest algorisme posem una fita per branca i quan arribem a aquesta fita (profunditat) continuem per la següent branca

      • Fondaria Limitada

        Fondaria Iterativa (ID)

        fEncuar

        si fondaria(n)<l

        llavors encuar_davant

        fsi

        Fondaria_limitada(1)

        Fondaria_limitada(2)

        Fondaria_limitada(3)

        per i=1 fins " fer

        cerca_amb_fond_limitada(i)

        fper

        Completesssa

        Si si l és bona

        Si

        Temps

        O(bl)

        O(bd)

        Espai

        O(b·l)

        O(b·d)

        Fondaria Prioritària

        OBERTS: llista de nodes als que s'ha arribat i encara no s'han expandit.

        TANCATS: llista de nodes ja examinats.

        INICIAL: descripció de l'estat inicial.

        FINAL: descripció de l'estat final.

        NODE_ACT: descripció de l'estat actual.

        FILLS: llista que conté els nodes fills de l'estat actual.

        OBERTS ! INICIAL

        TANCATS ! NULL

        NODE_ACT ! INICIAL

        Associar un punter buit a INICIAL

        mentre ¬buit(OBERTS) " (NODE_ACT<>FINAL) fer

        OBERTS ! OBERTS - NODE_ACT

        TANCATS ! NODE_ACT + TANCATS

        si nivell(NODE_ACT) < PROF_MAX llevors

        FILLS ! expandir (NODE_ACT)

        FILLS ! FILLS - TANCATS

        Associar a cada elements de FILLS un pnter a NODE_ACT

        si algun_final (FILLS) llavors

        NODE_ACT ! el_fill(FILLS)

        sino OBERTS ! OBERTS - FILLS

        OBERTS ! FILLS + OBERTS

        NODE_ACT ! cap(OBERTS)

        fsi

        sino NODE_ACT ! cap (OBERTS)

        fsi

        fmentre

        si NODE_ACT = FINAL llavors

        proporcionar la seqüència solució

        sino

        informar de que no existeix soució

        fsi

        L'algorisme de cerca en amplada garanteix que recorrem l'espai de forma sistemàtica, en canvi l'algorisme en forndaria agafem una branca fins que aquesta acaba i aquesta pot ser infinita. A continuació veiem una taula resum de les característiques dels dos algorismes:

        Amplada

        Fondaria

        b= # maxim de fills (branching factor)

        d=fondaria

        Fencuar

        Encuar_al_darrera

        Completessa

        SI

        NO

        Cost temp

        O(bd)

        Cost espaial

        O(bd)

        El cost d'una operació és el cost que està associat a un arc de l'arbre. Si el cost és el mateix i positiu la optimalitat és bona en amplada.

        Cerca bidireccional

        Un altre esquema és el de cerca bidireccional: fem la cerca pels dos costats i amb els nodes que anem obtenint fem la intersecció. Si coincideixen en algun node, al´´o és un camí a la solució. Ara explorem un arbre de mida d/2 enlloc d'un arbre de mida d. L'ordre total serà 2·O(bd/d) per tant el cost en temps i espai és el següent:

        Temps

        O(bd/2)

        Espai

        O(bd/2)

        Gestió dels estats repetits

        Tenim tres possibilitats:

      • Generar només els fills diferents del pare

      • Anem guardant els nodes dels quals penja l'actual. Si no es pot expandir més, esborrem els pares (si no hi han més germans per probar).

      • Gusrem tots els nodes (i punters).

      • Si estem en amplada

        Cost Uniforme

        Una variant del d'amplada és el de cost uniforme. En aquest algorisme els arcs quevan d'arc a arc tenen una etiqueta (prioirtat). El nostre algorisme posa primer a la cua el de prioritat menor (es a dir, el que l'etiqueta més petita. Així va buscant els nodes amb prioirtat més petita fins que troba la solució.

        Troba la solució òptima si la funció de cost sobre els camins és creixent

        Amb una altra versió de l'algorisme de cerca necessitem a més de la funció d'encuar, una funció d'evaluació.

        Funció cerca_general (problema, fencuar, fevaluació)

        ...

        mentre

        ....

        estats ! cua_encuar (estats, expandir (actual), f evaluació)

        fmentre

        ffunció

        El problema conté l'estat inicial, els operadors, la condició d'estat final, la funció de cost, etc.

        La funció que tenim represnetada el que fa es encuar els estats nous amb ells vells en ordre decreixent segons fEvaluació.

        Tipus de funció d'evaluació:

        Algorisme

        fEvaluació

        Cost uniforme

        G(n)

        Cost mínim

        Greedy Search (cerca avariciosa)

        H(n)

        Qualsevol estimació del cost del millor camí de n a l'estat objectiu més proper

        A*

        F(n)=g(n)+h(n)

        Per un estat inicial i un estat objectiu. És l'estimació del millor camí cap a la solució que passa per n

        Els millors algorisme són A* i el greedy search però aquest últim no es complet, en canvi A* es òptim amb les següents condicions:

        • Si f és monotona

        • Si h és admisible. h(n) és sempre més petit que el cost del millor camí de n al node objectiu.

        Triarem la funció h “mes informada” i és més informada que h' si "n h'(n)<h(n) i h(n)<f(n).

        Cerca Heuristica

        Definicions prèvies:

        • Cost d'un arc: c(mi, mj)

        • Cost d'un camí: Introducció a la intel-ligencia artificial # Introducción a la inteligencia artificial

        • Cost del camí mínim K(mi,mj)= min Cl(l=1,...m)

        • Cas on mj és un termnal final K(m, t)= h(m).

        Si hi ha varis nodes termnals fials T={t1,.., tl}

        h(m)= min K(m, ti)

        • Cas on mi és un node inicial K(s, m)= g(m)

        Si hi ha varis nodes inicials S= {s1, ...sl}

        g(m) = min K(si, m)

        Algorisme A*

        En aquest algorisme necesitem una funció d'evaluació per intentar esbrinar quin és el millor camí. Per esbrinar quin pot sr el millor camí utilitzarem la funció heuristica (h(n), en concret utilitzarem l'estimador de l'heuristic h'(n))) i el cost propi del node (g(n)).

        Les propietats dels heuristics són les següents:

        • h' és admisible si "n: h'(n) " h(n)

        • Si h' és admisible ! A*(h') serà òptim.

        • La funció d'evaluació és monotona, es a dir, f va creixent cada vegada)

        • Si h' és admisible ! h' és monotona.

        • monotonia h ! consistencia h ! h(ni) - h(nj) " K(ni, nj)

        K(ni, nj) ! camí optim de ni fins a nj.

        En aquest algorisme tenim una cua d'oberts en la qual els elements s'ordenen de forma creixent segons la funció f. Sempre anem treient el node de cost minim i l'hem d'expandir.

        Al agafar un node de la cua d'oberts i intentar exapandir-lo ens podem trobar dos casos:

      • Orir un node ja obert, llavors actualitzem la nova f dins de la cua d'oberts, això si sempre agafant el valor petit de f

      • Obrir un node ja tancat:

        • Si h és consistent llavors no cal reobrir-lo

        • Si h no és consistent llavors es torna a obrir (i encuar) i li asignem la f que li correspongui.

        OBERTS ! INCIAL

        TANCATS ! NULL

        NODE_ACT ! INICIAL

        Associar un pauntador buit a INICIAL

        Associar valor de l'estimació a INICIAL

        mentre ¬buit (OBERTS) " (NODE_ACT <> FINAL) fer

        OBERTS ! OBERTS - NODE_ACT

        TANCATS ! NODE_ACT + TANCATS

        FILLS ! expandir (NODE_ACT)

        FILLS1 ! FILLS - OBERTS

        FILLS2 ! FILLS - FILLS1 /* FILLS2: duplicats que són OBERTS*/

        FILLS ! FILLS1 - TANCATS

        FILLS1 ! FILLS1 - FILLS /*FILLS1: duplcats que són a TANCATS*/

        Tractar_FILLS

        Tractar_FILLS1 /*Innecesari si l'heurístic usat és consistent*/

        Tractar_FILLS2

        OBERTS ! ordenar (OBERTS)

        NODE_ACT ! cap(OBERTS

        fmentre

        si NODE_ACT = FINAL llavors

        proporcionar la seqüència solució

        sino

        informar de que no existeix solució

        fsi

        Funció ordenar: ordena la llista d'oberts segons el valor de l'estimació (f)

        Tractar_FILLS1 pot provocar “reobrir” nodes tancats i per tant, aquests nodes pooden ser novament expandits (re-exapnsió)

        Tractar_Fills

        Associar els valors de g' i f' a cada element de FILLS

        Associar l'apuntador al pare (NODE_ACT) a cada element de FILLS

        OBERTS ! FILLS + OBERTS

        Tractar_Fills1 {duplicats que són a TANCATS}

        Per a cada n de FILLS1 fer

        si nva_g'(n) < antigag'(n) llavors

        Associar a n un apuntador a NODE_ACT.

        Associar a n la nova g' i la nova f'

        TANCATS ! TANCATS - n

        OBERTS ! n + OBERTS

        fsi

        fper

        Tractar_Fills2 {duplicats que són a OBERTS}

        Per a cada n de FILLS2 fer

        si nova_g'(n) < antiga_g'(n) llavors

        Associar a n un apuntador a NODE_ACT

        Associar a n lanova g' i la nova f'

        fsi

        fper

        Algorisme IDA*

        Aquest algorisme és una combincació de l'algorisme A* juntament amb l'algorisme de fondaria iterativa o progressiva. En aquest algorisme necessitem el NVELLTALL, quest nivell és el valor màxim de la funció d'avaluació (f')

        NIVELLTALL ! 1

        NODE_ACT ! NULL

        mentre (NODE_ACT <> FINAL) fer

        OBERTS ! INICIAL

        TANCATS ! NULL

        NODE_ACT ! FINAL

        Associar un apuntador buit a INCIAL

        mentre ¬buit(OBERTS) " (NODE_ACT <> FINAL) fer

        OBERTS ! OBERTS - NODE_ACT

        TANCATS ! NODE_ACT + TANCATS

        FILLS ! expandir (NODE_ACT, NIVELLTALL)

        FILLS ! FILLS - TANCATS

        Associar a cada element de FILLS un apuntador a NODE_ACT

        si algun_final (FILLS) llavors

        NODE_ACT ! el_fill (FILLS)

        sino

        OBERTS ! OBERTS - FILLS

        OBERTS ! FILLS + OBERTS

        NODE_ACT ! cap (OBERTS)

        fsi

        fmentre

        NIVELLTALL ! NIVELLTALL +1

        fmentre

        Proporcionar la seqüència solució

        La funció “expandir” només genera els nodes fills tals que el seu valor de f' sigui més petit o igual que NIVELLTALL.

        Cal modificar-lo per tal de contemplar el cas de que no existeixi solució i fins i tot la possibilitat d'entrar en una branca infinita.

        El grau d'informació entre dos heurístics és el sgüent:

        • Donada h'1, h'2, llavors h'1 està més informada que h'2 si "n h'2(n) < h'1(n)

        Esta més informada vol dir que esta més propera a l'estat al que volem arribar, es a dir, a l'estat solució.

        Descomposició en subproblemes

        La descomposició d'un problemes i altres més petits, és molt útil, ja que podem resoldre un problema bastant gran i difícil, resolent d'altres més petits i senzills. Per resoldre els problemes ens poden apareixer dos tipus d'unions entre els subproblemes:

        • Conjució:per resoldre el problema principal hem de resoldre tots els seus subproblemes.

        • Disjunció: per solucinar un problema només cal resoldre un dels seus subproblemes.

        Els problemes que es troben en alguna fulla, són els anomenats problemes trivials o primitius

        Les característiques de la descomposició en subproblemes són les següents:

        • Dos tipus d'expansió de nodes: disjuntiva i conjuntiva.

        • Els estats han de pertanyer al conjunt de subproblemes.

        • Complexitat (subproblemes) < complexitat (problema)

        • Solució: serà un graf degut a que existeix la conjunció i el su cost es calcula fent sumes en les expansions conjuntives

        • Operadors: són de forma conjuntiva.

        • Nodes resolts (R) són els:

      • nodes terninals (problemes trivials o primitius)

      • nodes de tipus o (disjunció) que tenen un fill resolt.

      • nodes de tipus i (conjunció) que tenen tots els fills resolts.

        • Nodes iressolubles:

      • nodes terminals (sense fills) que no són problemes primitius (nodes queno surten a les capçaleres de les implicacions i nodes que oes troben a la base de fets).

      • nodes de tipus o en que tots els fills són irresolubles.

      • nodes de tipus i en que un dels fills és irresoluble.

        • Condició d'acabament: que el node inicial es marqui com resolt o que es determini que és iresoluble.

        • Solució: graf on l'arrel és el node incial, amb nodes i, nodes o, tots els nodes o tenen un sol fill. Cost: (node+arc) però en els node i, s suma el cost e tots els fills.

        • funció heuristica: h': node ! R (estimació del cost òptim de resoldre aquell subproblemes)

        • Nodes de tipus o: h'(n)= min [c(n,ni)+h'(ni)]

        • nodes de tipus i : h'(n) = " [c(n,ni)+h'(ni)]

        Algorisme AO*

        OBERTS ! INICIAL

        TANCATS ! NULL

        GRAF ! INICIAL

        Associar un apuntador buit a INICIAL

        Associar valor de h' a INICIAL

        mentre INICIAL_no_marcat fer

        GE ! estimar_graf(GRAF)

        NODE_ACT ! millor_node (GE " OBERTS)

        OBERTS ! OBERTS - NODE_ACT

        TANCATS ! NODE_ACT + TANCATS

        si terminal_resluble(NODE_ACT) llavors

        marcar_resolt_NODE_ACT

        rutina_etiquetatge_nodes_resolts_a_GRAF

        eliminar_d'OBERTS_nodes_si_avantpassats_resolts

        sino

        FILLS ! expandir (NODE_ACT)

        si buit(FILLS) llavors

        marcar_irresoluble_NODE_ACT

        rutina_etiquetatge_nodes_irresolubles_a_GRAF

        eliminar_d'OBERTS_nodes_si_avantpassats_irresolubles

        actualitzar_h'_dels_avantpasats_de_NODE_ACT

        sino

        associar_apuntadors_entre_NODE_ACT_i_FILLS

        associar_valor_h'_a_tots_FILLS

        actualitzar_h'_de_NODE_ACT_i_dels_avantpassats

        OBERTS ! FILLS + OBERTS

        GRAF ! FILLS + GRAF

        fsi

        fsi

        fmentre

        si resolt (INICIAL) llavors

        mostrar_graf_solució

        sino

        fracàs

        fsi

        Jocs

        Nosaltres veurem un joc com a cerca en un espai d'estats.

        • Estat: situació concreta (del joc) de la partida, i un booleà que indica a qui li toca jugar.

        L'estructura de dades del joc seria la següent:

        • Estat inicial

        • Operadors. succesors: estat! {estat}

        • Criteri d'acabament

        • Funció d'utilitzat: serveix per evaluar cada un dels estats.

        Funció=cond.favorables - cond desfavorables

        • La solució serà l'estrategia o moviments que hem de fer per guanyar.

        Tenim tres tipus d'algorismes sobre els jocs:

        • MINMAX

        • MINMAX heuristc

        • Poda Alfa-Beta (-)

        Algorisme MINMAX

        L'idea d'aquest algorisme és etiquetar els estats des de les fulles amunt segons el torn del participant:

        • Si hem d'escollir nosaltres agafem el node màxim

        • Si li toca al contrincant agafem el mínim (que seria el millor resultat per ell)

        Exemple:

        funció MinMax (joc) retorna (operador, valor, utilitzat, final)

        per cada op"joc.operadors fer

        valor[op] ! MinMaxValor(aplicar(op, joc.estat_inicial), joc)

        fper

        retorna maxim (op, valor[op])

        ffuncio

        funció MinMaxValor(estat, joc) retorna valor

        si jo.criteriFi (estat) llavors

        retorna joc.fUtilitat (estat)

        sino

        si juga(estat)='jo' llavors

        retorna Introducció a la intel-ligencia artificial # Introducción a la inteligencia artificial

        sino

        retorna Introducció a la intel-ligencia artificial # Introducción a la inteligencia artificial

        fsi

        fsi

        ffunció

        estat: tupla

        r: representació d'un estat

        juga: (jo, contrincant)

        ftupla

        Algorisme MINMAX Heuristic

        Les diferencies que hi han entre l'algorisme anterior i aquest són les següents:

        • Canviar la funció d'utilitat a funció d'evaluació (per aprofitar algun coneixement heuristic, per cada estat dona un valor que seria el cost estimat d'arribar al node solució).

        • Canviar el criteri de Fi pel criteri de Poda que indica si hem de podar o no les branques que ens queden, es adir, si les hem de mirar o no.

        Algorisme Alfa-Beta

        En aquest algorisme anem mirant si podem ignorar alguna de les branques de l'arbre de la cerca, per fer això existeixen dos paràmetres alfa i beta. Es pot veure en el següent gràfic:

        Els pares passen ,  als fills (un a un segons l'ordre d'exploració). Si estem en un fill MAX el valor d'aquest pasa al paràmetre beta del pare, i si estem en un fill MIN el valor d'aquest pasa al paràmetre alfa del pare. El criteri de poda serveix per treure els germans d'un node a partir del qual hem decidit podar.Es pot observar en el següent gràfic:

        Mirar transparencias pàgina 34 en andavant.

        funció MAXVALOR (estat, joc, , ) retorna el valor minmax de l'estat

        si CriteriPoda (estat) llavors

        retorna fEvaluació(estat)

        sino

        per cada s " suc (estat) fer

         ! MAX{, MINVALOR (s, joc, , )}

        si  "  ! retorna 

        fper

        retorna 

        fsi

        ffunció

        funció MINVALOR ( estat, joc, , ) retorna el valor minmax de l'estat

        si CriteriPoda (estat) llavors

        retorna fEvaluació(estat)

        sino

        per cada s " suc (estat) fer

         ! MIN{, MAXVALOR (s, joc, , )}

        si  "  ! retorna 

        fper

        retorna 

        fsi

        ffunció

        1

        IIA-25

        Què x y

        -Buscar y x z

        -retornar z

        Persona

        Alumnes

        Alumnes

        Telecos

        Alumnes

        informàtica

        Maria

        Pere

        Joan

        elements

        Conjunts

        Esquema d'un coneixement heretable

        -fill

        -filla

        -mare

        -pare

        -germa

        -germana

        Si condició llavors accio1

        Accio2

        .

        fsi

        Base de coneixement

        Base de coneixement

        animal

        vertebrat

        volar

        ales

        groc

        canta

        ocell

        canari

        piolin

        es_un

        es_un

        instancia_de

        pot

        capacitat de

        habilitat

        te_com_part

        color

        color de

        NODES:

        concpetes - ocell

        individus - piolin

        accions - volar

        valors - groc

        ARCS:

        relacions - es_un

        atributs -- color

        resultat

        e1

        equiplocal

        golsev

        equipVis

        golsl

        inst_de

        Joan

        100000 pts

        sou

        Joan

        sou-j

        Pere

        sou-p

        50000

        sou

        sou

        mes_gran

        valor

        sou_mes_gran

        Pere

        Joan

        A

        B

        C

        Frame slot

        Facet valor

        Facet demon if_needed

        Prioritat dins del frame

        frame

        pare

        avi

        Inst_de

        Es_un

        Prioritat dintre de la jeràrquia

        valor

        If_needed

        pare

        avi

        frame

        1

        2

        4

        3

        6

        5

        N-Herència

        Z-Herència

        5

        6

        3

        4

        2

        1

        frame

        avi

        pare

        If_needed

        valor

        Dintre del frame

        Dintre de la taxonomia

        OCELLS

        ESTRUÇ

        ELI

        OCELLS DOMESTICS

        -vola=si

        -vola=no

        Es_un

        Es_un

        Inst_de

        Inst_de

        *

        *

        MECANISME

        GENERAL

        · model declaratiu

        · Demostració de

        correctessa

        MENYS

        MENYS

        MECANISME

        ESPECÍFIC

        · model procedimental

        · correctessa?

        MENYS

        MENYS

        Expressivitat

        Eficiència

        CP

        SP

        XS/F

        Estat inicial

        0

        0

        3

        0

        0

        3

        3

        3

        1

        5

        1

        0

        0

        1

        3

        1

        0

        4

        Gerra gran

        Gerra petita

        Omplir la petita

        mj

        mi

        c(mi, mj)

        C

        mi

        mj

        K(ni, nj)

        h(ni) - h( nj)

        h(ni)

        h( nj)

        objectiu

        ni

        nj

        f=0+h'(inicial)

        c1

        f=c10+h(node)

        Objectiu

        ....

        ....

        nostre torn

        torn del contrincant

        3

        12

        8

        2

        4

        6

        14

        5

        2

        2

        2

        3

        3

        MAX

        MIN

        MAX

        (MAX)

        

        

        ....

        ....

        vi

        Si vi >  ! modificar 

        Si vi "  ! poda 

        al final retorna 

        vi

        ....

        ....

        

        

        (MIN)

        Si vi <  ! modificar 

        Si vi "  ! poda 

        al final retorna 

        A

        B

        C

        D

        E

        MAX

        MAX

        MIN

        = i inf

        = + inf

        = i inf

        = + inf /3

        (3)

        (3)

        (3)

        = i inf /3

        = + inf

        MIN

        MAX

        MAX

        E

        D

        C

        B

        A