This research introduces a novel framework that enables Large Language Models to solve complex, multi-constraint planning problems with high accuracy.

• Transforms planning challenges into Constraint Satisfaction Problems that can be formally verified
• Achieves 90% success rate on the challenging TravelPlanner benchmark where even advanced LLMs like OpenAI o1 only reached 10%
• Implements a systematic approach where LLMs handle natural language processing while verification tools ensure correctness
• Provides explanations for unsolvable problems, identifying conflicts in constraints

This breakthrough enables engineering teams to leverage LLMs for mission-critical planning applications with mathematical guarantees of correctness, bridging the gap between AI capabilities and formal verification requirements.

Large Language Models Can Solve Real-World Planning Rigorously with Formal Verification Tools