Uno de los proyectos que siempre había soñado implementar era los bots de tareas modulares con memoria. El objetivo final del proyecto era crear un mundo con criaturas capaces de actuar de forma independiente y colectiva.
Solía programar generadores mundiales, así que quería poblar el mundo con bots simples que usan IA para determinar su comportamiento e interacciones. Por lo tanto, gracias a la influencia de los actores en el mundo, fue posible aumentar sus detalles.
Ya implementé el sistema básico de canalización de tareas de Javascript (porque simplificó mi vida), pero quería algo más confiable y escalable, así que escribí este proyecto en C ++. La competencia por la implementación del jardín de procedimientos en el subreddit / r / proceduralgeneration me llevó a esto (de ahí el tema correspondiente).
En mi sistema, la simulación consta de tres componentes: el mundo, la población y un conjunto de acciones que los conectan. Por lo tanto, necesitaba crear tres modelos, que analizaré en este artículo.
Para aumentar la dificultad, quería que los actores mantuvieran información sobre experiencias previas con el mundo y usaran el conocimiento sobre estas interacciones en acciones futuras.
Al crear un modelo del mundo, elegí un camino simple y usé el ruido de Perlin para colocarlo en la superficie del agua. Todos los demás objetos en el mundo se ubicaron absolutamente al azar.
Para el modelo de población (y su "memoria"), simplemente creé una clase con varias características y coordenadas. Se suponía que esto era una simulación de baja resolución. La memoria es una cola, los robots se miran a su alrededor, guardan información sobre su entorno, escriben en la cola y administran esta cola como una interpretación de su memoria.
Para conectar estos dos sistemas de acciones, quería crear un marco de tareas primitivas dentro de un sistema jerárquico de colas de tareas para que las entidades individuales pudieran implementar comportamientos complejos en el mundo.
Mapa de muestra El agua tomó la forma de un río completamente sin querer. Todos los demás elementos se ubican al azar, incluido el hormiguero, que en esta semilla se desplaza demasiado hacia el borde (pero el río se ve hermoso).Decidí que un montón de hormigas en el pasto recolectando hojas será un buen modelo de prueba que garantiza la confiabilidad de la implementación de funciones básicas (y el sistema de colas de tareas en su conjunto) y evita pérdidas de memoria (había muchas).
Quiero describir con más detalle la estructura de los sistemas de tareas y la memoria, y también mostrar cómo se creó la complejidad a partir de (principalmente) funciones básicas primitivas. También quiero mostrar algunas divertidas "fugas de memoria de las hormigas" que puede encontrar cuando las hormigas comienzan a correr locamente en círculos en busca de hierba o se detienen y hacen que el programa se ralentice.
Estructura general
Escribí esta simulación en C ++ y usé SDL2 para renderizar (ya escribí una pequeña clase de presentación para SLD2 antes). También usé la implementación A * (ligeramente modificada) que encontré en github porque
mi implementación fue irremediablemente lenta y no podía entender por qué.
Un mapa es solo una cuadrícula de 100 × 100 con dos capas: una capa de suelo (utilizada para buscar rutas) y una capa de relleno (para completar la interacción y buscar rutas). La clase mundial también maneja varias funciones cosméticas, como el crecimiento de hierba y vegetación. Estoy hablando de esto ahora porque estas son las únicas partes que no se describirán en el artículo.
La población
Los bots estaban en una clase con propiedades que describían una sola criatura. Algunos de ellos eran cosméticos, otros influyeron en la ejecución de acciones (por ejemplo, la capacidad de volar, el rango de visión, lo que come y lo que la criatura puede usar).
Los más importantes aquí fueron los valores auxiliares que determinan el comportamiento. A saber: un vector que contiene su ruta actual A *, de modo que no es necesario contarlo en cada ciclo de reloj (esto ahorra tiempo de cálculo y le permite simular más bots), y una cola de memoria que define la interpretación de las criaturas de su entorno.
Cola de memoria
Una cola de memoria es una cola simple que contiene un conjunto de objetos de memoria de tamaño limitado por una propiedad bot. Cada vez que se agregaban nuevos recuerdos, se avanzaban y todo lo que iba más allá de las fronteras se cortaba. Gracias a esto, algunos recuerdos podrían ser más "frescos" que otros.
Si el bot quería recuperar información de la memoria, entonces creó un objeto de memoria (solicitud) y lo comparó con lo que había en la memoria. Luego, la función de recuperación devolvió un vector de memorias que coinciden con cualquiera o todos los criterios especificados en la consulta.
class Memory{ public:
Los recuerdos consisten en un objeto simple que contiene varias propiedades. Estas propiedades de memoria se consideran "asociadas" entre sí. A cada memoria también se le asigna un valor de "recordar puntaje", que se repite cada vez que la memoria recuerda la memoria. Cada vez que el bot recuerda los recuerdos, realiza una clasificación de una sola pasada, comenzando desde atrás, cambiando el orden de los recuerdos si el puntaje de memoria de una memoria anterior es mayor que el de una nueva. Gracias a esto, algunos recuerdos pueden ser más "importantes" (con grandes tamaños de memoria) y almacenarse más tiempo en la cola. Con el tiempo, serán reemplazados por otros nuevos.
Colas de memoria
También agregué varios operadores sobrecargados a esta clase para que se puedan realizar comparaciones directas entre la cola de memoria y la consulta, comparando las propiedades "cualquiera" o "todas", de modo que solo se sobrescriban las propiedades especificadas cuando se sobrescribe la memoria. Gracias a esto, podemos tener la memoria del objeto asociada a algún lugar, pero si miramos este lugar nuevamente y el objeto no está allí, podemos actualizar la memoria sobrescribiéndola con la memoria que contiene un nuevo mosaico de relleno, utilizando la consulta correspondiente a este lugar .
void Bot::updateMemory(Memory &query, bool all, Memory &memory){
En el proceso de creación del código para este sistema, aprendí mucho.
Sistema de tareas
La naturaleza del bucle o representación del juego es que las mismas funciones se repiten en cada medida, sin embargo, quería implementar un comportamiento no cíclico en mis bots.
En esta sección, explicaré dos puntos de vista sobre la estructura del sistema de tareas diseñado para contrarrestar este efecto.
Estructura de abajo hacia arriba
Decidí moverme de abajo hacia arriba y crear un conjunto de "acciones primitivas" que los bots deberían realizar. Cada una de estas acciones dura solo un latido. Con una buena biblioteca de funciones primitivas, podemos combinarlas en acciones complejas que consisten en varias funciones primitivas.
Ejemplos de tales acciones primitivas:
Tenga en cuenta que estas acciones contienen referencias tanto al mundo como a la población, lo que le permite cambiarlas.
- Esperar hace que la criatura no haga nada en este bucle.
- Look analiza el entorno y pone en cola nuevos recuerdos.
- Swap toma un objeto en la mano de la criatura y lo reemplaza con uno que yace en el suelo.
- El consumo destruye el objeto en la mano de la criatura.
- El paso lleva la ruta calculada actual al destino y realiza un paso (con un montón de comprobaciones de error).
- ... y así sucesivamente.
Todas las funciones de tareas son miembros de mi clase de tarea; Después de pruebas rigurosas, han demostrado su fiabilidad y capacidad para combinarse en tareas más complejas.
En estas funciones secundarias, construimos funciones simplemente encadenando otras tareas:
- La tarea de caminar es solo unos pocos pasos (con manejo de errores)
- La tarea de toma es la tarea de mirar e intercambiar (es necesaria debido al procesamiento de memoria de hormigas, que explicaré más adelante)
- La tarea inactiva es seleccionar un lugar aleatorio y moverse allí (usando caminar), esperar varios ciclos (usar esperar) y repetir este ciclo un número determinado de veces
- ... y así sucesivamente
Otras tareas son más complicadas. La tarea de búsqueda ejecuta una consulta de memoria para buscar cualquier recuerdo de los lugares que contienen el objeto "comida" (comestible para este tipo de bot). Ella descarga estos recuerdos y los recorre a todos, "buscando" comida (en el caso de las hormigas, esto es hierba). Si no hay recuerdos de comida, la tarea hace que la criatura deambule aleatoriamente por el mundo y mire a su alrededor. Al observar y estudiar (haciendo una "mirada" con viewRadius = 1; es decir, mirando solo el mosaico debajo), la criatura puede actualizar su memoria con información sobre su entorno, buscando comida de manera inteligente y decidida.
Una tarea de forraje más generalizada consiste en encontrar comida, recoger comida, inspeccionar (para actualizar la memoria y encontrar comida en el vecindario), regresar a casa y almacenar comida.
Puede notar que las hormigas salen del hormiguero y buscan alimento a propósito. Debido a la inicialización, la ruta inicial de las hormigas se dirige a un punto aleatorio, porque su memoria en t = 0 está vacía. Luego se les da la orden de recoger comida en la tarea de forraje, y también miran a su alrededor, asegurándose de que no haya más comida. De vez en cuando comienzan a vagar, porque se quedan sin lugares en los que vieron comida (miopía ominosa).Y finalmente, el bot tiene una "vista" que determina el tipo de IA que se le asigna. Cada vista está asociada con una tarea de control que define todo su comportamiento: consiste en una cascada de tareas cada vez más pequeñas, determinadas fácilmente por un conjunto de colas de memoria y tareas primitivas. Estas son tareas como Ant and Bee.
Estructura de arriba hacia abajo
Si observa de arriba a abajo, el sistema consiste en una clase maestra de tareas que coordina las tareas de control y su ejecución para cada bot individual en el mapa.
Taskmaster tiene un vector de tareas de control, cada una de las cuales está asociada con un bot. Cada tarea de control, a su vez, tiene una cola de subtareas que se cargan durante la primera inicialización del objeto de tarea con la función de tarea asociada.
class Task{ public:
Cada objeto de tarea en la cola almacena una matriz de argumentos, que pasa al manejador de funciones asociado. Estos argumentos determinan el comportamiento de estas tareas primitivas creadas de la manera más general posible. Los argumentos se pasan por referencia, por lo que el objeto de tarea en la cola puede almacenar sus argumentos y permitir que se modifiquen sus subfunciones, por lo que puede implementar cosas como iteraciones para esperar un cierto número de ticks o solicitudes para recopilar un cierto número de elementos, etc. Las subfunciones cambian el valor del iterador (argumento [n]) de la función padre por referencia y hacen que su condición de éxito dependa de su valor.
En cada medida, el administrador de tareas revisa la lista de tareas de control y las ejecuta llamando a su método de ejecución. El método de ejecución, a su vez, mira el elemento superior de la cola dentro de la tarea y lo ejecuta con argumentos de la tarea. Por lo tanto, puede descender en la cola de tareas, siempre realizando la tarea más alta. Luego, el valor de retorno de la tarea determina la finalización de la tarea.
Cuando una tarea primitiva devuelve verdadero, ha alcanzado su punto estable, o al menos no debe repetirse (por ejemplo, el paso devuelve verdadero cuando la criatura ha alcanzado el punto final). Es decir, se cumple su condición de devolución y se elimina de la cola para que la siguiente tarea se pueda completar en la siguiente medida.
Una tarea que contiene una cola de tareas devuelve verdadero después de que la cola esté vacía. Debido a esto, es posible crear tareas complejas con la estructura de colas y subcolas en las que se llaman constantemente las mismas funciones, pero cada llamada itera el estado del juego y el estado de la tarea en un paso.
Finalmente, las tareas de control usan una estructura simple: se llaman en cada ciclo, cargan la tarea solo si están vacías y, de lo contrario, realizan tareas cargadas en su cola.
Con la ayuda de mi bucle de cola (ver código), puedo ejecutar repetidamente una función y cada vez ejecutar el elemento superior en su cola, empujando elementos fuera de él si llamar a su método de ejecución devuelve verdadero.
Resultados
Todo esto está envuelto en libconfig, por lo que los parámetros de simulación son muy fáciles de cambiar. Puede codificar muchas tareas de control sin problemas (creé hormigas y abejas), y definir y cargar nuevas especies usando libconfig es sorprendentemente simple.
Fueron elegantemente cargados en la simulación. Gracias a una nueva búsqueda mejorada de rutas, puedo simular una gran cantidad de robots activos individuales que recolectan alimentos en un plano bidimensional.
Simulación de 40 hormigas recolectando pasto al mismo tiempo. Los caminos que crean en la arena se deben al mayor peso asignado a la tierra "virgen". Esto lleva a la creación de "carreteras de hormigas" características. También se pueden interpretar como feromonas, pero sería más como la verdad si las hormigas realmente intercambiaran recuerdos.La modularidad de este sistema asegura la creación rápida de nuevas especies cuyo comportamiento está determinado por una simple tarea de control. En el código anterior, puede ver que creé gusanos y abejas IA simplemente cambiando su color, las restricciones de búsqueda de ruta (no pueden volar), el rango de visibilidad y el tamaño de la memoria. Al mismo tiempo, cambié su comportamiento general, porque todos estos parámetros son utilizados por funciones de tareas primitivas.
Depuración de recuerdos de hormigas
La estructura de tareas complejas y memoria ha llevado a dificultades imprevistas y la necesidad de manejar excepciones.
Aquí hay tres errores de memoria particularmente complejos que me hicieron rehacer los subsistemas:
Hormigas corriendo en círculo
Uno de los primeros errores que tuve que enfrentar: las hormigas corrían locamente a lo largo del patrón encerrado en la plaza en busca de hierba en el suelo desnudo. Este problema surgió porque en ese momento aún no había implementado una actualización de memoria. Las hormigas tenían recuerdos de la ubicación de la comida, y tan pronto como recogieron la hierba y volvieron a mirar a su alrededor, se formaron nuevos recuerdos.
El problema era que la nueva memoria estaba en el mismo punto, pero la antigua estaba preservada. Esto significó que en el proceso de búsqueda de alimentos, las hormigas recordaron y mantuvieron la ubicación de los alimentos que ya no eran válidos, pero estos viejos recuerdos se conservaron y suplantaron a otros nuevos (recordaron esta deliciosa hierba).
Lo arreglé de la siguiente manera: los datos del objeto simplemente se sobrescriben en viejos recuerdos, si vemos el mismo lugar y el objeto ha cambiado (por ejemplo, la criatura ve que no hay más hierba allí, pero no recuerda que solía haber hierba). Quizás en el futuro simplemente agregue la propiedad "no válida" a mis recuerdos para que los bots puedan recordar información antigua que puede ser importante, pero la información que ya no es válida "apareció" ("Vi un oso aquí, pero ahora no está").
Las hormigas recogen objetos debajo de otras hormigas
De vez en cuando (especialmente con una gran cantidad de hormigas y una alta densidad de hierba), dos hormigas pueden subirse a una baldosa de hierba en una medida e intentar recogerla. Esto significó que la primera hormiga entró en el azulejo, miró a su alrededor y tomó el artículo en 3 pasos. A su vez, la segunda hormiga hizo lo mismo, solo justo antes de levantar el objeto, otra hormiga se lo arrebató debajo de la nariz. Continuó tranquilamente sus tareas, examinando el mismo entorno que la otra hormiga en la medida anterior, y procesó su línea de memoria de la misma manera (porque en esta etapa sus recuerdos son idénticos). Esto llevó a que la segunda hormiga copiara la primera, nunca recogiera objetos y siguiera a la primera, que realmente hizo todo el trabajo. Me di cuenta de esto porque en la simulación de las cinco hormigas, solo tres eran visibles. Me llevó mucho tiempo encontrar la causa.
Resolví este problema haciendo que la tarea de intercambio sea primitiva y creando la tarea de toma, que primero mira al suelo para ver si hay un objeto allí. Si es así, "intercambia", y si no, "espera" dos movimientos para que la otra hormiga definitivamente se vaya. En un caso, esta acción es para dos medidas, en el otro, para una medida.
Ubicaciones inalcanzables
Otro error desagradable que me obligó a rehacer el procesamiento de la memoria fue que algunos lugares que la hormiga podía ver eran inalcanzables para él. Surgieron debido a mi colocación perezosa de "cruces de hierba" en tierra, que a veces colgaba sobre el agua. Esto me hizo generalizar la tarea paso.
Al transmitir una solicitud de búsqueda de alimentos, las hormigas a menudo tenían recuerdos de lugares a los que realmente no podían llegar (vieron hierba sobre el agua y querían
locamente recogerla). Si no estaba marcado en su memoria (por ejemplo, la variable booleana "accesible"), continuaron recordando esto y escribiendo en la cola hasta que esta acción fue la única. Esto causó una inhibición severa, porque
constantemente realizaron operaciones de búsqueda de ruta en cada medida, tratando de llegar allí, y fallaron .
La solución fue actualizar la memoria en la tarea de pasos si no puede encontrar la ruta al lugar, marcándola en la memoria como inalcanzable. Además, la tarea de búsqueda solo consulta lugares con comida para obtener recuerdos accesibles.
Sistema en general
En general, quiero decir: sí, lamento haber pasado una semana de mi vida en un maratón de programación, porque me inspiró para crear bots que hagan lo que les digo (¡y también lo que quieren hacer!). Tuve que hacer algunos trucos y aprendí mucho.
El sistema que creé no es 100% confiable, y todavía noto algunos artefactos. Por ejemplo, como la dirección para analizar el aspecto, la acción se usa de arriba hacia abajo y de izquierda a derecha, es decir, el último recuerdo está en la esquina inferior derecha. Al recuperar información para buscar elementos, esto significa que las criaturas tenderán a moverse hacia el sureste. Esto es especialmente notable en simulaciones grandes, cuando la hierba crece rápidamente y se dobla ligeramente hacia el sureste, independientemente de la semilla.
Mejoras
Creo que se necesitan mejoras significativas para simular recuerdos más complejos de criaturas más complejas.
Esto incluye aumentar la confiabilidad de las funciones de procesamiento de memoria, así como agregar nuevas primitivas, como "pensar", y derivados de tareas de alto nivel, como "decidir" o "soñar". "Pensar" puede ser una acción primitiva de una solicitud de memoria. Un "sueño", a su vez, puede consistir en varias llamadas de "pensar": elegir una memoria aleatoria, obtener una propiedad aleatoria y repetirla repetidamente para reforzar temas comunes o asociaciones importantes.
Para el futuro, planeo tres adiciones específicas:
- Agregue manejo de interrupciones y priorización de tareas
- Agregar comunicación entre entidades
- Agregue una estructura de grupo para que las entidades puedan identificarse formalmente
La interrupción del procesamiento y la priorización de tareas pueden ser necesarias para la interacción entre entidades, porque el bot no puede continuar ciegamente sus actividades cuando se comunican con él (de alguna manera debe "escuchar") o es atacado ("huir" o "pelear" )
La comunicación entre entidades probablemente consiste en una o dos tareas primitivas para intercambiar recuerdos o hacer solicitudes a los recuerdos de otros bots (por ejemplo, "decir" o "preguntar"). De esta manera, se puede transmitir información como la ubicación de los alimentos u otros recursos.
Espero implementar estas tareas y elaborar un gráfico de la tasa de acumulación de recursos por un grupo grande con y sin comunicación. La población ya está rastreando la cantidad de alimentos recolectados en cada medida. Sería interesante mostrar que compartir recuerdos puede afectar la eficiencia.
El futuro
La función más importante para simular comunidades será agregar estructuras grupales y dotar a estos grupos de propiedades de nivel macro, por ejemplo, sus "objetivos y responsabilidades" comunes. Esto nos da una especie de "semilla" de la que podemos obtener tareas de alto nivel que se delegan en la jerarquía de las estructuras de grupo para "bajar" las tareas de alto nivel que afectan directamente al mundo. También ayuda a crear una forma de estructura política.
Tal sistema es bastante autosuficiente, y la visualización simplemente se superpone encima. Será muy sencillo reemplazar los insectos con humanoides, recolectar recursos y almacenarlos en algún lugar, para que crezca en tamaño.
La naturaleza del crecimiento de su hogar puede, por ejemplo, ser muy dependiente o completamente independiente de las acciones de los bots. Diferentes especies pueden tener diferentes tribus con diferentes características y tendencias.Además, puedo combinar este sistema con generadores de mapas creados previamente (expandiendo la clase mundial) para hacer que el mundo sea más real.En conclusión
En un futuro próximo, planeo reemplazar a las criaturas con personas e implementar algunas de las últimas funciones. Quizás publique el código fuente completo cuando mejore la calidad del sistema (en algunos lugares el código es bastante caótico).Espera el próximo artículo. Mientras tanto, aquí hay un video con abejas buscando polen en flores; están codificados usando el mismo marco.Elegí esta semilla porque el punto de partida se encuentra en una pequeña isla. Sin embargo, las abejas no están programadas para regresar a la colmena, sino que simplemente recolectan polen constantemente. Puede notar que su rango de visión es mayor y, a veces, se mueven intencionalmente a la flor que acaban de ver.... y aquí está la función miembro de Bee Task: bool Task::Bee(Garden &garden, Population &population, int (&arguments)[10]){