SETS, l’algorithme de Caltech qui accélère les décisions des robots

Pour un robot mobile, prendre une décision ne consiste pas seulement à choisir entre avancer ou tourner. Il faut aussi estimer ce qui se produira quelques instants plus tard, anticiper un obstacle, tenir compte d’un environnement qui change et agir assez vite pour que le calcul reste utile. C’est précisément le problème auquel s’attaque Spectral Expansion Tree Search, ou SETS, un algorithme développé à Caltech pour améliorer la planification de mouvements en temps réel.

L’ambition est concrète : permettre à une même méthode de décision d’aider des robots très différents à sélectionner des actions sûres et efficaces. Les essais décrits par les chercheurs concernent aussi bien un drone évoluant parmi des obstacles et des courants d’air qu’un véhicule terrestre sur un tracé sinueux, ou encore des engins spatiaux chargés de manipuler des objets. Les détails techniques ont été publiés dans la revue Science Robotics.

Pourquoi décider vite est un défi majeur pour un robot

Un robot autonome ne peut pas se contenter d’appliquer un itinéraire fixe. Dans le monde réel, un obstacle peut apparaître, un courant d’air peut dévier un drone et les conséquences d’un mouvement dépendent de la vitesse, de l’inertie ou de l’adhérence. La machine doit donc évaluer plusieurs suites d’actions possibles avant de choisir la suivante.

Cette opération est souvent représentée sous la forme d’un arbre de décision. À partir de la situation présente, chaque branche correspond à une action envisageable. Si le robot avance, tourne, freine ou accélère, chacune de ces possibilités ouvre à son tour de nouvelles options. Plus l’algorithme regarde loin dans le temps, plus le nombre de branches augmente rapidement.

C’est le dilemme classique de la robotique autonome : explorer un maximum de scénarios peut améliorer la qualité de la décision, mais demander trop de calculs risque d’arriver trop tard. À l’inverse, décider sans avoir assez envisagé d’alternatives expose le robot à une trajectoire inefficace ou dangereuse.

SETS cherche à résoudre ce compromis. Il s’appuie sur des simulations dynamiques des mouvements potentiels et repère les options qui offrent le meilleur équilibre entre sécurité et efficacité. Les simulations peuvent être comparées à une succession de parties jouées à l’avance : le système teste les conséquences plausibles d’une action plutôt que d’attendre de les découvrir une fois le mouvement engagé.

Comment fonctionne l’algorithme SETS

Le nom Spectral Expansion Tree Search désigne une méthode de recherche dans cet arbre de décisions. L’idée centrale est de ne pas traiter toutes les branches de la même façon. Certaines deviennent très tôt peu intéressantes, par exemple parce qu’elles conduisent à une collision ou à une impasse. Plutôt que de continuer à investir du temps de calcul dans ces directions, SETS concentre ses simulations sur les trajectoires qui paraissent les plus utiles.

Dans l’exemple le plus simple, si plusieurs simulations montrent qu’une direction mène à un mur, il serait peu pertinent d’examiner indéfiniment des variantes de cette même direction. Le robot doit réallouer ses ressources de calcul à d’autres itinéraires. Cette capacité est particulièrement importante lorsque la décision doit être renouvelée en continu, à mesure que le robot progresse et que son environnement évolue.

D’après les informations présentées avec l’étude, SETS peut effectuer une recherche complète dans un arbre de décision en environ un dixième de seconde. À cette échelle de temps, l’algorithme peut simuler des milliers de trajectoires et retenir rapidement une action adaptée à la situation.

Cette logique différencie SETS d’approches d’optimisation plus classiques, qui peuvent avoir davantage de difficultés à trouver vite des solutions à la fois performantes et sûres dans des situations complexes. Il ne s’agit pas de supprimer la complexité du problème, mais de mieux choisir où employer la puissance de calcul disponible.

Exploration et exploitation, le cœur du compromis

Dans le vocabulaire de l’intelligence artificielle, SETS organise un équilibre entre exploration et exploitation. L’exploitation consiste à approfondir les options qui semblent déjà donner de bons résultats. L’exploration consiste au contraire à garder une place pour des possibilités encore peu évaluées, qui pourraient s’avérer meilleures ou nécessaires face à un changement imprévu.

Un système qui n’exploiterait que la meilleure option connue risquerait de répéter un mauvais choix initial. À l’inverse, un système qui explorerait sans cesse de nouvelles voies pourrait ne jamais décider à temps. Pour des robots confrontés à des obstacles, au mouvement ou à l’incertitude, l’enjeu est donc d’arbitrer entre ces deux comportements au cours même de la planification.

Dans SETS, cette répartition du calcul aide notamment à éviter que le robot multiplie les simulations de trajectoires manifestement infructueuses. L’objectif n’est pas de garantir qu’un robot aura toujours une solution parfaite, mais de lui permettre de prendre une meilleure décision avec le temps de calcul dont il dispose.

Des essais sur un drone, un véhicule et des engins spatiaux

L’un des intérêts majeurs de ces travaux réside dans la diversité des plateformes utilisées lors des essais. Un drone, une voiture robotisée et un engin spatial n’obéissent pas aux mêmes contraintes physiques. Le premier évolue en trois dimensions et peut être affecté par les courants d’air. Le deuxième doit négocier un parcours au sol sans collision. Le troisième intervient dans un contexte de manipulation où les mouvements doivent être précisément contrôlés.

Ces démonstrations ne signifient pas qu’un seul programme résout instantanément tous les problèmes de la robotique. Chaque robot conserve ses capteurs, ses modèles physiques et ses contraintes opérationnelles. Elles montrent en revanche qu’une même approche de recherche et de sélection de trajectoires peut être appliquée à des catégories de machines éloignées les unes des autres.

Le professeur Soon-Jo Chung souligne que le système explore un grand nombre d’options afin de sélectionner le meilleur mouvement. Benjamin Rivière, co-auteur principal de l’étude, met pour sa part en avant le gain de performance permis par cette optimisation en temps réel. Les deux dimensions sont indissociables : la qualité de la planification compte, mais elle n’a de valeur pratique que si elle peut être produite avant que la situation ne change.

Ce que SETS change, et ce qu’il ne remplace pas

Une avancée en planification de mouvements ne transforme pas, à elle seule, un robot en machine totalement autonome. Pour appliquer une bonne trajectoire, il faut d’abord que le robot perçoive correctement son environnement. Une caméra, un lidar, un radar ou d’autres capteurs doivent fournir une représentation suffisamment fiable des obstacles et de l’état du système. Il faut également que le robot puisse exécuter fidèlement la décision calculée.

SETS intervient à une étape spécifique, mais essentielle : celle qui relie les informations disponibles à une action. Il peut aider un robot à déterminer comment se déplacer compte tenu de ce qu’il sait de son environnement et de ses propres capacités physiques.

La méthode repose aussi sur la qualité des simulations qu’elle utilise. Une simulation peut évaluer des milliers de scénarios rapidement, mais elle reste une approximation du monde réel. Si les conditions réelles diffèrent fortement du modèle disponible, une trajectoire évaluée comme sûre peut ne plus l’être dans les mêmes proportions. C’est pourquoi les tests dans des environnements variés comptent autant que les résultats obtenus en simulation.

L’intérêt pratique d’une décision produite en un dixième de seconde est de pouvoir recommencer fréquemment le processus. Le robot peut alors tenir compte d’un obstacle nouveau, d’une déviation ou d’une évolution de sa position au lieu de suivre aveuglément une trajectoire calculée longtemps auparavant.

Une application prévue à l’Indy Autonomous Challenge

Au moment de la publication de ces travaux, le 5 décembre 2024, les chercheurs prévoyaient d’appliquer SETS à une voiture de course de l’Indy Autonomous Challenge en janvier 2025. Ce cadre est particulièrement exigeant pour une technologie de planification : à grande vitesse, la moindre décision tardive réduit la marge de sécurité, tandis que les trajectoires doivent rester précises et efficaces.

Cette perspective constitue une prochaine étape annoncée, non un résultat déjà établi à cette date. Elle doit permettre de confronter l’algorithme à un cas d’usage où le délai de calcul, la dynamique du véhicule et le suivi de trajectoire sont particulièrement déterminants.

Au-delà de la compétition automobile, les cas d’usage évoqués par les essais donnent une idée des secteurs concernés : inspection par drone, mobilité autonome, manipulation robotisée ou opérations spatiales. Dans chacun de ces domaines, le besoin fondamental est similaire : un système doit choisir une action parmi un très grand nombre de possibilités sans disposer d’un temps illimité pour réfléchir.

Ce qu’il faut surveiller

La suite des travaux devra d’abord confirmer la robustesse de SETS hors des conditions expérimentales. Les environnements les plus difficiles ne sont pas seulement complexes, ils sont aussi imprévisibles : données de capteurs incomplètes, objets mobiles, météo changeante ou contraintes physiques mal anticipées. La capacité de l’algorithme à conserver de bonnes performances dans ces cas déterminera une part importante de son intérêt opérationnel.

Il faudra également observer le rapport entre le gain de décision et les ressources de calcul nécessaires. L’algorithme est conçu pour éviter d’examiner inutilement des trajectoires peu prometteuses, mais les environnements très riches peuvent faire exploser le nombre de mouvements théoriquement possibles. La limite pratique dépendra donc de la plateforme, de ses capteurs et de la puissance embarquée.

Enfin, l’application annoncée à l’Indy Autonomous Challenge en janvier 2025 sera un indicateur à suivre. Elle illustrera la manière dont une recherche publiée dans Science Robotics peut être transposée à un véhicule autonome confronté à des contraintes de vitesse et de précision. Si cette approche tient ses promesses dans des situations variées, SETS pourrait devenir un outil utile pour rapprocher les capacités de calcul des robots des exigences du monde réel.