The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Theta*: Any-Angle Path Planning on Grids
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738
Probabilistic roadmaps for path planning in high-dimensional configuration spaces
Kavraki, L. E., Svestka, P., Latombe, J.-C., & Overmars, M. H. (1996) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.508439 · Cited by 6,343
Voronoi diagrams—a survey of a fundamental geometric data structure
Aurenhammer, F. (1991) · ACM Computing Surveys · doi:10.1145/116873.116880 · Cited by 4,340
An algorithm for planning collision-free paths among polyhedral obstacles
Lozano-Pérez, T., & Wesley, M. A. (1979) · Communications of the ACM · doi:10.1145/359156.359164 · Cited by 2,304
Principles of Robot Motion: Theory, Algorithms, and Implementations
Choset, H., & Latombe, J. (2005) · Medical Entomology and Zoology · Cited by 2,031
Heuristics: Intelligent search strategies for computer problem solving.
(1985) · Information Processing & Management · doi:10.1016/0306-4573(85)90100-1 · Cited by 1,430
Rapidly-Exploring Random Trees: Progress and Prospects
(2001) · Algorithmic and Computational Robotics · doi:10.1201/9781439864135-43 · Cited by 1,146
Path Planning Using a Tangent Graph for Mobile Robots Among Polygonal and Curved Obstacles
Liu, Y., & Arimoto, S. (1992) · The International Journal of Robotics Research · doi:10.1177/027836499201100409 · Cited by 135
Pohl, I. (1973) · International Joint Conference on Artificial Intelligence · Cited by 134
Framed-quadtree path planning for mobile robots operating in sparse environments
Yahja, A., Stentz, A., Singh, S., & Brumitt, B. L. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1998.677046 · Cited by 126
Cited by
Path planning techniques for mobile robots: Review and prospect
Liu, L., Wang, X., Yang, X., Liu, H., Li, J., & Wang, P. (2023) · Expert Systems with Applications · doi:10.1016/j.eswa.2023.120254 · Cited by 707
Path Planning for Autonomous Mobile Robots: A Review
Sánchez-Ibáñez, J. R., Pérez-del-Pulgar, C. J., & García-Cerezo, A. (2021) · Sensors · doi:10.3390/s21237898 · Cited by 462
Path Planning for the Mobile Robot: A Review
Zhang, H.-Y., Lin, W.-M., & Chen, A.-X. (2018) · Symmetry · doi:10.3390/sym10100450 · Cited by 447
Liu, P., Chen, A. Y., Huang, Y.-N., Han, J.-Y., Lai, J.-S., Kang, S.-C., Wu, T.-H., Wen, M.-C., & Tsai, M.-H. (2014) · Smart Structures and Systems · doi:10.12989/sss.2014.13.6.1065 · Cited by 377
Autonomous driving system: A comprehensive survey
Zhao, J., Zhao, W., Deng, B., Wang, Z., Zhang, F., Zheng, W., Cao, W., Nan, J., Lian, Y., & Burke, A. F. (2024) · Expert Systems with Applications · doi:10.1016/j.eswa.2023.122836 · Cited by 361
Metadata
- Authors
- Daniel, K., Nash, A., Koenig, S., & Felner, A.
- Venue
- Journal of Artificial Intelligence Research
- Publisher
- AI Access Foundation
- Published
- 2010-10-29
- Volume
- 39
- Pages
- 533-579
- ISSN
- 1076-9757 (ISSN-L)
- OpenAlex
- W1935926926
- Cited by
- 465
- References
- 11
- FWCI
- 6.63
- Type
- journal article
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Theta*: Any-Angle Path Planning on Grids. https://app.cochat.ai/papers/10.1613/jair.2994
- The paper
- Daniel, K., Nash, A., Koenig, S., & Felner, A. (2010). Theta*: Any-Angle Path Planning on Grids. Journal of Artificial Intelligence Research. https://doi.org/10.1613/jair.2994
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
