Tondeuse Robotique

Projet de optimisation stochastique : optimisation évolutionnaire de FSM ¹⁾

• Tondre un terrain par un automate à états finis.
• Terrain de 1024×768
• Tondeuse de 10×10
• Avance case par case
• 20 arbres dans le terrain, répartis aléatoirement, de 10×10.
• Position initiale aléatoire.
• Détection de choc / détection de périmètre.
• Détection de l'herbe coupée.

Trouver le meilleur algorithme par évolution artificielle. Fonction d'évaluation : % tondu (ou nb de cases restantes) après 100 000 pas. Evaluation de la qualité sur une moyenne de 30 runs.

Le choix de la représentation de l'automate est primordiale pour plusieurs raisons : ça conditionne les possibilités de croisement et de mutation, et ça influence le fonctionnement de la fonction d'évaluation (fitness). Notre choix est porté sur une représentation très classique : chaque état est une table de réponses à chaque signal possible en entrée, la réponse étant composée d'un “voeu” de déplacement à l'indication de sa transition d'état (y compris “pas de changement”).

Etant donné que l'énoncé ne mentionne que trois sortes de détection (ou absence de détection), la liste des signaux possibles en entrée peut n'être que de huit (2*2*2). Cependant, pour éviter à l'automate de mémoriser sa dernière voeu de déplacement, nous le lui renvoyons, ce qui multiplie le nombre de cas possibles par neuf ({-1,0,1}x{-1,0,1}). Il est envisageable d'avoir plusieurs réponses possibles pour un même signal; nous n'avons pas pris cette option.

L'initialisation (“conception”) de chaque individu attribue à chacune des 72 signaux d'entrée possibles des chacun de ses états, des réponses choisies au hasard pour les voeux de déplacement horizontal, vertical, et changement d'état. Le changement d'état se spécifie non par “matricule” de l'état successeur, mais par décalage par rapport à l'état courant.

Chaque individu sera doté de sept états ²⁾, dont certains pourront “s'atrophier” si transition vers eux se révèlent désavantageuse.

La fonction de fitness “exécute” chaque automate de la façon suivante, pour un jardin et emplacement de départ donnés³⁾ :

• initialisation :
  • calcul des signaux (périmètre, obstacle, herbe, vx, vy) pour le point de départ.
  • vx et vy sont aléatoires mais identique pour chaque individu (comme le point de départ),
  • l'état initial de l'automate aussi.
• boucle (pour les 100k pas)
  • recherche dans les tables de l'automate de la réponse aux signaux
  • calcul de la réponse aux voeux
    • si faisable, exécution du déplacement (mémorisation du nouvel emplacement) et décompte de l'herbe coupé le cas échéant
    • calcul des nouveaux signaux :
      • périmètre ou pas,
      • obstacle (arbre) ou pas,
      • herbe coupé ou pas (le seuil pour que la réponse à “herbe coupé?” soit “vrai” sera plus de la moitié des case nouvellement occupées n'étaient pas tondues avant).
  • fin de boucle

Grande question (pour ne pas entrer un biais) : si elle se déplace en diagonale, elle va occuper 19 (potentiellement) nouvelles cases; est-ce qu'elle coupe les 19? Si oui, est-ce que ça compte un pas ou deux? Logiquement, on peut estimer que ça compte deux pas, ou plus généralement, qu'on compte un pas pour chaque 1 ou -1 dans un voeu. Mais cette règle du jeu n'est pas clairement définie.

Après discussion,

• Admettons que les mouvements en diagonal ne se fassent pas par un mouvement directement en diagonal, mais par une succession (cyclique) de mouvements horizontaux et verticaux. Ainsi les mouvements en diagonal tondent 20 cases en deux pas.

Il y a beaucoup de choix stratégiques dans ce domaine :

• Nombre d'individus par génération (pour 30 générations)
• Sélection pour croisement, nombre d'enfants
• Type de croisement
• Taux de mutation

Nous n'avons pas trouvé les réponses facilement, et expérimentons encore pour améliorer notre choix.

• Sélection des parents par tournoi
• Tous les individus gardent sept états ⁴⁾, dont certains peuvent “s'atrophier” si la sélection favorise des individus avec moins.

Les possibilités :

• pas de mutations
• mutations dans les voeux de déplacement
• mutations dans les transitions d'état
• mutations dans les voeux de déplacement et dans les transitions d'état

Pour la première série de tests, pas de mutation. Si on constate une convergence trop rapide, on introduira des mutations.

• Démarrage: On prend n automates construits aléatoirement. Cf. représentation : initialisation ⁵⁾
• Nombre de jardins pour évaluer une génération: Trois voir Cinq en fonction du temps d'exécution (un n'étant pas suffisant), ils sont construits aléatoirement au début du protocole et utilisés par tous les automates avec le même emplacement (et intention de déplacement) de démarrage afin d'avoir une évaluation sur les même conditions.
• Les n individus sont évalués par un tournois pour le choix des reproducteurs;
• on garde x% des individus de base avec les y% premiers et z% pris aléatoirement dans les restant (x,y, et z restent à définir suivant les tests avec y+z = x) → ce sont les reproducteurs
  • et on crée w% de fils avec des croisements (pour commencer)
  • on évalue ensuite toute la population et on garde ceux que l'on souhaite, les autres sont 'tués'

Notre choix pour le développement s'est porte sur EASEA, ce qui nous permet de concentrer nos efforts de développement sur les fonctions de fitness et de croisement (et représentation et initialisation, évidement).

• Les jardins sont représentés par des images, les bordures sont en noir, les arbres en bruns, l'herbe en vert (foncé ou clair en fonction de la tonte).

En cours d'évaluation et mise au point.