Skip to content

ATLAS: Constraints-Aware Multi-Agent Collaboration for Real-World Travel Planning

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

Multi-agent travel planning under complex constraints; grounded reasoning [ICLR 2026]

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

ATLAS is a multi-agent framework that reframes travel planning as a Constraint Satisfaction Problem (CSP) and addresses three fundamental challenges: constraint construction, plan verification under constraints, and resolving information gaps via interleaved search. On TravelPlanner, ATLAS raises the final pass rate from 23.3% to 44.4% over the prior best, and in a live web-search multi-turn setting achieves 84% final pass rate vs. 59% for ReAct and 27% for a monolithic agent.

Problem

Existing LLM planning approaches either assume all information is given upfront (no search needed) or integrate search but treat all constraints as known in advance. Neither handles the realistic case where the agent must simultaneously discover constraints (explicit and implicit) and retrieve supporting information, especially as user requirements evolve over multiple turns.

Method

ATLAS models travel planning as a Dynamic CSP \(P^t = \langle X, D^t, C^t \rangle\), where variable domains \(D\) are populated by live tool calls and constraints \(C = C_E \cup C_I\) combine explicit user requirements with LLM-inferred commonsense invariants. The framework comprises five specialized agents orchestrated in a two-level loop:

  1. Search Agent — ReAct-based tool caller that populates domain \(D^{t,\ell}\) from external APIs or live web search; accepts targeted feedback \(F_\text{search}^{t,\ell-1}\) to refine subsequent queries.
  2. Constraint Manager — extracts both explicit constraints \(C_E^{t,\ell} := \Pi(Q^t, D^{t,\ell})\) and implicit commonsense constraints \(C_I\) from world knowledge.
  3. Planner — proposes candidate assignment \(\sigma^{t,\ell,k}\), conditioned on prior failed attempts and checker feedback.
  4. Checker — verifies \(\sigma\) against \(C^{t,\ell}\), returning verdict \(V \in \{\text{valid}, \text{invalid}, \text{unsat}\}\) plus targeted feedback \(F_\text{plan}^{t,\ell,k}\).
  5. Search Advisor — triggered on unsat; diagnoses the information gap from full context \((Q, D, C, H^{t,\ell,k})\) and emits \(F_\text{search}^{t,\ell}\) directing the Search Agent to augment \(D\).

The inner loop runs up to \(K\) Planner–Checker iterations; an unsat verdict triggers the outer interleaved search loop (up to \(L\) steps). Multi-turn support caches the prior turn's domain \(D^{t,L}\) and re-runs constraint extraction before any new search.

Key Contributions

  • Formal CSP framing of travel planning with explicit/implicit constraint decomposition, extended to a Dynamic CSP for multi-turn settings.
  • Constraint Manager agent that infers and codifies the complete constraint set \(C = C_E \cup C_I\) without prior knowledge.
  • Interleaved search mechanism: a Search Advisor diagnoses unsatisfiable sub-problems and redirects search adaptively rather than re-running a static pipeline.
  • First quantitative evaluation of a constrained planning agent in a fully live setting (real-time web search + multi-turn feedback).
  • SOTA on TravelPlanner benchmark (+14% final pass rate over best prior multi-agent baseline on test set).

Results

  • TravelPlanner validation (Gemini-2.5-Pro): ATLAS 44.44% final pass rate vs. PMC 23.33%, ReAct 20.56%.
  • TravelPlanner test (Gemini-2.5-Pro): ATLAS 35.00% vs. PMC 21.08%, ReAct 19.50%.
  • TravelPlanner test (Claude-Sonnet-4): ATLAS 18.00% vs. PMC 12.12%, ReAct 10.40%.
  • Live multi-turn setting: ATLAS 84% final pass rate vs. ReAct 59%, monolithic agent 27%.
  • Ablations show Constraint Manager alone (+commonsense rate), increasing \(K\) (checker iterations), and increasing \(L\) (interleaved search steps) each contribute independently to final pass rate.
  • Adding naive search to EvoAgent or Reflexion yields no improvement; ReAct+EvoAgent underperforms bare ReAct, validating that adaptive search (not just more search) is necessary.

Limitations

  • Evaluation domain is narrow (travel planning); generalization to other constrained planning domains is claimed but not demonstrated empirically.
  • Performance on TravelPlanner test with Claude-Sonnet-4 remains substantially lower than with Gemini-2.5-Pro (18% vs. 35%), suggesting strong dependence on base model capability.
  • Cost analysis is deferred to appendix; the multi-agent overhead (5 agents, up to \(K \times L\) interactions) is not quantified in the main body.
  • The 120 tool-call cap is imposed for fairness but may not reflect real-world deployment budgets.
  • Implicit constraint coverage depends on LLM world knowledge and may miss domain-specific rules the LLM was not trained on.

Relevance to Harnesses / Meta-Harnesses

ATLAS is a concrete instantiation of a constraint-aware multi-agent harness: it defines a principled orchestration loop (Search → Constrain → Plan ↔ Check → SearchAdvise) with typed agent interfaces and explicit feedback channels between agents, directly analogous to the harness patterns used in automated pipeline orchestration. The interleaved search mechanism—where a diagnostic agent rewrites the search directive and re-enters the pipeline—is a runtime self-repair loop that mirrors meta-harness patterns for detecting and recovering from plan failures without restarting from scratch. The formal CSP substrate and the multi-turn domain-caching strategy are transferable design primitives for any harness that must manage evolving task state across iterations.