====== Tondeuse Robotique ======

===== Enoncé =====

Projet de optimisation stochastique : optimisation évolutionnaire de FSM ((finite states machine, automate à états finis))

  * Tondre un terrain par un automate à états finis.
  * Terrain de 1024x768
  * Tondeuse de 10x10
  * Avance case par case
  * 20 arbres dans le terrain, répartis aléatoirement, de 10x10.
  * 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.

===== Notre Réflexion =====

==== Représentation d'un automate ====

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.

=== Initialisation ===

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 ((ce qui sera le nombre maximum effectif car nous ne prévoyons pas des changements de nombre d'états par croisement ni mutation)), dont certains pourront "s'atrophier" si transition vers eux se révèlent désavantageuse.

==== Fonction de Fitness ====

La fonction de fitness "exécute" chaque automate de la façon suivante, pour un jardin et emplacement de départ donnés((aléatoires, mais les mêmes pour tous les individus de chaque génération)) :

  * 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.  

==== Evolution ====

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.

=== Croisements ===

  * Sélection des parents par tournoi
  * Tous les individus gardent sept états ((on pourra jouer avec des nombres d'état variables entre individus)), dont certains peuvent "s'atrophier" si la sélection favorise des individus avec moins. 

=== Mutations ===

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.

==== Protocole ====

  * Démarrage: On prend n automates construits aléatoirement. Cf. représentation : initialisation (( on peut se dire "selon leurs réactions : (entre 7 et 2 réactions différentes) " si l'on entend par "réactions" des états comportementaux, ou "états" tout simplement. Mais ils ne sont pas produit par ingénierie, ils sont de construction aléatoire  )) 
  * 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'
  
 
===== Réalisation =====

Notre choix pour le développement s'est porte sur [[http://sourceforge.net.projects/easea|EASEA]], ce qui nous permet de concentrer [[mower:project_track|nos efforts de développement]] sur les fonctions de fitness et de croisement (et représentation et initialisation, évidement).


==== Affichage ====

  * 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).

===== Résultats et Conclusions =====

En cours d'évaluation et mise au point.