¿Por qué el aprendizaje por refuerzo se usa tan raramente en la búsqueda de caminos?

El venerable algoritmo teórico del gráfico de la ruta más corta A * y las mejoras posteriores (por ejemplo, Hierarchical Annotated A *) es claramente la técnica de elección para encontrar rutas en el desarrollo del juego.

En cambio, me parece que RL es un paradigma más natural para mover un personaje por un espacio de juego.

Y, sin embargo, no conozco un solo desarrollador de juegos que haya implementado un motor de búsqueda de caminos basado en Reinforcement Learning. (No deduzco de esto que la aplicación de RL en la búsqueda de rutas es 0, solo que es muy pequeña en relación con A * y amigos).

Cualquiera sea la razón, no es porque estos desarrolladores no estén al tanto de RL, como lo demuestra el hecho de que RL se usa con frecuencia en otras partes del motor del juego.

Esta pregunta no es un pretexto para ofrecer una opinión sobre RL en la búsqueda de rutas; de hecho, supongo que la preferencia tácita por A * et al. sobre RL es correcto, pero esa preferencia no es obvia para mí y tengo mucha curiosidad acerca de la razón, especialmente de cualquiera que haya intentado usar RL para encontrar caminos.

Me imagino que es porque, dado que no obtendrá una generalización útil de la política de nada más que problemas de juguetes, y la función de recompensa se verá sospechosamente como una heurística A *, la posibilidad de usar RL tiende a parecer realmente forma demasiado eficiente e indefinida de obtener resultados idénticos a los de A * en el mejor de los casos, pero que probablemente no sean tan buenos.

Esto puede ser injusto para RL, y si es así, me interesaría saber por qué, pero realmente no veo nada que indique eso.

Muchos de nosotros también recordamos cómo era la búsqueda de caminos en los juegos antes de la adopción generalizada de A *, y no estamos ansiosos por infligir nada parecido a esos días en los jugadores, o sufrir las consecuencias del mercado al hacerlo.

Sin saber mucho sobre RL, intentaré responder tu pregunta con otras preguntas:

Usando RL, ¿puedes determinar si es posible llegar al punto A desde el punto B?

¿Puede RL garantizar un comportamiento de navegación reproducible / coherente / comprobable?

¿Cómo se comparan los requisitos de tiempo de ejecución de memoria y CPU con A *? Del mismo modo, ¿cuánto puede calcular previamente en comparación con, por ejemplo, mallas de navegación?

¿Cómo funciona RL en un entorno con colisión dinámica?

¿Cuánto más difícil es comprender e implementar RL correctamente frente a, digamos, comportamientos de dirección?

¿Hay algún buen proveedor de middleware para RL?

Tal vez esas preguntas puedan ayudarte con tu respuesta.

Estoy confundido por la sugerencia de que RL es "un paradigma más natural". No veo cómo el aprendizaje por refuerzo se asigna al dominio del problema en un lugar tan limpio o preciso como la búsqueda de gráficos. Por lo general, no desea que un agente aprenda; ha asumido que ya conoce la ruta. En cambio, desea que elijan y usen la ruta más directa disponible, y la búsqueda de gráficos facilita eso de una manera casi óptima. Si usara RL fuera de línea para calcular la mejor dirección a seguir en un nodo dado para un destino determinado, eso terminaría generando un equivalente general de A *, excepto que requeriría mucha más memoria * y también requeriría que los desarrolladores fueran muy cuidadosos asegúrese de que todos los nodos se exploraron adecuadamente durante el entrenamiento. Y ese entrenamiento solo arrojará un valor que ya podemos aproximar muy bien con la ecuación de Pitágoras, debido a que sabemos de antemano que el gráfico obedece las reglas de distancia euclidianas. (Por supuesto, este no es el caso para todas las situaciones en las que se puede emplear la búsqueda de gráficos y / o el aprendizaje por refuerzo).

(Con respecto al problema de memoria: si tenía 1000 posibles posiciones cuantizadas en un mapa, eso es 1000 nodos más 1000 * M bordes (donde M es el número promedio de nodos alcanzables desde cualquier otro nodo). Eso, más la heurística, es suficiente para A * para operar. Para que el refuerzo aprenda a funcionar, al menos en la forma en que lo imagino, también necesitaría 1000 entradas para cada uno de esos 1000 * M bordes, para obtener el valor de recompensa de seguir ese borde para cualquiera de los 1000 posibles destinos. Esa es una gran cantidad de datos, y cada uno de ellos debe ser razonablemente preciso para evitar bucles, desvíos o callejones sin salida.

Pathfinding es un problema relativamente "resuelto", RL no lo es.

Con A *, los desarrolladores pueden crear heurísticas rápidamente y mejorarlas con el tiempo. RL (estoy hablando de Q-Learning, cuando me refiero a RL aquí), toma tiempo para calcular las mejores tasas de aprendizaje y factores de descuento (tiempo que vale la pena gastar en otros aspectos del juego).

Realmente depende de los tipos de juego. Si todo en el juego es estático, es más eficiente usar la búsqueda A *. Sin embargo, si hay otros jugadores humanos moviéndose en la misma área, la búsqueda A * garantiza el fracaso. Una búsqueda * no tiene idea de hacia dónde se dirigen otros jugadores. Por otro lado, RL puede modelar el comportamiento de otros jugadores y encontrar un mejor camino que tenga en cuenta el movimiento de otros jugadores.