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

arXiv: https://arxiv.org/abs/2509.25586 · HTML: https://mlsanity.com/paper/2509.25586/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 7 of its 51 references that are in the map.
- First posted on arXiv 29 Sep 2025.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 7 of 7)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [Know Me, Respond to Me: Benchmarking LLMs for Dynamic User Profiling and Personalized Responses at Scale](https://mlsanity.com/paper/2504.14225/) (2025)
- [Mind2Web 2: Evaluating Agentic Search with Agent-as-a-Judge](https://mlsanity.com/paper/2506.21506/) (2025)
- [TravelAgent: An AI Assistant for Personalized Travel Planning](https://mlsanity.com/paper/2409.08069/) (2024)
- [Decompose, Plan in Parallel, and Merge: A Novel Paradigm for Large Language Models based Planning with Multiple Constraints](https://mlsanity.com/paper/2506.02683/) (2025)

## Built on by (most cited first, 13 of 13)

- [Terrarium: Revisiting the Blackboard for Multi-Agent Safety, Privacy, and Security Studies](https://mlsanity.com/paper/2510.14312/) (2025)
- [Demystifying Reinforcement Learning for Long-Horizon Tool-Using Agents: A Comprehensive Recipe](https://mlsanity.com/paper/2603.21972/) (2026)
- [AdaPlanBench: Evaluating Adaptive Planning in Large Language Model Agents under World and User Constraints](https://mlsanity.com/paper/2606.05622/) (2026)
- [AutoRefine: Compiling Trajectories into Validated Typed Agent Artifacts](https://mlsanity.com/paper/2601.22758/) (2026)
- [HiMAP-Travel: Hierarchical Multi-Agent Planning for Long-Horizon Constrained Travel](https://mlsanity.com/paper/2603.04750/) (2026)
- [State-Centric Decision Process](https://mlsanity.com/paper/2605.12755/) (2026)
- [PlanningBench: Generating Scalable and Verifiable Planning Data for Evaluating and Training Large Language Models](https://mlsanity.com/paper/2605.20873/) (2026)
- [Replan, Repair, or Edit? A Unified Empirical Evaluation of Travel Agents for Itinerary Revision under Resource Disruptions](https://mlsanity.com/paper/2609.19654/) (2026)
- [IMAGINE: Integrating Multi-Agent System into One Model for Complex Reasoning and Planning](https://mlsanity.com/paper/2510.14406/) (2025)
- [Revisiting the Travel Planning Capabilities of Large Language Models](https://mlsanity.com/paper/2605.03308/) (2026)
- [When Do Multi-Agent Systems Help? An Information Bottleneck Perspective](https://mlsanity.com/paper/2607.16133/) (2026)
- [AI Tour Meeting: Group Travel Planning by LLM Agents](https://mlsanity.com/paper/2607.18806/) (2026)
- [UTP-Bench: Uncertainty-aware Travel Planning Benchmark](https://mlsanity.com/paper/2609.02421/) (2026)

## Abstract (arXiv)

While Large Language Models (LLMs) have shown remarkable advancements in reasoning and tool use, they often fail to generate optimal, grounded solutions under complex constraints. Real-world travel planning exemplifies these challenges, evaluating agents' abilities to handle constraints that are explicit, implicit, and even evolving based on interactions with dynamic environments and user needs. In this paper, we present ATLAS, a general multi-agent framework designed to effectively handle such complex nature of constraints awareness in real-world travel planning tasks. ATLAS introduces a principled approach to address the fundamental challenges of constraint-aware planning through dedicated mechanisms for dynamic constraint management, iterative plan critique, and adaptive interleaved search. ATLAS demonstrates state-of-the-art performance on the TravelPlanner benchmark, improving the final pass rate from 23.3% to 44.4% over its best alternative. More importantly, our work is the first to demonstrate quantitative effectiveness on real-world travel planning tasks with live information search and multi-turn feedback. In this realistic setting, ATLAS showcases its superior overall planning performance, achieving an 84% final pass rate which significantly outperforms baselines including ReAct (59%) and a monolithic agent (27%).