Robot de résolution de labyrinthe, utilisant l'intelligence artificielle

Avec l'ajout des 2 nouveaux, leurs sorties possibles sont :

• Capteur extrême GAUCHE :sortie analogique supérieure ou inférieure à un SEUIL

• Capteur d'extrême droite :sortie analogique supérieure ou inférieure à un seuil

Afin de stocker les valeurs de chaque capteur, une variable de tableau est créée pour les 5 capteurs numériques d'origine :

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

Et deux variables entières pour les 2 nouveaux capteurs analogiques :

int farRightSensor =0;int farLeftSensor =0; 

Chaque position du tableau et des variables sera constamment mise à jour avec la sortie de chacun des capteurs :

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); 

Avoir 5 capteurs, comme vu dans le projet Follower Line Robot, permet la génération d'une "variable d'erreur" qui aidera à contrôler la position du robot sur la ligne. De plus, une variable appelée "mode" sera utilisée pour la définition si le robot suit une ligne , sur une ligne continue , une intersection ou pas de ligne du tout.

Cette variable "mode " sera également utilisé avec le "Extrême GAUCHE/DROITE " capteurs. Pour la représentation, considérons les capteurs d'extrême gauche et de droite ayant 3 états possibles :

• H (supérieur au SEUIL),

• L (plus petit que THRESHOLD) et

• X (non pertinent).

Pour les sorties numériques , sera l'habituel 0, 1 et nous introduirons également le X :

• H 0 X X X X L ==> mode =RIGHT_TURN; erreur =0 ; (voir l'exemple sur l'image ci-dessus)

• L X X X X 0 H ==> mode =LEFT_TURN; erreur =0 ;

• X 0 0 0 0 0 X ==> mode =NO_LINE ; erreur =0 ;

• H 0 0 0 0 1 H ==> mode =FOLLOWING_LINE; erreur =4 ;

• H 0 0 0 1 1 H ==> mode =FOLLOWING_LINE; erreur =3 ;

• H 0 0 0 1 0 H ==> mode =FOLLOWING_LINE; erreur =2 ;

• H 0 0 1 1 0 H ==> mode =FOLLOWING_LINE; erreur =1 ;

• H 0 0 1 0 0 H ==> mode =FOLLOWING_LINE; erreur =0 ;

• H 0 1 1 0 0 H ==> mode =FOLLOWING_LINE; erreur =-1 ;

• H 0 1 0 0 0 H ==> mode =FOLLOWING_LINE; erreur =-2

• H 1 1 0 0 0 H ==> mode =FOLLOWING_LINE; erreur =-3;

• H 1 0 0 0 0 H ==> mode =FOLLOWING_LINE; erreur =-4 ;

• X 1 1 1 1 1 X ==> mode =CONT_LINE ; erreur =0 ;

Donc, en implémentant la logique ci-dessus dans la fonction :

void readLFSsensors() 

renverra les variables "mode " et "erreur " qui sera utilisé à la logique du programme. Il est important de tester la logique des capteurs avant de poursuivre avec le projet. La fonction soufflet est incluse dans le code et peut être utilisée à des fins de test :

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

Étape 4 :Résoudre le labyrinthe - La règle de la main gauche

Comme indiqué dans l'introduction, la majorité des labyrinthes, aussi complexe que leur conception puisse paraître, étaient essentiellement formés d'un mur continu avec de nombreuses jonctions et branches. Si le mur entourant le but d'un labyrinthe est relié au périmètre du labyrinthe à l'entrée, le labyrinthe peut toujours être résolu en gardant une main en contact avec le mur, quel que soit le nombre de détours que cela implique. Ces labyrinthes "simples" sont correctement appelés "Simply-connected ."

En cherchant sur Wikipédia, nous apprenons que :

En bref, la règle de la main gauche peut être décrit comme :

À chaque intersection et dans tout le labyrinthe, gardez votre main gauche touchant le mur sur votre gauche.

• Placez votre main gauche sur le mur.

• Commencez à avancer

• Finalement, vous arriverez au bout du labyrinthe. Vous n'emprunterez probablement pas le chemin le plus court et le plus direct, mais vous y arriverez.

Donc, la clé ici est d'identifier les intersections , définissant le cours à suivre en fonction des règles ci-dessus. Spécifiquement dans notre genre de labyrinthe 2D, nous pouvons trouver 8 types d'intersections différents (voir la première image ci-dessus) :

En regardant l'image, on peut se rendre compte que les actions possibles aux intersections sont :

1. À une "Croix " :

• Aller à gauche, ou

• Aller à droite, ou

• Allez tout droit

2. À un "T " :

• Aller à gauche, ou

• Aller à droite

3. À un "Droit seulement " :

• Aller à droite

4. À un "À gauche seulement " :

• Aller à gauche

5. À "Droite ou gauche " :

• Aller à gauche, ou

• Allez tout droit

6. À "Droit ou à droite " :

• Aller à droite, ou

• Allez tout droit

7. Dans une "impasse " :

• Revenir en arrière (« Demi-tour »)

8. À "Fin du labyrinthe " :

• Arrêtez

Mais, en appliquant la "règle de la main gauche", les actions seront réduites à une option chacune :

• À une "croix" :aller à gauche

• À un "T" :aller à gauche

• À "Droite uniquement" :aller à droite

• À "gauche seulement" :aller à gauche

• À "Droite ou à gauche" :aller à gauche

• À un "droit ou à droite" :allez tout droit

• Dans une "Impasse" :Revenir en arrière ("De retour")

• Au "Fin du Labyrinthe" : Stop

Nous y sommes presque! "Soyez calme !"

Lorsque le robot atteint une « impasse » ou la « fin d'un labyrinthe », il est facile de les identifier, car il n'existe pas de situations ambiguës (nous avons déjà implémenté ces actions sur le robot suiveur de ligne, vous vous souvenez ?). Le problème est lorsque le robot trouve une " LIGNE " par exemple, car une ligne peut être une " Croix " (1) ou un " T " (2). De plus, lorsqu'il atteint un "virage à gauche ou à droite", il peut s'agir d'un simple virage (options 3 ou 4) ou d'options pour aller tout droit (5 ou 6). Pour découvrir exactement sur quel type d'intersection se trouve le robot, une étape supplémentaire doit être franchie :le robot doit parcourir un "pouce supplémentaire" et voir ce qui va suivre (voir la deuxième image ci-dessus, à titre d'exemple).

Ainsi, en termes de flux, les actions possibles peuvent maintenant être décrites comme :

1. Dans une « impasse » :

• Retour ("De retour")

2. À une "LIGNE" :Courez un pouce supplémentaire

• S'il y a une ligne :C'est une "Croix" ==> Aller à GAUCHE

• S'il n'y a pas de ligne :c'est un "T" ==> Aller à GAUCHE

• S'il y a une autre ligne :c'est la "Fin du Labyrinthe" ==> STOP

3. À un « VIRANT À DROITE » :Courez un centimètre supplémentaire

• s'il y a une ligne :c'est une ligne droite ou droite ==> aller TOUT DROIT

• S'il n'y a pas de ligne :c'est une droite uniquement ==> Aller à DROITE

4. Lors d'un « VIREMENT À GAUCHE » :Courez un centimètre supplémentaire

• s'il y a une ligne :C'est une Droite ou à GAUCHE ==> Aller à GAUCHE

• S'il n'y a pas de ligne :c'est une GAUCHE uniquement ==> Aller à GAUCHE

Notez qu'en fait, en cas de « TOUR À GAUCHE », vous pouvez sauter le test, car vous prendrez de toute façon à GAUCHE. J'ai laissé l'explication plus générique uniquement pour plus de clarté. Au vrai code, je sauterai ce test. La 3ème photo ci-dessus montre un labyrinthe très simple sur le sol de mon laboratoire, utilisé à des fins de test.

Étape 5 :Implémentation de l'algorithme "La main gauche sur le mur" dans le code Arduino

Une fois que nous avons le readLFSsensors() fonction modifiée pour inclure les 2 capteurs supplémentaires, nous pouvons réécrire la fonction de boucle pour exécuter l'algorithme comme décrit à la dernière étape :

void loop(){ readLFSsensors(); switch (mode) { case NO_LINE:motorStop(); allerEtTourner (GAUCHE, 180); Pause; case CONT_LINE :runExtraInch(); readLFSsensors(); if (mode ==CONT_LINE) mazeEnd(); sinon goAndTurn (GAUCHE, 90); // ou c'est un "T" ou une "Croix"). Dans les deux cas, va à la pause GAUCHE ; cas RIGHT_TURN:runExtraInch(); readLFSsensors(); if (mode ==NO_LINE) goAndTurn (RIGHT, 90); Pause; cas LEFT_TURN :goAndTurn (LEFT, 90); Pause; case FOLLOWING_LINE:followLine(); Pause; }} 

Quelques nouvelles fonctions apparaissent ici :

• suivantLigne() est le même que celui utilisé avec le robot de ligne suivante où, s'il ne fait que suivre une ligne, il doit calculerPID() ; et contrôler les moteurs en fonction des valeurs PID :motorPIDcontrol();

• runExtraInch() : poussera le robot juste un peu vers l'avant. La durée de fonctionnement du robot dépendra du temps que vous utiliserez dans la fonction de retard, avant de commander l'arrêt du moteur.

void runExtraInch(void){ motorPIDcontrol(); retard (extraPouce); arrêt moteur();} 

• goAndTurn (direction, angle) : cette fonction spéciale est importante car vous ne pouvez pas faire tourner le robot dès que vous vous rendez compte du type d'intersection que vous êtes. N'oubliez pas que nous avons projeté un Robot Différentiel qui, lors des virages, "tourne autour de son axe" et donc, pour se déplacer de 90o et suivre continuellement la ligne, le centre des roues doit être aligné avec le centre d'intersection. Une fois que la ligne de capteurs est en avant de son axe, vous devez faire avancer le robot pour les aligner. La constante de temps adjGoAndTurn doit être ajusté en fonction de la distance entre l'axe et la ligne du capteur ("d "), la vitesse et la taille des roues (voir l'image ci-dessus pour illustration).

void goAndTurn(int direction, int degrés){ motorPIDcontrol(); delay(adjGoAndTurn); motorTurn(direction, degrés);} 

À ce stade, le robot est en fait en train de « résoudre un labyrinthe » ! Vous venez de terminer le "First Pass". Peu importe où vous commencez dans un labyrinthe, vous atteindrez toujours la fin.

Ci-dessous, un test de cette phase du projet :

Étape 6 : stockage du chemin

Considérons l'exemple illustré sur la photo ci-dessus. Au point de départ choisi, le robot trouvera 15 Intersections avant d'atteindre la fin du Labyrinthe :

• Gauche (L)

• Retour (B)

• Gauche (L)

• Gauche (L)

• Gauche (L)

• Retour (B)

• Droite (S)

• Retour (B)

• Gauche (L)

• Gauche (L)

• Retour (B)

• Droite (S)

• Gauche (L)

• Gauche (L)

• Fin

Ce qui doit être fait dans l'une de ces intersections, c'est d'enregistrer chaque action effectuée exactement dans la même séquence qu'elle se produit. Pour cela, créons une nouvelle variable (tableau) qui stockera le chemin parcouru par le robot :

char path[100] =" "; 

Nous devons également créer 2 variables d'index à utiliser avec le tableau :

unsigned char pathLength =0 ; // la longueur du pathint pathIndex =0; // utilisé pour atteindre un élément de tableau spécifique. 

Donc, si nous exécutons l'exemple montré dans l'image, nous terminerons par :

path =[LBLLLBSBLLBSLL]et pathLengh =14 

Étape 7 :Simplifier (optimiser) le chemin

Revenons à notre exemple. En regardant le premier groupe d'intersections, nous avons réalisé que la première branche gauche est en fait une "impasse" et donc, si le robot au lieu d'un "gauche-arrière-gauche" ne passait tout droit qu'à cette première intersection, beaucoup d'énergie et du temps serait gagné ! En d'autres termes, une séquence "LBL" serait en fait la même que "S". C'est exactement ainsi que le chemin complet peut être optimisé. Si vous analysez toutes les possibilités où un « demi-tour » est utilisé, l'ensemble des 3 intersections où ce « demi-tour » (« B ») apparaît (« xBx ») peut être réduit à un seul.

Ce qui précède n'est qu'un exemple, vous trouverez ci-dessous la liste complète des possibilités (essayez-le) :

• LBR =B

• LBS =R

• RBL =B

• SBL =R

• SBS =B

• LBL =S

En prenant le chemin complet ou notre exemple, nous pouvons le réduire :

path =[LBLLLBSBLLBSLL] ==> LBL =Spath =[SLLBSBLLBSLL] ==> LBS =Rpath =[SLRBLLBSLL] ==> RBL =Bpath =[SLBLBSLL] ==> LBL =Spath =[SSBSLL ] ==> SBS =Bpath =[SBLL] ==> SBL =Rpath =[RL] 

Incroyable! En regardant l'exemple, il est très clair que si le robot prend à DROITE à la première intersection et après cela, à GAUCHE, il atteindra la fin du labyrinthe par le chemin le plus court !

Le code total de First Path of Maze Solver sera consolidé dans la fonction mazeSolve() . Cette fonction est en fait la fonction loop() utilisée auparavant, mais intégrant toutes ces étapes de stockage et d'optimisation du chemin. Une fois le premier chemin terminé, le tableau path[] aura le chemin optimisé. Une nouvelle variable est introduite :

statut int non signé =0 ; // résolution =0; atteindre Maze End =1 

Sous la fonction Premier chemin :

void mazeSolve(void){ while (!status) { readLFSsensors(); switch (mode) { case NO_LINE:motorStop(); allerEtTourner (GAUCHE, 180); recIntersection('B'); Pause; case CONT_LINE :runExtraInch(); readLFSsensors(); if (mode !=CONT_LINE) {goAndTurn (LEFT, 90); recIntersection('L');} // ou c'est un "T" ou une "Croix"). Dans les deux cas, va à GAUCHE else mazeEnd(); Pause; cas RIGHT_TURN:runExtraInch(); readLFSsensors(); if (mode ==NO_LINE) {goAndTurn (RIGHT, 90); recIntersection('R');} else recIntersection('S'); Pause; cas LEFT_TURN :goAndTurn (LEFT, 90); recIntersection('L'); Pause; case FOLLOWING_LINE:followLine(); Pause; } }}  

Ici, une nouvelle fonction a été introduite :recIntersection (direction). Cette fonction sera utilisée pour stocker l'intersection et aussi pour appeler une autre fonction simplifyPath() , cela réduira le groupe de 3 intersections impliquant un « demi-tour » comme nous l'avons vu précédemment.

void recIntersection(char direction){ path[pathLength] =direction; // Stocke l'intersection dans la variable de chemin. pathLength ++; simplifierPath(); // Simplifie le chemin appris.} 

Le CRÉDIT pour le simplifyPath( ) est à Patrick McCabe pour le chemin Solving Code (pour plus de détails, veuillez visiter https://patrickmccabemakes.com) ! La stratégie de simplification de chemin est que chaque fois que nous rencontrons une séquence xBx, nous pouvons la simplifier en supprimant l'impasse. Par exemple, LBL ==> S comme nous l'avons vu sur l'exemple.

void simplifierPath(){ // ne simplifie le chemin que si l'avant-dernier tour était un 'B' if(pathLength <3 || path[pathLength-2] !='B') return; int totalAngle =0; int je; for(i=1;i<=3;i++) { switch(path[pathLength-i]) { case 'R':totalAngle +=90; Pause; cas 'L' :totalAngle +=270 ; Pause; cas 'B' :totalAngle +=180 ; Pause; } } // Récupère l'angle sous la forme d'un nombre compris entre 0 et 360 degrés. TotalAngle =TotalAngle % 360 ; // Remplace tous ces tours par un seul. switch(totalAngle) { case 0:path[pathLength - 3] ='S'; Pause; cas 90 :path[pathLength - 3] ='R' ; Pause; cas 180 :path[pathLength - 3] ='B' ; Pause; cas 270 :path[pathLength - 3] ='L' ; Pause; } // Le chemin est maintenant plus court de deux étapes. pathLength -=2; }  

Étape 8 :Deuxième passe :résolvez le labyrinthe le plus rapidement possible !

Le programme principal :loop() c'est simple comme ça :

boucle vide() { ledBlink(1); readLFSsensors(); labyrintheRésoudre(); // Première passe pour résoudre le labyrinthe ledBlink(2); while (digitalRead(buttonPin) { } pathIndex =0; status =0; mazeOptimization(); // Second Pass:exécuter le labyrinthe aussi vite que possible ledBlink(3); while (digitalRead(buttonPin) { } mode =STOPPED; status =0; // 1ère passe pathIndex =0; pathLength =0;} 

Ainsi, lorsque le premier passage se termine, nous devons uniquement alimenter le robot avec le réseau de chemins optimisé. Il commencera à courir et lorsqu'une intersection sera trouvée, il définira maintenant ce qu'il faut faire en fonction de ce qu'il est stocké dans path[] .

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

Pour commander quoi faire, une nouvelle fonction mazeTurn(path[]) a été créé. La fonction mazeTurn (chemin[]) sera :

void mazeTurn (char dir) { switch(dir) { case 'L':// Tourner à gauche goAndTurn (LEFT, 90); Pause; case 'R' :// Tourner à droite goAndTurn (RIGHT, 90); Pause; case 'B' :// Revenir en arrière goAndTurn (RIGHT, 800); Pause; case 'S' :// Aller tout droit runExtraInch(); Pause; }} 

Le deuxième passage est terminé ! La vidéo ci-dessous montre l'exemple complet travaillé ici, premier et deuxième passage. Ci-dessous le code Arduino utilisé sur ce tutoriel :

Étape 9 :Utiliser Android pour le réglage

L'application Android développée pour le projet Follow Line peut également être utilisée ici (si vous en avez besoin, l'application Android et son code sont disponibles sur :Line Follower Robot - PID Control - Android Setup. Le code Arduino présenté à la dernière étape inclut déjà la communication avec l'appareil Android. Si vous ne souhaitez pas utiliser l'application Android, pas de problème car le code est "transparent ".

J'ai beaucoup utilisé Android pendant le projet pour envoyer des données de test du robot à l'appareil en utilisant le "Message reçu ". Plusieurs variables doivent être bien définies afin de garantir que le robot tournera le bon angle. Les plus importantes sont ci-dessous (celles marquées en gras je les ai changé plusieurs fois) :

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

Étape 10 : Conclusion

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

Je ne suis pas une IA expert et sur la base de certaines informations que j'ai obtenues du Web, j'ai compris que ce que notre petit Rex, le robot a fait, résoudre le labyrinthe pourrait être considéré comme une application de l'IA. Jetons un œil aux 2 sources ci-dessous :

De Wikipédia :

Ou de cet article universitaire :"Maze Solving Robot Using Freeduino and LSRB Algorithm International Journal of Modern Engineering Research (IJMER)"

Les fichiers mis à jour pour ce projet peuvent être trouvés sur GITHUB. J'espère pouvoir contribuer à ce que d'autres en apprennent davantage sur l'électronique, le robot, Arduino, etc. Pour plus de didacticiels, veuillez visiter mon blog :MJRoBot.org

Salutations du sud du monde !

Merci

Marcelo