Tutoriel graphe de point ?

[Alexis]

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

[baptiste_c]

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

[Alexis]

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

[baptiste_c]

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"

[Alexis]

Encore merci pour la réponse,

On va creuser tout ça !

[oG]

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 !

[arno]

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 !

[baptiste_c]

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

[Nirgal]

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 !

[baptiste_c]

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

[romain_cvra]

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 ?

[baptiste_c]

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_c]

Pour plus de clarté :

zones.PNG (2.61 KiB) Viewed 2210 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.