Behavior Tree : Première version pour Arduino Uno

On a tendance à ne pas vouloir montrer notre travail tant que ce n'est pas terminé. La peur de la critique ou tout simplement qu'avoir le nez dans un projet ne nous fait voir que les défaut et les manquements. Tout ça pour dire que j'ai décidé de diffuser la première version fonctionnelle de mon projet de Behavior Tree pour Arduino malgré sont état encore prototype. Vous pouvez cloner le projet sur github.

Voici ce qui le projet en date du 28 juillet supporte:

• Classe de gestion du graph de l'arbre
• Classe visiteur pour naviguer l'arbre
•  Désérialisation a partir de la mémoire Flash et en RAM
• Banque de sous-arbre pour facilité la désérialisation
• Affichage de l'état de l'arbre via le lien série
• Noeuds de composition: sequence, selector, random, parallel et loop
• Noeud de décoration: Success, Failure, Inverter
• Noeud de désérialisation: Proxy
• Noeud de débogage: Delay et Print
• Noeud spécifique au projet: setLED 
• Quelque méthodes pour effectuer différent tests. 
• Classe utilitaire pour la gestion de DEL, boutons et alarmes

Les méthodes "degugPrint" envoient sur le port série l'état de l'arbre et des noeuds. L'indice, le type, la domnée, le statut, la priorité, l'id de l'enfant et l'id du suivant sont afficher dans hiérarchique, séparés par des deux point ":". Des tirets avant le type permet de connaitre la profondeur du noeud dans l'arbre. Comme l'arbre est parcouru à partir de la racine, l'affichage permet de visualiser rapidement les liens et l'état de l'ensemble des noeuds de l'arbre.

La sérialisation utilise 4 octets par noeud selon le schéma:

Octet 0 - type du noeud
Octet 1 - octet data 0
Octet 2 - octet data 1
Octet 3 - déplacement du prochain noeud

Le déplacement utilise les constantes suivantes:

0: Fin de l'arbre
1: Ajout à la suite
2: Ajout en tant qu'enfant
-X : remonte de X dans l'arbre

L'utilisation d'une valeur négative évite d'encoder la fin d'une branche ou de détecter selon le type si un enfant est possible ou non. C'est un peu plus pointilleux sur la désérialisation mais moins gourmand en mémoire.

Ce qui reste à implémenter:

• Compilation pour Arduino d'architecture SAMD .
• Meilleur gestion des type de base ( utiliser uint_8 au lieu de byte, etc. )
• Utilisation d'un "Blackboard" dont les clés sont une valeur entre 0 et 254.
• Permettre le déclenchement de sous-arbre selon  un système d'évènements.
• Désérialisation à partir d'une carte SD ou via une réception ( Série, RF) et stockage en EEPROM
• Transfert du code d'exécution des noeuds de base hors du fichier de projet ( .ino ).
• Soit par une surcharge de la classe ou d'appel de méthode recevant en paramètre les objets nécessaire.
• Permettre d'interrompre le parcours après un certains délais et reprendre au prochain tick.
• Gestion de la priorité des sous-arbre afin d'être réclamé par une sérialisation plus importante .
• Optimisation!
• Code python pour facilité la création de sous-arbre.
• Code python + Web pour afficher les sous-arbre.
• Aide à l'édition.
• Au runtime en lisant le contenu de la connexion série..

Une fois le blacboard implémenté, possible que je commence un petit projet de robot 2 roues pour tester le behavior tree sur un projet moins théorique, mais je garderai ce projet comme projet de base pour les tests et la documentation. D'ailleur, je me demande comment en faire une librairie puisque le code du handler doit être étendu. Enfin, c'est un creusage de méninges pour un autre jour.

PROGMEM et Behavior Tree, la suite

Puisque des parties de l'arbre pourront être désérialisées à la demande dans le projet de Behavior Tree pour Arduino, il est nécessaire d'avoir un mécanisme d'accès pour se facilité la vie. Dans mon cas, le type de noeud "proxy" à la comportement suivant:

• Premier appel: désérialise selon une valeur en "data" le sous-arbre en tant qu'enfant.
• En traitement, appel le traitement de l'enfant
• Sur "Success" ou "Failure" de l'enfant, prend l'état et détruit le sous-arbre.

De cette manière, toute une partie de l'arbre n'existe pas en mémoire et n'est que présent que lors de son exécution. Comme l'élément "data" d'un noeud n'est un int, il est nécessaire de pouvoir adresser une liste de noeuds et d'en instancier au besoin.

Pour ce faire, j'ai créer la classe BehaviorBank qui permet de gérer une liste d'éléments et de répondre à la question de la taille sans devoir en parcourir le contenue. Pour le moment, l'implémentation de l'arbre et des classes utilitaire est faite de façon naïve sant me soucier de l'optimisation ou de la gestion d'erreur. La défition de la classe est la suivante:

 

class BehaviorBank
{
  int totalElements;
  const byte* behaviorIndexesSizes;
  const int* behaviorIndexes;
  const char* behaviorDatas;
public:
  void init( const byte* sizes, const int* indexes, const char* datas, int total );
  byte getNbrNodes( int idx );
  char* getDataPtr( int idx );
};

Ici, trois tableaux permettent de garder en mémoire Flash un ensemble de sous-arbre. L'indice dans le tableau et le nombre de noeud par sous-arbre permettent d'extraire selon un indice passé en paramère le pointeur vers les donnée. Le nombre d'indice total est passé en paramètre lors de l'inisialisation.

Les données sont présentement encoder comme suit:

const PROGMEM byte BBankSizes[] = {3, 3};
const PROGMEM int BBankIndexes[] = { 0, 12 };
const PROGMEM char BBankData[] = {1, 0, 0, 2, 20, 11, 0, 1, 20, 22, 

    0, 0, 1, 0, 0, 2, 20, 33, 0, 1, 20, 44, 0, 0};

 Et l'initialisation ressemble à:

BehaviorBank bBank;
bBank.init( BBankSizes, BBankIndexes, BBankData, 2 );

L'implémentation des méthode getNbrNodes et getDataPtr est la suivante:

byte BehaviorBank::getNbrNodes( int idx )
{
  byte ret = 0;
  if ( idx <= this->totalElements )
  {
    ret = pgm_read_byte_near( this->behaviorIndexesSizes + idx );
  }
  return ret;
}

char* BehaviorBank::getDataPtr( int idx )
{
   if ( idx <= this->totalElements )
  {
    int pos = pgm_read_word_near(this->behaviorIndexes + idx);
    return this->behaviorDatas + pos;
  }
  return NULL;
}

Ensuite, le code lors de la désérialisation dans le noeud "proxy" ayant accès à cette instance de BehaviorBank est:

if ( this->bBank.getNbrNodes(mePtr->data) <= this->b_tree.getFreeNodes() )
{
  char* behavSer = this->bBank.getDataPtr( mePtr->data );
  if ( this->b_tree.deserialize_flash( this->visitor.getIndex(), behavSer ) == false )

    return false;

} 

Il reste encore un peu de nettoyage dans mon projet avant de le partager mais il est maintenant fonctionniel avec un ensemble restreint d'éléments de test. Il me reste aussi à le faire compiler pour architecture SAMD en utilisant quelque directive de compilation.