Un pathfinding courbe : Kraken

L'endroit pour parler de logiciel, programmation et algorithme.
Place to discuss on software, programming and algorithms.
Post Reply
User avatar
PF
Posts: 22
Joined: Wed 19 Jul 2017, 16:15
Location: Toulouse
Contact:

Un pathfinding courbe : Kraken

Post by PF » Mon 02 Oct 2017, 13:20

Bonjour !

Je travaille depuis quelques années sur une librairie Java nommée Kraken. C'est un pathfinding qui donne des trajectoires courbes facilement suivables par un robot.

C'est quoi ?

Voici un exemple de trajectoire sur la table de l'année dernière (les traits perpendiculaire à la trajectoire symbolisent la courbure, c'est-à-dire à quel point ça tourne fort).

Image

Pourquoi ?

Les trajectoires courbes, par rapport aux plus classiques lignes brisées, ont deux avantages :
  • elles sont parcourues plus rapidement car il y a moins d'arrêts
  • elles sont élégantes
Je pense que l'utilisation la plus facile et contrôlable de Kraken est la planification de trajectoires en amont des matchs. Les trajectoires sont trouvées par Kraken puis hardcodées dans le robot. Exemples : la trajectoire d'un rush initial, des trajectoires pour slalomer entre les éléments de jeux, etc.

Il est aussi possible d'utiliser Kraken en match pour trouver des trajectoires à la volée. C'est que mon équipe a fait l'année dernière avec le rover lunaire : https://intechsenpai.github.io/moon-rover/, vous pouvez aussi voir la vidéo d'un match.

Comment ?

Kraken est hautement configurable, notamment :
  • la courbure maximale
  • le maximum de la dérivée de la courbure
  • un timeout sur la recherche
  • et plus…
Quelques features :
  • gère la vitesse du robot pour limiter l'accélération latérale
  • gère la marche avant et la marche arrière (la marche arrière peut être désactivée)
  • a un affichage graphique pour visualiser le trajet
Un asservissement en trajectoire courbe est exposée sur la page du projet. Prochainement, nous mettrons en ligne une implémentation C++.

Le dépôt contient aussi plusieurs codes d'exemple pour pouvoir tester rapidement Kraken; voici le premier exemple.

En résumé

La page du projet : https://github.com/PFGimenez/The-Kraken-Pathfinding

Merci de votre attention ! Que Kraken vous intéresse ou non, je lirai avec plaisir toutes vos remarques et commentaires. C'est un projet encore jeune qui pourra évoluer selon les besoins.

Robotiquement,
PF
INTech (2013-2015)
TechTheTroll (2016)
INTech Senpaï (2017-2018)

Prix de l'innovation 2017 :D
Un pathfinding courbe dont les trajectoires sont facilement suivables (librairie Java) : https://github.com/PFGimenez/The-Kraken-Pathfinding

User avatar
wix
PMI
Posts: 509
Joined: Sun 17 Sep 2006, 22:35

Re: Un pathfinding courbe : Kraken

Post by wix » Mon 02 Oct 2017, 20:41

Bravo pour ce beau travail !

Petit point important : les trajectoires courbes ont tendances à générer de la complexité pour la localisation (dérive latérale) et l'évitement. Rien d'insurmontable, mais l’élégance se paie, et pour avoir pratiqué, je dirai que ce n'est pas donné.
Qui fait le malin............... tombe dans le ravin
(Equipe Ard, suivez nous sur Twitter : )

User avatar
PF
Posts: 22
Joined: Wed 19 Jul 2017, 16:15
Location: Toulouse
Contact:

Re: Un pathfinding courbe : Kraken

Post by PF » Mon 02 Oct 2017, 21:30

Tu as raison wix, on perd en précision de localisation.

Pour donner un ordre de grandeur, sur notre robot à quatre roues, on perdait environ 0.5 cm de précision par mètre. C'est une dérive énorme, très majoritairement issue de nos roues codeuses très larges (environ 2cm !), mais en partie issue du suivi de trajectoire courbe. À noter que Kraken peut limiter la force latérale (en ralentissant lors des virages forts) ce qui limite la dérive.

Concernant la détection de l'ennemi, nous avons appris l'importance d'être bardé de capteurs, surtout les capteurs regardant dans les coins ; sinon on ne regarde pas là toujours où le robot va… Pour la procédure d'évitement elle-même, nous avions des résultats satisfaisant avec Kraken l'année dernière, même si ce ne fut pas utilisé en match (on restait sur notre demi-table).

Après, on peut régulièrement voir des équipes ponctuellement faire des trajectoires courbes (notamment RCVA, mais pas que) et réussir à garder/récupérer sa localisation avec des moyens autre que l'odométrie.
INTech (2013-2015)
TechTheTroll (2016)
INTech Senpaï (2017-2018)

Prix de l'innovation 2017 :D
Un pathfinding courbe dont les trajectoires sont facilement suivables (librairie Java) : https://github.com/PFGimenez/The-Kraken-Pathfinding

Post Reply