Goal Reaching with Eikonal-Constrained Hierarchical Quasimetric Reinforcement Learning

Cet article propose Eik-HiQRL, une méthode d'apprentissage par renforcement hiérarchique qui reformule l'apprentissage quasimétrique à l'aide de l'équation aux dérivées partielles d'Eikonal pour obtenir une généralisation hors distribution supérieure et des performances de pointe dans les tâches de navigation et de manipulation.

L'essentiel

🎯 Le Grand Défi : Apprendre à un robot sans lui donner de manuel

Imaginez que vous voulez apprendre à un robot à aller chercher un objet dans une maison remplie d'obstacles.

• L'ancienne méthode (RL classique) : Vous devez lui dire exactement quoi faire à chaque seconde : "Avance de 1 cm", "Tourne à gauche", "Évite cette chaise". C'est comme essayer d'apprendre à un enfant à marcher en lui donnant des ordres précis pour chaque muscle. C'est long, fastidieux, et si vous ratez un détail, le robot ne comprend rien.
• La méthode de ce papier (GCRL) : Vous dites simplement : "Va chercher la tasse". Le robot doit découvrir lui-même le chemin. C'est plus flexible, mais c'est comme si vous laissiez un enfant seul dans un labyrinthe géant sans boussole : il risque de tourner en rond pendant des heures.

📏 La Révolution : Le "Quasimétrique" (La règle de la distance)

Les chercheurs ont réalisé quelque chose d'intelligent : pour atteindre un but, le robot a besoin de connaître la distance. Pas seulement la distance en ligne droite (comme un oiseau), mais la distance réelle en évitant les murs.
En mathématiques, cela s'appelle une quasimétrique. C'est comme une règle magique qui dit : "La distance de A à B plus la distance de B à C doit toujours être supérieure ou égale à la distance directe de A à C".

L'algorithme précédent (QRL) utilisait cette règle, mais il apprenait en regardant des trajets précis (comme un film). Il regardait : "Ah, le robot est passé de la porte à la cuisine, donc je note que c'est proche".

• Le problème : Si le robot n'a jamais vu un coin de la maison dans ses données d'entraînement, il est perdu. Il ne peut pas "imaginer" le chemin.

🌊 La Nouvelle Idée : L'Équation de l'Eikonal (Le son qui voyage)

C'est ici que les auteurs introduisent leur grande innovation : Eik-QRL.

Imaginez que vous lancez une pierre dans un étang calme. Les vagues se propagent de manière fluide et continue dans toutes les directions.

• L'ancienne méthode (QRL) regardait des photos de l'eau à des moments précis (discret).
• La nouvelle méthode (Eik-QRL) utilise une équation mathématique appelée l'équation d'Eikonal. C'est l'équation qui décrit comment une onde de son ou une vague se propage dans l'espace.

L'analogie du feu de forêt :
Imaginez que le but est un feu de forêt. L'équation d'Eikonal permet de calculer exactement à quelle heure le feu va atteindre n'importe quel point de la forêt, en tenant compte des arbres (obstacles).

• Au lieu de regarder des pas de danse précis (trajectoires), l'algorithme "sent" la forme du terrain.
• Avantage majeur : Il n'a plus besoin de voir le robot bouger d'un point A à un point B. Il a juste besoin de connaître la position du robot et la position du but. Il peut "deviner" le chemin optimal partout, même dans des zones qu'il n'a jamais visitées. C'est comme avoir une carte complète de la maison au lieu d'un simple carnet de notes.

🏗️ Le Problème et la Solution Hiérarchique (Le Chef et l'Exécutant)

Mais il y a un hic. Cette équation magique fonctionne parfaitement dans un monde lisse et simple (comme un robot qui glisse sur de la glace). Mais dans la vraie vie (un robot qui attrape des objets, qui heurte des murs, qui change de mode), les choses deviennent "rugueuses" et imprévisibles. L'équation s'embrouille.

La solution : Eik-HiQRL (La Hiérarchie)
Pour résoudre ce problème, les auteurs ont créé une équipe de deux :

1. Le Chef (Niveau Élevé) : Il utilise la magie de l'équation d'Eikonal. Il ne regarde pas les détails. Il dit : "Pour aller de la cuisine au salon, je dois passer par le couloir". Il découpe le gros problème en petits sous-problèmes (des sous-buts).
2. L'Exécutant (Niveau Bas) : C'est un robot plus simple qui se concentre uniquement sur le petit objectif immédiat donné par le Chef. "Ok, je dois juste aller jusqu'à la porte du couloir".

Pourquoi ça marche ?
C'est comme si vous vouliez traverser l'Europe à pied.

• Le Chef regarde la carte et trace la route générale (Paris -> Lyon -> Marseille).
• L'Exécutant ne s'inquiète que de ne pas trébucher sur le prochain pavé.
  En combinant la vision globale (l'équation d'Eikonal) avec la gestion des détails (le niveau bas), le robot devient beaucoup plus fort et ne se perd plus, même dans des environnements complexes.

🏆 Les Résultats : Gagnant du Tournoi

Les chercheurs ont testé leur méthode sur des robots virtuels dans des labyrinthes géants et des tâches de manipulation (comme empiler des cubes).

• Résultat : Leur méthode (Eik-HiQRL) bat tous les autres robots existants.
• Particularité : Elle est particulièrement excellente dans les grands labyrinthes où il faut "relier" des morceaux de chemin que le robot n'a jamais vus ensemble (ce qu'on appelle le "stitching").

🚀 En Résumé

Ce papier propose une nouvelle façon d'enseigner aux robots comment se déplacer :

1. Arrêter de leur montrer des vidéos de trajets précis.
2. Utiliser une équation mathématique (comme celle des vagues) pour comprendre la géométrie de l'espace de manière fluide.
3. Ajouter un "chef" qui découpe les gros problèmes en petits morceaux pour que l'équation fonctionne même dans des environnements difficiles.

C'est un pas de géant vers des robots capables de s'adapter à n'importe quelle maison, usine ou route, sans avoir besoin d'un manuel d'instructions pour chaque situation possible.

Résumé technique

1. Problématique et Contexte

Le Renforcement Learning Conditionné par un Objectif (GCRL) vise à résoudre des tâches en apprenant des politiques capables d'atteindre des objectifs arbitraires, évitant ainsi la difficulté de concevoir des fonctions de récompense manuelles. Une propriété géométrique fondamentale a été identifiée : la fonction de valeur optimale conditionnée par l'objectif, $V^*(s, g)$, correspond à la longueur du chemin le plus court entre un état $s$ et un objectif $g$. Cela définit naturellement une quasimétrique.

L'algorithme existant, Quasimetric RL (QRL), exploite cette propriété en contraignant l'apprentissage de la valeur à des mappings quasimétriques, en imposant une cohérence locale via des contraintes basées sur des trajectoires discrètes. Cependant, cette approche présente deux limites majeures :

1. Elle dépend de paires de transitions $(s, s')$ issues de trajectoires, ce qui limite la couverture de l'espace d'états et la généralisation hors distribution (OOD).
2. L'apprentissage de quasimétriques dans des espaces d'états de haute dimension ou avec des dynamiques complexes (non-lisses, discontinues) est instable et difficile.

2. Méthodologie Proposée

Les auteurs proposent une reformulation continue de QRL basée sur les Équations aux Dérivées Partielles (EDP), spécifiquement l'équation Eikonal.

A. Eikonal-Constrained Quasimetric RL (Eik-QRL)

Au lieu d'imposer des contraintes de cohérence locale sur des transitions discrètes, Eik-QRL reformule le problème dans un cadre continu en temps.

• Formulation EDP : En supposant des dynamiques isotropes à vitesse unitaire ($\dot{s} = a$ avec $\|a\| \le 1$), l'équation de Hamilton-Jacobi-Bellman (HJB) se simplifie en l'équation Eikonal : $\|\nabla_s d(s, g)\| = 1$.
• Contrainte Locale : La contrainte de cohérence locale devient une régularisation sur le gradient de la fonction de valeur apprise : $\|\nabla_s d_\theta(s, g)\| \approx 1$.
• Avantages Clés :
  • Sans trajectoire (Trajectory-free) : L'algorithme n'a besoin que d'échantillons i.i.d. d'états et d'objectifs $(s, g)$, et non de paires de transitions $(s, s')$. Cela permet d'échantillonner directement dans l'espace d'états libre (ex: cartes d'occupation).
  • Régularisation implicite : L'EDP agit comme un régularisateur fort, améliorant la stabilité de l'apprentissage et la précision de l'estimation hors distribution.
  • Théorie : Les auteurs fournissent des garanties théoriques montrant que, sous des hypothèses de régularité (dynamiques lipschitziennes, valeur optimale 1-lipschitzienne), Eik-QRL permet une récupération approximative de la valeur optimale.

B. Limites et Solution Hiérarchique : Eik-HiQRL

Les hypothèses de régularité (notamment la continuité lipschitzienne des dynamiques et de la valeur) ne tiennent pas toujours dans des environnements complexes (ex: robots avec contacts, changements de modes discrets). Pour pallier cela, les auteurs introduisent Eik-HiQRL (Eikonal-Constrained Hierarchical QRL).

• Architecture Hiérarchique :
  • Niveau Élevé (High-level) : Opère dans un espace abstrait de basse dimension (ex: coordonnées de l'agent). Il utilise un modèle de quasimétrique contraint par l'équation Eikonal pour générer des sous-objectifs. Cela permet de bénéficier de la régularisation PDE dans un espace où les hypothèses sont plus probables.
  • Niveau Bas (Low-level) : Utilise une fonction de valeur standard (basée sur la récurrence Temporal-Difference) et un réseau de représentation d'objectifs pour atteindre les sous-objectifs générés.
• Synergie : Cette structure atténue le problème du rapport signal/bruit dans les tâches à long horizon et contourne les limitations de régularité des dynamiques complexes en décomposant le problème.

3. Contributions Principales

1. Nouvelle Formulation PDE : Introduction d'Eik-QRL, une reformulation continue de QRL utilisant l'équation Eikonal pour imposer des contraintes locales sans dépendre des trajectoires.
2. Algorithme Hiérarchique (Eik-HiQRL) : Conception d'une architecture hiérarchique qui combine les avantages de la régularisation PDE (au niveau élevé) avec la flexibilité des méthodes TD (au niveau bas), permettant de traiter des tâches complexes et à long horizon.
3. Garanties Théoriques : Preuve de la récupération approximative de la valeur optimale sous des conditions de régularité spécifiques, et analyse des limites de ces conditions.
4. Évaluation Expérimentale Rigoureuse : Évaluation sur des benchmarks de navigation (OGbench) et de manipulation, incluant une analyse des collisions et de la généralisation hors distribution.

4. Résultats Expérimentaux

Les expériences ont été menées principalement en mode Offline GCRL sur la suite de benchmarks OGbench (PointMaze, AntMaze, HumanoidMaze, AntSoccer, Manipulation).

• Navigation (PointMaze & AntMaze) :

  • Eik-HiQRL atteint des performances de l'état de l'art (SOTA), surpassant significativement les méthodes de base (HIQL, CRL, QRL standard) sur les environnements à long horizon (Giant, Stitch).
  • Dans les environnements "Stitch" (nécessitant de relier des segments de trajectoires), la régularisation PDE permet une meilleure généralisation et une réduction drastique des taux de collision par rapport aux méthodes purement basées sur des trajectoires.
  • Eik-QRL (sans hiérarchie) fonctionne bien dans les environnements isotropes (PointMaze) mais échoue partiellement dans les environnements complexes (AntMaze Giant), confirmant la nécessité de l'approche hiérarchique.

• Manipulation et Environnements Non-Réguliers (AntSoccer, Cube, Scene) :

  • Dans ces tâches où les dynamiques sont discontinues (contacts, objets externes), les hypothèses de régularité de l'équation Eikonal sont violées.
  • Eik-HiQRL reste compétitif par rapport aux bases, bien que les gains soient moins marqués que dans la navigation pure. Cela souligne que la méthode est robuste mais que l'application directe de contraintes Eikonal dans des espaces de haute dimension avec des discontinuités introduit un biais.

• Généralisation Hors Distribution :

  • La nature "sans trajectoire" d'Eik-QRL permet une meilleure couverture de l'espace d'états, conduisant à des politiques plus sûres (moins de collisions) et plus généralisables.

5. Signification et Impact

Ce travail établit un pont important entre l'apprentissage par renforcement et les méthodes basées sur les équations aux dérivées partielles (via les Physics-Informed Neural Networks - PINNs).

• Changement de paradigme : Il démontre que l'apprentissage de valeurs pour la navigation peut se faire sans données de trajectoires complètes, en exploitant uniquement la géométrie de l'espace d'états et des objectifs.
• Robustesse : L'approche hiérarchique proposée offre une voie pratique pour appliquer des contraintes théoriques fortes (comme l'équation Eikonal) à des problèmes réels complexes où les hypothèses de régularité ne sont pas strictement satisfaites.
• Futur : L'article ouvre la voie à la conception de représentations d'états (embeddings) spécifiques qui satisferaient les conditions de régularité nécessaires pour les algorithmes basés sur les EDP, comblant ainsi l'écart entre les garanties théoriques et le déploiement dans des environnements réels.

En résumé, Eik-HiQRL représente une avancée significative pour le GCRL offline, offrant une meilleure généralisation, une sécurité accrue (réduction des collisions) et des performances de pointe sur des tâches de navigation complexes, tout en identifiant clairement les limites de l'application directe de contraintes Eikonal dans des dynamiques hybrides.