Tema 2: El concepto de AGENTE.
Arquitecturas
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
Objetivos
Conocer el concepto de agente inteligente y el ciclo de vida percepcin, decisin y actuacin. Conocer las arquitecturas posibles para construir un agente. Conocer el concepto de Sistema MultiAgente (SMA) y los problemas que conlleva Adquirir las habilidades bsicas para construir sistemas capaces de resolver problemas mediante tcnicas de IA.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
Objetivos
Conocer el concepto de agente inteligente y el ciclo de vida percepcin, decisin y actuacin. Adquirir las habilidades bsicas para construir sistemas capaces de resolver problemas mediante tcnicas de IA. Entender que la resolucin de problemas en IA implica definir una representacin del problema y un proceso de bsqueda de la solucin. Conocer la representacin de problemas basados en estados (estado inicial, objetivo y espacio de bsqueda) para ser resueltos con tcnicas computacionales. Conocer las tcnicas ms representativas de bsqueda no informada en un espacio de estados (en profundidad, en anchura y sus variantes), y saber analizar su eficiencia en tiempo y espacio.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
Estudia este tema en
Nils J. Nilsson, Inteligencia Artificial: Una nueva sntesis, Ed. Mc Graw Hill, 2000. pp. 17-32, 63-74, 103-122, 147-162
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
Contenido
Diseo de un agente reactivo: arquitecturas de agentes Agentes reactivos con memoria Diseo de un agente deliberativo: bsqueda Ejemplos
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
Concepto de Agente
Un Agente es cualquier sistema (de ordenador) situado en algn entorno, que es capaz de realizar acciones de forma autnoma y que es flexible para lograr los objetivos planteados.
El agente recibe entradas sensoriales de un entorno en donde est situado y realiza acciones que cambian dicho entorno El sistema es capaz de actuar sin la intervencin directa de los humanos y tiene control sobre sus propias acciones y estado interno
Tema 1: Introduccin a la Inteligencia Artificial Inteligencia Artificial 6
Agentes inteligentes (racionales)
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
Agentes e Inteligencia Artificial
Inteligencia Artificial: mbito cientifico/tcnico dedicado a la construccin de agentes que exhiban comportamiento inteligente, (RACIONALIDAD) Los agentes permiten dar una nueva forma de mostrar la Inteligencia Artificial
Tema 1: Introduccin a la Inteligencia Artificial Inteligencia Artificial 8
Caractersticas de los Agentes
*Capacidad Estmulo -Respuesta: el agente debe percibir el entorno y responder de una forma temporal a los cambios que ocurren en dicho entorno, *Pro-activo: los agentes no deben simplemente actuar en respuesta a su entorno, deben de ser capaces de exhibir comportamientos dirigidos a lograr objetivos, y tomar la iniciativa cuando sea apropiado, *Autonomia :El sistema es capaz de actuar sin la intervencin directa de los humanos y tiene control sobre sus propias acciones y estado interno Capacidad Social: los agentes deben de ser capaces de interactuar, cuando sea apropiado, con otros agentes artificiales o humanos para completar su propio proceso de resolucin del problema y ayudar a otros con sus actividades. *: Caracteristicas indispensables
Tema 1: Introduccin a la Inteligencia Artificial Inteligencia Artificial 9
Sistemas basados en agentes
Un Sistema Basado en Agentes ser un sistema en el que la abstraccin clave utilizada es precisamente la de agente Sistemas multi-agente: un sistema diseado e implementado con varios agentes interactuando Los sistemas multi-agente son interesantes para representar problemas que tienen
mltiples formas de ser resueltos, mltiples perspectivas y/o mltiples entidades para resolver el problema
Tema 1: Introduccin a la Inteligencia Artificial Inteligencia Artificial 10
Interaccin entre agentes
Cooperacin: trabajar juntos para resolver algo Coordinacin: organizar una actividad para evitar las interacciones perjudiciales y explotar las beneficiosas Negociacin: llegar a un acuerdo que sea aceptable por todas las partes implicadas
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
11
Sistemas Multi-Agente
Inteligencia Artificial Distribuida
Resolucin de Problemas Distribuida Sistemas Multi-Agente
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
12
Sistemas Multiagente
SMA: una red ms o menos unida de resolvedores de problemas que trabajan conjuntamente para resolver problemas que estn ms all de las capacidades individuales o del conocimiento de cada uno de ellos Resolvedor = agente (autnomo y de naturaleza heterognea)
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
13
Caractersticas de un SMA
Cada agente tiene informacin incompleta, o no todas las capacidades para resolver el problema, as cada agente tiene un punto de vista limitado. No hay un sistema de control global. Los datos no estn centralizados. La computacin es asncrona.
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
14
Cooperacin y Negociacin
Cooperacin: herramienta fundamental en la formacin de equipos (p.e. ROBOCUP)
Negociacin: coordinacin y resolucin de conflictos
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
15
Arquitecturas de Agentes
POR SU TOPOLOGIA Arquitecturas horizontales Arquitecturas verticales Arquitecturas hbridas
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
16
Arquitecturas horizontal y vertical
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
17
Arquitecturas de Agentes
POR SU NIVEL DE ABSTRACCIN Arquitecturas deliberativas Arquitecturas reactivas Arquitecturas hbridas
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
18
Arquitecturas deliberativas
Sistema de smbolos fsicos: un conjunto de entidades fsicas (smbolos) que pueden combinarse para formar estructuras, y que es capaz de ejecutar procesos que operan con dichos smbolos de acuerdo a conjuntos de instrucciones codificadas simblicamente. La hiptesis de sistema de smbolos fsicos dice que tales sistemas son capaces de generar acciones inteligentes. Agente deliberativo: aquel que contiene un modelo simblico del mundo explcitamente representado, y cuyas decisiones se realizan a travs de un razonamiento lgico basado en emparejamientos de patrones y manipulaciones simblicas.
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
19
Arquitecturas deliberativas
El problema de trasladar en un tiempo razonable para que sea til el mundo real en una descripcin simblica precisa y adecuada El problema de representar simblicamente la informacin acerca de entidades y procesos complejos del mundo real, y como conseguir que los agentes razonen con esta informacin para que los resultados sean tiles Los agentes suelen tener estructura vertical
Tema 1: Introduccin a la Inteligencia Artificial Inteligencia Artificial 20
Arquitecturas Reactivas
Una arquitectura reactiva es aquella que no incluye ninguna clase de modelo centralizado de representacin simblica del mundo, y no hace uso de razonamiento complejo
El comportamiento inteligente puede ser generado sin una representacin explcita de la clase que la IA simblica propone El comportamiento inteligente puede ser generado sin un razonamiento abstracto explcito de la clase que la IA propone La inteligencia es una propiedad emergente de ciertos sistemas complejos
Tema 1: Introduccin a la Inteligencia Artificial Inteligencia Artificial 21
Arquitecturas Reactivas
La inteligencia real est situada en el mundo, y no es sistemas incorpreos tales como la demostracin de teoremas o los sistemas expertos El comportamiento inteligente surge como el resultado de la interaccin del agente con su entorno. La inteligencia est en el ojo de espectador no es una propiedad innata ni aislada Los agentes suelen tener arquitectura horizontal
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
22
Arquitecturas Hbridas
Estructura vertical Estructuras mixtas
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
23
Ejemplo de agentes reactivo: un robot que recorre un pasillo
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
24
Ejemplo de agente deliberativo: Problema del viajante de comercio
Tema 1: Introduccin a la Inteligencia Artificial
Inteligencia Artificial
25
Ejemplo de arquitectura hbrida
Agente capaz de cambiar la rueda de un coche: Sacar gato deliberacin Quitar rueda pinchada Sacar rueda nueva Poner rueda nueva Quitar gato reaccin Guardar gato
Tema 1: Introduccin a la Inteligencia Artificial Inteligencia Artificial 26
Diseo de un agente reactivo
Percepcin y Accin: El agente reactivo percibe su entorno a travs de sensores.
Entradas de Sensores Procesamiento de entradas Representacin interna perceptual
Procesa la informacin percibida y hace una representacin interna de la misma. Escoge una accin, entre las posibles, considerando la informacin percibida. Transforma la accin en seales para los actuadores y la realiza.
Seleccin de accin
Procesamiento de salidas Accin
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
27
Diseo de un agente reactivo
Ejemplo: Supongamos un robot en un mundo dividido en cuadrculas. El robot puede percibir si las 8 casillas vecinas estn libres o no, con un sensor si por cada casilla i. El objetivo del robot es ir a una pared y seguir su permetro indefinidamente. Tiene 4 posibles movimientos (de 1 casilla cada uno): Ir a Norte, Sur, Este u Oeste. No se permite que el entorno contenga pasillos estrechos (aquellas casillas rodeadas por dos o ms obstculos a ambos lados).
Tema 2: Estrategias de bsqueda no informada Inteligencia Artificial 28
Representaciones del mundo
Representaciones del mundo:
modelos icnicos modelos basados en caractersticas
El mundo espacial cuadriculado
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
29
Diseo de un agente reactivo
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
30
Representacin
Sensores: S1 S8 S7 S6 S2 S3 S4 S5
Usaremos un vector de 8 componentes. Cada componente i vale 0 si el sensor si no detecta obstculo y vale 1 si lo detecta. Ejemplo posicin A:
Movimientos:
A B
A=
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
31
Movimientos posibles
NORTE: mueve el robot una celda hacia arriba ESTE: mueve el robot una celda a la derecha SUR: mueve el robot una celda hacia abajo OESTE: mueve el robot una celda a la izquierda
TRABAJO DEL DISEADOR:
desarrollar una funcin definida sobre las entradas sensoriales que seleccione la accin apropiada en cada momento para llevar a cabo con xito la tarea del robot.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
32
Proceso en dos fases
Procesamiento perceptual Fase de clculo de la accin
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
33
Percepcin y accin
Percepcin:
Accin:
si todas las caractersticas son cero, moverse al norte si x1=1 y x2=0, moverse al este si x2=1 y x3=0, moverse al sur si x3=1 y x4=0, moverse al oeste si x4=1 y x1=0, moverse al norte
Inteligencia Artificial 34
Tema 2: Estrategias de bsqueda no informada
Algunas tcnicas para agentes reactivos
Agentes en una tabla, Sistemas de produccin, Redes Neuronales, Arquitecturas de subsuncin, Etc.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
35
Sistemas de Produccin
c1a1 c2a2 ciai
cmam
en donde Ci es una funcin booleana definida sobre el vector de caractersticas, habitualmente una conjuncin de literales booleanos.
Inteligencia Artificial 36
Tema 2: Estrategias de bsqueda no informada
Sistemas de Produccin
Ejecucin del sistema de produccin: 1. Se selecciona la primera regla y se comprueba si se cumple su condicin. En caso contrario, se contina con la siguiente hasta que se encuentre una regla con condicin con valor 1. 2. La accin de la primera regla encontrada cuya condicin sea 1 es la que se ejecuta. Su accin puede ser: 2.1. La ejecucin de una o varias acciones primitivas 2.2. Una llamada a otro sistema de produccin 3. Accin por defecto: La ltima regla de produccin del sistema debe ser del tipo 1A, para ejecutar una accin en caso de que ninguna de las reglas anteriores cumpla su condicin de ejecucin
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
37
Tarea de seguimiento de bordes
Ejemplo de proceso sin fin
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
38
Tarea llevar al robot a una esquina cncava
Ejemplo de proceso con objetivo
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
39
Redes
Unidad Lgica con Umbral
Red neuronal: red de unidades lgicas con umbral
Tema 2: Estrategias de bsqueda no informada Inteligencia Artificial 40
Arquitectura de subsuncin
La arquitectura de subsuncin consiste en agrupar mdulos de comportamiento. Cada mdulo de comportamiento tiene una accin asociada, recibe la percepcin directamente y comprueba una condicin. Si esta se cumple, el mdulo devuelve la accin a realizar. Un mdulo se puede subsumir en otro. Si el mdulo superior del esquema se cumple, se ejecuta este en lugar de los mdulos inferiores.
Tema 2: Estrategias de bsqueda no informada Inteligencia Artificial 41
Arquitectura de subsuncin
Percepcin Calcular Accin Calcular Accin Calcular Accin Calcular Accin Accin
Percepcin Seales Sensoriales Percepcin Percepcin
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
42
Agentes reactivos con memoria
Limitaciones del sistema sensorial de un agente. Mejorar la precisin teniendo en cuenta la historia sensorial previa: sistemas con memoria
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
43
Agentes reactivos con memoria
la representacin de un estado en el instante t+1 es funcin de la entradas sensoriales en el instante t+1, la representacin del estado en el instante anterior t y la accin seleccionada en el instante anterior t.
Vector de catactersticas Xt
1 1 0
Entrada sensorial
Procesamiento perceptual Xt-1 at-1 Memoria
0 . . . 1
Seleccin de Accin at Accin
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
44
Ejemplo
Usaremos las caractersticas wi=si i=2,4,6,8 y las caractersticas restantes del siguiente modo
w1=1 si en el instante anterior w2=1 y el robot se movi al este w3=1 si en el instante anterior w4=1 y el robot se movi al sur w5=1 si en el instante anterior w6=1 y el robot se movi al oeste w7=1 si en el instante anterior w8=1 y el robot se movi al norte
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
45
Implementacin de la memoria con representaciones icnicas
Adicionalmente el robot podra utilizar otras estructuras de datos: matriz que almacene el mapa con las casillas libres u ocupadas en el momento en el que se percibieron.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
46
Campo de potencial artificial
Componente atractiva:
Componente repulsiva:
Potencial:
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
47
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
48
Implementacin de la memoria con sistemas basados en pizarras
Son extensiones de los sistemas de produccin. En el agente existen varios programas denominados Mdulos de Conocimiento (MC), formados por una parte de condicin y otra parte de accin. Existe una memoria comn a todos los MC denominada pizarra.
Informacin Sensorial MC1 MC4
MC2
PIZARRA
MC5
...
MC3 Efectos de salida MCn
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
49
Implementacin de la memoria con sistemas basados en pizarras
Cada MC es experto en una parte concreta del problema a resolver. Cuando se cumple su condicin, un MC puede actualizar la pizarra, realizar una accin concreta o ambas. Es necesario implementar un programa de resolucin de conflictos cuando dos MCs pueden actuar simultneamente, decidiendo cul acta y cul no o, en su caso, el orden de ejecucin de ambos.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
50
Implementacin de la memoria con sistemas basados en pizarras
La actualizacin de una parte de la pizarra correspondiente a un MC puede desencadenar la ejecucin de otros MCs. La pizarra, por tanto, alberga la solucin que se est construyendo conforme al objetivo general del agente.
Informacin Sensorial MC1 MC4
MC2
PIZARRA
MC5
...
MC3 Efectos de salida MCn
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
51
Implementacin de la memoria con sistemas basados en pizarras
Ejemplo: Robot para salir de un laberinto.
La pizarra contiene la informacin leda desde los sensores (que puede ser imperfecta debido a errores de los mismos). Tambin contiene un mapa del laberinto, que puede tener errores debido a previas lecturas errneas de los sensores, junto con la posicin del robot en el mapa. Contamos con 4 mdulos MC de accin de movimiento (Norte, Sur, Este, Oeste). Contamos con 2 MC adicionales: Rellenador de huecos para rellenar el mapa del laberinto. Filtro sensorial para arreglar errores en el mapa.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
52
Agentes reactivos con memoria
Implementacin de la memoria con sistemas basados en pizarras. Ejemplo: Agente en el mundo cuadriculado.
MC Norte MC Oeste
Mapa del entorno
Rellenador de huecos
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 0 0 ? ? ? ? ? 1 1 0 ? ? ? 1 0 0 0 0 ? ? ?
En el ejemplo, el filtro sensorial detecta un error entre la percepcin y el estado del mundo.
Accin
Entradas Sensoriales
Filtro sensorial
? R 0 0 0 0 ? ? ? 0 0 1 1 ? ? ? ? ? ? ? ? ? ? ?
1 0 0 ? R 1 1 0 0
MC Este
MC Sur
Percepcin
El rellenador de huecos usa la informacin sensorial para rellenar las nuevas casillas desconocidas por el robot.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
53
Ejemplo de agente reactivo: un robot que recorre un pasillo
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
54
Ejemplos de agente reactivo: un agente que juega al tres en raya
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
55
Caractersticas de los agentes reactivos
Se disean completamente y por tanto es necesario anticipar todas las posibles reacciones para todas las situaciones
Realizan pocos clculos Almacenan todo en memoria
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
56
Diseo de un agente deliberativo
El agente dispone de un modelo del mundo en el que habita, El agente dispone de un modelo de los efectos de sus acciones sobre el mundo, El agente es capaz de razonar sobre esos modelos para decidir que hacer para conseguir un objetivo.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
57
El espacio de estados
Modelo del mundo/Estado del agente: representacin Espacio de estados Operadores de cambio de estado: acciones del agente. Acciones del agente: representacin
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
58
La bsqueda en un espacio de estados
Problema: El agente se encuentra en un estado inicial (origen, de partida, etc), Se desea alcanzar un estado final (meta, objetivo, etc.) Bsqueda en el espacio de estados Resolucin del problema mediante anlisis de las distintas acciones
Tema 2: Estrategias de bsqueda no informada Inteligencia Artificial 59
La bsqueda en un espacio de estados
A la secuencia de acciones que lleva al agente desde un estado inicial hasta un estado destino se denomina plan. La bsqueda de dicha secuencia se denomina planificacin. En este curso veremos modelos elementales de planificacin.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
60
La bsqueda en un espacio de estados
Representacin en forma de grafo (grafo de estados) : Nodo: estado = estructura de datos Arco: asociado a una accin. Une un nodo (estado) con el nodo (estado) resultante de la accin. Bsqueda en espacio de estados: bsqueda en grafos
Tema 2: Estrategias de bsqueda no informada Inteligencia Artificial 61
Bsqueda en Grafos
Grafos explcitos: nodos y arcos que unen dichos nodos. Grafos implcitos: reglas de representacin de estados y reglas de cambio de estado por medio de operadores.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
62
Bsqueda en espacios de estados
Pequeo: se puede representar la totalidad del espacio de estados con un grafo explicito y puede buscarse un camino que nos lleve desde el estado inicial hasta el estado objetivo.
Grande : se va generando un grafo explcito segn
se va resolviendo el problema en cada paso. Tcnicas de busqueda. Grafo del Espacio vs. Grafo de la busqueda ( arbol)
Tema 2: Estrategias de bsqueda no informada Inteligencia Artificial 63
Pequeo: El mundo de bloques
Supongamos un mundo compuesto por una mesa sobre la que hay tres bloques: A, B, C. En cada momento, se conoce el estado del sistema. Lo modelamos como una lista de listas de (objetos sobre objetos): ((A),(BC)); ((AB),(C))
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
64
El mundo de los bloques
En cada momento, se dispone de la operacin mover(x,y) para poner x sobre y, donde x={A, B, C} e y={A, B, C, Suelo}. Asumimos que se descartan los operadores imposibles mover(A,A), mover(B,B), mover(C,C), etc., para cada estado.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
65
El mundo de los bloques
((A),(B),(C))
Mo ver (A ,C)
B) , A ( ver o M
Mov er(C M ,B) ov e
r(C ,A )
Mover(B,A)
,C) (B ver Mo
((AB),(C))
((A),(CB))
((B),(AC)) ((BA),(C)) ((BC),(A)) ((CA),(B))
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
66
El mundo de bloques
Estado inicial: todos los bloques estn directamente sobre la mesa: ((A), (B), (C)) Estado objetivo: A quede sobre B, B quede sobre C, y C est en la mesa:((ABC)).
A B C ((ABC))
A B C ((A),(B),(C))
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
67
Espacio (Grafo) de estados en el mundo de bloques
((BAC)) ((CAB)) ((B),(AC))
C) ) ((BAC)) , B m( (B,S m ((CA),(B))
m(A ,B) m(A,C )
) ,S (B m A) B, m(
m (C ,S )
((BA),(C))
m(A ((AB),(C)) m( ,B) A,S)
((A),(B),(C))
) ,S B ( m
m( B, A)
m(C,B) m(B,A)
m( C,A m( ) C, S)
) ,C S) A , m( m(A
((ACB))
,A) m(C ,B) m(C
m(C,B)
Tema 2: Estrategias de bsqueda no informada
) C,A m(
((CBA))
,C) m(A ) S A, m(
,B) ((A),(CB)) m(C ,S) m(C
S) B, m( C) B, m(
((A),(BC))
m(A,B)
m(A,S)
m(C,S)
((ABC))
Inteligencia Artificial
68
Bsqueda
Estado Objetivo
Estado Objetivo
Estado Objetivo
1 2 2
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
69
Bsqueda
Ejemplo de planificacin en el mundo de los bloques: Planificacin de acciones.
Estado Inicial: ((ABC))
0 3 Estado Objetivo 3 4
1 2 2
4 3
Accin 1: Mover(A, Suelo) Accin 2: Mover(B, Suelo) Accin 3: Mover(A, C) Accin 4: Mover(B, A) Estado objetivo alcanzado: ((BAC))
3 Estado Inicial
Propagacin de movimientos: Recorrido en anchura. Bsqueda del plan: Recorrido en profundidad.
Inteligencia Artificial 70
Tema 2: Estrategias de bsqueda no informada
Ejemplo de agente deliberativo: Problema del mono y los pltanos
Un mono est en la puerta de una habitacin. En el centro de la habitacin hay un pltano colgado del techo, pero no puede alcanzarle desde el suelo. En la ventana de la habitacin hay una caja, que el mono puede mover y a la que puede encaramarse para alcanzar el pltano. El mono puede realizar las siguientes acciones: desplazarse de la puerta al centro, del centro a la ventana y viceversa; empujar la caja a la vez que se desplaza; subirse y bajarse de la caja; coger el pltano. El problema consiste en encontrar una secuencia de acciones que permita al mono coger el pltano.
Tema 2: Estrategias de bsqueda no informada Inteligencia Artificial 71
Problema del mono y los pltanos
Como estado se puede utilizar una lista con cuatro elementos (X, Y, W, Z) donde:
X: posicin del mono en la habitacin (puerta, centro, ventana). Y: situacin del mono respecto a la caja (suelo, caja). W: posicin de la caja en la habitacin (puerta, centro, ventana). Z: posesin del pltano (tiene, no_tiene).
Para describir todas las posibles acciones del mono, se necesitan seis operadores: andar, empujar, subir, bajar, coger y soltar. Sin embargo, para el problema que nos ocupa, son suficientes cuatro operadores: andar, empujar, subir y coger; nos limitaremos a estos 4 operadores . El operador andar se puede definir como: para indicar que el mono se desplaza de la posicin X a la posicin Y. El estado se puede representar por la estructura estado(X, Y, W, Z), que simplemente refleja la definicin del estado.
(X, suelo, W, Z) -------> (Y, suelo, W, Z)
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
72
Ejemplo de agente deliberativo: Problema del viajante de comercio
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
73
Ejemplo de agente deliberativo: Mapa de Carreteras
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
74
Ejemplo de un agente deliberativo: Problema de la aspiradora
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
75
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
76
Problema de la aspiradora
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
77
Problema de la aspiradora Russell Norvig
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
78
Espacio de estados Grande
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
79
Espacio de estados Grande
Estado: configuracin del tablero
una matriz 3x3 con entradas del 0 al 8 un vector de 9 trminos de 0 a 8.
Movimientos:
Mover casillas adyacentes al hueco Mover hueco a casillas adyacentes (4 pos. Max.)
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
80
Espacio de estados Grande
Numero de estados: 9! , en realidad 9!/2 9!=362.880 Imposible representar explcitamente todo el grafo de estados. Necesidad de recurrir al grafo implcito y explicitar solo el grafo o rbol de bsqueda. Necesidad de tcnicas de bsqueda.
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
81
Tcnicas de Bsqueda
Reglas Acciones Operadores Base de Conocimiento
Estrategia de Control
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
82
Estrategias de control (Russelll-Norvig)
Escoger el nodo a expandir, Escoger como expandirlo. Debe producir cambios Debe ser sistemtica Debe garantizar construir la solucin
Tema 2: Estrategias de bsqueda no informada
Inteligencia Artificial
83
Rendimiento de una estrategia de Control
Completitud: encuentra una solucin(si existe)? Optimalidad: Encuentra una solucin optima en algun sentido? Complejidad en tiempo, Complejidad en espacio, irrevocable vs tentativa Costo de la bsqueda, Costo total.
Tema 2: Estrategias de bsqueda no informada Inteligencia Artificial 84
Tipos de busqueda
Busqueda sin informacin: El siguiente nodo a expandir se escoge sin emplear conocimiento explicito sobre la distancia entre el nodo en curso y el objetivo. Busqueda heuristica: El siguiengte nodo a expandir emplea algun tipo de informacin para guiar la busqueda
Tema 3: Mtodos de bsqueda heurstica
Inteligencia Artificial
85
