Le 08/11/2023 par lmoalic :
Contexte
Les splines sont des fonctions mathématiques utilisées pour représenter des courbes. Elles servent par exemple à définir les polices de caractères PostScript ou à modéliser les trajectoires des véhicules autonomes [1]. Dans différentes applications on est amené à résoudre le problème suivant : étant donné une suite de points dans le plan ou dans l'espace, trouver une courbe spline qui passe « le mieux possible » par ces points. Une telle courbe est appelée une spline d'approximation.
De nombreux algorithmes ont été développés pour déterminer des splines d'approximation. Certains utilisent des méthodes d'optimisation déterministe [3], d'autres mettent en oeuvre des métaheuristiques [2].
Objectifs
Le premier objectif de ce stage est de faire une étude bibliographique comparative des différentes techniques récemment mises en oeuvre pour déterminer les splines d'interpolation. On pourra, en particulier, s'appuyer sur l'article [4] et sur les références qu'il contient.
Le deuxième objectif du stage est d'implémenter l'un des algorithmes d'optimisation déterministe puis de mettre en oeuvre des métaheuristiques afin d'améliorer les splines trouvées par cet algorithme.
Profil du candidat
Bac +5 avec de très bonnes compétences en algorithmique et en programmation. Des connaissances en C++, en géométrie algorithmique et/ou en optimisation combinatoire sont un plus.
Poursuite en thèse
Le stage est susceptible de donner lieu à une poursuite en thèse sur la généralisation des résultats obtenus à la construction de surfaces splines en 3D.
Durée et lieu du stage
Stage de 5 à 6 mois entre janvier et juillet 2024.
Équipe OMeGA, Institut IRIMAS, Université de Haute-Alsace, 12 rue des Frères Lumière, Mulhouse.
Renseignements et candidature
Dominique Schmitt (Dominique.Schmitt@uha.fr)
Laurent Moalic (Laurent.Moalic@uha.fr)
[1] R. Walambe, N. Agarwal, S. Kale, V. Joshi, Optimal trajectory generation for car-type mobile robot using spline interpolation, IFAC-PapersOnLine, 49 (1) (2016), pp. 601-606.
[2] O. Valenzuela, B. Delgado-Marquez, M. Pasadas, Evolutionary computation for optimal knots allocation in smoothing splines, Appl Math Model, 37 (8) (2013), pp. 5851-5863.
[3] E. Aguilar, H. Elizalde, D. Cárdenas, O. Probst, P. Marzocca, R.A. Ramirez-Mendoza, An adaptive curvature-guided approach for the knot-placement problem in fitted splines, Journal Comput Inf Sci Eng, 18 (2018).
[4] R. Yeh, Y.S.G. Nashed, T. Peterka, X. Tricoche, Fast Automatic Knot Placement Method for Accurate B-spline Curve Fitting, Computer-Aided Design, Volume 128 (2020).
