Tutoriel graphe de point ?

Le plus célèbre des concours de robotique français dédié à tous les jeunes amateurs de nouvelles technologies.
[EN FRANCAIS UNIQUEMENT - ONLY IN FRENCH]
Alexis
Posts: 3
Joined: Thu 25 Jan 2018, 09:54

Tutoriel graphe de point ?

Post by Alexis » Thu 25 Jan 2018, 10:10

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

User avatar
baptiste_c
Posts: 101
Joined: Mon 20 May 2013, 15:09

Re: Tutoriel graphe de point ?

Post by baptiste_c » Thu 25 Jan 2018, 10:44

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 :)
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

Alexis
Posts: 3
Joined: Thu 25 Jan 2018, 09:54

Re: Tutoriel graphe de point ?

Post by Alexis » Thu 25 Jan 2018, 11:35

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 ^^

User avatar
baptiste_c
Posts: 101
Joined: Mon 20 May 2013, 15:09

Re: Tutoriel graphe de point ?

Post by baptiste_c » Thu 25 Jan 2018, 12:42

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" ;)
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

Alexis
Posts: 3
Joined: Thu 25 Jan 2018, 09:54

Re: Tutoriel graphe de point ?

Post by Alexis » Thu 25 Jan 2018, 15:33

Encore merci pour la réponse,

On va creuser tout ça !

User avatar
oG
Posts: 52
Joined: Fri 02 Jun 2006, 11:28
Location: Bordeaux(33)
Contact:

Re: Tutoriel graphe de point ?

Post by oG » Thu 25 Jan 2018, 16:20

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 ! :wink:

arno
PMI
Posts: 711
Joined: Wed 23 Jun 2004, 21:51
Location: Un peu partout...

Re: Tutoriel graphe de point ?

Post by arno » Thu 25 Jan 2018, 22:49

Alexis wrote:
Thu 25 Jan 2018, 11:35
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 ^^
Personnellement, je n'ai jamais utilisé ROS, juste survolé leur wiki et lu quelques articles.

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 !

User avatar
baptiste_c
Posts: 101
Joined: Mon 20 May 2013, 15:09

Re: Tutoriel graphe de point ?

Post by baptiste_c » Fri 26 Jan 2018, 09:57

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 :)
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

User avatar
Nirgal
Posts: 210
Joined: Mon 25 Oct 2010, 20:05
Contact:

Re: Tutoriel graphe de point ?

Post by Nirgal » Fri 26 Jan 2018, 21:49

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 !
Nirgal
Robot-ESEO

User avatar
baptiste_c
Posts: 101
Joined: Mon 20 May 2013, 15:09

Re: Tutoriel graphe de point ?

Post by baptiste_c » Fri 26 Jan 2018, 22:23

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 :)
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

User avatar
romain_cvra
PMI
Posts: 1116
Joined: Sat 30 Jun 2007, 16:17
Location: suisse
Contact:

Re: Tutoriel graphe de point ?

Post by romain_cvra » Mon 29 Jan 2018, 10:41

baptiste_c wrote:
Fri 26 Jan 2018, 22:23
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
Est ce que tu aurais un exemple concret de comportement que cela implique a donner ?
Site web : http://www.cvra.ch.
Le code source : GitHub
Visualisation CAO 3D de nos robots : GrabCAD

User avatar
baptiste_c
Posts: 101
Joined: Mon 20 May 2013, 15:09

Re: Tutoriel graphe de point ?

Post by baptiste_c » Mon 29 Jan 2018, 11:13

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.
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

User avatar
baptiste_c
Posts: 101
Joined: Mon 20 May 2013, 15:09

Re: Tutoriel graphe de point ?

Post by baptiste_c » Mon 29 Jan 2018, 14:24

Pour plus de clarté :
zones.PNG
zones.PNG (2.61 KiB) Viewed 1129 times
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

Post Reply