Robot Résolveur de Labyrinthe IA avec Arduino et Bluetooth

Composants et fournitures

Arduino Nano R3	×	1
Module Bluetooth HC-06	×	1
Module capteur suiveur de ligne TCRT5000 4 canaux	×	1
Capteur suiveur de ligne SparkFun RedBot	×	1
Capteurs infrarouges réfléchissants ZX03 (sortie analogique)	×	2
Appareil Android	×	1
Servomoteurs rotation continue RobotGeek	×	2
Support 4 piles AA	×	2

Applications et services en ligne

Arduino IDE

MIT App Inventor 2

À propos de ce projet

Introduction

Ce tutoriel s'appuie sur mon projet précédent : Robot Suiveur de Ligne – Contrôle PID – Configuration Android. Une fois qu'un robot sait suivre une ligne, l'étape naturelle suivante est de lui donner un certain degré d'intelligence. Notre cher « Rex, le Robot » va maintenant tenter de trouver comment s'échapper d'un « labyrinthe » par le chemin le plus court et le plus rapide (au passage, il déteste le Minotaure).

Quelle est la différence entre Labyrinthe et Maze ? Selon labyrinthos.net, un maze doit offrir des choix dans le parcours, incluant de nombreuses installations modernes. Un labyrinthe, lui, n'a qu'un seul chemin menant inexorablement de l'entrée au but, aussi sinueux soit-il.

La majorité des mazes, aussi complexes paraissent-ils, sont formés d'un mur continu avec de nombreuses jonctions et branches. Si le mur entourant le but est connecté au périmètre à l'entrée, le maze peut toujours être résolu en gardant une main en contact avec le mur. Ce sont des mazes « simplement connexes » ou « parfaits » – sans boucles.

Le projet se divise en deux passes :

Première passe : Le robot trouve sa sortie depuis un « maze parfait inconnu ». Peu importe où il démarre, il trouvera une « solution ».
Deuxième passe : Une fois une solution trouvée, le robot l'optimise pour trouver le « plus court chemin du départ à l'arrivée ».

Dans la première passe, le robot explore, teste les possibilités, emprunte des impasses, fait des demi-tours inutiles. Il accumule de l'expérience, « prend des notes » sur les intersections et élimine les mauvaises branches. Dans la deuxième passe, il fonce droit au but sans erreur ni hésitation.

Étape 1 : Liste du matériel

La liste est globalement la même que pour le robot suiveur de ligne, avec 2 capteurs supplémentaires pour mieux détecter les intersections GAUCHE et DROITE. Le robot final reste très bon marché (environ 85 $).

Corps (adaptable selon vos besoins/matériaux) :

2 carrés de bois (80×80 mm)
3 pinces de reliure
2 roues en bois (diamètre 50 mm)
1 roulette à bille
9 élastiques
Bande de fixation 3M Command
Joints en plastique pour fixation des capteurs
Plaque d'essai et câblage
2 jeux de 4 accus Ni-MH (5 V chaque jeu)
2 servos rotation continue SM-S4303R 360°
Arduino Nano
Module Bluetooth HC-06
5 capteurs de ligne (module TCRT5000 4 canaux + 1 capteur indépendant)
2 capteurs ZX03 (basés sur TCRT5000, sortie analogique)
1 LED, 1 bouton

Note : J'ai utilisé des capteurs analogiques (article 7) faute de capteurs numériques comme ceux de l'article 6. L'idéal est d'avoir tous les capteurs identiques. Le projet fonctionne avec seulement les 5 capteurs d'origine, mais nécessite des réglages plus fins pour la détection d'intersections.

Étape 2 : Modifications du châssis

Retirez le jeu original de 5 capteurs suiveurs de ligne et fixez les nouveaux capteurs « FAR LEFT » et « FAR RIGHT » à chaque extrémité de la barre de support en plastique. Il est conseillé d'aligner au mieux les 7 capteurs.

Étape 3 : Installation et test des nouveaux capteurs

Le nouveau réseau de 7 capteurs est monté de façon que les 5 originaux servent exclusivement au contrôle PID (et détection de « ligne pleine ») et les 2 nouveaux, exclusivement à la détection des intersections GAUCHE et DROITE.

Rappel du fonctionnement des 5 capteurs « numériques » originaux : un capteur centré sur la ligne noire donne un signal HIGH. L'espacement permet à 2 capteurs de couvrir la largeur totale de la ligne simultanément.

Fonctionnement des 2 nouveaux capteurs « analogiques » : centrées sur la ligne noire, elles donnent une valeur analogique (souvent < 100 sur l'ADC Arduino, 0-1023). Sur surfaces claires, la valeur est plus élevée (500-600 sur papier blanc). Cette valeur doit être testée selon la lumière et les matériaux pour définir le bon seuil THRESHOLD.

Dans le code Arduino, chaque capteur reçoit un nom spécifique (le capteur original le plus à gauche = index 0) :

const int lineFollowSensor0 = 12; // Entrée numérique
const int lineFollowSensor1 = 18; // Pin A4 comme entrée numérique
const int lineFollowSensor2 = 17; // Pin A3 comme entrée numérique
const int lineFollowSensor3 = 16; // Pin A2 comme entrée numérique
const int lineFollowSensor4 = 19; // Pin A5 comme entrée numérique
const int farRightSensorPin = 0;  // Pin analogique A0
const int farLeftSensorPin  = 1;  // Pin analogique A1

Sorties possibles des 5 capteurs originaux en suivi de ligne :

Avec les 2 nouveaux capteurs :

Capteur FAR LEFT : Sortie analogique supérieure ou inférieure au SEUIL
Capteur FAR RIGHT : Sortie analogique supérieure ou inférieure au SEUIL

Pour stocker les valeurs : un tableau pour les 5 capteurs numériques :

int LFSensor[5] = {0, 0, 0, 0, 0};

Et deux entiers pour les 2 capteurs analogiques :

int farRightSensor = 0;
int farLeftSensor = 0;

Chaque position est constamment mise à jour :

LFSensor[0] = digitalRead(lineFollowSensor0);
LFSensor[1] = digitalRead(lineFollowSensor1);
LFSensor[2] = digitalRead(lineFollowSensor2);
LFSensor[3] = digitalRead(lineFollowSensor3);
LFSensor[4] = digitalRead(lineFollowSensor4);
farRightSensor = analogRead(farRightSensorPin);
farLeftSensor = analogRead(farLeftSensorPin);

Les 5 capteurs permettent de générer une « variable d'erreur » pour contrôler la position du robot sur la ligne. Une variable « mode » définit si le robot suit une ligne, est sur une ligne continue, une intersection, ou aucune ligne.

Cette variable « mode » s'utilise aussi avec les capteurs « FAR LEFT/RIGHT ». Pour la représentation, considérons 3 états pour les capteurs lointains : H (supérieur au seuil), L (inférieur au seuil), X (irrelevant). Pour les sorties numériques : 0, 1 et X.

Logique de détection (exemples) :

H 0 X X X X L → mode = RIGHT_TURN; error = 0
L X X X X 0 H → mode = LEFT_TURN; error = 0
X 0 0 0 0 0 X → mode = NO_LINE; error = 0
H 0 0 0 0 1 H → mode = FOLLOWING_LINE; error = 4
H 0 0 0 1 1 H → mode = FOLLOWING_LINE; error = 3
H 0 0 0 1 0 H → mode = FOLLOWING_LINE; error = 2
H 0 0 1 1 0 H → mode = FOLLOWING_LINE; error = 1
H 0 0 1 0 0 H → mode = FOLLOWING_LINE; error = 0
H 0 1 1 0 0 H → mode = FOLLOWING_LINE; error = -1
H 0 1 0 0 0 H → mode = FOLLOWING_LINE; error = -2
H 1 1 0 0 0 H → mode = FOLLOWING_LINE; error = -3
H 1 0 0 0 0 H → mode = FOLLOWING_LINE; error = -4
X 1 1 1 1 1 X → mode = CONT_LINE; error = 0

La fonction readLFSsensors() implémente cette logique et retourne « mode » et « error ». Il est crucial de tester cette logique avant de continuer. Fonction de test incluse :

void testSensorLogic(void) {
  Serial.print(farLeftSensor);
  Serial.print(" <= LEFT RIGH=> ");
  Serial.print(farRightSensor);
  Serial.print(" mode: ");
  Serial.print(mode);
  Serial.print(" error:");
  Serial.println(error);
}

Étape 4 : Résolution du maze – La règle de la main gauche

Comme discuté, la plupart des mazes sont formés d'un mur continu. Si le mur du but est connecté au périmètre à l'entrée, le maze se résout en gardant la main gauche sur le mur. C'est la « Règle de la Main Gauche » (Left-Hand Rule).

En bref :

Placez votre main gauche sur le mur.
Avancez.
Vous atteindrez la fin (pas nécessairement par le plus court chemin, mais vous y arriverez).

Dans notre maze 2D, on trouve 8 types d'intersections. Les actions possibles sans règle :

Croisement : Gauche, Droite, ou Tout droit
T : Gauche ou Droite
Droite seulement : Droite
Gauche seulement : Gauche
Tout droit ou Gauche : Gauche ou Tout droit
Tout droit ou Droite : Droite ou Tout droit
Impasse : Demi-tour
Fin du maze : Stop

En appliquant la « Règle de la Main Gauche », les actions se réduisent à une seule option chacune :

Croisement → Gauche
T → Gauche
Droite seulement → Droite
Gauche seulement → Gauche
Tout droit ou Gauche → Gauche
Tout droit ou Droite → Tout droit
Impasse → Demi-tour
Fin du maze → Stop

Le défi : identifier exactement le type d'intersection. Une « LIGNE » peut être un Croisement (1) ou un T (2). Un « VIRAGE GAUCHE/DROITE » peut être un virage simple (3 ou 4) ou une option tout droit (5 ou 6). Le robot doit avancer d'un « pouce supplémentaire » pour voir ce qui suit.

Flux d'actions :

IMPASSE : Demi-tour
LIGNE : Avancer d'un pouce
- S'il y a une ligne → Croisement → Gauche
- S'il n'y a pas de ligne → T → Gauche
- S'il y a une autre ligne → Fin du maze → STOP
VIRAGE DROITE : Avancer d'un pouce
- S'il y a une ligne → Tout droit ou Droite → TOUT DROIT
- S'il n'y a pas de ligne → Droite seulement → DROITE
VIRAGE GAUCHE : Avancer d'un pouce
- S'il y a une ligne → Tout droit ou Gauche → GAUCHE
- S'il n'y a pas de ligne → Gauche seulement → GAUCHE

Note : Pour un « VIRAGE GAUCHE », le test est en fait inutile car on tourne à gauche de toute façon. L'explication est générique pour la clarté ; le code réel saute ce test.

Étape 5 : Implémentation de l'algorithme « Main Gauche sur le Mur » dans le code Arduino

Une fois la fonction readLFSsensors() modifiée pour inclure les 2 capteurs supplémentaires, on réécrit la fonction Loop :

void loop() {
  readLFSsensors();
  switch (mode) {
    case NO_LINE:
      motorStop();
      goAndTurn(LEFT, 180);
      break;
    case CONT_LINE:
      runExtraInch();
      readLFSsensors();
      if (mode == CONT_LINE) mazeEnd();
      else goAndTurn(LEFT, 90); // T ou Croisement → Gauche
      break;
    case RIGHT_TURN:
      runExtraInch();
      readLFSsensors();
      if (mode == NO_LINE) goAndTurn(RIGHT, 90);
      break;
    case LEFT_TURN:
      goAndTurn(LEFT, 90);
      break;
    case FOLLOWING_LINE:
      followingLine();
      break;
  }
}

Nouvelles fonctions :

followingLine() : Identique au robot suiveur – calculatePID() et motorPIDcontrol()
runExtraInch() : Fait avancer le robot légèrement. La distance dépend du délai avant l'arrêt moteur.
```
void runExtraInch(void) {
  motorPIDcontrol();
  delay(extraInch);
  motorStop();
}
```
goAndTurn(direction, angle) : Crucial car on ne peut pas tourner immédiatement. Le robot à entraînement différentiel tourne sur son axe ; pour tourner à 90° et continuer à suivre la ligne, le centre des roues doit s'aligner avec le centre de l'intersection. La constante adjGoAndTurn s'ajuste selon la distance axe-capteurs, vitesse et taille des roues.
```
void goAndTurn(int direction, int degrees) {
  motorPIDcontrol();
  delay(adjGoAndTurn);
  motorTurn(direction, degrees);
}
```

À ce stade, le robot « résout un maze » ! La « Première Passe » est terminée. Peu importe où vous le placez dans un maze, il atteindra la fin.

Étape 6 : Mémorisation du parcours

Exemple : au point de départ choisi, le robot rencontre 15 intersections avant la fin :

L, B, L, L, L, B, S, B, L, L, B, S, L, L, End

(L=Gauche, B=Demi-tour/Back, S=Tout droit/Straight)

Il faut sauvegarder chaque action dans l'ordre exact. Création d'un tableau pour stocker le chemin :

char path[100] = "";
unsigned char pathLength = 0;
int pathIndex = 0;

Résultat pour l'exemple :

path = [LBLLLBSBLLBSLL], pathLength = 14

Étape 7 : Simplification (optimisation) du chemin

Analysons le premier groupe : la première branche à gauche est une impasse. Au lieu de « Gauche-Demi-tour-Gauche » (LBL), passer tout droit (S) économise temps et énergie. En d'autres termes, LBL = S.

Liste complète des simplifications possibles (à vérifier) :

LBR = B
LBS = R
RBL = B
SBL = R
SBS = B
LBL = S

Application sur le chemin complet :

path = [LBLLLBSBLLBSLL] → LBL = S
path = [SLLBSBLLBSLL] → LBS = R
path = [SLRBLLBSLL] → RBL = B
path = [SLBLBSLL] → LBL = S
path = [SSBSLL] → SBS = B
path = [SBLL] → SBL = R
path = [RL]

Incroyable ! Si le robot prend DROITE à la première intersection puis GAUCHE, il atteint la fin par le chemin le plus court !

Le code de la Première Passe est consolidé dans mazeSolve() – c'est la fonction loop() précédente enrichie du stockage et de l'optimisation. Quand la première passe se termine, path[] contient le chemin optimisé. Nouvelle variable :

unsigned int status = 0; // 0 = résolution, 1 = fin du maze atteinte

Fonction mazeSolve() :

void mazeSolve(void) {
  while (!status) {
    readLFSsensors();
    switch (mode) {
      case NO_LINE:
        motorStop();
        goAndTurn(LEFT, 180);
        recIntersection('B');
        break;
      case CONT_LINE:
        runExtraInch();
        readLFSsensors();
        if (mode != CONT_LINE) {
          goAndTurn(LEFT, 90);
          recIntersection('L');
        } else mazeEnd();
        break;
      case RIGHT_TURN:
        runExtraInch();
        readLFSsensors();
        if (mode == NO_LINE) {
          goAndTurn(RIGHT, 90);
          recIntersection('R');
        } else recIntersection('S');
        break;
      case LEFT_TURN:
        goAndTurn(LEFT, 90);
        recIntersection('L');
        break;
      case FOLLOWING_LINE:
        followingLine();
        break;
    }
  }
}

Nouvelle fonction recIntersection(direction) : stocke l'intersection et appelle simplifyPath().

void recIntersection(char direction) {
  path[pathLength] = direction;
  pathLength++;
  simplifyPath();
}

Le crédit de simplifyPath() revient à Patrick McCabe (https://patrickmccabemakes.com). Stratégie : dès qu'on rencontre une séquence xBx, on la simplifie en supprimant l'impasse. Exemple : LBL → S.

void simplifyPath() {
  if (pathLength < 3 || path[pathLength-2] != 'B') return;
  int totalAngle = 0;
  for (int i = 1; i <= 3; i++) {
    switch (path[pathLength-i]) {
      case 'R': totalAngle += 90; break;
      case 'L': totalAngle += 270; break;
      case 'B': totalAngle += 180; break;
    }
  }
  totalAngle %= 360;
  switch (totalAngle) {
    case 0:   path[pathLength-3] = 'S'; break;
    case 90:  path[pathLength-3] = 'R'; break;
    case 180: path[pathLength-3] = 'B'; break;
    case 270: path[pathLength-3] = 'L'; break;
  }
  pathLength -= 2;
}

Étape 8 : Deuxième passe – Résoudre le maze le plus vite possible !

Programme principal loop() :

void loop() {
  ledBlink(1);
  readLFSsensors();
  mazeSolve();        // Première passe
  ledBlink(2);
  while (digitalRead(buttonPin)) { }
  pathIndex = 0;
  status = 0;
  mazeOptimization(); // Deuxième passe : aussi vite que possible
  ledBlink(3);
  while (digitalRead(buttonPin)) { }
  mode = STOPPED;
  status = 0;
  pathIndex = 0;
  pathLength = 0;
}

Quand la première passe se termine, on alimente le robot avec le tableau path[] optimisé. À chaque intersection, il décide selon ce qui est stocké dans path[].

void mazeOptimization(void) {
  while (!status) {
    readLFSsensors();
    switch (mode) {
      case FOLLOWING_LINE:
        followingLine();
        break;
      case CONT_LINE:
        if (pathIndex >= pathLength) mazeEnd();
        else { mazeTurn(path[pathIndex]); pathIndex++; }
        break;
      case LEFT_TURN:
        if (pathIndex >= pathLength) mazeEnd();
        else { mazeTurn(path[pathIndex]); pathIndex++; }
        break;
      case RIGHT_TURN:
        if (pathIndex >= pathLength) mazeEnd();
        else { mazeTurn(path[pathIndex]); pathIndex++; }
        break;
    }
  }
}

Fonction mazeTurn(path[]) :

void mazeTurn(char dir) {
  switch (dir) {
    case 'L': goAndTurn(LEFT, 90); break;   // Tourner à gauche
    case 'R': goAndTurn(RIGHT, 90); break;  // Tourner à droite
    case 'B': goAndTurn(RIGHT, 800); break; // Demi-tour
    case 'S': runExtraInch(); break;        // Tout droit
  }
}

La deuxième passe est terminée ! La vidéo ci-dessous montre l'exemple complet (première et deuxième passe). Le code Arduino complet est disponible dans les fichiers joints.

Étape 9 : Utilisation de l'Android pour le réglage

L'application Android développée pour le projet suiveur de ligne fonctionne aussi ici (disponible sur le tutoriel précédent). Le code Arduino inclut déjà la communication Android. Si vous ne voulez pas l'utiliser, pas de problème – le code est « transparent ».

J'ai beaucoup utilisé l'Android pour envoyer des données de test du robot vers l'appareil via le champ « Message Reçu ». Plusieurs variables doivent être bien définies pour garantir les bons angles de virage. Les plus importantes (celles en gras que j'ai souvent modifiées) :

const int adj = 0;
float adjTurn = 8;
int adjGoAndTurn = 800;
THRESHOLD = 150;
const int power = 250;
const int iniMotorPower = 250;
int extraInch = 200;

Étape 10 : Conclusion

C'est la deuxième et dernière partie d'un projet complexe explorant le potentiel d'un robot suiveur de ligne, où des concepts simples d'Intelligence Artificielle (IA) ont été utilisés pour résoudre un maze.

Je ne suis pas expert en IA, mais d'après mes recherches, ce que fait notre petit Rex pourrait être considéré comme une application d'IA. Voyons deux sources :

Wikipedia
Article universitaire : « Maze Solving Robot Using Freeduino and LSRB Algorithm » (International Journal of Modern Engineering Research – IJMER)

Les fichiers mis à jour sont sur GitHub. J'espère avoir contribué à l'apprentissage de l'électronique, la robotique, Arduino, etc. Pour plus de tutoriels, visitez mon blog : MJRoBot.org

Saludos du sud du monde !

Merci,
Marcelo

Code

Plusieurs extraits de code sont fournis (voir le projet original pour les fichiers complets) :

Déclaration des broches capteurs
Lecture des capteurs
Fonction de test des capteurs
Boucle principale (première passe)
Fonctions runExtraInch, goAndTurn
Fonction mazeSolve (résolution + stockage + simplification)
Fonctions recIntersection et simplifyPath
Boucle principale complète (2 passes)
Fonctions mazeOptimization et mazeTurn

Lien GitHub : https://github.com/Mjrovai/MJRoBot-Maze-Solver

Schémas

Fichier Fritzing disponible : z7IdLkxL1J66qOtphxqC.fzz

Machine à Pince Arduino DIY – Construisez Votre Propre Arcade Horloge RTC Arduino Nano : Chronométrage Précis avec DS1307

Processus de fabrication

impression en 3D

Système de contrôle d'automatisation

Technologie industrielle