LLM-Based Grid-World Path Planning With Probabilistic Model Checking

Abstract

Recent advances in large language models (LLMs) have extended their capabilities beyond text generation to structured reasoning and planning, motivating their deployment in physical systems. A representative safety-critical setting is autonomous navigation, commonly abstracted as stochastic grid-world path planning, where an agent makes sequential decisions under uncertainty while satisfying temporal, probabilistic requirements. Classical deterministic planners offer formal guarantees but cannot adequately model stochastic dynamics, while reinforcement learning (RL) approaches are often problem-specific and may not ensure constraint satisfaction. Existing LLM-based planners largely focus on deterministic task planning and not stochastic grid-world planning with formal guarantees. In this paper, we present a neuro-symbolic path planning framework that integrates LLM-based planners with probabilistic model checking to provide guarantees for temporal and probabilistic requirements. We evaluate three state-of-the-art LLMs, assessing success rate, convergence behavior, and performance against a reinforcement learning baseline. Results show that our approach achieves high success rates across diverse grid-world configurations and outperforms the RL baseline.