Loco

Resolución de problemas Búsqueda

Dr. Francisco J. Ruiz Dep. ESAII

© Francisco J. Ruiz Vegas 2011

1

AGENTES
Agente

AGENTE: Elemento hardware o software elemental de la IA Entidad que percibe y actúa consecuentemente sobre el entorno [Rusell y N i 96] [R ll Norvig

percibe Función agente

actúa

© Francisco J. Ruiz Vegas 2011

2

1

AGENTES
Tipos de Agente

AGENTESBASADOS EN MODELOS Son aquellos agentes que tienen en su estado interno un modelo del mundo exterior que se va actualizando con sus percepciones. AGENTES BASADOS EN OBJETIVOS Son aquellos agentes que actúan con la intención de alcanzar sus metas. AGENTES BASADOS EN UTILIDAD Son agentes que disponen de una función de utilidad asociadas a un estado o secuencias de estado. Actúan guiados por estafunción de utilidad utilidad. AGENTES QUE APRENDEN Son agentes que pueden modificar su función de agente a partir de sus percepciones pasadas.

© Francisco J. Ruiz Vegas 2011

3

RESOLUCIÓN DE PROBLEMAS
Resolución de problemas

Estado inicial Función sucesor (devuelve los posibles estados siguientes) Espacio de estados (conjunto de todos los estados alcanzables) Estado objetivo Camino(secuencia de estados que comienza en el estado inicial)

Solución

Una solución de un problema es un camino q p p que parte del estado inicial y acaba en un estado objetivo

© Francisco J. Ruiz Vegas 2011

4

2

FORMALIZACIÓN DE PROBLEMAS
Formulación de un problema: Ajedrez

Estado inicial:

Función sucesor. Movimientos válidos en el juego

Espacio de estados. El conjunto de todoslas dispociones posibles de las piezas en el tablero. Cota superior: 64*63*...*331050

Estado objetivo. Jaque mate al contringante y evitarlo de éste. Camino. Una partida completa

© Francisco J. Ruiz Vegas 2011

5

FORMALIZACIÓN DE PROBLEMAS
Ejemplo: Jarras de agua

Se tienen dos jarras de agua, una de 4l y otra de 3l sin escala de medición. Se desea tener 2l de agua en la jarra de 4l.Las siguientes operaciones son válidas: * llenar totalmente una jarra, * tirar totalmente el agua de una jarra, *pasar agua de una jarra a otra hasta que la primera esté vacía o hasta que la segunda esté llena.

4l

3l

© Francisco J. Ruiz Vegas 2011

6

3

FORMALIZACIÓN DE PROBLEMAS
Espacio de estados

El espacio de estados se define como { (X,Y)/ X son los litros en la jarra de4l con 0 (X, 0)

5. Pasar agua de la jarra de 4l a la jarra de 3l hasta llenarla: Si (X,Y) AND X>0 AND X+Y>=3 => (X-(3-Y),3) 6. Pasar agua de la jarra de 3l a la jarra de 4l hasta llenarla: Si (X,Y) AND Y>0 AND X+Y>=4 => (4, Y-(4-X)) 7. Pasar toda el agua de la jarra de 4l a la jarra de 3l: Si (X,Y) AND X>0 AND X+Y (0,X+Y) 8. Pasar toda el agua de la jarra de 3l a la jarra de 4l: Si (X,Y) AND Y>0AND X+Y (X+Y,0)

© Francisco J. Ruiz Vegas 2011

8

4

FORMALIZACIÓN DE PROBLEMAS
Solución

(0,0) => (0,3) => (3,0) => (3,3) => (4,2) => (0,2) => (2,0) reglas 2 8 2 6 3 8

Otra solución

(0,0) => (4,0) => (1,3) => (1,0) => (0,1) => (4,1) => (2,3) => (2,0) reglas 1 5 4 7 1 5 4

© Francisco J. Ruiz Vegas 2011

9

FORMALIZACIÓN DE PROBLEMAS
Ejemplo: Monjes y caníbalesExisten 3 monjes y 3 caníbales en el margen Oeste de un río. Existe una canoa con capacidad para dos personas como máximo. Se desea que los seis pasen al margen Este del río, pero hay que considerar que no debe haber más caníbales que monjes en ningún sitio porque entonces l íb l j i ú iti t los caníbales se comen a los monjes. Además, la canoa siempre debe ser conducida por alguien.

© Francisco J.Ruiz Vegas 2011

10

5

FORMALIZACIÓN DE PROBLEMAS
Espacio de estados

{(Mo, Co, Me, Ce, C) / *Mo es el número de monjes en el margen oeste con 0 (3,0,0,3,E) => (3,1,0,2,O) => (1,1,2,2,E) => (2,2,1,1,O) => (0,2,3,1,E) => (0,3,3,0,O) => (0,1,3,2,E) => (0,2,3,1,O) =>(0,0,3,3,E) (0 2 3 1 O) =>(0 0 3 3 E)

¿Es posible mejorar la notación? Ver actividad 2

© Francisco J. Ruiz Vegas 2011...