Sujet : Algorithme A - Robot Nxt

Bonjour ,

Nous avons comme projet d'appliquer l'agorithme A star a un robot Nxt de chez lego affin qu'il sorte

2

Re : Algorithme A - Robot Nxt

J'ai l'impression que le message a été tronqué au moment de le poster.

Où doit tourner l'algo : sur le NXT ? sur PC ?
Si c'est sur NXT qu'utilisez-vous pour développer ? S'il s'agit de l'environnement Mindstorms d'origine, je crains que ce genre de projet ne soit pas à la portée de l'outil, qui n'est fait que pour créer des algos très simples.

Pour information, il existe un environnement open-source dénommé LeJOS, qui permet de programmer le NXT en Java (il faut charger un firmware particulier sur la brique, mais on peut revenir au firmware d'origine quand on veut sans problème). Il existe une implémentation de A* dans la bibliothèque de classes de LeJOS (pour être plus précis, il s'agit de la classe lejos.robotics.pathfinding.AstarSearchAlgorithm). Cela peut être une source d'inspiration.

Pour plus de détail sur LeJOS au cas où vous ne connaîtriez pas déjà : http://lejos.sourceforge.net/

Bonne continuation

Eric

Re : Algorithme A - Robot Nxt

Bonjour , en effet il a été tronqué , alors pour re-définir notre but plus précisément , nous voulons faire sortir le robot nxt (model au plus simple : roues , capteur..) d'un labyrinthe , mais de manière

Re : Algorithme A - Robot Nxt

Message encor tronqué , je ne comprend pas ...

Re : Algorithme A - Robot Nxt

mais de maniere rapide (ne pas passer plusieurs fois par le meme noeud)
Auriez vous une idée ??

Re : Algorithme A - Robot Nxt

Merci en tout cas pour votre précédent message , bonne journée !

7

Re : Algorithme A - Robot Nxt

Comme je suppose qu'on ne dispose pas de la carte du labyrinthe, et qu'on le découvre via des capteurs (sinon à quoi cela servirait-il de faire un robot), il n'y a pas de solution pour éviter de repasser par un noeud déjà parcouru.

En effet lorsqu'on emprunte une voie, on ne sait pas à l'avance si cela ne va pas être une impasse, qui conduira donc à revenir sur ses pas.

Quel est l'intitulé complet du problème à résoudre ? S'agit-il de découvrir son chemin dans un labyrinthe exploré par le robot ou bien de trouver la sortie du labyrinthe en utilisant sa carte ?

Re : Algorithme A - Robot Nxt

Alors , nous donnons au robot nxt les coordonnés du noeud de depart et celle de l'arrivée . Nous voulons qu'il sorte en évitant au mieux (il peut retourner sur ses pas) de ne pas ré-emprunter les chemins qui sont des impasses . Nous commencons avec un labyrinthe simple en 6x6 , il doit essayer d'y sortir rapidement ...
Avez vous une idée de comment y parvenir ?? merci !

9

Re : Algorithme A - Robot Nxt

Cela ne dit toujours pas si le robot connait la carte du labyrinthe ou pas.

S'il ne la connait pas et que la seule chose qu'il puisse faire c'est de détecter les murs ou la ligne au sol (s'il s'agit d'un labyrinthe tracé), un algo de type A* n'est d'aucune utilité puisqu'il travaille sur une carte de l'environnement.

Quelle est la manip que vous cherchez à faire ? Le NXT est-il placé dans un vrai labyrinthe ou bien travaille-t-il sur une descriptions de ce labyrinthe ? Ce qui n'est pas clair est quand vous parlez des coordonnées d'un noeud. Qu'appelez-vous un noeud ?

En général, quand on parle de noeud dans ce genre de contexte c'est qu'on travaille sur une carte du labyrinthe, modélisée par exemple par des noeuds représentant les intersections de chemins et des arcs représentant les portions de chemins entre deux  intersections. Si c'est bien cela, qu'est ce que le robot est-il censé faire ? Simplement suivre des instructions de parcours selon les calculs fait sur la carte, ou bien reconnaitre lui-même la configuration du labyrinthe ?

Décrivez un peu mieux ce que vous cherchez à faire en gardant à l'esprit que je ne sais rien de votre projet et qu'il n'est pas facile de devinez dans ces conditions.

10

Re : Algorithme A - Robot Nxt

Je debute en robotique et aussi sur ce site , est il possible d'envoyer une photos du labyrinthe pour etre plus clair ?? Le labyrinthe se compose 6 ligne verticale et 6 ligne horizontale. Ce que nous appelons un noeud c'est l'intersection de deux lignes .
Le robot est placé a un noeud du quadrillage (il pourra connaitre les coordonnées de ce noeud) et connaitra aussi les coordonnées du noeud d'arriver . Ensuite nous enlèverons quelques lignes (qui relis les noeuds entre eux) ce qui permetra de créé des passage impossible . Le but est bien-sur qu'il sorte du labyrinthe , mais nous ne voulons pas qu'il ré-essaye les passage qu'il a deja testé et qui ce sont avérés impossible ... Est-ce plus clair ?? merci !

11

Re : Algorithme A - Robot Nxt

Je debute en robotique et aussi sur ce site

Pas de souci, nous sommes là pour aider.

est il possible d'envoyer une photos du labyrinthe

Oui en utilisant le lien "images" juste au-dessus de la zone de rédaction du message

OK pour la signification du terme "noeud". Nous sommes donc bien en phase.

Il reste toujours quelque chose qui n'est pas dit. Est-ce que le robot a la connaissance de la configuration du labyrinthe en termes de noeuds et de connexions ? En d'autres termes connait-il la carte du labyrinthe ou bien doit-il la découvrir en explorant ?

C'est là toute la question, car selon le cas, la solution est totalement différente.

Pour essayer d'expliquer :

1er cas : le robot est placé dans un labyrinthe (avec de vrais murs par exemple) et il doit essayer de trouver la sortie sans connaitre la carte.

Pour ce type de problème le robot doit donc disposer d'un capteur qui le renseigne sur la présence de murs autour de lui (typiquement devant et sur les côtés, encore qu'on puisse résoudre le problème avec un seul capteur). Il peut par exemple adopter la stratégie "main droite", qui consiste à suivre le mur à sa droite en se servant de son ou ses capteurs. Si le labyrinthe ne comporte pas de cycle, il finira par trouver la sortie.

Dans cette situation, on voit bien qu'on n'a pas besoin de carte, et donc que des algos de type A* ne sont donc d'aucune utilité.

2eme cas : le robot connait la carte, et on lui indique les positions de départ et d'arrivée.

Dans ce cas A* peut être utilisé, ainsi que tout autre algo de parcours de graphe. Mais par contre, on n'a besoin ni de capteur, ni de robot à la limite, car on peut traiter cela sur PC, puisque ce n'est que du calcul. Une approche simple est d'appliquer la stratégie "main droite" évoquée tout à l'heure, et dans le cas où on rebrousse chemin lorsqu'on a exploré une impasse, on retire les noeuds concernés, de manière à arriver au final au parcours optimal. Ce parcours n'est pas obligatoirement le plus court, si par exemple le plan comporte des "ilôts" (un obstacle qu'on peut contourner par deux chemins ou plus). En termes d'algorithme, on ajoute les  noeuds explorés à une liste au fur et à mesure qu'on les traverse, sauf si le noeud concerné est déjà dans la liste. Si c'est le cas, on retire tous les noeuds en fin de liste (les plus récents donc) jusqu'au noeud re-traversé (exclu). En faisant cela, on efface le parcours inutile de sa "feuille de route".

Une autre option est de mettre un indicateur de passage sur les noeuds lorsque qu'on les traverse. Si on arrive sur un noeud déjà marqué, on retire l'indicateur du noeud qu'on vient de quitter (un peu comme si on déposait un petit caillou blanc à chaque fois sur les noeuds explorés, en récupérant ceux qui y sont déjà en cas de passage sur ses propres pas).

Pour comprendre le fonctionnement de ces deux options, il suffit de faire tourner la logique "à la main" en utilisant un papier et un crayon pour faire soi-même les "calculs" que ferait le programme.

---

Il reste cependant toujours une question : si votre problème correspond à la 2ème option, que doit faire le robot, étant donné qu'il n'a pas besoin de découvrir son environnement puisqu'on lui en donne le modèle ? Voulez-vous qu'il effectue les divers déplacements en fonction des indications de la carte (longueur des arcs,...) ?

12

Re : Algorithme A - Robot Nxt

Bonjour ,
ce que nous voudrions faire c'est lui indiquer les positions de départ et d'arrivée MAIS il doit essayer de trouver la sortie sans connaitre la carte (ou du moins sans connaitre les passages impossible , il peut savoir que le labyrinthe est dessiné en 6X6). Il disposera d'un suiveur de ligne (le labyrihthe sera fait a partir de scotch noir)
Merci beaucoup pour votre aide !

13

Re : Algorithme A - Robot Nxt

OK, c'est beaucoup plus clair maintenant.

Si le robot n'a pas la carte, alors aucun algo de planification de parcours tel que A* ne peut être utilisé car ils en ont tous besoin.

Vous êtes donc dans le premier cas. Si le labyrinthe est constitué de lignes au sol, il faut donc des capteurs pour les suivre. Une configuration courante est constituée de 3 capteurs "réflex" (ie une source lumineuse, souvent I/R, et un capteur qui mesure la quantité de lumière réfléchie) placés à l'avant du robot selon l'axe transversal et espacés d'une distance supérieure à la largeur de la ligne. Ces capteurs "regardent" le sol bien entendu.

Pour suivre une ligne droite, il faut faire en sorte que seul le capteur central "voit" la ligne. Si seulement un des capteurs latéraux voit la ligne il faut tourner dans le sens qui va ramener le capteur central au-dessus de la ligne.

La détection des croisements ou des virages correspond aux cas de figure où à la fois le capteur central ET un (ou les deux) capteur latéraux voient une ligne.

Une configuration plus "luxueuse" est d'avoir 5 capteurs : les 3 les plus au centre servent au suivi de la ligne et les deux de part et d'autre servent à la détection des carrefours.

Un exemple de ce genre de configuration est utilisé par le robot 3PI : http://www.pololu.com/catalog/product/975
Il y a d'ailleurs pas mal de vidéos avec ce robot utilisé pour sortir de labyrinthes tels que celui que vous voulez utiliser. Google vous les indiquera.