Interleaving Scheduling and Motion Planning with Incremental Learning of Symbolic Space-Time Motion Abstractions

Cet article propose un cadre novateur qui intercale l'ordonnancement et la planification de mouvement dans une boucle d'apprentissage incrémental, permettant de générer des plans exécutables et sans collision pour la navigation multi-objets dans des espaces partagés en utilisant des retours symboliques pour guider l'ordonnancement vers des solutions réalisables.

L'essentiel

Imaginez que vous êtes le chef d'orchestre d'une équipe de robots dans un entrepôt géant. Votre mission ? Faire en sorte qu'ils livrent des colis, ouvrent des portes et évitent de se cogner, le tout en un temps record.

C'est là que se pose le problème traité par cette recherche : comment organiser le travail (le planning) et le mouvement physique (la trajectoire) en même temps ?

Voici une explication simple de leur solution, appelée SAMP, en utilisant des analogies du quotidien.

1. Le Problème : Le Chef d'Orchestre vs. Le Violoniste

Traditionnellement, on séparait les deux tâches :

• Le Planificateur (le Chef d'Orchestre) disait : "Toi, tu vas prendre le colis A à 10h00, et toi, tu prends le colis B à 10h05." Il ne se souciait pas de savoir si les robots pouvaient physiquement faire ça sans se percuter.
• Le Planificateur de Mouvement (le Violoniste) disait : "Ok, je vais calculer comment bouger les bras pour ne pas toucher les murs."

Le problème : Si le Chef d'Orchestre dit "Faites-le en même temps" mais que le Violoniste réalise que les deux robots vont se coincer dans un couloir étroit, tout le plan s'effondre. C'est comme si un chef d'orchestre demandait à deux violonistes de jouer la même note sur la même corde en même temps : ça ne marche pas physiquement.

2. La Solution : Une Conversation Continue (L'Apprentissage Progressif)

Les auteurs proposent une méthode où le Chef d'Orchestre et le Violoniste discutent en boucle au lieu de travailler séparément. C'est comme un jeu de "Oui, mais..." :

1. Le Chef propose un plan : "Ok, Robot A et Robot B partent ensemble à 10h00."
2. Le Violoniste vérifie : "Attends, si vous partez ensemble, vous allez vous bloquer dans le couloir !"
3. Le retour d'information (La Magie) : Au lieu de juste dire "Non", le Violoniste donne des indices précis au Chef :
   • Indice Géométrique : "Le Robot B ne peut pas atteindre la porte parce qu'un autre robot la bloque." -> Le Chef va donc changer l'ordre des tâches.
   • Indice Temporel : "Le Robot A peut passer, mais il faut qu'il attende 2 secondes de plus pour laisser le Robot B passer." -> Le Chef ajuste les horaires.
4. L'Apprentissage : Le Chef se souvient de ces erreurs. La prochaine fois, il ne proposera pas ce plan impossible. Il "apprend" des contraintes physiques sans avoir besoin de tout calculer dès le début.

3. L'Analogie du "Jeu de la Rue"

Imaginez que vous devez traverser une rue très fréquentée avec des amis, mais que vous ne pouvez pas parler pendant que vous marchez.

• L'ancienne méthode : Vous décidez tous de traverser en même temps (le planning), puis vous vous rendez compte que vous vous heurtez (échec du mouvement). Vous recommencez tout à zéro.
• La méthode SAMP : Vous décidez de traverser, mais vous avez un ami qui regarde la circulation. Dès qu'il voit un danger, il vous fait un signe (un "refinement").
  • "Attends 2 secondes !" (Ajustement temporel).
  • "Change de voie, il y a un trou là-bas !" (Ajustement géométrique).
  • Vous ajustez votre marche instantanément, sans avoir à tout annuler.

4. Pourquoi c'est génial ?

• Éviter les impasses : Le système détecte les "bouchons" avant qu'ils ne se produisent.
• Optimisation : Il permet aux robots de travailler en parallèle (en même temps) là où c'est possible, au lieu de les faire attendre inutilement. Les tests montrent que cela améliore l'efficacité de 41 % par rapport aux méthodes anciennes.
• Flexibilité : Le système fonctionne avec différents types de robots et de logiciels de planification, comme un adaptateur universel.

En résumé

Cette recherche a créé un système de collaboration intelligent entre celui qui décide quoi faire et celui qui décide comment le faire. Au lieu de travailler en silos, ils apprennent l'un de l'autre en temps réel, transformant un chaos potentiel de robots qui se cognent en une danse synchronisée et efficace.

C'est comme passer d'un chef d'orchestre qui crie des ordres à un chef qui écoute ses musiciens et ajuste la partition en direct pour que la symphonie soit parfaite.

Résumé technique

1. Problématique : Le Problème de Planification et d'Ordonnancement (SAMP)

Le papier aborde une limitation majeure des approches classiques de Planification de Tâches et de Mouvement (TAMP). Alors que le TAMP traditionnel se concentre sur la décision de quoi faire et comment l'exécuter (génération de tâches), de nombreux scénarios réels (comme les entrepôts automatisés) impliquent un ensemble de tâches prédéfinies. Le défi se déplace alors vers la décision de quand et dans quel ordre exécuter ces tâches de manière sûre et efficace, compte tenu des contraintes de ressources, de temps et de mouvement.

Les auteurs formalisent ce défi sous le nom de Scheduling and Motion Planning (SAMP) pour la navigation multi-objets dans un espace partagé.

• Défi principal : L'interdépendance stricte entre l'espace et le temps. Un plan d'ordonnancement (scheduling) peut être valide symboliquement mais impossible géométriquement (conflits spatiaux) ou temporellement (impossibilité de synchroniser les mouvements pour éviter les collisions dans des passages étroits).
• Complexité : Contrairement aux abstractions de chemin discret (MAPF), le SAMP nécessite de raisonner directement dans des espaces de configuration continus avec des contraintes cinodynamiques explicites (cinématique et dynamique des robots).

2. Méthodologie : Un Cadre d'Apprentissage Incrémental par Interleaving

Les auteurs proposent un cadre novateur qui entrelace (interleave) un ordonnanceur (scheduler) standard et un planificateur de mouvement (motion planner) standard dans une boucle d'apprentissage incrémental de abstractions symboliques du mouvement.

A. Architecture du Framework

Le système fonctionne selon une boucle itérative (Algorithme 1) :

1. Génération de candidats : L'ordonnanceur génère un calendrier candidat $\rho$ (séquence et timing des tâches) sans tenir compte des contraintes de mouvement détaillées.
2. Vérification de faisabilité : Le planificateur de mouvement (traité comme une boîte noire) évalue la faisabilité de ce calendrier en tenant compte de la cinématique et de la dynamique des objets.
3. Retour d'information symbolique (Refinements) :
   • Si le plan est faisable, des trajectoires valides sont renvoyées.
   • Si le plan échoue, le planificateur renvoie des réfinements symboliques pour guider l'ordonnanceur vers une solution valide :
     • Réfinements Géométriques : Identification de configurations inaccessibles ($\Sigma$) et d'obstacles bloquants ($\Omega$). Cela force l'ordonnanceur à modifier l'ordre des tâches ou à déplacer des obstacles avant d'atteindre une zone bloquée.
     • Réfinements Temporels : Ajustement des durées d'activité et des délais de démarrage ($\delta$) pour permettre une synchronisation sûre (ex: un robot doit attendre qu'un autre passe).

B. Stratégie de Décomposition (Layering)

Pour éviter l'explosion combinatoire, le framework décompose le problème en groupes de mouvements parallèles (ensembles d'activités qui peuvent interférer). Il utilise une architecture à deux couches :

• Couche 1 (Vérification d'activité unique) : Vérifie la faisabilité géométrique et temporelle de chaque activité individuellement. Cela permet de rejeter rapidement les plans impossibles sans lancer de calculs coûteux de groupe.
• Couche 2 (Vérification de groupe) : Planifie les trajectoires spatio-temporelles synchronisées pour les groupes d'activités parallèles (utilisant des algorithmes comme ST-RRT*).

C. Formalisation

Le problème est défini comme un tuple incluant des tâches obligatoires et optionnelles, des ressources, et des contraintes de fluents (états) ou de précédence. Le framework est flexible : il fonctionne aussi bien avec des solveurs basés sur des fluents (ex: Aries) que sans (ex: OR-Tools/CPSE), et s'adapte à divers planificateurs de mouvement.

3. Contributions Clés

1. Formalisation du problème SAMP : Définition rigoureuse du problème combinant ordonnancement optionnel et planification de mouvement dans un espace continu, avec gestion des conflits spatiaux et temporels.
2. Framework d'interleaving incrémental : Une méthode générique qui ne nécessite pas de "grounding" (instanciation complète) de toutes les contraintes à l'avance. Elle apprend progressivement les abstractions de mouvement (conflits, délais nécessaires) pour guider l'ordonnanceur.
3. Génération de contraintes symboliques : Mécanisme innovant pour transformer les échecs de planification géométrique/temporelle en contraintes logiques (préconditions sur les fluents ou contraintes de précédence) compréhensibles par l'ordonnanceur.
4. Architecture à deux couches : Une stratégie d'optimisation qui réduit considérablement le coût computationnel en filtrant les problèmes simples au niveau de l'activité unique avant de lancer des vérifications de groupe complexes.

4. Résultats Expérimentaux

Les auteurs ont évalué leur framework sur des benchmarks de logistique et d'atelier (Job-Shop Problem) augmentés de tâches de navigation, en utilisant des solveurs d'état de l'art (Aries, OR-Tools) et des planificateurs (RRT, ST-RRT*).

• Performance globale : Le framework réussit à générer des plans valides et synchronisés pour des scénarios complexes impliquant jusqu'à 3 robots et de multiples tâches optionnelles.
• Gain par parallélisation : Comparé à une approche séquentielle (sans parallélisation), le framework permet une réduction moyenne de 41% du makespan (temps total d'exécution) grâce à une synchronisation efficace des mouvements.
• Efficacité des réfinements :
  • La majorité du temps de calcul est consacrée à la planification de mouvement (jusqu'à 92%), ce qui justifie l'approche incrémentale.
  • L'architecture à deux couches est cruciale : désactiver la couche 1 réduit drastiquement le nombre de problèmes résolus (de 359 à 140 instances).
  • L'utilisation de fluents (états symboliques) améliore les performances, permettant de résoudre plus d'instances (87,7 instances en moyenne pour Aries avec fluents).
• Robustesse : Le système gère efficacement les contraintes spatiales complexes (portes fermées, couloirs étroits) et les interactions dynamiques entre robots.

5. Signification et Perspectives

Ce travail est significatif car il comble le fossé entre la planification symbolique (ordonnancement) et la planification géométrique continue, en traitant spécifiquement les scénarios où les tâches sont connues mais leur exécution temporelle et spatiale est critique.

• Indépendance du domaine : Le framework est conçu pour être agnostique au domaine, permettant de combiner divers solveurs d'ordonnancement et de mouvement.
• Évolutivité : En évitant de modéliser toutes les contraintes de mouvement dès le départ, le système reste scalable dans des environnements dynamiques.
• Travaux futurs : Les auteurs prévoient d'étendre ce cadre pour intégrer la Multi-Agent Path Finding (MAPF), créant ainsi un ordonnanceur conscient du MAPF capable de gérer une classe plus large de problèmes en combinant raisonnement discret et continu.

En résumé, cette approche démontre qu'un apprentissage incrémental des abstractions de mouvement via un feedback symbolique permet de résoudre des problèmes d'ordonnancement et de mouvement complexes qui seraient autrement ingérables pour les approches séquentielles ou purement discrètes.