Tutoriel graphe de point ?
Tutoriel graphe de point ?
Bonjour,
Avec une bande d'amis nous avons décidé de nous lancer dans cette grande aventure qu'est la coupe de France de robotique 2018. Partant de zéro en robotique nous nous sommes donc démenés tant bien que mal
dans cette vaste jungle et à force d'acharnement nous progressons (à une certaine vitesse certes). Tout ça pour dire, après avoir traîné sur nombre de forums ou autre, j'ai vu beaucoup de posts à propos de la stratégie de déplacement du robot. Une stratégie qui nous a paru alléchante fait appel à un graphe de point à faire manuellement pour ensuite faire naviguer le robot de points en points jusqu'à l'objectif.
Ma question est donc: que faut-il faire précisément ? Quels logiciels utiliser ? Plus simplement quelle est la marche à suivre pour réaliser un graphe de points et l'implanter dans notre robot ?
Nous avons modélisé avec succès notre robot sur Gazebo et avons réalisé le mapping de la carte du tournoi mais nous n'avons trouvé aucun tutoriel traitant de la réalisation d'un graphe de point, et les recherches Google nous mènent plus souvent sur des études de fonctions que sur des solutions à notre problème :/
En vous souhaitant bonne chance pour la compétition,
Une équipe d'amateurs passionnés
Avec une bande d'amis nous avons décidé de nous lancer dans cette grande aventure qu'est la coupe de France de robotique 2018. Partant de zéro en robotique nous nous sommes donc démenés tant bien que mal
dans cette vaste jungle et à force d'acharnement nous progressons (à une certaine vitesse certes). Tout ça pour dire, après avoir traîné sur nombre de forums ou autre, j'ai vu beaucoup de posts à propos de la stratégie de déplacement du robot. Une stratégie qui nous a paru alléchante fait appel à un graphe de point à faire manuellement pour ensuite faire naviguer le robot de points en points jusqu'à l'objectif.
Ma question est donc: que faut-il faire précisément ? Quels logiciels utiliser ? Plus simplement quelle est la marche à suivre pour réaliser un graphe de points et l'implanter dans notre robot ?
Nous avons modélisé avec succès notre robot sur Gazebo et avons réalisé le mapping de la carte du tournoi mais nous n'avons trouvé aucun tutoriel traitant de la réalisation d'un graphe de point, et les recherches Google nous mènent plus souvent sur des études de fonctions que sur des solutions à notre problème :/
En vous souhaitant bonne chance pour la compétition,
Une équipe d'amateurs passionnés
- baptiste_c
- Posts: 128
- Joined: Mon 20 May 2013, 15:09
Re: Tutoriel graphe de point ?
Salut,
Chez les AIGRIS, on le fait "à la mano".
On représente le graphe par une matrice carrée : 1 si il y a une arrête entre deux sommets, 0 sinon.
Après tu peux facilement pondérer les arrêtes : distance euclidienne entre les points, +infini sinon.
En espérant que ça vous aide
Chez les AIGRIS, on le fait "à la mano".
On représente le graphe par une matrice carrée : 1 si il y a une arrête entre deux sommets, 0 sinon.
Après tu peux facilement pondérer les arrêtes : distance euclidienne entre les points, +infini sinon.
En espérant que ça vous aide

Baptiste
Supaero 2011 - 2014
A.I.G.R.I.S. 2015 - ...
Prix de l'innovation 2016
Vice-champion de France et 3ème à Eurobot 2017
Supaero 2011 - 2014
A.I.G.R.I.S. 2015 - ...
Prix de l'innovation 2016
Vice-champion de France et 3ème à Eurobot 2017
Re: Tutoriel graphe de point ?
Merci de la réponse rapide !
Effectivement l'idée est assez claire (ça nous donne déjà quelque chose à faire sans que ça soit stérile). Mais tant que je vous tiens, sans vouloir être lourd, cette matrice ne s'enregistre sûrement pas en format .txt si ? Avec quels ROS_stacks doit-elle communiquer ?
Merci encore pour la réponse et désolé d'insister hein ^^
Effectivement l'idée est assez claire (ça nous donne déjà quelque chose à faire sans que ça soit stérile). Mais tant que je vous tiens, sans vouloir être lourd, cette matrice ne s'enregistre sûrement pas en format .txt si ? Avec quels ROS_stacks doit-elle communiquer ?
Merci encore pour la réponse et désolé d'insister hein ^^
- baptiste_c
- Posts: 128
- Joined: Mon 20 May 2013, 15:09
Re: Tutoriel graphe de point ?
Hum nous la matrice est calculée quand on lance le robot.
Et la carte est presque en txt : on a fait le choix de stocker les points dans un yaml qu'on vient charger avec rosparam.
Par contre, je ne sais pas quel pourcentage des gens à la coupe utilisent ros, mais pas sûr que ça soit la majorité, donc ne demande pas trop de choses "ros-specific"
Et la carte est presque en txt : on a fait le choix de stocker les points dans un yaml qu'on vient charger avec rosparam.
Par contre, je ne sais pas quel pourcentage des gens à la coupe utilisent ros, mais pas sûr que ça soit la majorité, donc ne demande pas trop de choses "ros-specific"

Baptiste
Supaero 2011 - 2014
A.I.G.R.I.S. 2015 - ...
Prix de l'innovation 2016
Vice-champion de France et 3ème à Eurobot 2017
Supaero 2011 - 2014
A.I.G.R.I.S. 2015 - ...
Prix de l'innovation 2016
Vice-champion de France et 3ème à Eurobot 2017
Re: Tutoriel graphe de point ?
Encore merci pour la réponse,
On va creuser tout ça !
On va creuser tout ça !
Re: Tutoriel graphe de point ?
Nous on fait ça "à la main" en donnant au robot la position absolue dans le repère de la table ou il doit aller ... et évidemment on finit toujours par se prendre un machin vissé au milieu parce qu'un recalage a raté à cause d'un élément de jeu ! 

Re: Tutoriel graphe de point ?
Personnellement, je n'ai jamais utilisé ROS, juste survolé leur wiki et lu quelques articles.Alexis wrote: ↑Thu 25 Jan 2018, 11:35Merci de la réponse rapide !
Effectivement l'idée est assez claire (ça nous donne déjà quelque chose à faire sans que ça soit stérile). Mais tant que je vous tiens, sans vouloir être lourd, cette matrice ne s'enregistre sûrement pas en format .txt si ? Avec quels ROS_stacks doit-elle communiquer ?
Merci encore pour la réponse et désolé d'insister hein ^^
J'imagine que tu as cherché sur le wiki de ROS ?
Les mots clés que tu recherches sont (en anglais) : map, navigation, path finding, path planning, a-star (ou A*), dijkstra, potential field, ....
On trouve assez rapidement des packages comme celui là : http://wiki.ros.org/global_planner, http://wiki.ros.org/base_local_planner?distro=lunar ou http://wiki.ros.org/nav_msgs
Reste ensuite à trouver un exemple de comment rentrer les infos la dedans, mais vous utilisez déjà ROS donc ça doit pas être bien différent des autres packages...
Pour la carte en elle même, le plus simple est de couper la carte en plein de petits carrés (par exemple carrés de 20cm de côté si vous n'avez pas trop de ressources, carrés de 1cm de côté si vous n'avez pas de limites de RAM/CPU pour calculer en temps réel dessus). Ensuite, pour chaque carré on défini si il est franchissage ou pas. Pour cela, on itère sur les obstacles, pour bloquer tous les carrés où l'obstacle est présent (même si il touche juste un peu sur le bord). Ensuite, il reste à appliquer un algo de type A* ou Dijkstra pour trouver le chemin le plus court franchissable entre 2 points.
C'est simple et systématique, mais il y a des méthodes plus fines et plus complexe pour créer une segmentation de la table non uniforme (pas juste des carrés de même taille), pour allier rapidité de calculs (moins de points nécessaires à calculer pour un même niveau de détail) et résolution (en adaptant le découpage, on peux avoir du cm de précision autour des obstacles, tout en restant à 20cm là où ce n'est pas nécessaire, ce qui rends possible une bonne précision même avec des limites de ressources).
Si tu as des questions sur les principes, je peux éventuellement t'aider, mais pour l'intégration dans ROS, je viens d'atteindre la limite de ce que j'en connais

Bon courage !
- baptiste_c
- Posts: 128
- Joined: Mon 20 May 2013, 15:09
Re: Tutoriel graphe de point ?
Comme l'a dit arno (et c'est je pense le meilleur ratio résultat / complexité), le pathfinder dans une grille d'occupation est une très bonne solution.
Je me rends compte que j'ai pas bien présenté notre solution qui est un peu différente :
- on considère chaque obstacle comme un polygone (la table est souvent pleine de rectangles)
- on a alors une liste de sommets : ce sont eux que je mets dans le graphe "matrice" en fonction de la visibilité directe ou non entre les points
- on fait un A* dans ce graphe pour trouver le chemin
Le chemin trouvé va longer les obstacles, ce qui est la solution optimale
Je me rends compte que j'ai pas bien présenté notre solution qui est un peu différente :
- on considère chaque obstacle comme un polygone (la table est souvent pleine de rectangles)
- on a alors une liste de sommets : ce sont eux que je mets dans le graphe "matrice" en fonction de la visibilité directe ou non entre les points
- on fait un A* dans ce graphe pour trouver le chemin
Le chemin trouvé va longer les obstacles, ce qui est la solution optimale

Baptiste
Supaero 2011 - 2014
A.I.G.R.I.S. 2015 - ...
Prix de l'innovation 2016
Vice-champion de France et 3ème à Eurobot 2017
Supaero 2011 - 2014
A.I.G.R.I.S. 2015 - ...
Prix de l'innovation 2016
Vice-champion de France et 3ème à Eurobot 2017
Re: Tutoriel graphe de point ?
Salut à tous,
face au danger du développement souvent trop complexe et intestable d'un algo magique intelligent qui devine direct comme contourner les obstacles pour se rendre à l'objectif...mon conseil (qui s'adresse ici à des débutants), c'est de viser simple :
1- construire une stratégie "nominale" : des machines à états bien découpées, et un parcours du terrain sur des points choisis. (un simple tableau de points peut suffire)
2- On ajoute à cela pour chaque étape des états de "replis en cas d'échec"... et on chaine les états intelligemment pour se sortir des situations non nominales (blocage / évitement)
Cette approche est à mon sens la plus simple pour avoir rapidement quelque chose qui tient la route...
Et en cadeau, un guide de la machine à états en C... (log = public, mdp = public)
http://tice.sea.eseo.fr/upro/svn/STM32/ ... a_etat.pdf
Bien sur, chaque développeur aura un avis propre... et de nombreux avis seront différents du mien... et c'est tant mieux !
face au danger du développement souvent trop complexe et intestable d'un algo magique intelligent qui devine direct comme contourner les obstacles pour se rendre à l'objectif...mon conseil (qui s'adresse ici à des débutants), c'est de viser simple :
1- construire une stratégie "nominale" : des machines à états bien découpées, et un parcours du terrain sur des points choisis. (un simple tableau de points peut suffire)
2- On ajoute à cela pour chaque étape des états de "replis en cas d'échec"... et on chaine les états intelligemment pour se sortir des situations non nominales (blocage / évitement)
Cette approche est à mon sens la plus simple pour avoir rapidement quelque chose qui tient la route...
Et en cadeau, un guide de la machine à états en C... (log = public, mdp = public)
http://tice.sea.eseo.fr/upro/svn/STM32/ ... a_etat.pdf
Bien sur, chaque développeur aura un avis propre... et de nombreux avis seront différents du mien... et c'est tant mieux !
Nirgal
Robot-ESEO
Robot-ESEO
- baptiste_c
- Posts: 128
- Joined: Mon 20 May 2013, 15:09
Re: Tutoriel graphe de point ?
Je suis 100% d'accord avec toi.
J'ai parlé de notre version actuelle parce que je suis en plein portage sur nos robots, mais un truc bien plus simple fait l'affaire.
Un truc envisageable c'est de découper la table en zones (souvent 5-6 font l'affaire). Ensuite pour chaque action, on définit le comportement en fonction des zones et c'est magique
J'ai parlé de notre version actuelle parce que je suis en plein portage sur nos robots, mais un truc bien plus simple fait l'affaire.
Un truc envisageable c'est de découper la table en zones (souvent 5-6 font l'affaire). Ensuite pour chaque action, on définit le comportement en fonction des zones et c'est magique

Baptiste
Supaero 2011 - 2014
A.I.G.R.I.S. 2015 - ...
Prix de l'innovation 2016
Vice-champion de France et 3ème à Eurobot 2017
Supaero 2011 - 2014
A.I.G.R.I.S. 2015 - ...
Prix de l'innovation 2016
Vice-champion de France et 3ème à Eurobot 2017
- romain_cvra
- PMI
- Posts: 1175
- Joined: Sat 30 Jun 2007, 16:17
- Location: suisse
- Contact:
Re: Tutoriel graphe de point ?
Est ce que tu aurais un exemple concret de comportement que cela implique a donner ?baptiste_c wrote: ↑Fri 26 Jan 2018, 22:23Un truc envisageable c'est de découper la table en zones (souvent 5-6 font l'affaire). Ensuite pour chaque action, on définit le comportement en fonction des zones et c'est magique
- baptiste_c
- Posts: 128
- Joined: Mon 20 May 2013, 15:09
Re: Tutoriel graphe de point ?
Tu définis quelques points de passage "en dur".
Ensuite si dans une zone tu ne peux pas aller directement au point final, tu demandes d'aller au bon point de passage, puis tu re-regardes dans quelle zone tu es, etc.
Par exmeple en 2012 avec le totem central, on avait 8 zones et 4 points de passages aux angles de ce totem.
Ensuite si dans une zone tu ne peux pas aller directement au point final, tu demandes d'aller au bon point de passage, puis tu re-regardes dans quelle zone tu es, etc.
Par exmeple en 2012 avec le totem central, on avait 8 zones et 4 points de passages aux angles de ce totem.
Baptiste
Supaero 2011 - 2014
A.I.G.R.I.S. 2015 - ...
Prix de l'innovation 2016
Vice-champion de France et 3ème à Eurobot 2017
Supaero 2011 - 2014
A.I.G.R.I.S. 2015 - ...
Prix de l'innovation 2016
Vice-champion de France et 3ème à Eurobot 2017
- baptiste_c
- Posts: 128
- Joined: Mon 20 May 2013, 15:09
Re: Tutoriel graphe de point ?
Pour plus de clarté :
1: on y va direct
2: go p1
3: go p1
4: on y va direct
5: go p4
6: on y va direct
7: on y va direct
8: on y va direct
On boucle à l'infini jusqu'à arriver.
On imagine qu'on veut aller à un point en zone 6 puisque l'action se trouve là. On alors suivant les cas : 1: on y va direct
2: go p1
3: go p1
4: on y va direct
5: go p4
6: on y va direct
7: on y va direct
8: on y va direct
On boucle à l'infini jusqu'à arriver.
Baptiste
Supaero 2011 - 2014
A.I.G.R.I.S. 2015 - ...
Prix de l'innovation 2016
Vice-champion de France et 3ème à Eurobot 2017
Supaero 2011 - 2014
A.I.G.R.I.S. 2015 - ...
Prix de l'innovation 2016
Vice-champion de France et 3ème à Eurobot 2017