Un seul algorithme peut aider les robots à prendre de bonnes décisions en temps réel

En 2018, le programme AlphaZero de Google DeepMind a appris les jeux d'échecs, de shogi et de Go en utilisant l'apprentissage automatique et un algorithme spécial pour déterminer les meilleurs mouvements pour gagner une partie dans une grille définie. Aujourd’hui, une équipe de chercheurs de Caltech a développé un algorithme analogue pour les robots autonomes : un système de contrôle de planification et de prise de décision qui aide les robots en mouvement libre à déterminer les meilleurs mouvements à effectuer lorsqu’ils naviguent dans le monde réel.

« Notre algorithme élabore une stratégie, puis explore tous les mouvements possibles et importants et choisit le meilleur grâce à une simulation dynamique, comme jouer à de nombreux jeux simulés impliquant des robots en mouvement », explique Soon-Jo Chung, professeur Bren de contrôle et de systèmes dynamiques à Caltech et professeur senior. chercheur au JPL, que Caltech gère pour la NASA. « L'innovation révolutionnaire ici est que nous avons développé un moyen très efficace de trouver ce mouvement sûr optimal que les méthodes classiques basées sur l'optimisation ne trouveraient jamais. »

L'équipe décrit la technique, qu'elle appelle Spectral Expansion Tree Search (SETS), dans l'article de couverture de la revue de décembre. Robotique scientifique.

De nombreux robots peuvent se déplacer librement et dans n’importe quelle direction. Prenons par exemple un robot humanoïde conçu pour assister une personne âgée dans un foyer. Un tel robot devrait être capable de se déplacer de différentes manières et, essentiellement, dans n'importe quelle direction dans l'espace lorsqu'il rencontre des obstacles ou des événements inattendus lors de l'accomplissement de ses tâches. L'ensemble des mouvements, des obstacles et des défis de ce robot sera très différent de celui d'une voiture autonome, par exemple.

Comment, alors, un seul algorithme peut-il guider différents systèmes robotiques pour prendre les meilleures décisions pour se déplacer dans leur environnement ?

« Vous ne voulez pas qu'un concepteur doive créer ces mouvements à la main et dire: 'C'est l'ensemble discret de mouvements que le robot devrait être capable d'effectuer' », explique John Lathrop, étudiant diplômé en contrôle et systèmes dynamiques. à Caltech et co-auteur principal du nouvel article. « Pour surmonter ce problème, nous avons créé SETS. »

SETS utilise la théorie du contrôle et l'algèbre linéaire pour trouver des mouvements naturels qui utilisent au maximum les capacités d'une plate-forme robotique dans un environnement physique.

Le concept de base sous-jacent est basé sur un Monte Carlo Tree Search, un algorithme de prise de décision également utilisé par AlphaZero de Google. Ici, Monte Carlo signifie essentiellement quelque chose de aléatoire, et la recherche arborescente fait référence à la navigation dans une structure de branchement qui représente les relations entre les données dans un système. Dans un tel arbre, une racine se ramifie vers des nœuds enfants reliés par des arêtes.

En utilisant Monte Carlo Tree Search pour un jeu comme Go, les mouvements possibles sont représentés sous forme de nouveaux nœuds et l'arbre s'agrandit à mesure que des échantillons plus aléatoires de trajectoires possibles sont tentés. L'algorithme joue les mouvements possibles pour voir les résultats finaux des différents nœuds, puis sélectionne celui qui offre le meilleur résultat sur la base d'une évaluation ponctuelle.

Le problème, explique Lathrop, est que lorsque l'on utilise cette structure arborescente ramifiée pour des systèmes dynamiques continus tels que des robots opérant dans le monde physique, le nombre total de trajectoires dans l'arbre augmente de façon exponentielle. « Pour certains problèmes, essayer de simuler toutes les possibilités et ensuite déterminer laquelle est la meilleure prendrait des années, voire des centaines d'années », dit-il.

Pour y remédier, SETS profite d’un compromis exploration/exploitation. « Nous voulons essayer de simuler des trajectoires que nous n'avons jamais étudiées auparavant : c'est ça l'exploration », explique Lathrop. « Et nous voulons continuer à rechercher des voies qui ont déjà donné lieu à de grandes récompenses : c'est l'exploitation. En équilibrant l'exploration et l'exploitation, l'algorithme est capable de converger rapidement vers la solution optimale parmi toutes les trajectoires possibles. »

Par exemple, si un robot commence par calculer quelques actions possibles qui, selon lui, l’entraîneraient à s’écraser contre un mur, il n’a pas besoin d’enquêter sur les autres nœuds de cette branche de l’arbre.

« Ce compromis exploration/exploitation et cette recherche sur les mouvements naturels du robot permettent à nos robots de penser, de se déplacer et de s'adapter à de nouvelles informations en temps réel », explique Benjamin Rivière, chercheur postdoctoral associé en génie mécanique et civil à Caltech and co. -auteur principal de l'article.

SETS peut exécuter une recherche arborescente complète en un dixième de seconde environ. Pendant ce temps, il peut simuler des milliers, voire des dizaines de milliers de trajectoires possibles, sélectionner la meilleure, puis agir. La boucle se poursuit encore et encore, donnant au système robotique la capacité de prendre de nombreuses décisions chaque seconde.

Une caractéristique clé de l’algorithme SETS est qu’il peut être appliqué à pratiquement n’importe quelle plate-forme robotique. Les fonctionnalités et capacités ne doivent pas nécessairement être programmées individuellement. Dans le nouvel article, Chung et ses collègues démontrent l'utilité de l'algorithme dans trois contextes expérimentaux complètement différents, ce qui est très rare dans les articles sur la robotique.

Dans le premier, un drone quadrirotor était capable d'observer quatre boules blanches en vol stationnaire tout en évitant quatre boules orange, tout en naviguant sur un aérodrome truffé de courants d'air ou de thermiques dangereux et aléatoires. L'expérience du drone a été menée au Center for Autonomous Systems and Technologies (CAST) de Caltech.

Dans le second cas, l’algorithme a permis au conducteur humain d’un véhicule terrestre à chenilles de naviguer sur une piste étroite et sinueuse sans heurter les barrières latérales. Et dans la configuration finale, SETS a aidé deux vaisseaux spatiaux captifs à capturer et à rediriger un troisième agent, qui pourrait représenter un autre vaisseau spatial, un astéroïde ou un autre objet.

Une équipe d'étudiants et de chercheurs de Caltech applique actuellement une version de l'algorithme SETS à une voiture Indy qui participera à l'Indy Autonomous Challenge au Consumer Electronics Show (CES) à Las Vegas le 9 janvier.