Lassé du suiveur de ligne conventionnel? Les gens perdent presque tout intérêt? Voici un article qui peut tout changer et faire tourner le vent de votre côté.

Imaginez si votre robot devait partir du nœud A (source) et se déplacer vers le nœud B (destination) et revenir au nœud A! Hmm … pas si génial … Et si votre robot pouvait trouver le chemin le plus court du nœud source au nœud de destination, puis revenir au nœud source en sélectionnant le chemin le plus court ?? N’est-ce pas un sacré robot? C’est là que ce message vous mène.

Pour ce tutoriel, je suppose que vous avez déjà lu mes précédents articles sur le robot suiveur de ligne et comment le programmer. Si vous ne l’avez pas, je vous suggère de leur donner un bref aperçu pour avoir une idée des choses.

Honnêtement, je ne crois pas qu’il faille gâcher tout le plaisir pour vous. Si vous êtes un penseur acharné, arrêtez-vous ici et découvrez votre propre logique. Ensuite, vous pouvez revenir ici et voir si c’est la méthode à laquelle vous pensiez. Si cela correspond bien! Vous gagnez. Si ce n’est pas le cas, publiez votre méthode ici dans la section commentaires ci-dessous. Qui sait que votre logique est peut-être meilleure que la mienne.

Dans l’intérêt de ceux qui ont essayé et abandonné au bord du succès, je posterai ma méthode (ou la méthode à laquelle je pourrais penser) ici. Encore une fois, permettez-moi de vous rappeler que ce n’est probablement pas la meilleure façon de procéder. Si vous connaissez une méthode plus optimisée, vous trouverez peut-être utile de la partager avec d’autres.

Revenons maintenant à la tâche actuelle, considérons une piste avec un point de départ et un point de fin. Ayons également de nombreuses intersections dans les lignes pour produire des points de décision pour le robot. Voici donc à quoi devrait ressembler la piste,

piste la plus courte

Supposons que le champ carré soit le point START et le patch circulaire que le point END sur la piste. Je suis sûr que vous auriez trouvé l’itinéraire le plus court entre la source et la destination; merci pour tous les jeux auxquels nous avons joué dans les magazines. De plus, il s’agit d’un labyrinthe assez simple comparé à ceux que l’on trouve dans le monde jeune. J’ai envoyé la solution de chemin le plus court pour votre confirmation.

Solution la plus courte

Le fait est que votre robot doit être capable de le faire non seulement pour cette piste, mais pour chaque piste à laquelle un esprit humain peut penser. Une autre chose que j’ai déjà mentionnée est que la piste ne devrait avoir aucune boucle. Si votre morceau a une boucle, ajoutez plus de logique, et comme d’habitude, pour garder les choses simples, je veux juste m’en tenir au concept traditionnel.

Avant de passer à cette discussion, il existe deux méthodes par lesquelles votre robot peut résoudre cette piste. Il s’agit de l’algorithme standard gauche et gauche standard. Le nom peut sembler beau, mais cela signifie simplement que le robot doit tourner à gauche à chaque intersection où des virages à gauche sont possibles. Sinon, il ne fait aucun voyage. Le droit par défaut est également le même, mais votre robot prend tous les droits.

Par défaut à gauche:

chemin le plus court vers la gauche

Droite par défaut:

plus court chemin standard à droite

Pour toute trace donnée qui suppose l’hypothèse précédente, l’un des algorithmes conduit toujours le robot vers le nœud de destination. Le temps peut varier, mais c’est une certitude mathématique qu’il réussira à atteindre la destination. L’image ci-dessus est la représentation graphique de l’algorithme de gauche standard.

Le secret de l’algorithme de chemin le plus court est d’apprendre à votre robot quel nœud se souvenir et lequel négliger. Lorsque le robot arrive à une position où il doit prendre une décision sur la direction, supposons que le point est un nœud. Certaines de ces notes méritent d’être rappelées et d’autres non. Le prochain aspect à prendre en compte est la différence entre une torsion et un nœud. Il joue un rôle important dans le choix des points à retenir dans une piste donnée.

Voyage:

Un virage, c’est quand le robot n’a d’autre choix que de tourner. Ces virages peuvent être considérés comme une ligne droite, car c’est le chemin évident que le robot doit emprunter.

Nœud:

Un nœud est lorsqu’il a plus d’une option pour changer de direction. Un nœud est le point d’intersection de plusieurs lignes.

Points à retenir:

Chaque fois que le robot fait face à un nœud, il doit faire une entrée dans le tableau directionnel. Il doit également faire une entrée à chaque fois qu’il arrive dans une impasse. L’image ci-dessous montre le point à retenir dans les algorithmes standard gauche (points rouges) et droit standard (jaune).

Pour mieux comprendre cela, suivez les points sur le côté gauche de la piste du nœud de départ au nœud de destination pour l’algorithme standard sur la gauche. Et aussi pour la norme sur la droite, suivez les points sur la droite. Ces points indiquent les positions auxquelles le robot entrera dans le registre de direction.

points de cours les plus courts

Faisons quelques hypothèses supplémentaires,

  1. Nord – op
  2. Est – droite
  3. Sud – bas
  4. Ouest – gauche

Votre programme ne gardera trace que des numéros de série (index de direction) pour les hypothèses ci-dessus; les instructions sont destinées à votre compréhension. Lorsque votre robot rencontre un nœud, (rappelez-vous), il doit entrer l’un de ces indices directionnels dans le tableau directionnel.

Dans l’algorithme de gauche par défaut, diminuez l’indice de direction du nœud précédent pour obtenir l’indice de direction du nœud actuel. Et dans l’algorithme standard de droite, vous devez augmenter l’indice de direction du nœud précédent pour obtenir l’indice de direction du nœud actuel. Ce n’est peut-être pas très clair à ce stade, lisez la suite …

L’augmentation et la diminution doivent également avoir lieu de manière circulaire. Autrement dit, si vous augmentez 4, il doit être remonté à 1 et, en conséquence, si vous diminuez 1, il doit devenir 4.

Algorithmes:

La procédure pour l’algorithme de gauche standard est la suivante,

  • Considérez toujours le robot faisant face au nord au démarrage.
  • Lorsque le robot rencontre le premier nœud, marquez sa direction par rapport à la direction d’origine supposée Nord. Dans ce cas, il devrait aller directement dans le premier nœud. Il va donc vers le nord en fonction du nord supposé (depuis aucun changement de direction).
  • Ensuite, le curseur diminue une fois à chaque fois que le robot rencontre un nœud et stocke le résultat dans les index matriciels successifs.
  • Et à chaque fois que le robot rencontre une impasse (rotation de 180 degrés), le curseur diminue deux fois et enregistre le résultat dans les index matriciels successifs.

La procédure standard de l’algorithme droit est la suivante,

  • Considérez que le robot fait toujours face au nord au décollage.
  • Lorsque le robot rencontre le premier nœud, marquez sa direction par rapport à la direction d’origine supposée Nord. Dans ce cas, il doit tourner à droite. Ensuite, il se déplace vers l’est par rapport au nord supposé.
  • Ensuite, le curseur augmente une fois à chaque fois que le robot rencontre un nœud et enregistre le résultat dans les index matriciels consécutifs.
  • Et chaque fois que le robot rencontre une impasse (rotation de 180 degrés), augmentez le curseur deux fois et enregistrez le résultat dans les index matriciels consécutifs.

En suivant l’algorithme, vous devriez avoir un tableau directionnel comme celui-ci,

// For default left algorithm:
dir_arr[20] = { 1 , 1 , 3 , 2 , 1 , 3 , 2 , 4 , 3 , 1 , 4 , 3 , 2 , 2 , 2 };

qui est -> [North , North , South , East , North , South , East , West , South , North , West , South , East , East , East]

// For default right algorithm:
dir_arr[20] = { 2 , 3 , 1 , 2 , 4 , 1 , 2 , 3 , 4 , 2 , 4 , 1 , 2 };

qui est -> [East , South , North , East , West , North , East , South , West , East , West , North , East]

Ce sont les valeurs que j’ai calculées après avoir suivi l’algorithme ci-dessus. Vérifiez ceci avec votre propre réponse pour être sûr. C’est le cœur de l’algorithme, donc cette logique ne doit pas être viciée.

Lorsque le robot atteint la cible, dir_arr doit être traité pour calculer le chemin le plus court. C’est la partie la plus difficile de la méthode. Pour comprendre, j’utiliserai des étiquettes de direction au lieu d’index de direction.

S’il y a un sud suivi du nord ou vice versa, c’est un mouvement inutile et doit être supprimé. De même, s’il y a un est suivi d’un ouest ou vice versa, alors il est également superflu. Effacez toutes ces paires de la matrice en premier lieu. Votre matrice devrait donc ressembler à ceci après le premier passage. Dans tous les cas, le premier élément est permanent, même s’il doit être annulé.

Réduction de l’algorithme par défaut sur la gauche:

Au départ, nous ne devons pas supposer que le système directionnel devrait être,

// Initial state.
[ North, North, South, East, North, South, East, West, South, North, West, South, East] 

Lors du premier passage, nous regroupons et supprimons les éléments suivants,

// Pass one
Before = [ North, (North, South), East, (North, South), (East, West), (South, North), West, South, East, East, East ]
After  = [ North, East, West, South, East, East, East ]

De même, nous groupons et supprimons un autre du résultat de la réduction précédente.

// Pass two
Before = [ North, (East, West), South, East, East, East ] 
After  = [ North, South, East, East, East ] 

Enfin, il n’y a plus qu’une chose que nous pouvons supprimer,

// Pass three.
Before = [ (North, South), East, East, East ] 
After  = [ East , East , East ]

Après le troisième passage, il n’y a plus de réduction possible, donc le passage s’arrête ici. Le tableau de sortie final contient le chemin le plus court que le robot doit emprunter pour atteindre la destination. Ainsi, à chaque nœud, le robot doit lire la valeur du tableau et prendre des décisions directionnelles en fonction de l’indice directionnel. La même logique peut être suivie pour l’algorithme standard à droite.

N’est-ce pas ce que nous avions prévu de faire correctement?

Notre robot doit aller au nœud de destination et revenir au nœud source dans le chemin le plus court. Pour ce faire, nous devons apporter quelques modifications au tableau directionnel.

Pour changer la direction du robot, nous avons les éléments du tableau inversés. donc 0e element devient nte element et et ne L’élément doit devenir un élément 0 et ainsi de suite.

Nous ne sommes pas encore là! Les directions sont inversées, mais les directions vers lesquelles elles pointent ne sont pas inversées. Nous devons donc remplacer chaque symbole de direction par son symbole de direction opposée. Autrement dit, le Nord devient le Sud et l’Est devient l’Ouest, et ainsi de suite.

Lorsque tout ce traitement est terminé, le tableau de direction inverse aura, { 4 , 4 , 4 } lequel est [ West , West , West ] dans notre convention.

Voici! L’algorithme de chemin le plus court est révélé. Maintenant, tout ce que vous avez à faire est de réfléchir à la façon dont nous pouvons implémenter cette logique en C et comment structurer le code de telle sorte que le robot doive remplir le tableau au fur et à mesure qu’il va de la source au nœud de destination et à son arrivée back doit utiliser le même tableau (ou différent, c’est votre souhait, mais les ingénieurs embarqués n’ont pas toujours cette option … la plupart du temps le contrôleur manque de mémoire disponible)

J’espère que cet article a été utile. Faites-moi savoir s’il y a une confusion dans le concept expliqué ci-dessus. Je ferai le suivi de cet article avec la section de programmation du robot suiveur de ligne le plus court.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *