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. Moore4
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.
ü 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.
