algorithm - sirve - PacMan: ¿Qué tipos de heurísticas se utilizan principalmente?

tipos de heuristica (8)

Encontré la comida aproximada más cercana (usando las distancias de manhattan) pero para mi heurística usé la distancia real desde mi posición hasta la comida más cercana. A esto agregué 1 para todos esos puntos de comida que no comparten fila o columna con mi posición o el punto de comida más cercano.

Debido a que los puntos de comida que comparten la fila o la columna con mi posición o la posición de comida más cercana se comen mientras voy de mi posición a la comida más cercana y ya he contado el costo de esto en la distancia real que mencioné en la segunda línea.

Entonces, en resumen: heurística = mazeDistance (mi posición, la comida más cercana estimada) + puntos que quedan fuera

Esto era admisible y consistente. Con esto, estaba expandiendo 5500 nodos y obtuve un 5/4 en FoodHeuristic. https://github.com/sukritiverma1996/Intro-to-AI-course

Además de A *, BFS, DFS y similares, ¿cuáles son otros buenos algoritmos / heurísticos de búsqueda de caminos utilizados popularmente en Pacman? No creo que las que mencioné funcionen si hay más de una fruta para que Pacman la encuentre.

Necesito algunos buenos algoritmos de búsqueda de caminos que PacMan pueda usar para terminar el laberinto con el menor número posible de pasos. He intentado buscar una guía, pero hasta ahora no he tenido suerte. A * con la distancia de Manhattan se menciona en todas partes, pero solo funcionará con laberintos con solo una fruta (o dos, o tal vez hasta unas pocas) para obtener.

Por cierto, para mantener las cosas simples, asumiendo que no hay fantasmas alrededor.

Algunos ejemplos de los problemas originales de PacMan: First , Second y Third

Heurística que funcionó para mí si conoces el aspecto del laberinto:

Encuentra la distancia real entre las dos frutas más alejadas en el laberinto; llamémosle x .
Encuentre la distancia real desde la posición actual de Pacman hasta la más cercana de las dos frutas anteriores. Llamemos a eso y .

Entonces, la respuesta es justa: x + y .

Tenga en cuenta que las distancias reales no son las distancias de Manhattan, sino real distancias real en laberinto; puede calcularlo (incluso precalcular si lo desea) porque conoce el aspecto del laberinto (conoce todas las paredes, ...). Esta información (distancia real entre algunos dos puntos en laberinto) es estática porque las paredes no cambian.

La interpretación de esta fórmula x + y podría ser algo como esto:

x - de cualquier manera, tendrás que recorrer esta distancia, al menos al final
y - mientras se encuentra en algunas de las dos frutas más alejadas, es mejor recolectar la comida que está cerca para que no tenga que volver

Si está resolviendo esto como parte del proyecto de clase AI de Berkeley, para calcular la distancia real entre dos puntos, puede usar la función mazeDistance(pos1, pos2, gameState) que ya está implementada y está usando su implementación de bfs. Además, esta heurística es admisible y consistente , al menos para sus casos de prueba. Por cierto, con esta heurística logré expandir solo 376 nodos en el laberinto de trickySearch .

Podrías forzarlo bruscamente por un pequeño número de frutas en un laberinto de tamaño razonable.

Crea una gráfica con un nodo para cada pieza de fruta en el laberinto.
Use A * o similar para encontrar la distancia entre cada par de frutas. (Necesitará O(n^2) series de A * para obtener todas las distancias en pares entre n frutas).
Enlace los nodos (frutas) en el gráfico con bordes ponderados por distancia.
Encuentre el ciclo más barato en el gráfico (visitando todos los nodos al menos una vez) por fuerza bruta. Ver traveral costo más barato en el gráfico completo.

Sé que esto es viejo, pero probablemente hay muchas otras personas que buscan resolver este problema (es parte de la clase gratuita de inteligencia artificial de Berkeley). Hay muchas sugerencias de fuerza bruta, por lo que contribuiré con una muy simple que se acerca mucho y ~~ES ADMISIBLE~~ :

Encuentra la fruta más cercana
Elimine esa fruta de la lista de frutas restantes y agregue la distancia al total
Encuentra la fruta más cercana a esta fruta.
Vuelve al paso 2 y repite hasta que no haya más frutas.
devolver el total

Edición: la afirmación anterior de que esto es una heurística admisible es falsa. ¡Lo siento!

Si desea reducir el número de nodos expandidos y no le importa el tiempo de ejecución, le recomendaría que utilice el árbol de expansión mínima, el costo de la ventaja debería ser mazeDistance y usar la utilidad PriorityQueue, cada vez que agregue un nodo en el nodo visitado, busque el nodo más cercano al nodo que se acaba de agregar y luego lo agrega al nodo visitado, hasta que todo el nodo de alimentos se haya agregado al nodo visitado. Si lo está haciendo con un problema de curso de IA, el nodo expandido debería ser muy bajo.

Suponiendo que esto es para el proyecto de AI de Berkeley:

En el caso general, encontrar el camino más corto que visita cada punto es NP-difícil. Sin embargo, eso no significa que sea difícil en la práctica. El motivo es que existen algoritmos de parámetros fijos y los laberintos proporcionados por Pacman se encuentran en el caso de gráficos fáciles de resolver.

En particular, para cualquier ancho de rama dado, la ruta más corta se puede encontrar en el polinomio de tiempo en el tamaño del gráfico (pero exponencial en el ancho de rama del gráfico) mediante una simple aplicación de programación dinámica. Esto no viola la dureza NP ya que los gráficos arbitrarios pueden tener un ancho de rama grande, pero significa que el problema se puede resolver de manera eficiente si solo te preocupan los gráficos que tienen un ancho de rama bajo. Los laberintos proporcionados por Pacman tienen una conectividad deficiente y, por lo tanto, un ancho de rama bajo.

Para más detalles, vea este post .

Tu comentario dice que estás buscando el camino más corto . Este problema es una variación de TSP en un gráfico planar, y por lo tanto es NP-Hard .

Posible función heurística para A* que puede resolver el problema pero no es admissible [por lo tanto, no se garantiza que el camino encontrado sea óptimo]:

Suma de las distancias de manhattan desde todas las frutas hasta el agente.

También puede usar una heurística que se puede emitir, de #fruits , pero llevará mucho tiempo.

Si lo que buscas es óptimo, bueno, es difícil. Puede probar todas las permutaciones de frutas y verificar la distancia total que necesita para viajar. Esta solución es factorial en el número de frutas , y si es mayor que 20, con fuerza bruta ingenua, tomará demasiado tiempo. De alguna manera puede mejorarlo reduciendo el problema a TSP , y usar una solución de programación dinámica, que también es exponencial, o algunas soluciones heurísticas para TSP.

También se puede mejorar la solución heurística no admisible para proporcionar un algoritmo en cualquier momento :

ejecute iterativamente A* con una función heurística decreciente : h(v) = h''(v) / m , donde h'' es la función heurística en la última iteración de A *, y m > 1 . Esto garantiza que, en algún momento, su función heurística será admisible, y la solución encontrada será óptima. Sin embargo, se espera que cada iteración tome mucho más tiempo que la anterior [exponencialmente más larga ..]

en un estado de juego dado, digamos que md(x) es la distancia de manhattan desde pacman al nodo x , considere minmd(X) como una función que devuelve xmin st md(xmin)<=md(x) para todas las x en X sea X el conjunto de alimentos que pacman tiene para comer.

Piensa en ello: si consideras una relajación de tu mundo pacman en el que no hay paredes, pacman no puede caminar menos que md(xmin) donde xmin=minmd(X) para comer algo de fruta, y luego, si quiere comer otra. debe ir no menos que md(xmin1) donde xmin1=minmd(X-{xmin}) y así sucesivamente. devuelva la suma de mds pacman caminó de xmin a xmin1 a xmin2 y así sucesivamente, y ya que esta es una solución óptima para la relajación, ¡tiene una gran función heurística admisible y cosistente !

Otro punto a considerar, es que incluso puedes obtener una mejor heurística si consideras las paredes, esto es un problema mucho más difícil, así que no lo hice mucho, pero noté que si atas a Pacman en un rectángulo con la próxima fruta óptima, Tendrá que pagar al menos 2 acciones más si hay alguna línea de pared vertical u horizontal COMPLETA entre ellas, ya que tendría que salir del rectángulo delimitador y volver a ingresarlo, pagando al menos 2 acciones al hacer cada una de esas paredes. Esto puede ser examinado más a fondo y también puede encontrar más características especiales en este rectángulo.