Unidad1

Universidad Nacional de Ingeniería Recinto Universitario Simón Bolívar RUSB

Unidad I : Métodos de Búsqueda Integrantes. •Nadir Antonio Soza Solís •Darling Palacios Laguna •Jacquelin Quezada Reyes. •Xaviera Sequeira Franco. •Ledy Pérez Jiménez.

2005-21410. 2005-20887. 2005-20408. 2005-21211. 2005-20808.

Docente: Ing. Alberto Silva. 05 de Mayo del 2009

Introducción Durante el desarrollo de la exposición conoceremos los campos en el cual se desarrolla la inteligencia artificial, el diseño y arquitectura de los agentes, así como los arboles y grafos. Además explicaremos los algoritmos de búsqueda (Primero el mejor, Costo Unitario, A*, Primero en profundidad y primero en anchura) con y sin lista de expandidos / visitados/ estricta y admisibilidad de la heurística.

Objetivo General  Dar a conocer a los alumnos los diferentes tipos de algoritmos de búsqueda así como el comportamiento de cada uno de ellos. Objetivos Específicos.  Conocer la definición de Inteligencia artificial, agente y su ambiente.  Explicar el funcionamiento de cada uno de los algoritmos de búsqueda en el aula de clases.  Dominar los algoritmos de búsqueda.  Identificar los diferentes tipos de heurística.

Qué es Inteligencia Artificial? Modelo computacional del comportamiento humano?(Turing)

Programas que parecen (externamente) humanos Modelo computacional del proceso de “pensamiento” humano?(neurociencia,

visión, cognición)

Programas que operan (internamente) la forma en que los humanos piensan. Sistemas computacionales que se comportan inteligentemente?(humano

o no) Qué significa comportamiento inteligente?

Agentes Son software que obtienen información acerca de un ambiente y realizan acciones basados en esa información. Un robot Un programa de compras por la web Una fábrica Un sistema de control de tráfico El agente y el ambiente Cómo comenzamos a formalizar el problema de construir un agente? Haciendo una dicotomía entre el agente y el ambiente. No es una idea aceptada por todos el hacer dicotomía, pero ayuda porque evita contemplar todas las posibilidades. percepciones

agen te

accione s

ambient e

Modelo del mundo A – el espacio de acciones ( puede hacer el agente) P – el espacio de percepciones(percibe y actualiza su estado) E - el ambiente: A*  P(mapa de secuencias de acciones) Alternativamente, se define: S – el estado interno [puede no ser visible] La función percepción: S  P(qué percibe) Función de transición: S x A  S(cuál será el próximo estado)

s

p

Función Percepción

Mundo dinámico

a

Diseño de un agente

U – función de utilidad: S lR (o S* lR) El problema del diseño del agente: Encontrar P*  A Mapeo de secuencias de percepciones a acciones. Maximizar la utilidad del resultado de la secuencia de estados.(cada acción mapea de un estado al próximo) Racionalidad

Un agente racional realiza acciones que cree será lo mejor para alcanzar sus meta. La racionalidad es diferente a omnisciencia .

La racionalidad es diferente a éxito.

Clases de ambientes •Accesible (versus Inaccesible)[observable]

Puede ver Ud.. directamente el estado del mundo?

•Determinístico (vs. estocástico) Hay un mapa de acción....?

•Episódico (vs. Secuencial)

La decisión presente puede afectar las decisiones futuras?

•Estático (vs. Dinámico)

Puede el mundo cambiar mientras ud. esta pensando?

•Discreto (vs. Continuo) ( tutor interactivo / taxista)

Como es la forma en que se manejan el tiempo, las percepciones y acciones? Discretas(como los enteros) o continuos (como reales).

Estructuras de los agentes

Agente reflexivo (“o reactivo”) No tiene memoria p

a

Que se puede resolver de esta forma? Ambientes accesibles

Backgammon Desplazarse por un pasillo Agente con memoria

Estado memoria/estimador Que escogiendo recordar de la historia de las percepciones? Mapea lo que sabia antes, lo que percibe y lo que usted hizo, con lo que usted sabe ahora.

Ejemplos de diversos tipos de agentes Tipo de agente

Percepciones

Acciones

Metas

Ambiente

Sistema para diagnóstico

Síntomas, evidencias y respuestas del paciente

Preguntas pruebas,

Paciente saludable, reducción al

Paciente, hospital

tratamientos

mínimo de costos

Sistema para el análisis de imágenes del satélite

Pixeles de intensidad y colores diversos

Imprimir una clasificación de la escena

Clasificar correctamente

Imágenes enviadas desde un satélite en orbita

Controlador de refinería

Lecturas de temperatura y presión

Abrir y cerrar válvulas, ajustar temperaturas

Lograr pureza, rendimiento y seguridad máxima

Refinería

Asesor interactivo de inglés

Palabras escritas a máquina

Ejercicios impresos,sugeren cias y correcciones

Que el estudiante obtenga la máxima calificación en una prueba

Grupo de estudiantes

medico

Búsquedas Por qué buscar? •La búsqueda permite explorar alternativas •Informada (heurística) vs. No informada (ciega) •Cualquier camino vs. El camino óptimo •Implementación y desempeño Árboles y grafos

Paradigmas para resolver problemas. ¿Que son los estados(los aspectos relevantes del problema)?

Organización de piezas ( un plan de montaje) Ubicación de camiones(plan de distribución de paquetes) Ciudad(plan de un viaje) Conjunto de datos (ej. Para probar un teorema de geometría)

¿Cuales son las acciones(operadores)?(determinístico y discreto) Montar dos piezas Mover un camión a una nueva posición Volar a una nueva ciudad Aplicar el teorema ¿Cual es la prueba de meta?(condiciones para el éxito) Todas las piezas en su lugar Todos los paquetes enviados Alcanzar la ciudad de destino Derivar datos finales

Búsqueda en grafo como búsqueda en árbol •Los árboles son grafos dirigidos sin ciclos y con nodos que tienen <= 1 padre. •Podemos cambiar el problema de la búsqueda en grafo por el problema de la búsqueda en árbol: Reemplazando los enlaces sin dirección por 2 enlaces dirigidos Evitando ciclos en el camino(mantener un registro de los nodos visitados)

Clases de Búsqueda

Clase

Nombre

Operación

Cualquier camino Primero en profundidad Exploración sistemática de todo el No informado Primero en anchura árbol hasta que la meta sea encontrada

Cualquier camino Informado

Primero el mejor

Usa mediciones heurísticas en cada estado ej.: distancia estimada al

objetivo

Optimo No informado Optimo Informado

Costo Uniforme A*

Usa medidas del camino. Encuentra el camino “ mas corto” sumando los pesos. Usa mediciones de longitud del camino y heurística. Encuentra el camino más corto

Implementando las estrategias de búsqueda •Primero en profundidad Tome el primer elemento de Q Agregue las extensiones del camino al frente de Q •Primero en anchura Tome el primer elemento de Q Agregue las extensiones del camino al final de Q

Terminos •Visitados –un estado M es visitado cuando un camino a M se agrega a Q. En general, un estado se dice que ha sido visitado, si ha sido colocado en un nodo de búsqueda en Q. La intuición es que lo hemos “visitado” brevemente para ubicarlos en Q, pero aun no le haya examinado cuidadosamente. •Expandido – un estado M será expandido cuando sea el estado de un nodo de búsqueda que es sacado de Q. En este punto, los descendientes de M son visitados (si los hay) y el camino a M es expandido para elegir el descendiente.En principio, un estado puede ser expandido múltiples veces. Algunas veces nos referiremos, como siendo expandido, al nodo de búsqueda que lleva a M (en vez de solo M) . De todos modos, una vez que un nodo ha sido expandido, no necesitaremos expandirlo de nuevo. De hecho lo descartaremos de Q. Esta distinción es clave en nuestra discusión sobre los diferentes algoritmos de búsqueda; estúdielo cuidadosamente

Heurística- La palabra generalmente se refiere a algo que puede ser útil en algunos casos pero no siempre. Generalmente se usa como contraste con “garantizado” u “optimo”. Función heurística- Una función definida sobre un estado-nodo que puede ser útil en guiar la búsqueda pero la cual no garantiza obtener el resultado deseado. Usar ésta función puede ayudarnos a encontrar, en promedio, la meta en menor tiempo. Distancia estimada a la meta: Este tipo de función heurística depende del estado y la meta. El ejemplo clásico es la distancia en línea-recta usada como un estimación para la distancia actual en una red de carretera. Este tipo de información puede ayudar a incrementar la eficiencia de una búsqueda.

Implementando las estrategias de búsqueda

•Primero en profundidad Tome el primer elemento de Q Agréguelo al frente de Q

•Primero en anchura

Tome el primer elemento de Q Agréguelo al final de Q

•Primero el mejor Tome “el mejor” (medido por el valor heurístico del estado) elemento de Q Agregue las extensiones del camino en cualquier lugar de Q(puede ser más eficiente mantener ordenada Q de alguna forma para que resulte mas fácil encontrar el “mejor”)

Primero en profundidad

Primero en profundidad (sin visitados)

Primero en anchura Tome el primer elemento de Q. Agregue el camino expandido al final de Q

Primero en anchura (sin lista de visitados)

Primero el mejor

Costo uniforme Como primero el mejor excepto porque usa la “longitud total” (costo) de un camino en vez del valor heurístico del estado. Cada trayecto del camino tiene una “longitud” o “costo” ( el cual es siempre mayor que 0) Queremos “acortar” o “minimizar el costo” del camino.

Costo uniforme (con lista estricta de expandidos)

S-A : 4 (longitud 2 + heurística 2) S-A-D: 7(2+4+1

A* (con lista estricta expandida) Q

Expandid o

1

A 1

S

1 (90 S) S

3 (101 AS)(104 CBS)

A, S

4 (102 CAS)(104 CBS) 5 (102 GCAS)

C, A, S G, C, A, S

Se agregan los caminos en azul; los caminos subrayados son escogidos para extenderse

C

2

2 2 (90BS)(101 AS)

100

B

Valores Heurísticos A=100

c=100

B=88

G=0

s=90

G

•No todas las heurísticas son admisibles Son los valores heurísticos dados desde el ejemplo Primero el Mejor una heurística admisible?

Valores heurísticos A=2 C=1 S=10 B=3 D= 4 G=0 A – es admisible, tiene 2 y se encuentra a 6 B – es admisible, 3 y se encuentra a 5 C – es admisible, 1 y no llega D – muy grande, 4 y esta a 2; tendría que ser <= 2

S – muy grande, 10 y esta a 8 ( se debe usar 0 para el inicio)

Complejidad del peor caso Un espacio de estado con N estados puede llevarnos a una búsqueda en árbol que tiene un numero de nodos que son exponenciales a N, como en este ejemplo

solo una vez.

Gracias por su atención!!!!!!!