Ignorer la navigation

La méthode pledge

La main gauche

Vous êtes dans un labyrinthe. Il fait nuit. Pour en sortir, d'abord avançons prudemment tout droit jusqu’à rencontrer un mur et nous longeons ce mur avec notre main gauche.Main gauche

Mais si vous tombez sur un ilot ou un pilier, il y a peu de chance que vous réussissiez.

Erreur main gauche

Afin de résoudre ce problème, nous avançons prudemment jusqu'au mur,
Puis, nous le longeons avec la main gauche, jusqu'à ce que nous soyons  dans la même direction que celle du départ.
Nous avançons tout droit jusqu'au prochain mur, et nous le suivons avec la main gauche.

Main gauche

Mais dans le premier labyrinthe cette méthode ne fonctionne plus.

Erreur main gauche

Alors comment résoudre ce problème ?

L 'algorithme de Pledge

John Pledge, un garçon de douze ans a eu cette idée, il ne suffit pas de marcher en ligne droite et de garder le mur à gauche, mais il faut aussi compter les changements de direction.

 Nous supposons dans les exemples que tous les angles sont droits. Nous n' avons que deux possibilités tourner à droite ou gauche selon un angle de 90°.
Au départ le décompte est à 0. A chaque fois que la valeur est à 0, nous allons tout droit jusqu'au prochain mur.
Sinon, on compte les changements de direction en augmentant d'un point lorsque je tourne à gauche, et en diminuant d'un point lorsque je tourne à droite .

L 'algorithme

Compteur =0
1. aller tout droit juqu'au mur.
2. longer le mur par la gauche (ou la droite mais toujours du même côté), et compter les changements de direction (+ 1 à gauche, -1 à droite).
Lorsque le décompte des changements atteint 0, passer à l'instruction 1.

Méthode Pledge

Résultats de la méthode Pledge en vidéo  :

Mbot contourne un pilier


Mbot contourne un pilier

Mbot dans un autre labyrinthe


Mbot dans labyrinthe (méthode Pledge)