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

HiMAP-Travel ist ein hierarchisches Multi-Agenten-Framework, das durch strategische Ressourcenverteilung, parallele Tagesplanung und einen Transaktionsmonitor langfristige Reiseplanung mit strengen Einschränkungen effizienter und präziser löst als sequenzielle Ansätze.

Das Wesentliche

🌍 HiMAP-Travel: Wie man eine perfekte Reise plant, ohne den Überblick zu verlieren

Stell dir vor, du möchtest eine 3-tägige Reise von St. Petersburg nach Rockford planen. Du hast ein festes Budget von 1.700 $ und musst Hotels, Flüge und Restaurants finden. Klingt einfach? Für künstliche Intelligenz (KI) ist das ein Albtraum, wenn die Reise länger wird oder viele Regeln gelten.

Bisherige KI-Systeme funktionieren wie ein einziger, müder Reiseleiter, der alles Schritt für Schritt durchdenkt. Das Problem: Je länger die Reise wird, desto mehr vergisst dieser Reiseleiter die Anfangsregeln (wie das Budget). Er plant den ersten Tag perfekt, vergisst aber am fünften Tag, dass das Geld schon fast weg ist. Das nennt man im Paper "Constraint Drift" (Regel-Drift) – die KI driftet von den Regeln ab, weil sie zu viel "Müll" in ihrem Gedächtnis hat.

HiMAP-Travel löst dieses Problem mit einem genialen Trick: Es baut nicht einen, sondern ein Team von Spezialisten auf.

🏗️ Das Team: Der Chef und die Handwerker

Stell dir HiMAP-Travel wie eine gut organisierte Baustelle vor:

1. Der Koordinator (Der Chef):
   Dieser KI-Agent ist der "Stratege". Er sieht die ganze Reise auf einen Blick. Er teilt das große Budget von 1.700 $nicht willkürlich auf, sondern gibt den Handarbeitern eine **Richtlinie**: "Für Tag 1 hast du ca. 600$, für Tag 2 und 3 den Rest." Er sorgt dafür, dass die grobe Route stimmt (z. B. "Wir fliegen nach Rockford, nicht nach Chicago").

   • Analogie: Er ist wie ein Architekt, der den Grundriss zeichnet, bevor der erste Stein gelegt wird.

2. Die Exekutoren (Die Handwerker):
   Diese Agenten sind die "Taktiker". Jeder Handwerker kümmert sich nur um einen einzigen Tag.

   • Handwerker A plant nur Tag 1.
   • Handwerker B plant nur Tag 2.
   • Handwerker C plant nur Tag 3.
   • Der Clou: Sie arbeiten parallel (gleichzeitig), nicht nacheinander. Handwerker A muss nicht warten, bis Handwerker B fertig ist. Das macht alles viel schneller.

🛡️ Der unsichtbare Wächter (Der Synchronisierte Globale Zustand)

Das größte Problem bei paralleler Arbeit ist: Was passiert, wenn Handwerker A und Handwerker B beide das gleiche, günstige Hotel buchen wollen? Oder wenn Handwerker A das ganze Budget verprasst und Handwerker B nichts mehr hat?

In alten Systemen müssten die Handwerker sich ständig anrufen und streiten ("Hey, ich wollte das Hotel!"). Das kostet Zeit und führt zu Missverständnissen.

HiMAP-Travel nutzt einen unsichtbaren, digitalen Wächter (den Synchronized Global State):

• Dieser Wächter hält eine Echtzeit-Liste aller gebuchten Hotels und des verbleibenden Geldes.
• Bevor ein Handwerker eine Buchung bestätigt, schaut er kurz zum Wächter: "Ist das Hotel noch frei? Ist noch Geld da?"
• Wenn die Antwort "Nein" ist, wird die Buchung sofort gestoppt.
• Analogie: Es ist wie ein Kassenbuch in einem Restaurant, das alle Kellner gleichzeitig einsehen können. Niemand kann etwas bestellen, das nicht auf der Karte steht, und niemand kann das gleiche Essen doppelt bestellen.

🤝 Der Verhandlungs-Mechanismus (Cooperative Bargaining)

Was passiert, wenn der Chef dem Handwerker für Tag 2 eine Aufgabe gibt, die unmöglich ist? (Zum Beispiel: "Finde ein 5-Sterne-Hotel für 50 $" – das gibt es nicht).

In alten Systemen würde der Handwerker verzweifelt versuchen, es trotzdem zu schaffen, und am Ende scheitern.
Bei HiMAP-Travel darf der Handwerker sagen: "Das geht nicht!"
Er sendet ein kurzes, klares Signal an den Chef: "Tag 2 ist nicht machbar mit diesem Budget."
Der Chef hört zu, ändert seinen Plan (vielleicht buchen wir ein etwas teureres Hotel für Tag 1, damit Tag 2 passt) und gibt eine neue Anweisung.

• Analogie: Es ist wie ein Verhandlungstisch, an dem der Chef und die Handwerker schnell hin- und herschalten, bis alle zufrieden sind, anstatt stur weiterzumachen.

🚀 Warum ist das besser?

1. Kein Gedächtnisverlust: Da jeder Handwerker nur einen Tag plant, hat er einen "sauberen" Kopf. Er vergisst das Budget nicht, weil er nicht mit dem Chaos von Tag 1 überladen ist.
2. Geschwindigkeit: Weil alle Handwerker gleichzeitig arbeiten, ist die Planung 2,5-mal schneller als bei den alten Systemen.
3. Fehlervermeidung: Der Wächter verhindert, dass das Budget überschritten wird oder dass man zweimal dasselbe Restaurant bucht.

📊 Das Ergebnis

Auf dem Prüfstand (den "TravelPlanner"-Tests) hat HiMAP-Travel gezeigt, dass es deutlich besser ist als die bisherigen besten Methoden.

• Es schafft es, über 52 % der komplexen Reisepläne perfekt zu erfüllen (alle Regeln eingehalten, Budget nicht gesprengt).
• Die alten Methoden lagen oft nur bei ca. 44 %.
• Besonders bei langen Reisen (7 Tage) glänzt es, weil dort die alten Systeme fast immer versagen.

Fazit

HiMAP-Travel ist wie der Wechsel von einem einzigen, überforderten Reiseleiter zu einem gut organisierten Reisebüro-Team.

• Der Chef sorgt für den Überblick.
• Die Spezialisten arbeiten parallel an ihren Tagen.
• Der Wächter sorgt dafür, dass niemand gegen die Regeln verstößt.
• Das Team verhandelt schnell, wenn etwas nicht klappt.

Das Ergebnis: Schnellere, zuverlässigere Reisepläne, bei denen das Budget wirklich hält, was es verspricht.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel" auf Deutsch:

Titel: HiMAP-Travel: Hierarchische Multi-Agenten-Planung für langfristige Reiseplanung unter strengen Randbedingungen

1. Problemstellung: Das „Constraint Drift"-Phänomen

Das Paper adressiert eine fundamentale Schwäche von Large Language Models (LLMs) bei der Planung langfristiger Aufgaben mit harten Randbedingungen (z. B. Budgets, Diversitätsanforderungen, zeitliche Konsistenz).

• Herausforderung: Herkömmliche sequenzielle Agenten-Architekturen (wie ReAct oder Chain-of-Thought) leiden unter dem Phänomen „Constraint Drift under Long Tool Traces".
• Ursache: Wenn der Planungshorizont wächst, akkumulieren sich Tool-Ausgaben und Reasoning-Traces im Kontextfenster. Dies führt dazu, dass die Aufmerksamkeit des Modells von den globalen Anfangsbedingungen (z. B. dem Gesamtbudget) abnimmt.
• Folge: Das Modell priorisiert lokale Kohärenz über globale Machbarkeit. Ein Budgetfehler am ersten Tag kann die gesamte mehrstufige Reiseplanung ungültig machen. Bestehende „Verify-and-Refine"-Ansätze (wie ATLAS) korrigieren Fehler erst nachträglich, was zu super-linearer Latenz und hohem Token-Overhead führt.

2. Methodik: HiMAP-Travel Architektur

HiMAP-Travel löst dieses Problem durch eine hierarchische Multi-Agenten-Architektur, die strategische Koordination von der taktischen Ausführung entkoppelt und auf Parallelisierung setzt.

Kernkomponenten:

1. Hierarchische Aufteilung:

   • Coordinator (Strategische Ebene): Zerlegt die komplexe Benutzeranfrage in sub-optimale Tagesziele (Sub-Goals). Er verteilt das Gesamtbudget und die Reiseroute auf die einzelnen Tage, fungiert aber nicht als starrer Befehlsgeber, sondern als Koordinator.
   • Parallel Executors (Taktische Ebene): Mehrere „Day Planners" planen die einzelnen Tage parallel in isolierten Kontextfenstern. Dies verhindert, dass Fehler oder Halluzinationen früher Tage die Planung späterer Tage kontaminieren (Vermeidung von „Context Rot").

2. Drei Schlüsselmechanismen:

   • Synchronized Global State ($\Sigma$): Ein externer, deterministischer Transaktionsmonitor (geschützt durch einen Mutex), der globale Invarianten erzwingt. Er trackt das kumulierte Budget, besuchte Orte (zur Vermeidung von Duplikaten) und Transportmodi. Jede Aktion wird atomar geprüft (CHECK) und nur bei Einhaltung der Invarianten committed (COMMIT). Dies verhindert Ressourcenkonflikte (z. B. Budget-Überlauf oder doppelte Buchungen) während der Generierung, nicht danach.
   • Cooperative Bargaining Protocol: Ein bidirektionales Feedback-System. Wenn ein Executor feststellt, dass ein zugewiesenes Tagesziel nicht machbar ist (z. B. Budget-Defizit), sendet er einen strukturierten Fehlercode (JSON) zurück. Der Coordinator nutzt dies, um die Ressourcenverteilung dynamisch neu zu kalibrieren (z. B. Stadtwechsel), anstatt das gesamte Szenario neu zu generieren.
   • Unified Role-Conditioned Policy: Alle Agenten (Coordinator und Executors) teilen sich ein einziges Policy-Modell ($\pi_\theta$). Das Verhalten wird durch System-Prompts gesteuert (Role Conditioning). Das Modell wurde mit GRPO (Group Relative Policy Optimization) trainiert, was eine effiziente End-to-End-Lernkurve ermöglicht.

3. Hauptbeiträge

1. Identifikation von Constraint Drift: Das Paper definiert und quantifiziert das Versagen monolithischer sequenzieller Architekturen bei langen Tool-Traces als primäre Fehlerquelle.
2. Architektonische Innovation: Einführung eines „Correct-by-Construction"-Paradigmas, bei dem globale Constraints durch parallele Ausführung und atomare Transaktionen (statt nachträglicher Korrektur) sichergestellt werden.
3. State-of-the-Art Performance: Erzielung neuer Bestwerte auf etablierten Benchmarks bei gleichzeitiger drastischer Reduktion der Latenz.

4. Ergebnisse und Evaluation

Die Evaluation erfolgte auf den Benchmarks TravelPlanner (Single-Turn) und FlexTravelBench (Multi-Turn/Adaptation) unter Verwendung des Qwen3-8B-Modells.

• TravelPlanner (Test-Set):

  • Final Pass Rate (FPR): HiMAP-Travel erreicht 52,65 %, was einen deutlichen Vorsprung gegenüber dem sequenziellen DeepTravel-Baseline (+8,67 pp), ATLAS (+17,65 pp) und MTP (+10,0 pp) darstellt.
  • Stabilität: Die Varianz über verschiedene Seeds hinweg ist extrem gering (Std: 0,48 % vs. 7,18 % bei DeepTravel), was auf eine robuste Konvergenz hindeutet.
  • Constraint-Einhaltung: Budget-Einhaltung bleibt über alle Tage hinweg stabil (>90 %), während sequenzielle Baselines am 5. Tag auf 42 % einbrechen.

• FlexTravelBench (Multi-Turn):

  • Erzielt 44,34 % (2-Turn) und 37,42 % (3-Turn) FPR, was die Fähigkeit zur Anpassung an neu enthüllte Constraints unter Beweis stellt.

• Effizienz:

  • Durch Parallelisierung wird die Latenz um den Faktor 2,5x bis 2,63x reduziert (z. B. 72 Sekunden für 7-Tage-Reisen vs. 189,5 Sekunden bei sequenziellen Ansätzen).

5. Bedeutung und Ausblick

HiMAP-Travel demonstriert, dass die Entkopplung von strategischer Ressourcenallokation und taktischer Ausführung in Kombination mit deterministischen Transaktionsmechanismen die Skalierbarkeit von LLM-Agenten für komplexe Optimierungsprobleme signifikant verbessert.

• Allgemeine Anwendbarkeit: Die Methodik ist nicht auf Reiseplanung beschränkt, sondern übertragbar auf andere Bereiche mit gekoppelten Constraints und hierarchischer Struktur, wie Software-Entwicklung, Lieferkettenoptimierung oder wissenschaftliches Experimentdesign.
• Trainierbarkeit: Es ist eines der ersten Frameworks, das eine End-to-End-Reinforcement-Learning-Training (GRPO) unter einem geteilten Policy für Multi-Agenten-Systeme erfolgreich implementiert.

Zusammenfassend bietet HiMAP-Travel einen praktischen Bauplan für skalierbare, trainierbare Agenten, die in der Lage sind, langfristige Pläne unter strengen logischen und ressourcenbezogenen Randbedingungen zuverlässig zu erstellen.