# Planning with Multi-Constraints via Collaborative Language Agents

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

## Key facts

- Cited by 26 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 37 of its 58 references that are in the map.
- First posted on arXiv 26 May 2024.

## 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, 30 of 37)

- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Self-Instruct: Aligning Language Models with Self-Generated Instructions](https://mlsanity.com/paper/2212.10560/) (2022)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [The Rise and Potential of Large Language Model Based Agents: A Survey](https://mlsanity.com/paper/2309.07864/) (2023)
- [CAMEL: Communicative Agents for "Mind" Exploration of Large Language Model Society](https://mlsanity.com/paper/2303.17760/) (2023)
- [WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents](https://mlsanity.com/paper/2207.01206/) (2022)
- [Mind2Web: Towards a Generalist Agent for the Web](https://mlsanity.com/paper/2306.06070/) (2023)
- [WizardLM: Empowering large pre-trained language models to follow complex instructions](https://mlsanity.com/paper/2304.12244/) (2023)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [ExpeL: LLM Agents Are Experiential Learners](https://mlsanity.com/paper/2308.10144/) (2023)
- [CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing](https://mlsanity.com/paper/2305.11738/) (2023)
- [Visual ChatGPT: Talking, Drawing and Editing with Visual Foundation Models](https://mlsanity.com/paper/2303.04671/) (2023)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [Understanding the planning of LLM agents: A survey](https://mlsanity.com/paper/2402.02716/) (2024)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [A Real-World WebAgent with Planning, Long Context Understanding, and Program Synthesis](https://mlsanity.com/paper/2307.12856/) (2023)
- [Large Language Models Empowered Agent-based Modeling and Simulation: A Survey and Perspectives](https://mlsanity.com/paper/2312.11970/) (2023)
- [GPT4Tools: Teaching Large Language Model to Use Tools via Self-instruction](https://mlsanity.com/paper/2305.18752/) (2023)
- [Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning](https://mlsanity.com/paper/2305.14909/) (2023)
- [Navigate through Enigmatic Labyrinth A Survey of Chain of Thought Reasoning: Advances, Frontiers and Future](https://mlsanity.com/paper/2309.15402/) (2023)
- [SwiftSage: A Generative Agent with Fast and Slow Thinking for Complex Interactive Tasks](https://mlsanity.com/paper/2305.17390/) (2023)
- [The Landscape of Emerging AI Agent Architectures for Reasoning, Planning, and Tool Calling: A Survey](https://mlsanity.com/paper/2404.11584/) (2024)

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

- [Can We Rely on LLM Agents to Draft Long-Horizon Plans? Let's Take TravelPlanner as an Example](https://mlsanity.com/paper/2408.06318/) (2024)
- [HyperTree Planning: Enhancing LLM Reasoning via Hierarchical Thinking](https://mlsanity.com/paper/2505.02322/) (2025)
- [Toward Personalized LLM-Powered Agents: Foundations, Evaluation, and Future Directions](https://mlsanity.com/paper/2602.22680/) (2026)
- [TP-RAG: Benchmarking Retrieval-Augmented Large Language Model Agents for Spatiotemporal-Aware Travel Planning](https://mlsanity.com/paper/2504.08694/) (2025)
- [Blueprint First, Model Second: A Framework for Deterministic LLM Workflow](https://mlsanity.com/paper/2508.02721/) (2025)
- [LRAgent: Efficient KV Cache Sharing for Multi-LoRA LLM Agents](https://mlsanity.com/paper/2602.01053/) (2026)
- [TripTide: A Benchmark for Adaptive Travel Planning under Disruptions](https://mlsanity.com/paper/2510.21329/) (2025)
- [Select-Then-Decompose: From Empirical Analysis to Adaptive Selection Strategy for Task Decomposition in Large Language Models](https://mlsanity.com/paper/2510.17922/) (2025)
- [LLMPC: Large Language Model Predictive Control](https://mlsanity.com/paper/2501.02486/) (2025)
- [GraphicBench: A Planning Benchmark for Graphic Design with Language Agents](https://mlsanity.com/paper/2504.11571/) (2025)
- [LumiMAS: A Comprehensive Framework for Real-Time Monitoring and Enhanced Observability in Multi-Agent Systems](https://mlsanity.com/paper/2508.12412/) (2025)
- [Unified-MAS: Universally Generating Domain-Specific Nodes for Empowering Automatic Multi-Agent Systems](https://mlsanity.com/paper/2603.21475/) (2026)
- [From Plan to Action: How Well Do Agents Follow the Plan?](https://mlsanity.com/paper/2604.12147/) (2026)
- [Constraint-Aware Route Recommendation from Natural Language via Hierarchical LLM Agents](https://mlsanity.com/paper/2510.06078/) (2025)
- [Cochain: Balancing Insufficient and Excessive Collaboration in LLM Agent Workflows](https://mlsanity.com/paper/2505.10936/) (2025)
- [Decoupled Travel Planning with Behavior Forest](https://mlsanity.com/paper/2604.21354/) (2026)
- [State-Centric Decision Process](https://mlsanity.com/paper/2605.12755/) (2026)
- [Does The Way You Plan Matter? An Empirical Study of Planning Representations for LLM Web Agents](https://mlsanity.com/paper/2605.29927/) (2026)
- [Multi-Agent Collaborative Reasoning with Tool-Augmented Evidence for Urban Region Profiling](https://mlsanity.com/paper/2607.13558/) (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)
- [GenEscape: Hierarchical Multi-Agent Generation of Escape Room Puzzles](https://mlsanity.com/paper/2506.21839/) (2025)
- [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)
- [Episodic Memory Temporal Consistency for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2606.04492/) (2026)
- [CARL: Constraint-Aware Reinforcement Learning for Planning with LLMs](https://mlsanity.com/paper/2607.04854/) (2026)
- [Agents in the Wild: Where Research Meets Deployment](https://mlsanity.com/paper/2607.19336/) (2026)

## Abstract (arXiv)

The rapid advancement of neural language models has sparked a new surge of intelligent agent research. Unlike traditional agents, large language model-based agents (LLM agents) have emerged as a promising paradigm for achieving artificial general intelligence (AGI) due to their superior reasoning and generalization capabilities. Effective planning is crucial for the success of LLM agents in real-world tasks, making it a highly pursued topic in the community. Current planning methods typically translate tasks into executable action sequences. However, determining a feasible or optimal sequence for complex tasks with multiple constraints at fine granularity, which often requires compositing long chains of heterogeneous actions, remains challenging. This paper introduces Planning with Multi-Constraints (PMC), a zero-shot methodology for collaborative LLM-based multi-agent systems that simplifies complex task planning with constraints by decomposing it into a hierarchy of subordinate tasks. Each subtask is then mapped into executable actions. PMC was assessed on two constraint-intensive benchmarks, TravelPlanner and API-Bank. Notably, PMC achieved an average 42.68% success rate on TravelPlanner, significantly higher than GPT-4 (2.92%), and outperforming GPT-4 with ReAct on API-Bank by 13.64%, showing the immense potential of integrating LLM with multi-agent systems. We also show that PMC works with small LLM as the planning core, e.g., LLaMA-3.1-8B.