BÚSQUEDA HEURISTICA

BÚSQUEDA HEURISTICA

En el presente blog le vamos a presentar los diferente concepto de busque heurística estos son los siguiente

Introducción

La búsqueda es una de las técnicas más utilizadas para resolver los problemas de pathfinding o planificación que se presentan en la inteligencia artificial en los juegos de vídeo. En particular, la búsqueda es utilizada para resolver el problema de la navegación. La constante evolución de los juegos de vídeo ha llevado a que la inteligencia artificial constituya uno de los aspectos más importantes; es fundamental que los agentes (entidades autónomas) controlados por la computadora se comporten en forma inteligente. Un problema característico es la navegación, que consiste en determinar el camino más conveniente entre una posición inicial y una posición de destino. Si bien el planteo del problema es sencillo, el mismo está lejos de ser trivial debido a la creciente complejidad de los entornos simulados y los requerimientos de tiempo real de los juegos modernos. Clasificación de los algoritmos de búsqueda.

HEURISTICA INFORMATICA

Una heurística es un algoritmo que abandona uno o ambos objetivos. Las heurísticas generalmente son usadas cuando no existe una solución óptima bajo las restricciones dadas o cuando no existe del todo.

Autores como Feigenbaum y Feldman definen la heurística como es una regla para engañar, simplificar un conjunto de reglas que evalúan la posibilidad de que una búsqueda va en la dirección correcta.

HEURISTICA EN IA

En inteligencia artificial son heurísticos por naturaleza, o usan reglas heurísticas. Cualquiera de las reglas usadas de forma independiente pueden llevar a errores de clasificación, pero cuando se unen múltiples reglas heurísticas, la solución es más robusta y creíble. Esto se llama alta credibilidad en el reconocimiento de patrones, Cuando se usa la palabra heurística en el procesamiento del lenguaje basado en reglas, el reconocimiento de patrones o el procesamiento de imágenes, es usada para referirse a las reglas.

BUSQUEDA HEURISTICA

La búsqueda es una técnica para resolver problemas cuya solución consiste en una serie de pasos que frecuentemente deben determinarse mediante la prueba sistemática de las alternativas. Desde los inicios de la Inteligencia Artificial, la búsqueda se ha aplicado en diversas clases de problemas como juegos de dos jugadores, problemas de satisfacción de restricciones y problemas de un único agente. Por lo tanto se puede decir que los algoritmos de búsqueda heurística son método computacional para resolver problemas de pathfinding “búsqueda de la mejor ruta del punto A al punto B”

Posteriormente se supone la existencia de una función de evaluación que debe medir la distancia estimada al objetivo. Esta función de evaluación se utiliza para guiar el proceso haciendo que en cada momento se seleccione el estado o las operaciones más prometedores. No siempre se garantiza encontrar una solución (de existir ésta). No siempre se garantiza encontrar la solución más próxima (la que se encuentra a una distancia, número de operaciones menores)

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.

SON CARACTERÍSTICAS DE LOS MÉTODOS HEURÍSTICOS:

ü  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 apriori), encontrarán una solución (aceptablemente buena) en un tiempo razonable.

FUNCIÓN HEURÍSTICA

La función heurística puede tener dos interpretaciones. Por una parte, la función puede ser una estimación de lo próximo que se encuentra el estado de un estado objetivo. Bajo esta perspectiva, los estados de menor valor heurístico son los preferidos. Pero en otros casos puede suceder que lo que convenga sea maximizar esa función.

BÚSQUEDA DE UN ESPACIO DE ESTADO

Es un proceso usado en el campo de la Informática, incluyendo la Inteligencia Artificial (AI), en el cual se consideran sucesivos estados de una instancia, con la meta de encontrar un "estado final" con las características deseadas.

Los problemas se modelan a menudo como un espacio de estados, un conjunto de estados que un contienen el problema. El conjunto de estados forma un grafo donde dos estados están conectados si hay una operación que pueda se pueda llevar a cabo para transformar el primer estado en el segundo.

La búsqueda en el espacio de estados difiere de los métodos de búsqueda tradicionales porque el espacio de estados está implícito: El grafo del espacio de estados típico es mucho es demasiado grande para generarlo y guardarlo en memoria. En su lugar, los nodos se generan en el momento en que se exploran y generalmente son descartados después. Una solución puede consistir solamente en un estado objetivo, o en un camino desde un estado inicial hasta el estado final.

Se dice que un problema de IA está definido como un problema de búsqueda en un espacio de estado, cuando para este se describen:

ü  Estado

ü  Espacio de Estado (no es necesario  para los métodos)

ü  Estado Inicial

ü  Estado Meta

ü  Reglas

GRADIENTE “VORAZ”

Es un método de búsqueda sin vuelta atrás (se convierte en un algoritmo voraz). Corresponde a la búsqueda en profundidad guiada por un fev. Al igual que su homologo exhaustivo, se puede fijar un límite de exploración.

Las característica importante de este estado es que, una vez tomado un camino, este no se puede dejar (no se evalúan alternativas, se toma una decisión optima). Ña fev normalmente será creciente (puede haber casos en los que interese que sea decreciente y lo que se busca es máxima su valor en la meta)

BEST-FIRST

Crea una agenda de un elemento (el nodo raíz)  hasta que la agenda este vacía o se alcance la meta  si el primer elemento es la meta  entonces acaba si no elimina el primer elemento y añade sus sucesores a la agenda ordena todos los elementos de la agenda

Idea: usar una función de evaluación para cada nodo

ü  Estimación de la “deseabilidad"

Expandir el nodo no expandido más deseable

Implementación:

Ordenar los nodos en el fringe en orden decreciente de  deseabilidad

A*

El algoritmo de búsqueda A* o también denominado “A Estrella” se encuentra dentro de los tipos de

Algoritmos de búsqueda en grafos, representado por Peter E. Hart, Nils J. Nilsson yBertram Rápale, en 1968.El algoritmo A* es el único que garantiza, sea cual sea la función heurística, que se tiene en cuenta el camino recorrido y por ende es mejor que la versión más extendida de "primero el mejor", aquélla que sólo considera la distancia a la meta. En definitiva, sí tiene razón en el caso concreto que usted plantea, pero no la tiene en general.

REPRESENTACIÓN

A continuación se muestra la clásica representación del algoritmo A *.

Dónde: g (n) es la distancia total que ha tomado para llegar desde la posición inicial a la ubicación actual.

h '(n) es la estimación de la distancia desde la posición actual con el destino, es una función heurística se utiliza para crear esta estimación sobre cuán lejos se está para alcanzar la meta.

f '(n) es la suma de g (n) y h' (n). Este es el camino actual estimado más corto. f (n) es el verdadero camino más corto que no se descubrieron hasta que el algoritmo A * ha terminado.

CARACTERISTICAS

ü  Realiza la búsqueda informada teniendo en cuenta dos factores fundamentales, el valor heurístico de los nodos y el coste real del recorrido.

ü  Se utiliza en la búsqueda de un camino más corto.

ü  El Algoritmo no desarrolla un camino por interacción, sino que desarrolla varios caminos y elige los más prometedores.

ü  Tiene algunas buenas referencias y consejos acerca elementos de juego de la programación y la industria del juego, ejemplo tetris, camino más corto entre dos puntos.

SSS*

El algoritmo SSS* (SSS estrella) se clasifica dentro de los algoritmos de búsqueda basada en grafos, de manera similar a como lo hacen los algoritmo A* o mini max. Se diferencia del algoritmo alfa-beta en que utiliza una lista como estructura.

Se genera un árbol en los que los nodos son de tipo MIN o MAX. Cada nodo del árbol es una tupla (N, s, h):

·         N: Nombre

·         s: Estado (vivo o solucionado)

·         h: Valor de la solución ( inicialmente menos infinito si se quiere maximizar la función)

Algoritmo:

·         1. Introducir en ABIERTA el estado inicial.

·         2. Eliminar el primer estado de ABIERTA.

·         3. Si n=raíz del árbol y e=resuelto, terminar con h=valor Minimax.

·         4. Sino, expandir el nodo p, aplicando un operador del espacio de estados.

·         5. Ir a 2.

IDA*

El IDA* (Iterative-Deepening A*) es al igual que el DFID un algoritmo basado en la profundización iterativa. La única diferencia entre ambos algoritmos estriba en que mientras el DFID se basa en la profundidad para cada una de sus iteraciones, el IDA se basa en la información heurística que posee para determinar el siguiente límite de la iteración. El tratamiento de esa información se realiza de igual forma que en el algoritmo del A*, o sea mediante la función de evaluación f introducida anteriormente. El funcionamiento del algoritmo es el siguiente:

En cada iteración el algoritmo realiza una búsqueda en profundidad hasta donde se lo permita su límite de coste. Cada vez que se visita todo el grafo de búsqueda contenido dentro de ese límite sin hallar la solución entonces, el algoritmo incrementa el límite de coste. Ese nuevo límite viene dado por el menor de los límites de corte, o sea, por el menor valor del coste de los nodos que tenían un valor superior en la anterior iteración.

Como señalamos anteriormente, este algoritmo se considera limitado en profundidad, aunque esta afirmación no sea estrictamente cierta. La razón de ello viene dado por su eficacia en cuanto al uso de memoria pero como se puede ver de su funcionamiento no realiza un control estricto de la memoria.

BÚSQUEDA  CON OPONENTES

Analiza los problemas en los que existe más de un adversario, modificando el estado del sistema. Hay dos operadores:

ü  El que lleva el problema a la mejor situación (jugada nuestra).

ü  El que lleva el problema a la peor situación (jugada de nuestro adversario).

MINIMAX

En teoría de juegos, Minimax es un método de decisión para minimizar la pérdida máxima esperada en juegos con adversario y con información perfecta. Minimax es un algoritmo recursivo.

El funcionamiento de Minimax puede resumirse como elegir el mejor movimiento para ti mismo suponiendo que tu contrincante escogerá el peor para ti.

ALGORITMOS ALTERNATIVOS

El algoritmo MINIMAX, aún con los refinamientos descriptos, contiene algunos aspectos problemáticos:

No considera el tiempo

Confía fuertemente en la suposición de que el oponente elija el camino óptimo

En esta sección se explican dos alternativas que consideran cuestiones por separado. 

OPTIMIZACION

En la práctica el método Minimax es impracticable excepto en supuestos sencillos. Realizar la búsqueda completa requeriría cantidades excesivas de tiempo y memoria.

Claude Shannon en su texto sobre ajedrez de 1950 (Programming a Computer for Playing Chess) propuso limitar la profundidad de la búsqueda en el árbol de posibilidades y determinar su valor mediante una función heurística. Para optimizar Minimax puede limitarse la búsqueda por nivel de profundidad o por tiempo de ejecución. Otra posible técnica es el uso de la poda alfa-beta. Esta optimización se basa en la suposición que el jugador contrario no nos permitirá jugar nuestras mejores jugadas.

ALGORITMO MINIMAX CON MOVIMIENTO ALTERNATIVOS

Pasos del algoritmo Minimax:

1.   Generación del árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal.

2.   Cálculo de los valores de la función de utilidad para cada nodo terminal.

3.   Calcular el valor de los nodos superiores a partir del valor de los inferiores. Según nivel si es MAX o MIN se elegirán los valores mínimos y máximos representando los movimientos del jugador y del oponente, de ahí el nombre de Minimax.

4.   Elegir la jugada valorando los valores que han llegado al nivel superior.

ALFA BETA

La poda alfa beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en programas de juegos entre adversarios como el ajedrez, el tres en raya o el Go.

Entre los pioneros en el uso de esta técnica encontramos a Arthur Samuel, D.J Edwards y T.P. Hart, Alan Kotok, Alexander Brudno, Donald Knuth y Ronald W. Moore⁴

El problema de la búsqueda Minimax es que el número de estados a explorar es exponencial al número de movimientos. Partiendo de este hecho, la técnica de poda alfa-beta trata de eliminar partes grandes del árbol, aplicándolo a un árbol Minimax estándar, de forma que se devuelva el mismo movimiento que devolvería este, gracias a que la poda de dichas ramas no influye en la decisión final.

DESARROLLO DEL ALGORITMO

La búsqueda minimax es primero en profundidad, por ello en cualquier momento sólo se deben considerar los nodos a lo largo de un camino en el árbol.

La poda alfa-beta toma dicho nombre de la utilización de dos parámetros que describen los límites sobre los valores hacia atrás que aparecen a lo largo de cada camino.

·         α es el valor de la mejor opción hasta el momento a lo largo del camino para MAX, esto implicará por lo tanto la elección del valor más alto

·         β es el valor de la mejor opción hasta el momento a lo largo del camino para MIN, esto implicará por lo tanto la elección del valor más bajo.

Esta búsqueda alfa-beta va actualizando el valor de los parámetros según se recorre el árbol. El método realizará la poda de las ramas restantes cuando el valor actual que se está examinando sea peor que el valor actual de α o β para MAX o MIN, respectivamente.

El desarrollo del algoritmo en pseudocódigo será el siguiente:

Función alfabeta(nodo, profundidad, α, β, jugadorMaximizador)

    si nodo es un nodo terminal o profundidad = 0

        devolver el valor heurístico del nodo

    si jugadorMaximizador

        para cada hijo de nodo

            α := max(α, alfabeta(hijo, profundidad-1, α, β, FALSE))

            si β≤α

                break (* poda β *)

        devolver α

    si no

        para cada hijo de nodo

            β := min(β, alfabeta(hijo, profundidad-1, α, β, TRUE))

            si β≤α

                break (* poda α *)

        devolver β

(* Llamada inicial *)

alfabeta(origen, profundidad, -infinito, +infinito, TRUE)

                                                                                        

APLICACIONES

Se mencionará algunas aplicaciones:

ü  Minería de datos, búsqueda de comportamiento en los datos.

ü  Procesamiento de imágenes.

ü  Medicina humana, software médicos, control de tumores, problemas cancerigenos, VESALIO.

ü  En la aeronavegación y transporte, el pilotaje automático, búsquedas de rutas más próximas.

ü  Video juegos de estrategia, camino más corto, ejemplo Pacman: Los fantasmas que persiguen a Pacman buscan el camino más corto, en lugar de aparecer en forma aleatoria en el Mapa del Juego.

ü  Juegos, ejemplo Age of Empires, un juego de conquista de civilizaciones, los enemigos salvan obstáculos para llegar a la ciudad del adversario

La búsqueda es una de las técnicas más utilizadas para resolver los problemas de pathfinding o planificación, que se presentan en la Inteligencia Artificial, especialmente en los videojuegos. En particular, la búsqueda es utilizada para resolver los problemas de navegación.

La constante evolución de los juegos de vídeo ha llevado a que la IA constituya uno de los aspectos más importantes; es fundamental que los agentes controlados por la computadora se comporten en forma inteligente. Un problema característico es la navegación, que consiste en determinar el camino más conveniente entre una posición inicial y una posición de destino. Si bien el planteo del problema es sencillo, el mismo está lejos de serlo debido a la creciente complejidad de los entornos simulados y los requerimientos de tiempo real de los juegos modernos.