Learning When to Quit: Meta-Reasoning for Motion Planning

Auteurs: Yoonchang Sung, Leslie Pack Kaelbling, Tomás Lozano-Pérez · IROS 2021

Licences

• Accès libre
• Article: CC BY 4.0

Tout ce qui suit s'appuie sur l'article complet sous sa licence CC BY 4.0 ; sa figure est montrée en citant les auteurs.

En bref

Apprend, à partir d'exécutions passées, quand arrêter un planificateur de mouvement anytime (RRT, PRM, Lazy PRM*) afin de maximiser le compromis entre qualité du chemin et temps de planification.

Pourquoi c'est important

Tout robot qui planifie avec RRT ou PRM doit choisir un budget de temps de planification, et un temps fixe ou un seuil de qualité fixe gaspille soit du temps, soit de la qualité de chemin. La méthode enveloppe un planificateur anytime non modifié ; elle peut donc s'ajouter à des planificateurs existants de type OMPL, à condition de disposer de problèmes d'entraînement issus de la distribution d'environnements visée.

Problème

Les planificateurs de mouvement anytime raccourcissent un chemin à mesure qu'ils s'exécutent, mais il n'existe pas de relation bien caractérisée entre qualité de la solution et temps de calcul ; on ne sait donc pas quand cesser de planifier et commencer à bouger. Leurs profils de performance sont très peu lisses, car des chemins plus courts apparaissent par sauts soudains lorsque le planificateur trouve une nouvelle classe d'homotopie, ce qui exclut une simple extrapolation en ligne de la qualité future.

Solution proposée

Les auteurs apprennent une politique d'arrêt à partir des profils de performance de problèmes de planification passés tirés de la même distribution, en maximisant une utilité pondérée par l'utilisateur U(q, t) = wq − (1 − w)t. Une variante avec modèle apprend un processus de décision markovien sur la qualité et le temps discrétisés et le résout par itération sur les valeurs ; deux variantes sans modèle (un classifieur à propagation avant sur des caractéristiques conçues à la main et un modèle RNN séquence à séquence) imitent des décisions d'arrêt oracle calculées a posteriori. Un CNN prédit la longueur du chemin optimal à partir d'une image 2D de l'espace de travail afin que les profils de problèmes de difficultés différentes puissent être normalisés et comparés.

Idées clés

• Les instants d'arrêt optimaux peuvent être calculés a posteriori pour chaque exécution d'entraînement, ce qui transforme l'apprentissage de la politique en apprentissage par imitation supervisé plutôt qu'en apprentissage par renforcement.
• Normaliser la qualité du chemin nécessite la longueur optimale inconnue ; un CNN qui la prédit à partir d'une image 2D de l'espace de travail rend les profils comparables d'un problème à l'autre, et un mauvais normalisateur (une ligne droite du départ au but) réduit fortement l'utilité.
• Des caractéristiques d'historique plus riches (pente, planéité) rendent le modèle de transition avec modèle bien plus précis, mais son coût d'estimation passe de quelques secondes à plus d'une journée, un cas direct de malédiction de la dimension.
• Le RNN apprend ses propres caractéristiques temporelles à partir de la séquence brute d'utilité et a donné les bons résultats les plus fiables d'un planificateur et d'un poids d'utilité à l'autre.

Principaux résultats

• Précision du prédicteur CNN de longueur de chemin optimal sur 200 espaces de travail réservés au test : 88,21 %, 96,23 % et 94,25 % dans trois distributions d'environnements.
• Avec le normalisateur CNN, les utilités ont été de 0,58, 0,65 et 0,66 dans ces trois environnements, contre 0,63, 0,70 et 0,67 avec les longueurs optimales réelles et 0,39, 0,40 et 0,60 avec un normalisateur en ligne droite.
• La perte du modèle de transition sur les données réservées est passée de 1,84 (sans caractéristiques) à 0,22 avec (t, q) et 0,10 avec (t, q, pente), tandis que le temps d'estimation passait de 0,41 s à 10,64 s et 11 933,72 s.
• RRT* à w = 0,8 : utilité oracle 0,677, RNN 0,670, avec modèle 0,663, classifieur 0,658, contre 0,634 pour la référence à qualité fixe et 0,575 pour la référence à temps fixe.
• PRM* à w = 0,8 : oracle 0,718, avec modèle 0,702, RNN 0,698, classifieur 0,697, qualité fixe 0,674, temps fixe 0,662.
• À w = 0,2, la référence à qualité fixe est devenue négative (−0,283 pour RRT, −0,344 pour PRM, −0,367 pour Lazy PRM*), tandis que les méthodes apprises restaient positives.

Limites

• Le prédicteur CNN de solution optimale prend une image 2D de l'espace de travail, ce qui limite les méthodes aux problèmes à espace de travail plan ; une extension à la 3D par grilles de voxels ou nuages de points est suggérée mais non réalisée.
• Un nouveau problème est supposé provenir de la même distribution que les problèmes d'entraînement, et l'entraînement nécessite de nombreuses longues exécutions du planificateur sur des problèmes représentatifs.
• Ajouter des caractéristiques d'historique à la méthode avec modèle était infaisable en calcul pour les plus grandes expériences ; elle n'a donc utilisé que (q, q_prev, t).
• Toute l'évaluation se fait en simulation avec un robot rigide à trois degrés de liberté dans des espaces de travail 2D ; aucun robot physique n'a été testé.
• Seule une utilité linéaire U(q, t) = wq − (1 − w)t a été étudiée.

Impact sur le domaine

L'article a été finaliste du IROS 2021 Best Paper Award on Cognitive Robotics et compte 14 citations. Il ne mentionne pas de publication de code ou de données.

Résumé

Les planificateurs de mouvement anytime sont largement utilisés en robotique. Cependant, la relation entre la qualité de leur solution et le temps de calcul n'est pas bien comprise, et il est donc difficile de savoir quand cesser de planifier et commencer l'exécution. Dans cet article, nous traitons le problème de décider quand arrêter la délibération sous une capacité de calcul bornée, appelé méta-raisonnement, pour la planification de mouvement anytime. Nous proposons des méthodes d'apprentissage fondées sur les données, un méta-raisonnement avec modèle et un méta-raisonnement sans modèle, applicables à différentes distributions d'environnements et indépendantes du choix du planificateur de mouvement anytime. Dans le cadre de cette approche, nous concevons un prédicteur de solution optimale fondé sur un réseau de neurones convolutif, qui prédit la longueur du chemin optimal à partir d'une image 2D de l'espace de travail. Nous évaluons empiriquement les performances des méthodes proposées en simulation, en les comparant à des méthodes de référence.

Liens

• arXiv 2103.04374: https://arxiv.org/abs/2103.04374
• DOI 10.1109/IROS51168.2021.9636864: https://doi.org/10.1109/IROS51168.2021.9636864
• PDF: https://arxiv.org/pdf/2103.04374v1