L'un des projets que j'avais longtemps rêvé de mettre en œuvre était des robots de tâches modulaires avec mémoire. Le but ultime du projet était de créer un monde avec des créatures capables d'agir indépendamment et collectivement.
J'avais l'habitude de programmer des générateurs de monde, donc je voulais peupler le monde avec des robots simples qui utilisent l'IA pour déterminer leur comportement et leurs interactions. Ainsi, grâce à l'influence des acteurs sur le monde, il a été possible d'augmenter ses détails.
J'ai déjà implémenté le système de pipeline de tâches Javascript de base (car cela m'a simplifié la vie), mais je voulais quelque chose de plus fiable et évolutif, j'ai donc écrit ce projet en C ++. Le concours pour la mise en œuvre du jardin procédural dans la génération subreddit / r / procédurale m'a conduit à cela (d'où le sujet correspondant).
Dans mon système, la simulation se compose de trois composants: le monde, la population et un ensemble d'actions les reliant. Par conséquent, j'avais besoin de créer trois modèles, dont je parlerai dans cet article.
Pour augmenter la difficulté, je voulais que les acteurs conservent des informations sur les expériences précédentes avec le monde et utilisent les connaissances sur ces interactions dans les actions futures.
Lors de la création d'un modèle du monde, j'ai choisi un chemin simple et j'ai utilisé le bruit Perlin pour le placer à la surface de l'eau. Tous les autres objets dans le monde étaient localisés de manière absolument aléatoire.
Pour le modèle de population (et sa «mémoire»), j'ai simplement créé une classe avec plusieurs caractéristiques et coordonnées. C'était censé être une simulation basse résolution. La mémoire est une file d'attente, les robots sont examinés, enregistrent des informations sur leur environnement, écrivent dans la file d'attente et gèrent cette file d'attente comme une interprétation de leur mémoire.
Pour connecter ces deux systèmes d'actions, j'ai voulu créer un cadre de tâches primitives à l'intérieur d'un système hiérarchique de files d'attente de tâches afin que les entités individuelles puissent implémenter un comportement complexe dans le monde.
Exemple de carte. L'eau a pris la forme d'une rivière sans le vouloir. Tous les autres éléments sont situés au hasard, y compris la fourmilière, qui dans cette graine est trop décalée vers le bord (mais la rivière est magnifique).J'ai décidé qu'un tas de fourmis dans les feuilles de collecte d'herbe serait un bon modèle de test qui garantit la fiabilité de la mise en œuvre des fonctions de base (et du système de file d'attente des tâches dans son ensemble) et empêche les fuites de mémoire (il y en avait beaucoup).
Je veux décrire plus en détail la structure des systèmes de tâches et de la mémoire, et montrer également comment la complexité a été créée à partir (principalement) de fonctions de base primitives. Je veux également montrer quelques "fuites de mémoire de fourmis" amusantes que vous pouvez rencontrer lorsque les fourmis commencent à tourner follement en rond à la recherche d'herbe ou à rester immobile et à ralentir le programme.
Structure générale
J'ai écrit cette simulation en C ++ et utilisé SDL2 pour le rendu (j'ai déjà écrit une petite classe de présentation pour SLD2 auparavant). J'ai également utilisé l'implémentation A * (légèrement modifiée) que j'ai trouvée sur github car
mon implémentation était désespérément lente et je ne comprenais pas pourquoi.
Une carte n'est qu'une grille 100 × 100 à deux couches - une couche de sol (utilisée pour rechercher des chemins) et une couche de remplissage (pour compléter l'interaction et rechercher des chemins). La classe mondiale gère également diverses fonctions cosmétiques, telles que la croissance de l'herbe et de la végétation. J'en parle maintenant car ce sont les seules parties qui ne seront pas décrites dans l'article.
La population
Les robots étaient dans une classe avec des propriétés décrivant une seule créature. Certains d'entre eux étaient cosmétiques, d'autres influençaient l'exécution des actions (par exemple, la capacité de voler, le champ de vision, ce qu'il mange et ce que la créature peut porter).
Les plus importantes ici étaient les valeurs auxiliaires qui déterminent le comportement. À savoir: un vecteur contenant leur chemin actuel A *, de sorte qu'il n'a pas besoin d'être compté à chaque cycle d'horloge (cela économise du temps de calcul et vous permet de simuler plus de bots), et une file d'attente de mémoire qui définit l'interprétation des créatures de leur environnement.
File d'attente mémoire
Une file d'attente de mémoire est une file d'attente simple contenant un ensemble d'objets de mémoire dont la taille est limitée par une propriété de bot. Chaque fois que de nouveaux souvenirs étaient ajoutés, ils étaient poussés vers l'avant et tout ce qui dépassait les frontières derrière était coupé. Grâce à cela, certains souvenirs pourraient être plus «frais» que d'autres.
Si le bot voulait rappeler des informations de la mémoire, alors il a créé un objet mémoire (demande) et l'a comparé avec ce qui était en mémoire. Ensuite, la fonction de rappel a renvoyé un vecteur de mémoires correspondant à tout ou partie des critères spécifiés dans la requête.
class Memory{ public:
Les mémoires consistent en un simple objet contenant plusieurs propriétés. Ces propriétés de mémoire sont considérées comme «associées» les unes aux autres. Chaque mémoire reçoit également une valeur de «rappel», qui est itérée chaque fois que les mémoires sont mémorisées par la fonction de rappel. Chaque fois que le bot se souvient des mémoires, il effectue à son tour un tri en une seule passe, en commençant par derrière, en changeant l'ordre des mémoires si le score de rappel d'une mémoire plus ancienne est supérieur à celui d'une nouvelle. Grâce à cela, certaines mémoires peuvent être plus «importantes» (avec de grandes tailles de mémoire) et stockées plus longtemps dans la file d'attente. Au fil du temps, ils seront remplacés par de nouveaux.
Files d'attente de mémoire
J'ai également ajouté plusieurs opérateurs surchargés à cette classe afin que des comparaisons directes entre la file d'attente de mémoire et la requête puissent être effectuées, en comparant «toutes» ou «toutes» les propriétés, de sorte que seules les propriétés spécifiées soient écrasées lorsque la mémoire est écrasée. Grâce à cela, nous pouvons avoir la mémoire de l'objet associée à un endroit, mais si nous regardons à nouveau cet endroit et que l'objet n'est pas là, nous pouvons mettre à jour la mémoire en la remplaçant par de la mémoire contenant une nouvelle tuile de remplissage, en utilisant la requête correspondant à cet endroit .
void Bot::updateMemory(Memory &query, bool all, Memory &memory){
Dans le processus de création du code pour ce système, j'ai beaucoup appris.
Système de tâches
La nature de la boucle de jeu ou du rendu est que les mêmes fonctions sont répétées dans chaque mesure, cependant, je voulais implémenter un comportement non cyclique dans mes bots.
Dans cette section, j'expliquerai deux points de vue sur la structure du système de tâches conçu pour contrer cet effet.
Structure ascendante
J'ai décidé de passer de bas en haut et de créer un ensemble «d'actions primitives» que les bots devraient effectuer. Chacune de ces actions ne dure qu'un seul battement. Avec une bonne bibliothèque de fonctions primitives, nous pouvons les combiner en actions complexes constituées de plusieurs fonctions primitives.
Exemples de telles actions primitives:
Notez que ces actions contiennent des références au monde et à la population, vous permettant de les modifier.
- L'attente fait que la créature ne fait rien dans cette boucle.
- Look analyse l'environnement et met en file d'attente de nouveaux souvenirs.
- Swap prend un objet dans la main de la créature et le remplace par un gisant sur le sol.
- Consommer détruit l'objet dans la main de la créature.
- Step prend le chemin calculé actuel vers la destination et effectue une étape (avec un tas de vérifications d'erreur).
- ... et ainsi de suite.
Toutes les fonctions de tâche sont membres de ma classe de tâches; après des tests rigoureux, ils ont prouvé leur fiabilité et leur capacité à se combiner en tâches plus complexes.
Dans ces fonctions secondaires, nous construisons des fonctions en enchaînant simplement d'autres tâches:
- La tâche de marche n'est que quelques étapes (avec gestion des erreurs)
- La tâche de prise est la tâche de recherche et d'échange (elle est nécessaire en raison du traitement de la mémoire des fourmis, que j'expliquerai plus tard)
- La tâche inactive est de sélectionner un endroit au hasard et de s'y déplacer (en utilisant la marche), d'attendre plusieurs cycles (en utilisant l'attente) et de répéter ce cycle un nombre donné de fois
- ... et ainsi de suite
D'autres tâches sont plus compliquées. La tâche de recherche exécute une requête de mémoire pour rechercher les mémoires de lieux contenant l'objet «nourriture» (comestibles pour ce type de bot). Elle télécharge ces souvenirs et les parcourt tous, «à la recherche» de nourriture (dans le cas des fourmis, c'est de l'herbe). S'il n'y a pas de souvenirs de nourriture, la tâche oblige la créature à parcourir le monde au hasard et à regarder autour d'elle. En regardant et en étudiant (en faisant un «regard» avec viewRadius = 1; c'est-à-dire en ne regardant que la tuile en dessous), la créature peut mettre à jour sa mémoire avec des informations sur son environnement, en recherchant intelligemment et délibérément de la nourriture.
Une tâche fourragère plus généralisée consiste à trouver de la nourriture, à ramasser de la nourriture, à inspecter (pour mettre à jour la mémoire et à trouver de la nourriture dans le quartier), à rentrer chez elle et à stocker de la nourriture.
Vous remarquerez peut-être que les fourmis sortent de la fourmilière et cherchent de la nourriture à dessein. En raison de l'initialisation, le chemin initial des fourmis est dirigé vers un point aléatoire, car leur mémoire à t = 0 est vide. Ensuite, ils reçoivent l'ordre de ramasser de la nourriture dans la tâche de fourrage, et ils regardent également autour de eux, s'assurant qu'il n'y a plus de nourriture. De temps en temps, ils commencent à errer, car ils manquent d'endroits où ils ont vu de la nourriture (myopie inquiétante).Et enfin, le bot a une «vue» qui détermine le type d'IA qui lui est attribué. Chaque vue est associée à une tâche de contrôle qui définit tout son comportement: elle est constituée d'une cascade de tâches de plus en plus petites, facilement déterminées par un ensemble de files d'attente mémoire et de tâches primitives. Ce sont des tâches comme Ant et Bee.
Structure descendante
Si vous regardez de haut en bas, le système se compose d'une classe maître de tâches qui coordonne les tâches de contrôle et leur exécution pour chaque bot individuel sur la carte.
Taskmaster dispose d'un vecteur de tâches de contrôle, chacune étant associée à un bot. Chaque tâche de contrôle, à son tour, possède une file d'attente de sous-tâches qui sont chargées lors de la première initialisation de l'objet de tâche avec la fonction de tâche associée.
class Task{ public:
Chaque objet de tâche dans la file d'attente stocke un tableau d'arguments, qu'il transmet au gestionnaire de fonctions associé. Ces arguments déterminent le comportement de ces tâches primitives créées de manière aussi générale que possible. Les arguments sont passés par référence, afin que l'objet de tâche dans la file d'attente puisse stocker ses arguments et permettre à ses sous-fonctions d'être modifiées, vous pouvez donc implémenter des choses comme des itérations pour attendre un certain nombre de ticks ou de demandes pour collecter un certain nombre d'éléments, etc. Les sous-fonctions modifient la valeur de l'itérateur (argument [n]) de la fonction parent par référence et font dépendre sa condition de succès de sa valeur.
Dans chaque mesure, le taskmaster parcourt la liste des tâches de contrôle et les exécute en appelant leur méthode perform. La méthode perform, à son tour, examine l'élément supérieur de la file d'attente à l'intérieur de la tâche et l'exécute avec les arguments de la tâche. Ainsi, vous pouvez descendre en cascade dans la file d'attente des tâches, en effectuant toujours la tâche la plus élevée. Ensuite, la valeur de retour de la tâche détermine l'achèvement de la tâche.
Lorsqu'une tâche primitive retourne vraie, elle a atteint son point stable, ou du moins ne doit pas être répétée (par exemple, l'étape retourne vrai lorsque la créature a atteint le point final). Autrement dit, sa condition de retour est satisfaite et il est supprimé de la file d'attente afin que la tâche suivante puisse être terminée dans la mesure suivante.
Une tâche contenant une file d'attente de tâches renvoie true après que la file d'attente est vide. Pour cette raison, il est possible de créer des tâches complexes avec la structure de files d'attente et de sous-files d'attente dans lesquelles les mêmes fonctions sont constamment appelées, mais chaque appel itère l'état du jeu et l'état de la tâche d'une étape.
Enfin, les tâches de contrôle utilisent une structure simple: elles sont appelées à chaque cycle, ne chargent la tâche que si elles sont vides et exécutent les tâches chargées dans leur file d'attente.
Avec l'aide de ma boucle de file d'attente (voir le code), je peux exécuter à plusieurs reprises une fonction et à chaque fois exécuter l'élément supérieur de sa file d'attente, en poussant les éléments hors de lui si l'appel de leur méthode perform renvoie true.
Résultats
Tout cela est enveloppé dans libconfig, donc les paramètres de simulation sont très faciles à modifier. Vous pouvez coder de nombreuses tâches de contrôle sans problème (j'ai créé des fourmis et des abeilles), et définir et charger de nouvelles espèces à l'aide de libconfig est étonnamment simple.
Ils ont été élégamment chargés dans la simulation. Grâce à une nouvelle recherche améliorée des chemins, je peux simuler un grand nombre de robots actifs individuels collectant de la nourriture sur un plan bidimensionnel.
Simulation de 40 fourmis ramassant de l'herbe en même temps. Les chemins qu'ils créent dans le sable sont dus au poids accru attribué à la terre «vierge». Cela conduit à la création de "routes de fourmis" caractéristiques. Ils peuvent également être interprétés comme des phéromones, mais ce serait plus comme la vérité si les fourmis échangeaient effectivement des souvenirs.La modularité de ce système assure la création rapide de nouvelles espèces dont le comportement est déterminé par une simple tâche de contrôle. Dans le code ci-dessus, vous pouvez voir que j'ai créé des vers et des abeilles IA en changeant simplement leur couleur, les restrictions de recherche de chemin (ils ne peuvent pas voler), la plage de visibilité et la taille de la mémoire. En même temps, j'ai changé leur comportement général, car tous ces paramètres sont utilisés par les fonctions des tâches primitives.
Débogage des mémoires Ant
La structure des tâches complexes et de la mémoire a conduit à des difficultés imprévues et à la nécessité de gérer les exceptions.
Voici trois bugs mémoire particulièrement complexes qui m'ont fait refaire les sous-systèmes:
Fourmis, courant, cercle
L'un des premiers insectes que j'ai dû affronter: des fourmis couraient follement le long du motif enfermé dans la place à la recherche d'herbe sur un sol nu. Ce problème est survenu car à cette époque, je n'avais pas encore implémenté de mise à jour de la mémoire. Les fourmis avaient des souvenirs de l'emplacement de la nourriture, et dès qu'elles ramassaient l'herbe et regardaient à nouveau autour, de nouveaux souvenirs se formaient.
Le problème était que la nouvelle mémoire était au même point, mais l'ancienne était conservée. Cela signifiait que dans le processus de recherche de nourriture, les fourmis se souvenaient et gardaient l'emplacement de la nourriture qui n'était plus valide, mais ces anciens souvenirs ont été conservés et ont supplanté de nouveaux (ils se souvenaient de cette délicieuse herbe).
Je l'ai corrigé comme suit: les données de l'objet sont simplement écrasées dans les vieux souvenirs, si nous voyons le même endroit et que l'objet a changé (par exemple, la créature voit qu'il n'y a plus d'herbe, mais ne se souvient pas qu'il y avait de l'herbe). Peut-être qu'à l'avenir, j'ajouterai simplement la propriété "invalide" à mes souvenirs pour que les robots puissent se souvenir d'anciennes informations qui peuvent être importantes, mais les informations qui ne sont plus valides "sont apparues" ("J'ai vu un ours ici, mais maintenant il n'y est plus").
Les fourmis ramassent des objets sous d'autres fourmis
De temps en temps (surtout avec un grand nombre de fourmis et une forte densité d'herbe), deux fourmis peuvent monter sur une tuile d'herbe dans une mesure et essayer de la ramasser. Cela signifie que la première fourmi est entrée dans la tuile, a regardé autour et a pris l'objet en 3 étapes. À son tour, la deuxième fourmi a fait de même, juste avant de soulever l'objet, une autre fourmi l'a arraché sous son nez. Il continua calmement ses tâches, examinant le même environnement que l'autre fourmi dans la mesure précédente, et traita sa ligne de mémoire de la même manière (car à ce stade, leurs souvenirs sont identiques). Cela a conduit la deuxième fourmi à copier le premier, à ne jamais ramasser d'objets et à suivre le premier, qui a fait tout le travail. J'ai remarqué cela parce que dans la simulation des cinq fourmis, seules trois étaient visibles. Il a fallu beaucoup de temps pour trouver la cause.
J'ai résolu ce problème en rendant la tâche d'échange primitive et en créant la tâche de prise, qui examine d'abord le sol pour voir s'il y a un objet. Si c'est le cas, il «échange», et sinon, il «attend» deux mouvements pour que l'autre fourmi parte définitivement. Dans un cas, cette action concerne deux mesures, dans l'autre - une mesure.
Lieux inaccessibles
Un autre bug désagréable qui m'a forcé à refaire le traitement de la mémoire était que certains endroits que la fourmi pouvait voir lui étaient inaccessibles. Ils sont survenus à cause de mon placement paresseux de «croix d'herbe» sur la terre, qui pendaient parfois au-dessus de l'eau. Cela m'a fait généraliser la tâche par étapes.
Lorsqu'elles transmettaient une demande de recherche de nourriture, les fourmis avaient souvent des souvenirs d'endroits qu'elles ne pouvaient vraiment pas atteindre (elles ont vu de l'herbe au-dessus de l'eau et ont
follement voulu la ramasser). Si elle n'était pas marquée dans leur mémoire (par exemple, la variable booléenne «accessible»), alors ils ont continué à s'en souvenir et à écrire dans la file d'attente jusqu'à ce que cette action soit la seule. Cela a provoqué une inhibition sévère, car ils ont
constamment effectué des opérations de recherche de chemin dans chaque mesure, essayant d'y arriver, et ont échoué .
La solution consistait à mettre à jour la mémoire dans la tâche d'étape si elle ne trouve pas le chemin d'accès à l'endroit, le marquant en mémoire comme inaccessible. De plus, la tâche de recherche interroge uniquement les lieux avec de la nourriture pour les souvenirs accessibles.
Système en général
En général, je veux dire - oui, je regrette d'avoir passé une semaine de ma vie sur un marathon de programmation, car j'ai été inspiré pour créer des bots qui font ce que je leur dis (et aussi ce qu'ils veulent faire!). J'ai dû faire quelques tours et j'ai beaucoup appris.
Le système que j'ai créé n'est pas fiable à 100% et je remarque encore des artefacts. Par exemple, comme direction pour analyser le look, l'action est utilisée de haut en bas et de gauche à droite, c'est-à-dire que la dernière mémoire se trouve dans le coin inférieur droit. Lors du rappel d'informations pour rechercher des objets, cela signifie que les créatures auront tendance à se déplacer vers le sud-est. Cela est particulièrement visible dans les grandes simulations, lorsque l'herbe pousse rapidement et se plie légèrement vers le sud-est, indépendamment des graines.
Améliorations
Je pense que des améliorations significatives sont nécessaires pour simuler des souvenirs plus complexes de créatures plus complexes.
Cela inclut l'augmentation de la fiabilité des fonctions de traitement de la mémoire, ainsi que l'ajout de nouvelles primitives, telles que «penser», et des dérivés de tâches de haut niveau, telles que «décider» ou «rêver». «Penser» peut être une action primitive d'une demande de mémoire. Un «rêve», à son tour, peut consister en plusieurs appels à la «réflexion»: choisir une mémoire aléatoire, obtenir une propriété aléatoire et la répéter à plusieurs reprises pour renforcer des thèmes communs ou des associations importantes.
Pour l'avenir, je prévois trois ajouts spécifiques:
- Ajouter la gestion des interruptions et la hiérarchisation des tâches
- Ajouter une communication entre les entités
- Ajouter une structure de groupe pour que les entités puissent s'identifier formellement
L'interruption du traitement et la hiérarchisation des tâches peuvent être nécessaires pour l'interaction entre les entités, car le bot ne peut pas continuer aveuglément ses activités lorsqu'il communique avec lui (il doit en quelque sorte «écouter») ou il est attaqué («fuir» ou «combattre» )
La communication entre les entités consiste probablement en une ou deux tâches primitives pour échanger des souvenirs ou faire des requêtes à la mémoire d'autres robots (par exemple, «dire» ou «demander»). De cette façon, des informations telles que l'emplacement de la nourriture ou d'autres ressources peuvent être transmises.
J'espère mettre en œuvre ces tâches et dresser un graphique du taux d'accumulation des ressources par un grand groupe avec et sans communication. La population suit déjà la quantité de nourriture collectée dans chaque mesure. Il serait intéressant de montrer que le partage de souvenirs peut affecter l'efficacité.
Le futur
La fonction la plus importante pour simuler des communautés consistera à ajouter des structures de groupe et à doter ces groupes de propriétés au niveau macro, par exemple, leurs «objectifs et responsabilités» communs. Cela nous donne une sorte de «graine» à partir de laquelle nous pouvons obtenir des tâches de haut niveau qui sont déléguées dans la hiérarchie des structures de groupe à des tâches de «haut» niveau inférieur qui affectent directement le monde. Il vous permet également de créer une forme de structure politique.
Un tel système est tout à fait autonome et la visualisation est simplement superposée au-dessus. Il sera très simple de remplacer les insectes par des humanoïdes, de collecter des ressources et de les stocker dans un certain endroit, afin qu'il grossisse.
La nature de la croissance de leur maison peut, par exemple, être très dépendante ou complètement indépendante des actions des robots. Différentes espèces peuvent avoir différentes tribus avec des caractéristiques et des tendances différentes.De plus, je peux combiner ce système avec des générateurs de cartes créés précédemment (élargissant la classe mondiale) pour rendre le monde plus réel.En conclusion
Dans un avenir proche, je prévois de remplacer les créatures par des personnes et de mettre en œuvre certaines des dernières fonctions. Peut-être que je publierai le code source complet lorsque j'améliorerai la qualité du système (à certains endroits, le code est plutôt chaotique).Attendez le prochain article. En attendant, voici une vidéo avec des abeilles à la recherche de pollen dans les fleurs; ils sont encodés en utilisant le même framework.J'ai choisi cette graine car le point de départ est situé sur une petite île. Cependant, les abeilles ne sont pas programmées pour retourner dans la ruche, mais simplement collecter constamment le pollen. Vous remarquerez peut-être que leur champ de vision est plus élevé et parfois ils se déplacent très intentionnellement vers la fleur qu'ils viennent de voir.... et voici la fonction membre Bee Task: bool Task::Bee(Garden &garden, Population &population, int (&arguments)[10]){