BUSQUEDA LOCAL EN ESPACIOS CONTINUOS

Fecha de la clase: 27 de Noviembre

INTRODUCCIÓN

En la clase de búsqueda local en espacios continuos el objetivo es comprender como el agente inteligente realiza la búsqueda en espacios continuos y lo que son las búsquedas online se basa en lo que está pasando en ese estado para tomar de nuevo otra acción clases impartidas en las respectivas exposiciones.

MARCO TEÓRICO

BUSQUEDA LOCAL EN ESPACIOS CONTINUOS

Aun ninguno de los algoritmos descritos puede manejar espacios de estados continuos, la función sucesor en la mayor parte de casos devuelve infinitamente muchos estados! la técnicas de búsqueda local para encontrar soluciones optimas en espacios continuos.

Un modo de evitar problemas continuos es simplemente discretizar la vecindad de cada estado. Podemos aplicar entonces cualquiera de los algoritmos de búsqueda local descritos anteriormente. Uno puede aplicar también la ascensión de colinas estocástica y el temple simulado directamente, sin discretizar el espacio. Estos algoritmos eligen a los sucesores aleatoriamente, que pueden hacerse por la generación de vectores aleatorios de longitud.

Los métodos locales de búsqueda sufren de máximos locales, crestas, y mesetas tanto en espacios de estados continuos como en espacios discretos. Se pueden utilizar el reinicio aleatorio y el temple simulado y son a menudo provechosos. Los espacios continuos dimensionalmente altos son, sin embargo, lugares grandes en los que es fácil perderse.

Un problema de optimización está restringido si las soluciones debieran satisfacer algunas restricciones sobre los valores de cada variable. La dificultad de los problemas de optimización con restricciones depende de la naturaleza de las restricciones y la función objetivo. La categoría más conocida es la de los problemas de programación lineal en los cuales las restricciones deben ser desigualdades lineales formando una región convexa y la función objetiva es también lineal. Los problemas de programación lineal pueden resolverse en tiempo polinomial en el número de variables. También se han estudiado problemas con tipos diferentes de restricciones y funciones objetivo (programación cuadrática, programación cónica de segundo orden, etcetera). (Russell, S y Norvig, P).

BUSQUEDA ONLINE Y AMBIENTES DESCONOCIDOS

Después de cada acción, un agente online recibe una percepción al decirle que estado ha alcanzado; de esta información, puede aumentar su mapa del entorno. El mapa actual se usa para decidir dónde ir después. Esta intercalación de planificación y acción significa que los algoritmos  de búsqueda online son bastantes diferentes de los algoritmos de búsqueda offline.

Un algoritmo online, por otra parte puede expandir sólo el nodo que ocupa físicamente. Para evitar viajar atravez de todo el árbol para expandir el siguiente nodo, parece mejor expandir los nodos en un orden local. La búsqueda primero en profundidad tiene exactamente esta propiedad, porque el siguiente nodo a expandir es hijo del nodo anteriormente expandido.

Objetivo del agente:

·       Alcanzar un estado objetivo

·       Minimizando el coste.

Búsqueda off-line:

– Calcula una solución completa antes de poner un pie en el mundo real.

– Después ejecutan la solución sin recurrir a las percepciones.

Búsqueda on-line: Intercala el calcula y la acción.

– Toma una acción

– Observa el entorno

– Calcula la siguiente acción.

Usos de la búsqueda on-line:

– Problemas de exploración, donde el agente desconoce los estados y acciones.

Problemas  de búsqueda en línea (online)

Un problema de búsqueda online puede resolverse solamente por un agente que ejecute acciones, más que por un proceso puramente computacional. Asumiremos que el agente sabe lo siguiente:

– Acciones (). Que devuelve una lista de acciones permitidas en el estado s;

– Funciones de coste individual c(s, a, s’), hay que tener en cuenta que no pude usarse hasta que el agente sepa que s’ es el resultado; y

– Test-Objetivo(s). (Gómez, F).

CONCLUSIÓN

Para las soluciones de problemas con estos algoritmos de búsqueda es que solo se enfocan en lo que sucede en ese estado y luego al darse cuenta de su entorno toma acciones nuevas ya que para otras búsquedas necesitan tener una vista general de la problemática para así realizar una acción.  

BIBLIOGRAFÍA

 Gómez, F. 2010. Métodos de búsqueda de soluciones (Búsqueda informada y exploración). En Línea. Formato (PDF). Disponible en:http://ants.inf.um.es/~felixgm/pub/others/InteligenciaArtificial.pdf

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España. 

FUNCIONES HEURÍSTICAS

Fecha de clase: 13 de noviembre

INTRODUCCIÓN

Otro tema de los tratados en clase con los compañeros y la docente, es este el de las funciones heurísticas que en si son aquellas que ya disponen de alguna información para llegar a su objetivo lo que hace que este tenga más claro el camino a recorrer.

MARCO TEÓRICO

FUNCIONES HEURÍSTICAS

Los métodos de búsqueda heurística disponen de alguna información sobre la proximidad de cada estado a un estado objetivo, lo que permite explorar en primer lugar los caminos más prometedores.

CARACTERÍSTICAS:

• No garantizan que se encuentre una solución, aunque existan soluciones.
• Si encuentran una solución, no se asegura que ésta tenga las mejor esas propiedades (que sea de longitud mínima o de coste óptimo).
• En algunas ocasiones (que, en general, no se podrán determinar a priori), encontrarán una solución (aceptablemente buena) en un tiempo razonable.
• En general, los métodos heurísticos son preferibles a los métodos no informados en la solución de problemas difíciles para los que una búsqueda exhaustiva necesitaría un tiempo demasiado grande. Esto cubre prácticamente la totalidad de los problemas reales que interesan en Inteligencia Artificial.
• La información del problema concreto que estamos intentando resolver se suele expresar por medio de heurísticas.
• El concepto de heurística es difícil de aprehender. Newell, Shaw y Simon en 1963 dieron la siguiente definición: "Un proceso que puede resolver un problema dado, pero que no ofrece ninguna garantía de que lo hará, se llama una heurística para ese problema".
• Si nos planteamos seguir concretando como aprovechar la información sobre el problema en sistemas de producción, la siguiente idea consiste en concentrar toda la información heurística en una única función que se denomina función de evaluación heurística. Se trata de una función que asocia a cada estado del espacio de estados una cierta cantidad numérica que evalúa de algún modo lo prometedor que es ese estado para acceder a un estado objetivo. Habitualmente, se denota esa función por h (e). (Malagón, S)

APRENDIZAJE DE HEURÍSTICAS DESDE LA EXPERIENCIA

Una función heurística h(n), como se supone, estima el costo de una solución que comienza desde el estado en el nodo n. Los métodos de aprendizaje inductivos trabajan mejor cuando se les suministrar características de un estado que sean relevante para su evaluación, más que sólo la descripción del estado.

A partir de esto, se puede utilizar un algoritmo de aprendizaje inductivo para construir una función h(n) que pueda predecir los costos solución para otros estados que surjan durante la búsqueda. Las técnicas para hacer esto, está basado en la  utilización de  redes neuronales, árboles de decisión. Y otros métodos. (Russell, S y Norvig, P.)

CONCLUSIÓN

Para la solución de problemas con esta como es la solución de la función heurística es que depende de la información, ya que dependiendo de esta, se puede  encontrar el estado objetivo de una manera eficiente o más rápida.

BIBLIOGRAFÍA

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

Malagón, S. 2010.Busqueda heurística. (En línea).Disponible en http://www.nebrija.es/~cmalagon/ia/transparencias/busqueda_heuristica.pdf

BÚSQUEDA INFORMADA

Fecha de clase: 6 de noviembre

INTRODUCCIÓN

En esta clase se aprendió sobre las diferentes búsquedas informadas, ya que para realizar una búsqueda óptima hay que tener conocimiento de los tipos de búsqueda existente, cabe recalcar que esta búsqueda ya tiene conocimiento acerca del estado en que se encuentra aparte de lo que indica el problema.

MARCO TEÓRICO

BUSQUEDA INFORMADA

Esta sección muestra cómo una estrategia de búsqueda informada puede encontrar soluciones de una manera más eficiente que una estrategia no informada. Algunas estrategias son:

BUSQUEDA VORAZ PRIMERO EL MEJOR

Trata de expandir el nodo más cercano al objetivo, alegando que probablemente conduzca rápidamente a una solución. Así, evalúa los nodos utilizando solamente la función heurística: f(n)=h(n). 

No tiene en cuenta el coste de llegar hasta n, Se pretende llegar rápidamente a la solución,  sin importar tanto el coste. La bondad que tenga la función heurística h determinará la rapidez con que llegamos a un estado objetivo.

La minimización de h(n) puede llevarnos a ventajas falsas, puede hacernos expandir nodos innecesarios. Si no se tiene cuidado con los estados repetidos,  podemos llegar a callejones sin salida; se parece a la búsqueda primero en profundidad y tiene las mismas desventajas:

° No es óptima y es incompleta

° La complejidad es O(bm). (Diez, J)

BUSQUEDA A*

A la forma más ampliamente conocida de la búsqueda primero el mejor se le llama búsqueda A* (pronunciada «búsqueda A-estrella»). Evalúa los nodos combinando g{n), el coste para alcanzar el nodo, y h(n), el coste de ir al nodo objetivo:

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

Ya que la g(n) nos da el coste del camino desde el nodo inicio al nodo n, y la h(n) el coste estimado del camino más barato desde n al objetivo, tenemos:

F(n) = coste más barato estimado de la solución a través de n.

Así, si tratamos de encontrar la solución más barata, es razonable intentar primero el nodo con el valor más bajo de g(n) + h(n). Resulta que esta estrategia es más que razonable: con tal de que la función heurística h(n) satisfaga ciertas condiciones, la búsqueda A* es tanto completa como óptima.

La optimalidad de A* es sencilla de analizar si se usa con la Búsqueda-Árboles.

En este caso, A* es óptima si h(n) es una heurística admisible es decir, con tal de que la h(n) nunca sobrestime el coste de alcanzar el objetivo. Las heurísticas admisibles son por naturaleza optimistas, porque piensan que el coste de resolver el problema es menor que el que es en realidad. Ya que g(rí) es el coste exacto para alcanzar n, tenemos como consecuencia inmediata que la f\ri) nunca sobrestima el coste verdadero de una solución a través de n. (Russell, S y Norvig, P)

CONCLUSIÓN

Como se habló en clases las búsquedas informadas son mucho más eficientes que las no informadas, ya que además de tener el conocimiento previo también da solución de una manera más rápida claro está dependiendo de la calidad y cantidad de heurística.

BIBLIOGRAFÍA

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

Diez, J. 2009. Búsqueda Informada. Formato PDF. (En línea). Disponible en http://www.aic.uniovi.es/ssii/SSII-T3-BusquedaII.pdf

BUSQUEDA DE PROFUNDIDAD LIMITADA

Fecha de clase: 16 de Octubre

INTRODUCCIÓN

En esta clase se aprendió sobre las diferentes búsquedas no informadas, como todas las clases se empezó con el narrador y el expositor sobre la búsqueda de profundidad limitada, búsqueda con profundidad iterativa, búsqueda bidireccional cabe recalcar que estas son herramientas para la búsqueda de solución de un problema.

MARCO TEÓRICO

BUSQUEDA DE PROFUNDIDAD LIMITADA

Se puede aliviar el problema de árboles ilimitados aplicando la búsqueda primero en profundidad con un límite de profundidad t predeterminado. Es decir, los nodos a profundidad i se tratan como si no tuvieran ningún sucesor. A esta aproximación se le llama búsqueda de profundidad imitada El límite de profundidad resuelve el problema del camino infinito. Lamentablemente, también introduce una fuente adicional de incompletitud si escogemos € < d, es decir, el objetivo está fuera del límite de profundidad.

La búsqueda de profundidad limitada también será no óptima si escogemos i > d. Su complejidad en tiempo es 0(kf) y su complejidad en espacio es 0(bí). La búsqueda primero en profundidad puede verse como un caso especial de búsqueda de profundidad limitada con t = infinito. (Rentería, R)

BUSQUEDA DE PROFUNDIDAD ITERATIVA

Intenta combinar el comportamiento espacial de la búsqueda en  profundidad (DFS) con la optimalidad de la búsqueda en anchura  (BFS), por esto es el más ventajoso de los anteriores. El algoritmo consiste en realizar búsquedas en profundidad  sucesivas con un nivel de profundidad máximo acotado y creciente  en cada iteración. Así se consigue el comportamiento de BFS pero sin su coste  espacial, ya que la exploración es en profundidad, y además los  nodos se regeneran a cada iteración. Además esto permite evitar los casos en que DFS no acaba (existen  ramas infinitas).

En la primera iteración la profundidad máxima será 1 y este valor irá aumentando en sucesivas iteraciones hasta llegar a la solución. Para garantizar que el algoritmo acaba si no hay solución, se puede definir una cota máxima de profundidad en la exploración. (Russell, S y Norvig, P)

BUSQUEDA BIDIRECCIONAL

La idea de la búsqueda bidireccional es ejecutar dos búsquedas simultáneas: una hacia delante desde el estado inicial y la otra hacia atrás desde el objetivo, parando cuando las dos búsquedas se encuentren en el centro. La motivación es que b^d/2 + b^d/2 es mucho menor que b^d, o en la figura, el área de los dos círculos pequeños es menor que el área de un círculo grande centrado en el inicio y que alcance al objetivo. La búsqueda bidireccional se implementa teniendo una o dos búsquedas que comprueban antes de ser expandido si cada nodo está en la frontera del otro árbol de bús queda; si esto ocurre, se ha encontrado una solución.

CONCLUSIÓN

Este es un método que consiste buscar mejores soluciones óptimas y que puedan solucionar los problemas planteados es necesario mencionar que existen diferentes formas de interpretar una búsqueda, es decir existe dos que son una búsqueda informativa y la búsqueda a ciegas.

BIBLIOGRAFÍA

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

Rentería, R. 2010. Búsqueda no Informada. Formato PDF. (En línea). Disponible en clasev.net/v2/mod/resource/view.php?id=11783

AGENTES QUE PLANIFICAN

Fecha de clase: 9 de Octubre 2014

INTRODUCCIÓN

Esta fue una de las primeras clases del semestre iniciando con un tema muy interesante como son los agentes resolventes de problemas y árboles de búsqueda para la resolución de problemas en la IA; esto nos muestra que hay agentes artificiales capaces y aptos para actuar de acuerdo a su entorno.

 Como ya lo sabemos el objetivo principal de la Inteligencia Artificial es que las máquinas sean capaces de obtener un comportamiento automático es decir que tomen decisiones por si mismos.

MARCO TEÓRICO

La comunidad de IA especializada en planificación se ha preocupado del problema de diseño de agentes artificiales capaces de actuar en un entorno.

La planificación se puede ver como una forma de programación automática.

Dentro de la comunidad de la IA simbólica, se ha asumido desde hace tiempo que algún tipo de sistema debe formar parte de los componentes centrales de cualquier agente artificial.

La idea básica es dotar al agente planificador:

- Representación del objetivo a alcanzar

- Representación de las acciones que puede realizar

- Representación del entorno

- Capacidad de generar un plan para alcanzar el objetivo

Un plan es una secuencia (lista) de acciones, que llevan de un estado inicial a un estado final. La planificación se puede ver como un problema de búsqueda en un espacio de estados. (Vazquez, J)

PROBLEMAS DEL MUNDO REAL

Hemos visto como el (roblona de busqueda de una ruta esta definido en terminos de posiciones y transiciones a lo largo de ellas. Los algoritmos de busqueda de rutas se han utilizado en una variedad de aplicaciones, tales como rutas en redes de computadores, planificacion de operaciones militares, y en sistemas de planificacion de viajes de lineas aereas. Estos problemas son complejos de especificar. Consideremos un ejemplo simplificado de un problema de viajes de lineas aereas que especificamos como:

• Estados: cada estado esta representado por una localizacion (por ejemplo, un aeropuerto) y la hora actual.

• Estado uncial: especificado por el problema.

• Fumian sucesor: devuelve los estados que resultan de tomar cualquier vuelo programado (quiza mas especificado por la clase de asiento y su posicion) desde el aeropuerto actual a otro, que salgan a la hora actual mas el tiempo de transito del aeropuerto.

• Test objetivo: .tenemos nuestro destino para una cierta hora especificada?

• Costo del camino: esto depende del costo en dinero, tiempo de espera, tiempo del vuelo, costumbres y procedimientos de la inmigracion, calidad del asiento, hora, tipo de avion, kilometraje del aviador experto...(Russell, S y Norvig, P)

BUSQUEDA DE SOLUCIONES

Hemos formulado algunos problemas, ahora necesitamos resolverlos. Esto se hace mediante busqueda a traves del espacio de estados. Este capitulo se ocupa de las tecnicas de busqueda que utilizan un arbol de busqueda explicito generado por el estado inicial y la funcion sucesor, definiendo asi el espacio de estados.

MEDIR EL RENDIMIENTO DE LA RESOLUCIÓN DEL PROBLEMA

La salida del algoritmo de resolución de problemas es fallo o una solución. Evaluaremos el rendimiento de un algoritmo de cuatro formas :

·         Completitud : ¿ está garantizado que el algoritmo encuentre una solución cuando esta exista?

·         Optimización: ¿encuentra la estrategia la solución óptima , según lo definido en la página 62 ?

·         Complejidad en tiempo: ¿cuánto tarda en encontrar una solución?

·         Complejidad en espacio: ¿cuánta memoria se necesita para el funcionamiento de la busqueda?

ESTRATEGIAS DE BUSQUEDA NO INFORMADA

El término significa que ellas no tienen información adicional acerca de los estados más allá de la que proporciona la definición del problema. Todo lo que ellas pueden hacer es generar los sucesores y distinguir entre un estado objetivo. (Russell, S y Norvig, P)

BUSQUEDA PRIMERO EN ANCHURA

La búsqueda en anchura prioritaria intenta explorar el espacio de búsqueda haciendo un recorrido por niveles, de manera que un nodo se visita solamente cuando todos sus predecesores y sus hermanos anteriores en orden de generación ya se han visitado.

Para obtener este algoritmo solo hemos de instanciar la estructura que guarda los nodos abiertos a una cola, en el algoritmo general de búsqueda que hemos visto en el capítulo anterior. Esta estructura nos consigue que se visiten los nodos en el orden que hemos establecido.

BUSQUEDA PRIMERO EN PROFUNDIDAD

Esta estrategia intenta seguir un camino hasta la mayor profundidad posible, retrocediendo cuando acaba el camino y retomando la última posibilidad de elección disponible.

El principal problema de este algoritmo es que no acaba si existe la posibilidad de que hayan caminos infinitos. Una variante de este algoritmo que evita este problema es el algoritmo de profundidad limitada (Búsqueda en profundidad prioritaria), éste impone un límite máximo de profundidad que determina la longitud máxima de los caminos recorridos. Esta limitación garantiza que el algoritmo acaba, pero no garantiza encontrar la solución, ya que ésta puede estar a mayor profundidad que el límite impuesto. (UNIVERSITAT POLITÉCNICA DE CATALUNYA)

CONCLUSIÓN

Los agentes que planifican son muy importante ya que por medio de la programación hace que las máquinas tengan comportamientos que solucionen problemas de manera rápida a comparación al que lo hace un ser humano, claro está que el equipo no va a resolver el problema al 100% como lo solucionaría una persona pero si cumple algunas normas que el ser humano como tal no tomaría en cuenta. Las estrategias de búsqueda para la búsqueda no informada son de vital importancia para la solución de los problemas a proponer.

BIBLIOGRAFÍA

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

UNIVERSITAT POLITÉCNICA DE CATALUNYA, 2013. Departament de Llenguatges i Sistemes Informátics. APUNTS D’INTEL.LIGE`NCIA ARTIFICIAL. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/ia/material/teoria/ApuntesIA.pdf

Vazquez, J. 2011. Agentes Planificadores. Formato PDF. (En línea). Consultado el 22 de oct. Disponible en http://www.lsi.upc.edu/~jvazquez/teaching/iag/transpas/4-PL1