2019 - Robotech Legends

Partagez votre expérience en expliquant comment vous travailler sur votre robot.
Share your experience by explaining how you work on your robot.
User avatar
baptiste_c
Posts: 154
Joined: Mon 20 May 2013, 15:09

Re: 2019 - Robotech Legends

Post by baptiste_c » Sun 13 Oct 2019, 18:16

Du coup, qu'est ce que tu entends par "implémentation continue" ? Parce que pour le coup je crois que nous on tombe dans l'implem discrète, et j'aimerai comprendre pourquoi on fait moins bien ;)
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
Vice-champion de France 2019

Riako
Posts: 89
Joined: Tue 05 May 2015, 18:07

Re: 2019 - Robotech Legends

Post by Riako » Sun 13 Oct 2019, 20:30

(Hummm... je ne suis pas sûr d'avoir utilisé les bon termes :oops: )
Ce que j'appelle "approche discrète", c'est le découpage du terrain en cases. Le chemin trouvé est une suite de cases adjacentes.
Pour l'"approche continue", pas de cases, seulement des polygones qui représentent robots, obstacles et terrain. Le chemin trouvé est une liste de segments.

L'approche continue est-elle meilleure que l'approche discrète ? Je ne pense pas qu'il y en ait une meilleure que l'autre, c'est très dépendant de l'usage et pour la coupe c'est discutable. Nous avons passé du temps à mettre en place cette solution (et à la corriger), bien que l'ancienne (en discret, donc) avait fait ses preuves (2015 à 2018) ! Ancienne solution qui était une bête méthode itérative, plus "simple" qu'un A* et par forcément plus optimisée.
Nous travaillons sur des microcontrôleurs limités en ressources et en performance. En utilisant la méthode continue, nous avons pu réduire le temps de calcul (calcul du chemin comme réinitialisation de la carte) et réduire la taille mémoire occupée (il n'y a pas beaucoup d'obstacles, donc peu de polygones). Plus besoin d’effectuer un second traitement pour "lisser" le résultat (même si certains algorithmes font ça directement en discret, comme theta*) et dans l'idéal nous pourrions générer des courbes de contournement en Bézier propres, connaissant la forme à éviter.

Mon avis : plus optimisé en continue qu'en discret, mais pas plus simple à mettre en place, et pas forcément une nécessité :roll:

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

Re: 2019 - Robotech Legends

Post by baptiste_c » Mon 14 Oct 2019, 07:59

OK ça marche. A ce que tu avais dit avant je pensais que vous aviez un truc encore mieux qu'un A* :) Mais du coup c'est ce qu'on fait aussi. C'est vrai que c'est vraiment pas évident à mettre en place, mais une fois que ça marche, c'est moins gourmand :D
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
Vice-champion de France 2019

antoine_cvra
Posts: 455
Joined: Mon 27 Aug 2007, 18:05
Location: Suisse

Re: 2019 - Robotech Legends

Post by antoine_cvra » Mon 14 Oct 2019, 18:10

On a aussi l'approche "continue". Pour moi le plus grand avantage c'est que le chemin final contient beaucoup moins de point, et que du coup il y a moins souvent des transitions d'un point de consigne au suivant, transitions qui sont souvent un petit choc dans la régulation.

User avatar
kmikaz
Posts: 11
Joined: Wed 19 Sep 2018, 09:38

Re: 2019 - Robotech Legends

Post by kmikaz » Tue 15 Oct 2019, 20:29

L'année dernière, on a implémenté un Dijkstra sur une map découpé en carré de 25mm.

Image

Le problème était surtout de réduire le nombre de points dans le chemin.

En 2015, j'avais commencé une approche continue dans le même genre mais:
- Je considérais que les obstacles étaient tous des rectangles.
- Quand l'obstacle coupait le chemin, je calculais les points pour contouner avec un principe de triangle equilatéral
Image

Le souci c'est que je sortais souvent de la map en calculant les points mais ça m'a donné beaucoup d'idées.

Image

Là j'implémente une solution similaire avec des polygones.
Lorsque je calcule les points pour contourner un obstacle, je fais un truc du genre:
- Je parcours les points de l'obstacle et je les rajoute tant qu'il y a une collision avec l'obstacle entre le point actuel et le point destination.

Le souci, c'est que quand je fusionne tous les obstacles et que un robot est proche d'un bord, je me retrouve à continuer à contourner parce qu'il y a une collision avec le même obstacle (bord + robot) même si c'est pas le même.

Image

Je pense rajouter un truc qui permet de différencier les obstacles dans ce cas-là.

Vous avez fait comment cette partie ?
--
EPITA 2020
Président Evolutek<<

Riako
Posts: 89
Joined: Tue 05 May 2015, 18:07

Re: 2019 - Robotech Legends

Post by Riako » Wed 16 Oct 2019, 11:04

Merci pour vos retours, ça vient compléter notre ressenti sur le sujet :wink:

@kmikaz, pourquoi ne pas utiliser 8 directions (avec les diagonales donc) pour ton Dijkstra ? Cela permettrait de réduire le nombre de points dans la solution et avoir des trajectoires un peu moins "carrées".
Comme je l’ai dit plus haut, nous faisions un traitement sur le résultat pour lisser la solution (edit : supprimer les points intermédiaires), mais un algorithme type theta* donnerait, je pense, un résultat plus directe.

Pour ton implémentation avec les polygones, je ne suis pas sûr d'avoir bien compris ta manière de procéder.
Le suivi du bord : est-ce que tu n'as pas un problème de collision car ton point de passage est sur un point d'un obstacle ?
Fait attention à comment tu traites le polygone représentant les bords et ceux qui représentent les autres obstacles : la transition intérieur / extérieur doit être faite correctement. Certaines erreurs sont parfois invisibles la plupart du temps, car le nombre d'obstacles est assez réduit et on a tendance à ne pas tester assez de cas. Gare à la fusion également, aux points qui se chevauchent et ceux parfaitement alignés.

User avatar
kmikaz
Posts: 11
Joined: Wed 19 Sep 2018, 09:38

Re: 2019 - Robotech Legends

Post by kmikaz » Wed 16 Oct 2019, 15:34

Yop,

Pour le Dijkstra, j'ai rajouté les diagonales et j'ai aussi implémenté un A* mais je me disais qu'une implementation continue serait plus appropriée.
En effet, le temps de traitements et la mémoire sont super importants à la coupe sachant que le code tourne sur une raspy en réseaux.
Je ferais un post sur nos robots d'ici-là pour tout vous expliquer.

Pour l'implémentation en continu:
- Je considère la table comme un polygone avec des polygones internes pour les obstacles
- Lorsque je rajoute un obstacle, je calcule la différence entre le polygone de la table et l'obstacle:
- Le polygone noir c'est le polygon externe de la table
- Les polygons rouges, c'est les polygons internes
Image
- Donc lorsque je rajoute un robot proche du bord, il est inclut dans le polygone de la table

Voici mon algo (en syntaxe Python):
Image

Le souci que j'ai, c'est que:
- Un robot prôhe d'un bord est considéré dans le polygon externe
- Lorsque je contourne un obstacle, j'utilise compute_contour qui calcule un chemin de contournement tant qu'il ya une collision avec ce même obstacle

D'où le cas où j'ai un point dans le coin en bas à droite dans ce cas:
Image
--
EPITA 2020
Président Evolutek<<

antoine_cvra
Posts: 455
Joined: Mon 27 Aug 2007, 18:05
Location: Suisse

Re: 2019 - Robotech Legends

Post by antoine_cvra » Thu 17 Oct 2019, 15:26

Pour info, quelques liens sur comment notre implémentation (pompée de Aversive) fonctionne:
++
Antoine

Riako
Posts: 89
Joined: Tue 05 May 2015, 18:07

Re: 2019 - Robotech Legends

Post by Riako » Thu 17 Oct 2019, 15:39

kmikaz wrote:
Wed 16 Oct 2019, 15:34
Je ferais un post sur nos robots d'ici-là pour tout vous expliquer.
Oh oui 8)
kmikaz wrote:
Wed 16 Oct 2019, 15:34
e
- Lorsque je contourne un obstacle, j'utilise compute_contour qui calcule un chemin de contournement tant qu'il ya une collision avec ce même obstacle
Corriges-moi si je me trompe : tu suis le bord (tu retiens le point adjacent) s'il y a toujours une collision avec le même objet, or cette méthode ne fonctionne pas avec les formes concaves. Il faudrait plutôt s'intéresser aux extrémités des segments que tu coupes pour trouver ta solution.
antoine_cvra wrote:
Thu 17 Oct 2019, 15:26
Pour info, quelques liens sur comment notre implémentation (pompée de Aversive) fonctionne:
Merci pour le partage, on y jettera un coup d’œil :wink:

User avatar
Marmothon
Posts: 22
Joined: Mon 12 Jan 2009, 17:30
Contact:

Re: 2019 - Robotech Legends

Post by Marmothon » Fri 08 Nov 2019, 11:37

Plop,

Quelques précisions : l'algo que l'on utilisait jusqu'a 2018 était un Lee bien basique, avec beaucoup de filtrage improvisé, si bien que les trajectoires issues du calcul pouvaient être bien lisses avec peu de points de passage (en rouge et bleu le Béziers qui sont directement suivis par le robot, chaque transition est une nouvelle courbe, donc seulement quatre courbes dans cet exemple) :
Sans titre.png
Sans titre.png (944.67 KiB) Viewed 332 times
L'inconvénient étant le temps de calcul long ( plusieurs dizaines de ms sur une stm32f7 ) et une utilisation de RAM importante. Mais ça marchait plutôt très bien !

Pour la solution si le robot est situé dans un obstacle, on a imaginé ça :
Capture.PNG
Capture.PNG (16.69 KiB) Viewed 332 times
L'obstacle se fait croquer, ce qui permet de générer une trajectoire qui commence par s’éloigner de l'obstacle, sans réduire la distance d'évitement ... à noter l'absence de lissage, qui faisait trembloter le robot.

Le polygone rouge est le bord de la table ( fusionné avec les obstacles qui touchent) et en violet les autres obstacles. Il n'y a pas de contournement, la solution globale est recalculé de zéro avec tout ce que le robot connait au moment du calcul.

Post Reply