Algorithme de Pledge

[AnissaB.]

Bonsoir à tous!
Je suis inscrite en Spé Informatique et Sciences du Numérique en Terminale S. Pour le bac, nous avons un projet à présenter à un jury. Nous avons déjà trouvé notre projet avec une amie: faire sortir un robot d'un labyrinthe. Pour cela, on a à disposition une carte Romeo avec un châssis robot de base. Enfin bref, ça c'est du détail.
Pour faire sortir le robot du labyrinthe, on a choisit l'algorithme de Pledge que notre prof nous a proposé. Je commence tout juste à me renseigner sur cet algorithme et je trouve que les explications ne sont pas très claires. Enfin, j'ai compris le principe, mais je ne comprends pas l'histoire du compteur, pourriez-vous m'aider? J'ai compris qu'il était indispensable mais pourquoi?
Voilà le site sur lequel j'ai trouvé toutes les explications.

Merci d'avance à tous
-----

[bisou10]

Pledge c'est le labyrinthe non ? On calcule les changements angulaires pour savoir si l'on n'est pas en train de tourner en rond.

[AnissaB.]

Ok merci! Mais le truc c'est que je comprends pas pourquoi on fait +1 ou -1 en fonction de la direction qu'on prend.

[Jack]

pour savoir lorsqu'on a trouvé la sortie (compteur = 0)

[A voir en vidéo sur Futura]

[AnissaB.]

Donc si j'ai bien compris, dès que le compteur est à 0, c'est qu'on est sorti?
En tous cas merci pour ta réponse!

[Jack]

L'explication fournie sur le site est pourtant claire: à 0, soit on est sorti, soit on va tout droit jusqu'au mur suivant et on reprends le cycle.

A+

[AnissaB.]

Ok merci, je vais essayer d'écrire l'algorithme et je vous demanderais si ça va. Merci!

[AnissaB.]

Bonjour! Voilà j'ai fait une ébauche de l'algorithme en langage naturel. On l'a fait avec ma partenaire et mon prof d'ISN mais on n'a jamais vu l'algorithme en lui-même. pourriez-vous me dire si'il est cohérent? Merci

L'algorithme:

Si:
	Il y a un mur en face
	→S'arrêter
Fin Si

Si:
	On tourne à gauche
	→-1 au compteur
Fin Si

Si:
	On tourne à droite
	→+1 au compteur
Fin Si

Si:
	Compteur = 0
	→ Aller tout droit
Fin Si

Tant que:
	Il y a un mur à gauche
	→ Aller tout droit
	Sinon:
	→Tourner à gauche
Fin Tant que

Si:
	Il y a un mur en face
	→ Tourner à droite
Fin si

[Jack]

Non, ton algorithme ne fonctionne pas. Pour trouver ce qui ne va pas, essaie-le avec les exemples qui sont proposés sur le site dont tu as donné la référence.

Tiens-nous au courant.

[AnissaB.]

Bon voilà j'ai refait un sketch en langage naturel. Le voilà:

Tant qu'il n'y a pas de mur en face, avancer.

Quand il y a un vide à gauche, tourner à gauche et décrémenter le compteur.

Si il y a un mur en face {
Si il y a un mur à gauche, tourner à droite et incrémenter le compteur.
Sinon, tourner à gauche et décrémenter le compteur.}

Quand le compteur = 0, avancer jusqu'à rencontrer un mur en face.

Si vous penser quil est pas bon, dites moi pourquoi! Merci!

[Jack]

Je ne comprends pas que tu ne voies pas ce qui ne va pas:
je ne vois aucune répétition une fois qu'on a atteint le mur en face pour la 1ère fois.

Donc tout s'arrêtera à la prochaine rencontre d'un mur en face, et encore, si le compteur arrive à 0 vu que tu ne vas tourner que 2 fois en tout.

[AnissaB.]

Ben je pense pas parce que c'est sur Arduino, et le programme s'insère dans un loop puisque c'est un langage C. Donc le programme tourne en boucle. En plus, il y a une boucle "tant que" donc normalement tout devrait fonctionner en boucle non?

[PA5CAL]

Ben je pense pas parce que c'est sur Arduino, et le programme s'insère dans un loop puisque c'est un langage C. Donc le programme tourne en boucle. En plus, il y a une boucle "tant que" donc normalement tout devrait fonctionner en boucle non?

S'il y a une boucle, ce n'est pas parce que c'est écrit en langage C, mais parce que tu utilises un Arduino (ce qui n'apparaît pas explicitement dans ton sujet), et que la boucle loop() est l'un des éléments de base appelés par le programme intégré dans le micro-contrôleur (l'autre élément étant la séquence initiale setup(), qui n'est exécutée qu'un fois).

Une présentation claire et complète du programme aurait donc nécessité l'indication que les opérations étaient dans une boucle infinie.

[PA5CAL]

En tenant compte de la boucle, l'exécution du programme dans le cas général donne :

Boucle infinie {

1     Tant qu'il n'y a pas de mur en face, avancer.

-- ici on a atteint le mur
2     Quand il y a un vide à gauche, tourner à gauche et décrémenter le compteur.

-- ici on a tourné à gauche et on a décrémenté le compteur
3     Si il y a un mur en face {
-- il n'y a pas de mur en face parce qu'en 2 il y avait un vide à gauche avant de tourner,
-- donc on passe directement à 4
3.1      Si il y a un mur à gauche, tourner à droite et incrémenter le compteur.
3.2      Sinon, tourner à gauche et décrémenter le compteur.}

4     Quand le compteur = 0, avancer jusqu'à rencontrer un mur en face.
-- le compteur n'étant déjà plus à 0 depuis l'étape 2, on ignore 4 et on recommence à 1

  }

Sauf dans le cas particulier où il atteindrait un angle immédiatement situé à sa gauche, le robot passe son temps à avancer tout droit et à tourner à gauche quand un mur lui fait obstacle, et son compteur est décrémenté sans fin.

Ce n'est pas ce que prescrit l'algorithme de Pledge, qui précise qu'après le premier obstacle, le robot doit commencer par suivre les murs.


Avec ce programme, le robot n'est pas capable de sortir d'un simple pièce avec quatre murs et un porte.

[Jack]

S'il y a une boucle, ce n'est pas parce que c'est écrit en langage C, mais parce que tu utilises un Arduino (ce qui n'apparaît pas explicitement dans ton sujet), et que la boucle loop() est l'un des éléments de base appelés par le programme intégré dans le micro-contrôleur (l'autre élément étant la séquence initiale setup(), qui n'est exécutée qu'un fois).

Une présentation claire et complète du programme aurait donc nécessité l'indication que les opérations étaient dans une boucle infinie.

En effet, s'il faut commencer à essayer de deviner des éléments qui ne sont pas évoqués, on ne va pas aller loin.
J'espère que vous avez aussi fait le choix des capteurs, de leur nombre et de leur emplacement parce qu'un algo c'est beau quand il fonctionne, mais s'il ne correspond pas au monde réel ça présente beaucoup moins d'intérêt.

A+

[AnissaB.]

En effet, s'il faut commencer à essayer de deviner des éléments qui ne sont pas évoqués, on ne va pas aller loin.

J'ai oublié de le mentionner en effet.

J'espère que vous avez aussi fait le choix des capteurs, de leur nombre et de leur emplacement parce qu'un algo c'est beau quand il fonctionne, mais s'il ne correspond pas au monde réel ça présente beaucoup moins d'intérêt.

Deux capteurs à ultrasons sont branchés sur la Romeo: un à gauche et un devant. Celui de gauche permettra de voir la position du robot par rapport au mur de gauche et celui de devant sert à éviter de buter sur un obstacle devant. Je pense que c'est suffisant.

Ce n'est pas ce que prescrit l'algorithme de Pledge, qui précise qu'après le premier obstacle, le robot doit commencer par suivre les murs.
Avec ce programme, le robot n'est pas capable de sortir d'un simple pièce avec quatre murs et un porte.

C'est pas possible? Je pensais parce que je teste quand y'a un vide à gauche. Donc du coup il faut que je fasse une boucle "tant que" au tout début du programme pour que le robot teste en permanence qu'on est a 5cm du mur par exemple? Et dans cette boucle je mettrais tout le reste du programme du coup?

En tous cas merci pour vos réponses.

[PA5CAL]

Je comprends mal la raison de ce bricolage algorithmique.

L'algorithme de Pledge a été clairement décrit sur la page dont tu as donné le lien :

1- Aller tout droit jusqu’au mur, passer à l'instruction 2 ;
2- Longer le mur par la droite (ou par la gauche, mais toujours dans le même sens) jusqu’à ce que le décompte des changements de direction atteigne zéro, passer à l'instruction 1 ;

Il faut répéter ces actions jusqu’à ce que l’on revienne à la lumière du jour.

Le seul problème sérieux concerne la retranscription du "longer le mur", puisque l'algorithme détaillé dépend alors intimement :
- de la façon dont le robot bouge (réalisation des changements de direction) et perçoit son environnement (position des capteurs par rapport aux murs après un changement de direction)
- de la configuration des murs (angles, largeur minimale, planéité)
- de l'orientation initiale du robot.

Or, pour l'instant on ne dispose pas de beaucoup d'éléments sur la situation qui permettraient de déterminer ce qu'il faut faire à ce niveau.


Pour donner un exemple, si l'on peut vérifier les hypothèses suivantes :
- le robot est celui indiqué dans la présentation du sujet (modèle rond à deux roues motrices diamétrales indépendantes)
- il sait réaliser des quarts de tour parfaits sur lui-même (!)
- il sait évaluer la distance qu'il parcourt
- ses capteurs "mur à gauche" et "mur devant" sont des capteurs de contact (et pas de présence à une distance mal évaluée)
- son capteur "mur à gauche" est situé au niveau de l'axe de la roue motrice gauche
- les murs sont placés sur un quadrillage rectiligne à angle droit, dont le pas est supérieur au rayon du robot, et permettant partout le passage du robot (i.e. pas de passage détectable où le robot resterait coincé)
- le robot démarre orienté parallèlement à l'un des axes de ce quadrillage
alors la réalisation de la partie de l'algorithme "longer le mur" est grandement simplifiée. Le programme pourrait s'écrite :

Mettre le compteur à zéro
Répéter  {
   Tant qu'on n'a pas de mur devant, répéter {
     Avancer tout droit
     Si on a atteint la sortie, ARRÊTER.
   }
   Arrêter d'avancer
   Tourner d'un quart de tour à droite
   Incrémenter le compteur
   Répéter {
     Avancer tout droit
     Si on a atteint la sortie, ARRÊTER.
     S'il n'y a pas de mur à gauche {
       Mettre le podomètre† à zéro
       Répéter {
         Avancer tout droit
       } Tant que le podomètre† indique une distance inférieure à R‡
       Arrêter d'avancer
       Tourner d'un quart de tour à gauche
       Décrémenter le compteur
       Mettre le podomètre† à zéro
       Répéter {
         Avancer tout droit
       } Tant qu'il n'y a pas de mur à gauche
           et qu'il n'y a pas de mur devant
           et que le podomètre† indique une distance inférieure à R‡
     } sinon
     S'il y a un mur devant {
       Arrêter d'avancer
       Tourner d'un quart de tour à droite
       Incrémenter le compteur
     }
   } Tant que le compteur est différent de zéro
}

^†: Le podomètre sert à compter la distance parcourue
^‡: R désigne le rayon du robot

La partie en violet retranscrit l'action "longer le mur par la droite", dans le cas où les hypothèses indiquées seraient toutes valables.

[AnissaB.]

Merci beaucoup pour le code, c'est gentil. Par contre, il y a un truc que je ne comprends pas: en quoi la partie en violet peut-elle nous permettre de longer un mur? Parce qu'aucune distance entre le mur et le robot est testé, enfin si j'ai bien compris.

[PA5CAL]

Avec les hypothèses que j'ai posées (notamment la détection du mur par contact), le robot touche le mur qu'il longe.

Toute autre façon de se déplacer se traduira par une partie en violet différente.

[Jack]

Merci beaucoup pour le code, c'est gentil. Par contre, il y a un truc que je ne comprends pas: en quoi la partie en violet peut-elle nous permettre de longer un mur? Parce qu'aucune distance entre le mur et le robot est testé, enfin si j'ai bien compris.

Je crois que la réponse est ici:

Le seul problème sérieux concerne la retranscription du "longer le mur", puisque l'algorithme détaillé dépend alors intimement :
- de la façon dont le robot bouge (réalisation des changements de direction) et perçoit son environnement (position des capteurs par rapport aux murs après un changement de direction)
- de la configuration des murs (angles, largeur minimale, planéité)
- de l'orientation initiale du robot.

Il faut donc une direction initiale parfaitement perpendiculaire au mur d'en face et les virage doivent être à 90% pile