# Theta*: Any-Angle Path Planning on Grids

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2014.

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

- [LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning](https://mlsanity.com/paper/2407.02511/) (2024)
- [Advances in Embodied Navigation Using Large Language Models: A Survey](https://mlsanity.com/paper/2311.00530/) (2023)
- [TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers](https://mlsanity.com/paper/2212.11730/) (2022)
- [Recent Advancements in Deep Learning Applications and Methods for Autonomous Navigation: A Comprehensive Review](https://mlsanity.com/paper/2302.11089/) (2023)
- [Path Planning for Air-Ground Robot Considering Modal Switching Point Optimization](https://mlsanity.com/paper/2305.08178/) (2023)
- [Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles](https://mlsanity.com/paper/2104.06681/) (2021)
- [Neural Potential Field for Obstacle-Aware Local Motion Planning](https://mlsanity.com/paper/2310.16362/) (2023)
- [Mind and Motion Aligned: A Joint Evaluation IsaacSim Benchmark for Task Planning and Low-Level Policies in Mobile Manipulation](https://mlsanity.com/paper/2508.15663/) (2025)
- [Spatial Imagination With Semantic Cognition for Mobile Robots](https://mlsanity.com/paper/2104.03638/) (2021)
- [The Emergence of Deep Reinforcement Learning for Path Planning](https://mlsanity.com/paper/2507.15469/) (2025)
- [Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding](https://mlsanity.com/paper/2404.16379/) (2024)
- [Quantum-Enhanced Hybrid Reinforcement Learning Framework for Dynamic Path Planning in Autonomous Systems](https://mlsanity.com/paper/2504.20660/) (2025)
- [Planning and Learning: Path-Planning for Autonomous Vehicles, a Review of the Literature](https://mlsanity.com/paper/2207.13181/) (2022)
- [SLOPE: Search with Learned Optimal Pruning-based Expansion](https://mlsanity.com/paper/2406.04935/) (2024)
- [DAA*: Deep Angular A Star for Image-based Path Planning](https://mlsanity.com/paper/2507.09305/) (2025)
- [A review of motion planning algorithms for intelligent robotics](https://mlsanity.com/paper/2102.02376/) (2021)
- [Augmenting GRIPS with Heuristic Sampling for Planning Feasible Trajectories of a Car-Like Robot](https://mlsanity.com/paper/2108.06789/) (2021)
- [Pathfinding with Lazy Successor Generation](https://mlsanity.com/paper/2408.15443/) (2024)
- [Dynamic Neural Potential Field: Online Trajectory Optimization in the Presence of Moving Obstacles](https://mlsanity.com/paper/2410.06819/) (2024)
- [NavTopo: Leveraging Topological Maps For Autonomous Navigation Of a Mobile Robot](https://mlsanity.com/paper/2410.11492/) (2024)
- [ColorDynamic: Generalizable, Scalable, Real-time, End-to-end Local Planner for Unstructured and Dynamic Environments](https://mlsanity.com/paper/2502.19892/) (2025)
- [Frenet Corridor Planner: An Optimal Local Path Planning Framework for Autonomous Driving](https://mlsanity.com/paper/2505.03695/) (2025)
- [Efficient Hierarchical Any-Angle Path Planning on Multi-Resolution 3D Grids](https://mlsanity.com/paper/2602.21174/) (2026)
- [FlexPath: Adapting Learned Connectivity Guidance to Path Preferences](https://mlsanity.com/paper/2606.10167/) (2026)
- [Solution Space Path Planning: A Real-Time Human-Centered Path Planning Algorithm for En-Route Air Traffic Control](https://mlsanity.com/paper/2607.00064/) (2026)
- [Optimal any-angle path planning in static and dynamic environments](https://mlsanity.com/paper/2607.00065/) (2026)

## Abstract (arXiv)

Grids with blocked and unblocked cells are often used to represent terrain in robotics and video games. However, paths formed by grid edges can be longer than true shortest paths in the terrain since their headings are artificially constrained. We present two new correct and complete any-angle path-planning algorithms that avoid this shortcoming. Basic Theta* and Angle-Propagation Theta* are both variants of A* that propagate information along grid edges without constraining paths to grid edges. Basic Theta* is simple to understand and implement, fast and finds short paths. However, it is not guaranteed to find true shortest paths. Angle-Propagation Theta* achieves a better worst-case complexity per vertex expansion than Basic Theta* by propagating angle ranges when it expands vertices, but is more complex, not as fast and finds slightly longer paths. We refer to Basic Theta* and Angle-Propagation Theta* collectively as Theta*. Theta* has unique properties, which we analyze in detail. We show experimentally that it finds shorter paths than both A* with post-smoothed paths and Field D* (the only other version of A* we know of that propagates information along grid edges without constraining paths to grid edges) with a runtime comparable to that of A* on grids. Finally, we extend Theta* to grids that contain unblocked cells with non-uniform traversal costs and introduce variants of Theta* which provide different tradeoffs between path length and runtime.