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