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

Constraint-aware multi-agent LLM for complex travel planning under real-world rules

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 for constraint-aware travel planning that decomposes the problem into a CSP and handles it with dedicated agents for constraint construction, iterative plan verification, and adaptive interleaved search. On the TravelPlanner benchmark it raises the final pass rate from 23.3% to 44.4% over the best prior method, and achieves 84% in a live, multi-turn, real-web-search setting where ReAct scores 59% and a monolithic agent scores 27%.

Problem

LLMs fail to produce valid plans under complex, partially-observable, and evolving constraints. Existing methods either assume all information is given upfront or assume all constraints are known in advance; no prior work simultaneously discovers constraints, searches for missing information, and adapts to user feedback across turns.

Method

ATLAS formalizes travel planning as a Constraint Satisfaction Problem \(P = \langle X, D, C \rangle\), where domains \(D\) are populated dynamically via tool calls and constraints \(C = C_E \cup C_I\) split into explicit (from query/search) and implicit (commonsense) rules. Four specialized agents collaborate:

  1. Search Agent — ReAct-based tool caller that populates domain \(D^{t,\ell}\) from live APIs or web search; re-invoked with targeted feedback when planning fails.
  2. Constraint Manager — parses query and search results to extract \(C_E\) and infer \(C_I\) (commonsense invariants such as "return to origin on the last day").
  3. Planner / Checker loop — Planner proposes an assignment \(\sigma^{t,\ell,k}\); Checker verifies it against all constraints and emits a verdict \(V \in \{\text{valid}, \text{invalid}, \text{unsat}\}\) plus targeted feedback \(F_{\text{plan}}\). The loop runs up to \(K\) revisions.
  4. Search Advisor — triggered on \(V = \text{unsat}\); diagnoses whether the failure is a logic error or an information gap and generates \(F_{\text{search}}\) directing a new search round (up to \(L\) interleaved search steps).

For multi-turn conversations the final domain \(D^{t,L}\) is cached as memory; the Constraint Manager re-evaluates it against the new query before triggering fresh search.

Key Contributions

  • First framework to jointly handle constraint discovery, constraint-aware planning with iterative verification, and adaptive interleaved search in a single pipeline.
  • State-of-the-art on TravelPlanner (single-turn): final pass rate 44.4% (Gemini-2.5-Pro, test set) vs. best baseline 23.3%, a +90% relative improvement.
  • First quantitative evaluation on live, multi-turn travel planning (real web search + user feedback): 84% final pass rate vs. ReAct 59%, monolithic agent 27%.
  • Formal CSP problem formulation covering both static and dynamic (multi-turn) planning objectives.

Results

  • TravelPlanner test set (Gemini-2.5-Pro): ATLAS 44.4% final pass rate vs. PMC 21.1%, ReAct+Reflexion 22.7%, ReAct 19.5%.
  • TravelPlanner test set (Claude-Sonnet-4): ATLAS 31.0% vs. PMC 12.1%, ReAct 10.4%.
  • TravelPlanner validation set (Gemini-2.5-Pro): ATLAS 74.4% hard-constraint macro pass rate vs. PMC 37.2%; commonsense macro 40.5% vs. 28.3% (PMC).
  • Live multi-turn setting: ATLAS 84% final pass rate vs. ReAct 59%, monolithic agent 27%.
  • Ablations: removing the Constraint Manager degrades final pass rate substantially; increasing \(K\) from 0→3 improves performance monotonically; increasing \(L\) beyond 0 consistently helps, with diminishing returns.
  • Adding search to non-adaptive planners (ReAct+EvoAgent) can hurt vs. plain ReAct, confirming that adaptive interleaved search is the critical enabler.

Limitations

  • Evaluated only on travel planning; generalizability to other constrained QA domains is asserted but not demonstrated empirically.
  • Computational cost is substantially higher than baselines (multiple agents, up to \(K \times L\) loops); cost analysis is deferred to an appendix.
  • Implicit constraint coverage depends on LLM world knowledge; rare domain rules not in pretraining may be missed.
  • Multi-turn evaluation uses a single live test case (qualitative + pass rate); no large-scale multi-turn benchmark exists.
  • Performance degrades significantly with the weaker Claude-Sonnet-4 backbone compared to Gemini-2.5-Pro, indicating backbone sensitivity.

Relevance to Agentic AI / LLM Agents

ATLAS is a direct demonstration that principled task decomposition into specialized agents—each addressing a distinct failure mode—outperforms both monolithic agents and generic multi-agent delegation (PMC) on a hard real-world benchmark. The CSP formalization of agent-observable, dynamically-constructed constraint sets is a reusable abstraction for any agentic planning domain, not just travel. The interleaved search-verify-re-search loop is a concrete instantiation of the broader "diagnose and repair" paradigm increasingly advocated for robust LLM agents. The multi-turn extension with cached domain memory addresses the efficiency–completeness tradeoff central to long-horizon agentic tasks.