# Optimal Scene Graph Planning with Large Language Model Guidance

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2023.

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

- [On the Prospects of Incorporating Large Language Models (LLMs) in Automated Planning and Scheduling (APS)](https://mlsanity.com/paper/2401.02500/) (2024)
- [Safety Guardrails for LLM-Enabled Robots](https://mlsanity.com/paper/2503.07885/) (2025)
- [Conformal Temporal Logic Planning using Large Language Models](https://mlsanity.com/paper/2309.10092/) (2023)
- [Probabilistically Correct Language-based Multi-Robot Planning using Conformal Prediction](https://mlsanity.com/paper/2402.15368/) (2024)
- [SPINE: Online Semantic Planning for Missions with Incomplete Natural Language Specifications in Unstructured Environments](https://mlsanity.com/paper/2410.03035/) (2024)
- [A Survey on Large Language Models for Automated Planning](https://mlsanity.com/paper/2502.12435/) (2025)
- [Air-Ground Collaboration for Language-Specified Missions in Unknown Environments](https://mlsanity.com/paper/2505.09108/) (2025)
- [Distilling On-device Language Models for Robot Planning with Minimal Human Intervention](https://mlsanity.com/paper/2506.17486/) (2025)
- [LLM Meets Scene Graph: Can Large Language Models Understand and Generate Scene Graphs? A Benchmark and Empirical Study](https://mlsanity.com/paper/2505.19510/) (2025)
- [MomaGraph: State-Aware Unified Scene Graphs with Vision-Language Model for Embodied Task Planning](https://mlsanity.com/paper/2512.16909/) (2025)
- [Multi-Agent Planning Using Visual Language Models](https://mlsanity.com/paper/2408.05478/) (2024)
- [Language-Grounded Hierarchical Planning and Execution with Multi-Robot 3D Scene Graphs](https://mlsanity.com/paper/2506.07454/) (2025)
- [ESCA: Contextualizing Embodied Agents via Scene-Graph Generation](https://mlsanity.com/paper/2510.15963/) (2025)
- [DOZE: A Dataset for Open-Vocabulary Zero-Shot Object Navigation in Dynamic Environments](https://mlsanity.com/paper/2402.19007/) (2024)
- [Long-Term Planning Around Humans in Domestic Environments with 3D Scene Graphs](https://mlsanity.com/paper/2503.09173/) (2025)
- [3D Scene Graphs: Open Challenges and Future Directions](https://mlsanity.com/paper/2606.19383/) (2026)
- [LookPlanGraph: Embodied Instruction Following Method with VLM Graph Augmentation](https://mlsanity.com/paper/2512.21243/) (2025)
- [General-Purpose Robotic Navigation via LVLM-Orchestrated Perception, Reasoning, and Acting](https://mlsanity.com/paper/2506.17462/) (2025)
- [UniGround: Universal 3D Visual Grounding via Training-Free Scene Parsing](https://mlsanity.com/paper/2603.08131/) (2026)
- [Integrating Graphs, Large Language Models, and Agents: Reasoning and Retrieval](https://mlsanity.com/paper/2604.15951/) (2026)
- [Urban Risk-Aware Navigation via VQA-Based Event Maps for People with Low Vision](https://mlsanity.com/paper/2605.11782/) (2026)
- [Actively Resolving Contextual Uncertainty for Underspecified Tasks in Natural Language](https://mlsanity.com/paper/2609.30428/) (2026)
- [Rhetorical Text-to-Image Generation via Two-layer Diffusion Policy Optimization](https://mlsanity.com/paper/2505.22792/) (2025)
- [Prompting Robot Teams with Natural Language](https://mlsanity.com/paper/2509.24575/) (2025)
- [OpenSGA: Efficient 3D Scene Graph Alignment in the Open World](https://mlsanity.com/paper/2605.10484/) (2026)
- [ChronoGraph: Functional 4D Scene Graphs with Vision-Language Models for Interaction Understanding and Grounded Planning](https://mlsanity.com/paper/2609.39665/) (2026)
- [Interactive Navigation Beyond Reachability: Benchmark and Agentic Framework](https://mlsanity.com/paper/2610.17089/) (2026)

## Abstract (arXiv)

Recent advances in metric, semantic, and topological mapping have equipped autonomous robots with semantic concept grounding capabilities to interpret natural language tasks. This work aims to leverage these new capabilities with an efficient task planning algorithm for hierarchical metric-semantic models. We consider a scene graph representation of the environment and utilize a large language model (LLM) to convert a natural language task into a linear temporal logic (LTL) automaton. Our main contribution is to enable optimal hierarchical LTL planning with LLM guidance over scene graphs. To achieve efficiency, we construct a hierarchical planning domain that captures the attributes and connectivity of the scene graph and the task automaton, and provide semantic guidance via an LLM heuristic function. To guarantee optimality, we design an LTL heuristic function that is provably consistent and supplements the potentially inadmissible LLM guidance in multi-heuristic planning. We demonstrate efficient planning of complex natural language tasks in scene graphs of virtualized real environments.