dimanche 23 juin 2019

Arduino progmem : Différence entre UNO et SAMD21

Puisque la RAM est si limitée sur un Arduino, il est important de l'utiliser à bon escient et surtout utiliser toute technique qui permet de tout simplement éviter de l'utiliser tout simplement. Un Arduino Uno utilisant un microcontroleur ATMEGA 328P n'a que 2 KByte de RAM mais 32 KBytes de mémoire Flash. Tout le programme compilé réside en Flash et bien qu'il soit possible d'avoir tellement de code en utilisant plein de librairie pour remplir ce 32KByte, la plupart du temps c'est pas mal vide là-dedans.

Il est possible d'ajouter des données dans cette espace Flash tant qu'elles sont utilisées qu'en lecture seule. Cependant, il faut ramener en RAM octet par octet pour en lire le contenue. La directive progmem indique au compilateur d'ajouter une variable en mémoire Flash et non en RAM.

Ex:

const PROGMEM char str_flash[] = "Je suis en memoire FLASH!";

 Ici, les 26 octets utilisés par cette chaine de caractères résident dans l'espace mémoire Flash et non en RAM, alors que:

const char str_flash[] = "Je suis en memoire FLASH!";

Réduit de 26 octets la RAM disponible et ce pour toute la durée d'exécution du programme.
Le compilateur inclus déjà une macro F() pour simplifier cette technique et les classe dérivant de Print tel de Serial permettent de passer en paramètre un pointeur vers un chaine de caractère en progmem.

Ex:

Serial.println(F("Je suis en memoire FLASH!"));

Il est a noter que le compilateur ne semble pas détecter que deux chaines identiques pourraient être stockées qu'une seule fois en mémoire, donc:

Serial.println(F("Je suis en memoire FLASH!"));
Serial.println(F("Je suis en memoire FLASH!"));

Utilise 52 octets en mémoire Flash puisque la chaine est stocké en deux endroits séparés.

Pour ce qui est d'accéder directement à une donnée, il est nécessaire d'utiliser les méthodes  tel que pgm_read_byte_near et pgm_read_word_near. Ces méthodes permettent de ramener en RAM un type de données sotcké en Flash. L'ensemble des méthodes disponibles est défini dans le fichier , qui est en passant nécessaire d'ajouter à votre programme. Puisse que ces méthodes nécessitent un pointeur vers la données, prenons par exemple:

const PROGMEM byte  untableudebyte[] = { 1, 2, 3, 4, 5 ,6 ,7, 8};

Afin de lire le 3e élément, il faut augmenter le pointeur de 2 et demander une lecture d'un seul octet à cette adresse:

byte byteEnRAM = pgm_read_byte_near(untableudebyte + 2);

la valeur de byteEnRAM sera maintennt de 3. Évidemment qu'il faut être à l'aise avec l'arithmétique de pointeur, ce qui est un sujet en soit. Mais si vous avez de long texte, de grosses tables de valeurs pré-calculées ou tout autre blob binaire devant être fourni tel qu'une image pour un écran, c'est vraiment pratique.

Ceci dit, toute cette mécanique n'est pas nécessaire sur les Arduino à base d'architecture ARM. Dès qu'une variable est déclarée const, elle est automatiquement stockée seulement qu'en Flash et l'adressage permet l'accès direct, donc pas de pgm_read_byte_near nécessaire. Si vous écrivez une librairie, il est possible de mettre le code selon différente architecture dans des sous-dossier, par contre si vous utilisez cette technique dans le .ino, il est nécessaire d'utiliser des directive du préprocesseur tel que #idef __AVR_ATmega328P__ pour identifier le genre d'architecture et inclure le code compatible.

Tout ce petit volet sur l'utilisation est utile pour la sérialisation des behavior tree. Ce sera le sujet du prochain post, avec un peu plus d'exemples concrets cette fois. 

mardi 18 juin 2019

Behavior Tree et Arduino, la suite

Comme j'ai peu de temps à mettre sur le projet, le code n'est pas encore terminé mais la structure principale est là. Cependant, avec le peu de RAM d'un Arduino UNO, il est impératif de pouvoir utilisé un mécanisme de proxy et de désérialisation au besoin. Il y a donc un type de noeud "proxy" qui désérialise lorsque demandé d'être exécutée et détruit les sous-éléments lorsque le résultat de l'enfant est disponible ( fail ou success ). 

Une étape plus loin serait de permettre une gestion de priorité et retirer une sous-structure si elle est jugée moins importante qu'une nouvelle devant être instanciée. La structure courante d'un nœud de l'arbre est la suivante:

class BehaviorTreeNode
{
public:
  int data;
  byte type;
  byte state;
  byte child;
  byte next;

};

Il y a donc 255 sortes de nœuds possibles, le state identifie si le nœud est running, fail, success ou encore non touché ou peut être remis dans le pool de non utilisé.Il serait possible d'utilisé 4 bits pour l'état et les 4 autre pour 16 niveaux de priorités.

Je veux permettre d’interrompre le parcours de l'arbre après un certains délais, et reprendre au prochain "tick", ce qui en ferai un type de système multitâche préemptif. Cependant, si des sections complète de l'arbre peuvent disparaitre en plein milieu de l'exécution, il faudra y faire bien attention.

Autres contraintes, un arbres est limité à 255 nœuds, quoi que trop pour la RAM d'un UNO, pourrait être utile pour un MEGA ou Zero. Aussi, il n'y a que 16 bits pour l'encodage des données. Soit deux 8 bits ou un entier. Les 8 bits utilisés pour l'indice de l'enfant pourrait être utilisés comme valeur temporaire pour une tâche n'ayant pas d'enfant mais devrait être refléter dans le state.

En passant, comme pour utiliser les données en Flash sur un UNO il est nécessaire d'utilisé la directive progmem et le méthodes de la famille des pgm_read_word_near, il y aura deux méthode pour la désérialisation, peut-être même trois si je décide de supporter les cartes SD. La version Flash pour microcontrôleur ARM ( SAMD ), ne fera que pointer version la version en RAM puisque les ARM peuvent adressé directement la Flash et n'a besoin que de lecture seule.

Ceci dit, avant d'implémenter de nouveau concept, je vais terminer la version de base. Il me reste quelques méthodes de parcours puis je pourrait commiter.

dimanche 9 juin 2019

Behavior Tree et Arduino Uno

C'est bien beau de connecter différents senseur et actuateurs sur un microcontrôleur, mais si ce n'est que pour afficher la valeur obtenue ou démarrer un moteur selon une valeur limite, me semble que c'est un occasion manquée d'utiliser un microcontrôleur efficacement. Afin d'ajouter un peu d'intelligence dans si peu de ressources, il faut tout de même faire quelques pirouettes.

Programmer en C n'est pas toujours facile et réussir à implémenter des comportements complexes est ni simple a écrire ni, et encore moins, à déboguer. Une technique efficace développée pour la conception de jeux vidéo est l'utilisation de Behavior Tree, ou en tant que traduction littérale "arbre de comportement". Cet arbre est composé de différents type de nœuds, soit de contrôle, de décoration ou d'action.

Unity et Unreal en font abondamment usage pour la création de NPC et c'est une technique reconnue en intelligence artificielle. Plusieurs autre engin en font aussi usage. Si l'implémentation dans le jeu vous intéresse, voici quelques vidéos sur Tom Clancy's The Division et l'excellent Horizon Zero Dawn.

Ceci dit, il est impossible de porter la plupart des librairies existantes puisqu'elle se base sur une utilisation efficace de l'allocation dynamique en mémoire. Une manière de contrer le problème est d'utiliser un pool limité pré-alloué mais vient avec la contrainte de taille fixe pour les éléments ( noeuds ) utilisés par l'arbre. Puisque le nombre total ne peux être bien grand, des techniques de proxy et de priorité et une bonne gestion des éléments non utilisé sont plus qu'essentiels.

Autre facteur limitant, l'utilisation de blackboard ne peut être aussi permissif qu'une simple clé/valeur. Donc un tableau de 16 entier de 16 bits dont l'indice devient la clé et la valeur est limité à 2 octets.

Ceci dit, puisque l'édition du Behavior Tree peut être externe et sérialiser en Flash, une partie de la complexité peut être relégué à l'éditeur.

Ceci dit,  je ne suis qu'au début de mon implémentation pour Arduino UNO et j'essaie de l'inclure dans une librairie, donc deux fronts en même temps. Bien que j'ai commencé l'implémentation à l'intérieur de ma librairie de robots, j'en ferait une version simplifiée pour en tester plus efficacement la stabilité et l'utilité. Le tout devra inclure du code Python et probablement un minimum de Web pour en faire un éditeur. Encore un autre mini projet qui pourrait être quasiment un créneau de développement à lui-seul!