Búsqueda de rutas mediante redes neuronales en videojuegos

ELO 329: Diseño y Programación Orientada a Objetos

Proyecto Grupal

Integrantes:

Jonathan Olavarría
Juan Chacón 		jolavarriam [at] elo [dot] utfsm [dot] cl
nankutremo [at] gmail [dot] com
Profesor: Agustín González V.






Indice:

Descripción del Problema
Análisis del Problema
Diseño de la Solución
Dificultades
Implementación

Descripción del Problema

El problema de encontrar una buena ruta o camino entre 2 puntos cualquiera dentro de un entorno con obstáculos, es uno de los tópicos de inteligencia artificial más comunes en la programación de videojuegos. Los algoritmos clásicos de Pathfinding, como A*, son costosos y requieren de un mapeo detallado de la topología de la zona de juego antes de poder ser recorrida, lo cual impide que el entorno cambie dinámicamente en tiempo real sin que el sistema deba hacer cálculos extras y ajustes adicionales para adaptarse a estos cambios, cosa que lo hace inviable de implementar debido a estas restricciones.

Análisis del Problema

El agente será dotado de una red neuronal entrenada para ir desde su posición incial hasta su posición final. El problema de encontrar un buen camino entre dos puntos está restringido a 2 habilidades que debe aprender el agente: Lo primero que se viene a la mente es tener un ambiente de prueba con obstáculos, que fácilmente puede ser un mapa con zonas blancas (permitidas) y negras (no permitidas). La problemática que surge es cómo el agente sabe que no debe avanzar más para no entrar en una zona negra, para ello se pensó en dotar al agente con sensores a distancia que detecten un choque antes de ocurrir. Lo segundo es a considerar es qué algoritmo de entrenamiento usar, para ello se pensó en un aprendizaje desatendido y fácil de implementar para este modelo de 'entorno de prueba', por lo que se optó por realizar el trabajo con un algoritmo genético.
Para realizar este entrenamiento se decide programar una GUI que nos permita implementar un entrenamiento de redes neuronales con las siguientes características:
Son 3 los casos de usos más importantes:

Caso de Uso Nº 1:

Nombre: Estructura base de red Neuronal.
Propósito: Permite generar una topología de red neuronal base.
Actor: Usuario.
Pre-Condiciones: Debe existir un objeto en donde guardar la estructura base.
Descripción: El usuario crea capas en la red neuronal a las cuales puede agregar nodos. Los nodos son conectados entre sí mediante enlaces. La red neuronal es guardada en un archivo para ser reutilizada en el futuro.
Post-Condiciones: Solo nodos de capas contiguas pueden ser conectados.

Curso normal de eventos

Curso alternativo de eventos
Paso 1: El usuario crea una o varias capas
Paso 2: El usuario selecciona una capa
Paso 3: El usuario agrega uno o varios nodos a esa capa
Volver a paso 1 o 2, o ir a paso 4
Paso 4: El usuario selecciona nodos
Paso 5: El usuario conecta/desconecta los nodos seleccionados Los nodos seleccionados no están en capas contiguas: Los nodos no se conectan/desconectan
Volver a paso 1 o 2 o 4, o ir a paso 6
Paso 6: Guardar red neuronal en el disco duro Error de escritura: No se realiza el guardado


Caso de Uso Nº 2:

Nombre: Algoritmo Genético.
Propósito: Permite entrenar al agente para que llegue correctamente al objetivo.
Actor: Usuario.
Pre-Condiciones: Debe existir una red neuronal con la topología base.
Descripción: El usuario configura la GUI y presiona 'start', la red neuronal se entrena en forma desatendida. Se entregan estadísticas al usuario.

Curso normal de eventos

Curso alternativo de eventos
Paso 1: El usuario configura la GUI.
Paso 2: El usuario presiona 'start' para comenzar a entrenar. La GUI está mal configurada o hay parámetros en blanco: Se avisa al usuario el detalle para que configure bien la GUI y no se realiza el algoritmo.
Paso 3: Se realiza el algoritmo con información y estadísticas relevantes para el usuario.

Volver al índice...

Diseño de la Solución

La solución fue programada en lenguaje Delphi (Object Pascal) por ser un lenguaje para desarrollo rápido de aplicaciones, ser orientado a objetos y por tener GLScene, una librería gráfica sencilla y poderosa para gráficos en 2D y 3D. Se presenta a continuación un diagrama de clases UML simplificado de nuestra aplicación:







Se presenta a continuación 3 capturas de pantalla de nuestra aplicación:



Configuración de la GUI:




Mejor red neuronal dada por el algoritmo:




Verificación de comportamiento correcto en el simulador:

Volver al índice...

Dificultades

La principal dificultad fue la complejidad de la aplicación, producto del poco tiempo del que se dispuso para desarrollarla, considerando el tiempo requerido para la lógica del programa y la intefáz de usuario.

Volver al índice...

Implementación

El programa fue compilado en Delphi 2009 Architect y para su desarrollo se usó la librería gráfica GLScene. El código está disponible para descargar comprimido en el siguiente link y la documentación del código fue generado con el programa DelphiCodeToDoc.

Volver al índice...



UTFSM 2010