Robotique : un nouvel algorithme pour accélérer les temps de calcul

Un nouvel outil de calcul pour la communauté de l'informatique théorique

Faire mieux avec moins : ce principe de l'optimisation est appliqué avec brio par Guillaume Moroz, chercheur membre de l'équipe GAMBLE, commune à Inria et au Loria, dans un article qu'il s'apprête à présenter entre le 7 et le 10 février à l'occasion du symposium FOCS (Foundations of Computer Science). Parrainée par l'IEEE Computer Society, cette conférence transdisciplinaire est l'une des plus importantes dans le domaine de l'informatique théorique. Elle réunit des spécialistes des algorithmes, des structures de données, des technologies de l'information…  « Pour être sélectionné à FOCS, les résultats doivent avoir des intérêts transverses et parler à plusieurs communautés scientifiques, détaille le chercheur. C'est bien le cas de mon article qui s'adresse autant aux experts du calcul formel qu'à ceux de la robotique ou de l'intelligence artificielle. » Guillaume Moroz propose en effet une nouvelle méthode pour résoudre l'un des problèmes fondamentaux de l'informatique théorique : l’évaluation numérique d’un polynôme, soit le calcul d'une suite d’additions et de multiplications. « Un papier retoqué quelques mois plus tôt à une autre conférence car jugé trop long et trop complexe », confie l'auteur qui ne regrette pas d'avoir suivi les recommandations du jury pour présenter une seconde version à FOCS. 

© Guillaume Moroz

Moins de 100 lignes de code pour résoudre un problème vieux de 50 ans

En 92 lignes de code écrites en langage Python, Guillaume Moroz formule « une nouvelle approche pour trouver plus rapidement les racines d'un polynôme dans un contexte numérique, résume-t-il. Les processeurs ne font que des additions, des soustractions et des multiplications, pas de fonctions plus complexes comme des sinus ou cosinus. Dès qu'on veut modéliser le monde réel, les polynômes sont impliqués. Même les études épidémiologiques peuvent s'appuyer sur des équations polynomiales. » Avec ses travaux, l'expert en calcul formel et géométrie algorithmique propose une méthode optimisée pour la robotique en particulier. Un domaine où les fonctions polynomiales sont omniprésentes et dans lequel sont effectués des calculs dits "approximatifs", qui acceptent une infime inexactitude afin de mieux prendre en compte des variations (distances d'un objet ou dilatation d'un matériau par exemple) pour ne pas entraver la bonne réalisation d'une opération. « Nous savons que les algorithmes rapides développés en 1972 pour évaluer un polynôme sont numériquement instables, avec des opérations approchées », rappelle le chercheur dont le code s'appuie tout de même sur la transformation de Fourier rapide (FFT), un célèbre algorithme de calcul datant de 1965, période à laquelle le mot "optimisation" fait son apparition dans le lexique informatique.

Un petit pas pour l'Homme, un grand pas pour les processeurs

Éviter les opérations redondantes pour faire moins de calcul : c'est en substance le principe clé de l'algorithme réalisé par Guillaume Moroz pour améliorer le temps de calcul des processeurs. « Mon code permet l'évaluation rapide d'un polynôme sur plusieurs points, sans sacrifier la précision. L'algorithme mutualise les opérations à chaque évaluation pour éviter de repartir de zéro. À un degré de 25 000 racines, il isole les racines des polynômes dix fois plus vite que les logiciels existants », affirme le chercheur, preuves à l'appui dans son article. Un travail salué notamment par Fredrik Johansson, chercheur de l'équipe LFANT à Inria Bordeaux :  « Cela conduit à un calcul massivement plus rapide des racines polynomiales. […] De plus, le code source est disponible (et il est vraiment simple) », a-t-il partagé sur Twitter :

Mon algorithme se parallélise très bien, confirme Guillaume Moroz. Il est raisonnablement simple à implémenter.

Un code en licence libre et contaminante

Publié sur HAL, le code de l'algorithme est à la disposition de tous. Une évidence pour son auteur : "Il est logique de partager avec le plus grand nombre des résultats de travaux financés par la recherche publique." Guillaume Moroz diffuse son code sous licence GNU GPL, libre et contaminante : « Si quelqu'un l'utilise, il doit respecter la même licence et rendre à son tour son logiciel libre. » Les intéressés n'ont pas tardé à se manifester. C'est notamment le cas d'un employé de Microsoft dans le cadre d'un projet d'implémentation de l'algorithme dans un processeur de carte graphique : « Je n'en sais pas plus sur la finalité mais mon code peut notamment contribuer au ray tracing, la représentation d'une image par des rayons lumineux », commente le chercheur.

Une implémentation imminente dans les logiciels de calcul scientifique

À ce jour, Guillaume Moroz collabore officiellement avec les équipes de Maplesoft, éditeur de Maple, un logiciel de calcul formel bien connu des chercheurs et ingénieurs en robotique et en théorie du contrôle : « Nous avons un contrat en cours pour intégrer ma méthode dans le logiciel à l'aide d'un prototype en langage C. Toutes les améliorations apportées seront la propriété d'Inria, toujours dans l'objectif d'améliorer un code qui a vocation à être public. » Le chercheur travaille aussi à l'intégration de son code dans Sage, « le pendant open source de Maple » et se réjouit de l'accueil réservé à son algorithme : « Il est assez rare que le délai entre une publication d'un article théorique et un transfert en entreprise soit aussi court. »