Bézier Curve

• Aussi appelé: Bezier curve
• Catégorie: Planning & manipulation › Trajectory optimisation
• Mots-clés: trajectory-optimization, splines, path-planning, geometry, motion-planning

Courbe polynomiale définie par des points de contrôle : elle commence au premier, se termine au dernier et est attirée vers ceux situés entre les deux ; très utilisée pour les chemins de robot, les trajectoires et les formes de tracés.

Définition

Une courbe de Bézier (Bézier curve) de degré n est une courbe polynomiale définie par n + 1 points de contrôle P₀ … Pₙ et un paramètre t qui varie de 0 à 1 : B(t) = Σ C(n, i) (1 − t)ⁿ⁻ⁱ tⁱ Pᵢ, où les poids sont les polynômes de la base de Bernstein. La courbe commence en P₀ et se termine en Pₙ, et sa tangente à chaque extrémité est dirigée selon le premier et le dernier côté du polygone de contrôle ; les points de contrôle intérieurs façonnent la courbe mais ne se trouvent généralement pas sur elle. Les courbes cubiques, à quatre points de contrôle, sont les plus courantes. La forme a été développée dans l'industrie automobile française dans les années 1960 par Pierre Bézier chez Renault et, indépendamment, par Paul de Casteljau chez Citroën.

Plusieurs propriétés rendent les courbes de Bézier commodes en robotique. La courbe entière se trouve dans l'enveloppe convexe de ses points de contrôle, de sorte que maintenir les points de contrôle dans une région convexe libre d'obstacles garantit que la courbe y reste aussi ; l'évitement de collision devient ainsi un ensemble de contraintes linéaires, comme dans l'optimisation de trajectoire sur des graphes d'ensembles convexes. La dérivée d'une courbe de Bézier est une autre courbe de Bézier de degré inférieur d'une unité, avec les points de contrôle n(Pᵢ₊₁ − Pᵢ), si bien que des bornes de vitesse et d'accélération peuvent aussi être imposées, de façon conservatrice, sur les points de contrôle. L'algorithme de de Casteljau évalue et subdivise les courbes de façon numériquement stable par interpolations linéaires répétées.

Il y a des limites à garder à l'esprit. Le paramètre t n'est ni le temps ni l'abscisse curviligne, donc une courbe utilisée comme trajectoire a encore besoin d'un paramétrage temporel, et des pas égaux en t ne donnent pas des distances égales le long de la courbe. Déplacer un point de contrôle modifie toute la courbe, c'est pourquoi les longs chemins sont généralement construits à partir de plusieurs segments de faible degré raccordés avec des conditions de continuité sur la position, la tangente et la courbure, ou représentés par des B-splines, qui offrent un contrôle local. Augmenter le degré pour épouser des formes complexes rend les courbes plus difficiles à façonner et moins bien conditionnées numériquement.

Pourquoi c'est important

Les courbes de Bézier offrent une représentation compacte, lisse et facile à contraindre des chemins et des trajectoires, des trajectoires de voitures et de drones jusqu'aux tracés d'outils et de pinceaux. Leurs propriétés d'enveloppe convexe et de dérivée transforment les limites de sécurité et de dynamique en contraintes simples sur une poignée de points, ce qui explique leur présence dans de nombreux planificateurs fondés sur l'optimisation.

Applications principales

• Génération de trajectoires lisses pour drones et robots mobiles
• Lissage de chemin après une planification par recherche dans un graphe ou par échantillonnage
• Chemins de changement de voie et de stationnement pour les véhicules autonomes
• Tracés d'outil, de pinceau et de stylo pour les robots de peinture, de dessin et de dépose
• Planification de mouvement avec des graphes d'ensembles convexes
• Trajectoires de jambe en phase de vol pour les robots à pattes

En pratique

Un planificateur de drone découpe un itinéraire à travers un entrepôt en une chaîne de régions convexes d'espace libre et attribue un segment de Bézier à chaque région. Il impose que les points de contrôle de chaque segment se trouvent dans sa région, relie les derniers points de contrôle d'un segment aux premiers du suivant pour que la position, la vitesse et l'accélération coïncident aux raccords, et borne les points de contrôle des courbes dérivées pour respecter les limites de vitesse et d'accélération. Comme toutes ces contraintes sont linéaires en les points de contrôle, le problème entier est un programme convexe qui se résout rapidement. Une dernière étape associe le paramètre t de chaque segment au temps avec une durée choisie ; raccourcir la durée augmente proportionnellement chaque vitesse et accélération que le drone doit atteindre.

Idées reçues

• Une courbe de Bézier passe par tous ses points de contrôle — seuls le premier et le dernier sont sur la courbe ; les points intérieurs l'attirent sans être touchés
• Le paramètre t est le temps — t est un paramètre de forme entre 0 et 1 ; une mise à l'échelle temporelle séparée fixe les vitesses et les accélérations
• Un degré plus élevé est toujours préférable pour des chemins complexes — les courbes de degré élevé perdent le contrôle local ; des chaînes de segments de faible degré ou des B-splines sont généralement préférables
• Borner les points de contrôle donne des limites de vitesse exactes — des bornes sur les points de contrôle de la dérivée sont suffisantes mais conservatrices, de sorte que le pic réel est généralement inférieur à la borne

Qui devrait le savoir

• Ingénieurs en planification de mouvement et de trajectoire
• Développeurs de véhicules autonomes et de drones
• Programmeurs de robots pour la peinture, le soudage et la dépose
• Ingénieurs en locomotion à pattes qui conçoivent des trajectoires de jambe en phase de vol

Technologies associées

• B-Splines
• Algorithme de de Casteljau
• Polynômes de Bernstein (Bernstein Polynomials)
• NURBS
• Paramétrage temporel optimal de chemin (Time-Optimal Path Parameterization)
• Optimisation convexe (Convex Optimization)

Termes associés

• Trajectory Planning
• Minimum-Snap Trajectory
• Graph of Convex Sets
• Motion Primitive
• Elastic band

Projets associés

• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms

Vidéos

• The Beauty of Bézier Curves: Freya Holmér