Le parcours d'un labyrinthe

Les labyrinthes parfaits

Un labyrinthe parfait est un labyrinthe dans lequel il existe un chemin unique qui passe par toutes les cases. Il ne contient donc pas d'îlots isolés.

labyrinthe parfait labyrinthe avec îlot

Pour ces labyrinthes parfaits, des stratégies simples permettent d'en parcourir toutes les cases et donc de trouver la sortie.

Dans un tel labyrinthe, poser sa main sur gauche (ou droite) sur un mur et avancer sans jamais le lâcher ou changer de main permet à coup sûr de parcourir exhaustivement le labyrinthe.

Parcours d'un robot dans un labyrinthe

Nous voulons programmer un robot pour qu'il puisse atteindre une cible dans un labyrinthe de façon sûre.

Ce robot possède deux capteurs permettant de savoir s'il touche un mur à gauche ou à droite. Ces capteur étant situés à l'avant du robot, ils permettent aussi de savoir si on touche le mur de face (dans ce cas il s'activent tous les deux).

Ce robot, peut se déplacer de trois façons :

  • Avancer tout droit
  • Tourner sur lui même (vers la gauche ou vers la droite)
  • Avancer tout en tournant (vers la gauche ou vers la droite)

Pour contrôler ses mouvements nous disposons de trois commandes :

  • Ordre pour avancer
  • Ordre pour tourner à gauche
  • Ordre pour tourner à droite

Stratégie

La stratégie que le robot devra employer est celle de la main gauche.

  • Au début il est perdu, il avance tout droit jusqu'à trouver un mur.
  • En suite, il tourne sur lui même jusqu'à laisser le mur sur sa gauche.
  • Puis il avance et s'éloignant du mur pour ne pas être bloqué.
  • S'il perd le contact avec le mur, il avance en revenant vers le mur.
  • S'il est bloqué des deux côtés, il tourne sur lui même pour suivre le nouveau mur.

Bien mise en oeuvre, cette stratégie doit permettre au robot de parcourir toutes les cases du labyrinthe et donc d'en trouver la sortie.

Travail à faire

Nous avons préparé sur la maquette FPGA un environnement simulant un robot (déguisé en souris) dans un labyrinthe.

Ce robot se déplace à une fréquence de quelques Hertz. Il attend à chaque front de l'horloge des ordres pour avancer et/ou tourner à gauche ou à droite.

Vous devez réaliser le contrôleur de ce robot qui permettra de sortir du labyrinthe (où un fromage l'attend). Vous réaliserez ce contrôleur sous la forme d'un automate fini.

Première étape

Construisez (dessinez) le graphe d'états de ce contrôleur. Ce graphe devra mettre en oeuvre le suivi main gauche décrit précédemment.

En entrée vous avez :

  • deux signaux venant de capteurs de contact indiquant un obstacle à gauche ou à droite :
    • hit_left : on touche à gauche
    • hit_right : on touche à droite
  • un signal permettant de valider ou stopper le déplacement du robot :
    • go : si go vaut "1" le robot peu se déplacer, si go vaut "0" le robot doit s'arrêter.

Vous aurez en sortie 3 signaux de commande :

  • forward : ordre d'avancer tout droit
  • rotate_r: ordre de tourner à droite (right)
  • rotate_l: ordre de tourner à gauche (left)

Après avoir dessiné le graphe d'état, vérifiez qu'il respecte les règles de construction des automates finis.

Seconde étape : codage en SystemVerilog de l'automate

Lisez attentivement toutes les explications et recommandations avant de commencer.

Pour vous aider à écrire un code lisible, voici quelques suppléments utiles à SystemVerilog.

Définition de types énumérés pour décrire des états

System Verilog supporte la définition de signaux de type énumérations de la façon suivante:

// sig est un signal pouvant prendre 7 valeurs:
//  "SWAIT", "S1", "S2", "S3", "S4", "S5" ou "S6".
enum logic[2:0] {SWAIT, S1, S2, S3, S4, S5, S6} sig;
// On peut alors écrire les choses suivantes :  
always@(*)  
   sig <= S1;

enum logic {V1, V2} sig1, sig2; // sig1 et sig2 sont deux signaux  
                                 // ne pouvant que la valeur "V1" ou "V2".
 // On peut alors écrire :
always@(*)
    if (sig1 == sig2)
       sig1 <= V2;
    else
       ...

Par défaut, les valeurs énumérées correspondent aux codes 0, 1, 2, 3... en partant de la première valeur.

La taille nécessaire au codage des différentes valeurs est définie dans la définition du type.

Codage de l'évolution d'un automate fini

L'usage de la syntaxe case permet de traduire facilement la table d'évolution des états. Pour cela vous pouvez regrouper dans un même vecteur l'ensemble des signaux d'entrée et l'état courant de manière à définir la table sous la forme :

always@(*)
  case ({etat_courant, entrée_1, entrée_2})
    {WAIT,1'b0, 1'b1} : next_state <= S1;
    {S1,  1'b1, 1'b1} : next_state <= S2;
     ...
     default : next_state <= current_state;
  endcase

Extension de l'usage du case: le casez

Il peut parfois être long et fastidieux de coder explicitement tous les cas. Lorsque certains signaux ne sont pas utiles dans les équations de transition, il est possible de les représenter par un "?". Dans ce cas la syntaxe case doit être casez.

 always@(*)
   casez ({etat_courant, entrée_1, entrée_2})
     {WAIT,1'b0, 1'b1} : next_state <= S1;
     {S1,  1'b1, 1'b?} : next_state <= S2;
     ...
     default : next_state <= current_state;
   endcase

Dans l'exemple précédent, on passe de l'état S1 à l'état S2 indépendamment de la valeur de entrée_2.

Travail proprement dit

Téléchargez l'archive attachée en bas de page puis modifiez le module mouse.

module mouse (
          input  logic clk,      // l'horloge
          input  logic nreset,   // reset asynchrone actif sur niveau bas
          input  logic go,       // entrée autorisant le déplacement
          output logic forward,  // ordre d'avancer tout droit
          output logic rotate_r, // ordre de tourner à droite
          output logic rotate_l, // ordre de tourner à gauche
          input  logic hit_left, // On touche à gauche
          input  logic hit_right // On touche à droite
         );

Vous pourrez tester ensuite le résultat en visualisant les déplacements de votre robot (souris) sur l'écran branché à la carte FPGA. Sur la carte nous avons attribué à certaines touches des fonction particulière :

  • key[0] : remise à zéro (reset) globale
  • key[3] : change la carte du labyrinthe et remet le robot en position initiale
  • sw[0] : relié au signal go

 

Fichier attachéTaille
Fichier maze.tgz103.93 Ko