HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel

Each language version is independently generated for its own context, not a direct translation.

🌍 HiMAP-Travel : Le Chef d'Orchestre et ses Musiciens

Imaginez que vous devez organiser un voyage de 3 jours, de Saint-Pétersbourg à Rockford, avec un budget serré de 1 700 $. C'est comme si vous deviez composer une symphonie parfaite où chaque note (chaque jour du voyage) doit respecter la partition (le budget) et ne jamais répéter le même instrument (pas de doublons de restaurants ou d'hôtels).

Le problème, c'est que les intelligences artificielles (les "agents") habituelles sont comme des musiciens solistes qui jouent note par note. Plus le voyage est long, plus ils oublient la partition de départ. Ils commencent bien, mais vers le jour 3, ils dépensent trop d'argent ou réservent le même hôtel deux fois, car ils ont "oublié" ce qu'ils ont fait le jour 1. C'est ce que les auteurs appellent la "Dérive des Contraintes".

HiMAP-Travel change la donne en utilisant une approche en équipe, divisée en deux rôles clés :

1. Le Chef d'Orchestre (Le Coordinateur) 🎼

Au lieu de laisser un seul agent faire tout le travail, HiMAP-Travel a un Chef d'Orchestre.

Son rôle : Il ne réserve pas les billets d'avion lui-même. Il regarde le budget total (1 700 $) et dit : *"Ok, pour le jour 1, on a 600$ . Pour le jour 2, 500 $. Pour le jour 3, 600$ ."*
L'analogie : C'est comme un chef de chantier qui divise la construction d'une maison en étages. Il s'assure qu'il y a assez de ciment pour chaque étage avant de commencer.

2. Les Musiciens (Les Exécuteurs) 🎻

Ensuite, le Chef envoie des Exécuteurs (des agents spécialisés) travailler en parallèle.

Leur rôle : Un agent planifie le jour 1, un autre le jour 2, un troisième le jour 3. Ils travaillent tous en même temps, comme des musiciens jouant leurs parties simultanément.
L'avantage : Comme ils ne travaillent que sur un seul jour à la fois, ils ne se fatiguent pas et ne se perdent pas dans un contexte trop long. Ils restent concentrés sur leur tâche immédiate.

3. Le Gardien du Trésor (L'État Global Synchronisé) 🛡️

C'est la pièce maîtresse du système. Imaginez un caisse enregistreuse magique et un gardien de sécurité qui surveille tout.

Le problème classique : Si deux agents réservent le même hôtel par erreur, le voyage est gâché.
La solution HiMAP : Avant qu'un agent ne valide une réservation, il doit demander la permission au Gardien.
- "Je veux réserver l'Hôtel X."
- Le Gardien vérifie : "Est-ce que l'Hôtel X est déjà réservé ?" -> NON.
- Le Gardien vérifie : "Est-ce qu'il reste assez d'argent ?" -> OUI.
- Résultat : La réservation est validée instantanément. Si quelqu'un essaie de réserver le même hôtel ou de dépasser le budget, le Gardien dit "STOP !" immédiatement.
L'analogie : C'est comme un jeu de société où un seul joueur peut toucher les pièces d'or à la fois. Personne ne peut voler la même pièce deux fois.

4. Le Négociateur (Le Protocole de Négociation) 🤝

Parfois, le Chef d'Orchestre fait une erreur de calcul. Il dit : "Pour le jour 2, vous avez 500 $."* Mais l'agent du jour 2 regarde les prix et dit : *"Impossible ! Avec 500$ , on ne peut pas trouver d'hôtel et de repas ici."

L'ancienne méthode : L'agent continue d'essayer, échoue, et tout le voyage s'effondre.
La méthode HiMAP : L'agent envoie un message court au Chef : "C'est impossible, trop cher !". Le Chef écoute, change son plan (peut-être en choisissant une ville moins chère pour le jour 2) et redémarre. C'est une négociation rapide pour corriger le tir avant que le désastre n'arrive.

🚀 Pourquoi est-ce si efficace ?

Vitesse (Parallélisme) : Au lieu de faire les jours un par un (lent), on les fait tous en même temps. C'est comme si vous aviez 3 cuisiniers préparant le dîner au lieu d'un seul. Le voyage est planifié 2,5 fois plus vite.
Précision (Zéro Erreur de Budget) : Grâce au Gardien du Trésor, le système ne dépasse jamais le budget et ne réserve jamais deux fois le même endroit.
Résultats : Sur les tests, ce système réussit à planifier des voyages complexes avec un taux de réussite de 52,65 %, ce qui est bien mieux que les méthodes précédentes (qui plafonnaient autour de 35-40 %).

En résumé

HiMAP-Travel, c'est passer d'un solitaire épuisé qui oublie ses contraintes en cours de route, à une équipe bien organisée avec un chef qui répartit le travail, des musiciens qui agissent en même temps, et un gardien vigilant qui empêche toute erreur de budget ou de doublon.

C'est une méthode qui transforme un problème complexe (organiser un long voyage avec plein de règles) en petits morceaux simples, gérés par une équipe intelligente qui ne se contredit jamais.

Each language version is independently generated for its own context, not a direct translation.

Titre : HiMAP-Travel : Planification Hiérarchique Multi-Agents pour les Voyages à Long Terme Contraints

1. Problématique : La Dérive des Contraintes (Constraint Drift)

Le papier identifie une limite fondamentale des agents LLM (Large Language Models) actuels dans les tâches de planification à long horizon, en particulier pour la planification de voyages complexes.

Le problème : Les architectures séquentielles monolithiques (comme ReAct ou Chain-of-Thought) souffrent d'un phénomène appelé "Constraint Drift under Long Tool Traces" (Dérive des contraintes sous de longues traces d'outils).
Mécanisme : À mesure que la planification progresse sur plusieurs jours, le contexte s'allonge avec l'accumulation des sorties d'outils et des traces de raisonnement. L'attention du modèle se dilue par rapport aux contraintes globales initiales (ex: budget total, diversité des lieux, règles de voyage).
Conséquence : Cela entraîne une dégradation mesurable de la faisabilité globale. Une erreur sur le premier jour (ex: dépassement de budget) peut invalider tout l'itinéraire, mais les modèles séquentiels ne détectent souvent ces erreurs qu'après avoir généré l'ensemble du plan, entraînant des coûts de calcul inutiles et une latence élevée.

2. Méthodologie : HiMAP-Travel

Les auteurs proposent HiMAP-Travel, un cadre de planification multi-agents hiérarchique qui découple la coordination stratégique de l'exécution tactique pour résoudre le problème de la dérive des contraintes.

Architecture Principale

Le système sépare la planification en deux niveaux fonctionnels :

Niveau Stratégique (Coordinateur) : Un agent haut niveau qui décompose la requête utilisateur en sous-objectifs quotidiens (sub-goals). Il alloue les ressources (budget, villes, rôles des jours) mais ne planifie pas les détails.
Niveau Tactique (Exécuteurs Parallèles) : Un ensemble d'agents spécialisés (un par jour de voyage) qui planifient indépendamment et en parallèle leurs itinéraires journaliers dans des fenêtres de contexte isolées.

Trois Mécanismes Clés

Pour permettre une exécution parallèle tout en maintenant la cohérence globale, HiMAP-Travel intègre trois innovations :

État Global Synchronisé (Synchronized Global State - $\Sigma$ ) :
- Fonctionne comme un moniteur transactionnel déterministe.
- Il gère les contraintes couplées (budget global, non-duplication des lieux, cohérence du mode de transport) via des opérations atomiques (CHECK et COMMIT).
- Avant qu'un agent ne valide une action (ex: réserver un hôtel), l'état global vérifie si cela viole le budget ou crée une duplication. Si c'est le cas, l'action est rejetée immédiatement, empêchant les conflits de ressources ("tragedy of the commons").
Protocole de Négociation Coopérative (Cooperative Bargaining Protocol) :
- Permet une rétroaction bidirectionnelle. Si un Exécuteur détecte qu'un sous-objectif est infeasible (ex: pas de logement abordable pour le jour 2), il renvoie un signal structuré (JSON) au Coordinateur.
- Le Coordinateur peut alors réallouer les ressources (changer de ville, ajuster le budget) et déclencher une nouvelle itération de planification sans avoir à tout recommencer manuellement.
- Cela évite la génération complète d'un plan erroné avant la détection d'erreur.
Politique Unifiée Conditionnée par le Rôle (Unified Role-Conditioned Policy) :
- Au lieu d'entraîner des modèles séparés, un seul modèle de politique $\pi_\theta$ est utilisé pour le Coordinateur et les Exécuteurs.
- Le comportement est différencié par un "prompt système" (conditionnement de rôle).
- Ce modèle est entraîné via GRPO (Group Relative Policy Optimization), une méthode d'apprentissage par renforcement qui optimise la politique sans nécessiter de critique séparé, en utilisant des avantages relatifs au sein d'un groupe de trajectoires.

3. Contributions Principales

Identification du "Constraint Drift" : Mise en évidence formelle de la dégradation des contraintes globales dans les planificateurs séquentiels à long terme.
Architecture "Correct-by-Construction" : Passage d'une approche "générer puis corriger" (verify-and-refine) à une approche où les contraintes sont appliquées de manière proactive et déterministe pendant la génération.
Intégration de l'Apprentissage par Renforcement (RL) : C'est le premier cadre multi-agent hiérarchique dans ce domaine à supporter un entraînement RL de bout en bout sous une politique partagée, permettant une convergence robuste.
Efficacité par le Parallélisme : Réduction significative de la latence grâce à l'exécution parallèle des jours de voyage.

4. Résultats Expérimentaux

Les évaluations ont été menées sur deux benchmarks majeurs : TravelPlanner (planification en un seul tour) et FlexTravelBench (adaptation multi-tours avec contraintes progressives).

Performance sur TravelPlanner :
- Avec le modèle Qwen3-8B, HiMAP-Travel atteint un Taux de Réussite Final (FPR) de 52,65% sur l'ensemble de test.
- Il surpasse la baseline séquentielle DeepTravel (même modèle, même entraînement) de +8,67 points.
- Il dépasse également ATLAS (+17,65 pp) et MTP (+10,0 pp).
- Réduction de la variance entre les graines aléatoires de 93% par rapport aux baselines séquentielles, indiquant une stabilité supérieure.
Performance sur FlexTravelBench :
- Atteint 44,34% (2 tours) et 37,42% (3 tours) de FPR, surpassant les méthodes existantes dans des scénarios d'adaptation dynamique.
Efficacité et Latence :
- Réduction de la latence de 2,5x (ex: 72s pour un voyage de 7 jours contre 189s pour une approche séquentielle) grâce au parallélisme.
- Le modèle 4B atteint 88% des performances du modèle 8B avec seulement 67% de la latence.
Analyse des Échecs :
- HiMAP-Travel réduit les violations de budget de 67% et les doublons de lieux de 83% par rapport aux approches séquentielles, grâce à la vérification transactionnelle de l'état global $\Sigma$ .

5. Signification et Impact

Ce travail démontre que la décomposition hiérarchique couplée à une exécution parallèle et à une surveillance transactionnelle des contraintes est une voie viable pour résoudre les problèmes d'optimisation combinatoire complexes avec des LLM.

Au-delà du voyage : La méthodologie (découplage des contraintes globales en sous-problèmes locaux avec surveillance transactionnelle) est applicable à d'autres domaines nécessitant une coordination de ressources sous contraintes, tels que le développement de logiciels, l'optimisation de la chaîne d'approvisionnement ou la conception d'expériences scientifiques.
Avancée technique : HiMAP-Travel prouve que les agents autonomes peuvent être entraînés de manière stable et efficace pour des tâches à long horizon, surmontant la fragilité des architectures séquentielles actuelles face à la complexité des contraintes couplées.

En résumé, HiMAP-Travel représente un état de l'art (SOTA) pour la planification de voyages contraints, offrant une solution robuste, rapide et généralisable aux défis de la planification à long terme.