Inteligencia artificial para videojuegos/Estrategias de búsqueda informada

Las estrategias de búsqueda informada se basan en aplicar un conocimiento al proceso de búsqueda para hacerlo más eficiente. Este conocimiento o función nos ayudará a estimar qué camino o estado es más prometedor, es decir qué configuración está más cercana del objetivo final.

Por lo tanto:

• Da preferencia a los mejores estados.
• Ordenados según su estado, de mayor prometedor a menos.

Concepto de heurística

Del griego heuriskein, descubrir. En nuestro caso es la función que nos ayudará a acercarnos al objetivo planteado.

La función heurística:

• Estima la distancia al objetivo.
• Siempre es mayor que 0.
• Valor en el estado final igual a 0.

Primero el mejor (Best First Search)

Analizar preferentemente los mejores nodos. Para saber cuáles son los mejores utilizaremos una función heurística f para evaluarlos, que estima el coste total de la función. Los ordenaremos de tal forma que el primer nodo será el que tenga la heurística mas baja. Por lo tanto estarán ordenados en función de f y no de g, que devuelve el coste de la raíz al nodo.

Primero el mejor - Voraz (Greedy BFS)

• Algoritmo que intenta llegar cuanto antes a la solución.
• No es completa, una mala heurística podría hacer tomar un camino infinito.
• No es óptima, no garantiza soluciones con el menor número de operaciones.
• La complejidad espacio-temporal es de 0(r ^m), donde r es el factor de ramificación y m la profundidad del árbol de búsqueda.

Sin embargo escogiendo una buena función heurística se pueden reducir mucho los costes.

A Estrella (A*)

Algoritmo basado en el primero el mejor. Combina el coste directo de la raíz al nodo con la estimación del nodo al objetivo.

Es uno de los algoritmos más populares para encontrar caminos y grafos.

A diferencia de otras técnicas transversales, tienen "cerebros". Lo que significa que es un algoritmo inteligente que lo separa de los otros algoritmos convencionales.

Nosotros estaremos en un nodo inicial y debemos dirigirnos a un nodo final. En cada paso el resultado de la función del A* será igual a la suma de otros dos parámetros g y h, f = g + h. En cada paso elegirá el nodo cuya f sea la más baja.

Definamos ahora g y h:

g = cuánto cuesta moverse desde el punto inicial a un nodo dado siguiendo la ruta generada para llegar allí.

h = el coste del movimiento estimado para pasar de ese nodo dado al destino final.Esto a menudo se conoce como la heurística, que no es más que una especie de suposición inteligente. Realmente no sabemos la distancia real hasta que encontramos el camino.

La cola a la hora de ir sacando nodos irá de menor a mayor f, siendo el nodo con menor f el nodo más prometedor. Un ejemplo de esto son los mapas cuadriculados. En ellos los nodos iniciales y destino son casillas. Pueden existir casillas por las que no se pueden pasar, la gracia del A* es que las tiene en cuenta, al igual que las casillas que supongan un mayor coste.

Heurísticas

Hemos visto como f es la función que evalúa el coste total de la función. Hemos visto como g calcula el coste hasta el nodo. Sin embargo cómo calculamos la heurística, h. Existen muchas heurísticas, algunas pueden partir del coste de subproblemas del problema original, otras parten de la experiencia de intentos fallidos. En cualquier caso podemos diferenciar entre calcular h exacta o una aproximación a esta, lo cual nos supone menos tiempo, ejemplo de ambas son: Distancia Manhattan, Distancia Diagonal y distancia Euclídea. Aplicado por ejemplo al algoritmo A*:

• Manhattan Distance:

h = abs (current_cell.x – goal.x) + abs (current_cell.y – goal.y)

Cuándo usarla:

Cuando te puedes mover en cuatro direcciones (right, left, top, bottom).

• Diagonal Distance:

h = max {abs (current_cell.x – goal.x), abs (current_cell.y – goal.y)}

Cuándo usarla:

Cuando te puedes mover en ocho direcciones

• Euclidean Distance:

h = sqrt ((current_cell.x – goal.x)2 + (current_cell.y – goal.y)2)

Cuándo usarla:

Cuando te puedes en cualquier dirección

• Hamming:

  Contar número de caracteres a cambiar

• Damerau-Levenshtein:

  Contar número de operaciones de edición a realizar

• Levenshtein:

  Trasponer cuenta como dos operaciones