The DOI matches its Crossref record.
Any-angle path planning on non-uniform costmaps
Abstract
A* on grid maps generates a path with zig-zag pattern, but Theta* is known to be free from this disadvantage. Theta* assumes that cost of each cell, cell-cost, is uniform, but non-uniform costs are effective ways to represent traversability on grid maps. Theta* does not work on non-uniform costmaps. In this paper, we generalize Theta* toward non-uniform costmaps. To extend Theta*, we propose two kinds of cost functions considering non-uniform cell-costs. The first function adopts the arithmetic mean under the assumption that all cells contribute equally to the overall cost. The second function uses the weighted mean by considering the true traversal length on each cell. We applied the proposed methods to two types of maps: synthetic and real maps. An experiment on synthetic maps quantifies performance of the two methods in terms of accuracy and computing time. The other experiment on real maps presents the effectiveness of Theta* with the proposed methods. The generalized Theta* generated the least-cost path compared with the original Theta* and A* on non-uniform costmaps.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 15
- ferguson, 2008, Efficiently using cost maps for planning complex maneuvers, Proceedings of ICRA Workshop on Planning with Costmaps
- rui, 2009, Smooth path planning in constrained environments, Proceedings of IEEE International Conference on Robotics and Automation (ICRA)
- 10.1109/IROS.2006.282516 · DOI
- 10.1109/ARSO.2010.5679696 · DOI
- 10.4218/etrij.10.1510.0138 · DOI
- 10.1002/rob.20109 · DOI
- 10.1109/ICSMC.2007.4414077 · DOI
- mills-tettey, 2008, Continuous-field path planning with constrained path-dependent state variables, Proceedings of ICRA Workshop on Planning with Costmaps
- 10.1177/0278364909359210 · DOI
- nash, 2010, Lazy theta*: Any-angle path planning and path length analysis in 3D, Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 10.1609/aaai.v24i1.7566 · DOI
- 10.1109/ROBIO.2010.5723473 · DOI
- nash, 2009, Incremental phi*: Incremental any-angle path planning on grids, Proceedings of International Joint Conference on Artificial Intelligence (IJCAI)
- nash, 2007, Theta*: Any-angle path planning on grids, Proceedings of AAAI Conference on Artificial Intelligence (AAAI)
- 10.1017/CBO9780511546877 · DOI
- daniel, 2010, Theta*: Any-angle path planning on grids, Journal of Artificial Intelligence Research (JAIR), 39, 533, 10.1613/jair.2994 · DOI
Cited by
Sorted by citations
Planetary Terrain Datasets and Benchmarks for Rover Path Planning
Chancán, M., Banerjee, A., & Nikolakopoulos, G. (2025) · arXiv · doi:10.48550/arxiv.2512.21438 · Cited by 1
“Graph-based methods, such as Dijkstra’s algorithm and its variants AStart (Hart et al., 1968) and ThetaStar (Choi and Yu, 2011), discretize the environment into a weighted graph structure, with non-negative edge weights, to find the shortest path from a start node to all other nodes.”
Influential
Metadata
- Authors
- Choi, S., & Yu, W.
- Affiliations
- Electronics and Telecommunications Research Institute (KR)
- Venue
- 2011 IEEE International Conference on Robotics and Automation
- Publisher
- IEEE
- Published
- 2011-05
- Pages
- 5615-5621
- ISSN
- 1050-4729 (ISSN-L)
- OpenAlex
- W2103465449
- Cited by
- 32
- References
- 0
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 5 · 2023: 4 · 2022: 5 · 2021: 3 · 2019: 2 · 2018: 2 · 2017: 2 · 2016: 1 · 2014: 2 · 2013: 1 · 2012: 3
- FWCI
- 1.43
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- Proceedings - IEEE International Conference on Robotics and Automation/Proceedings (publishedVersion)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Robotic Path Planning Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence in Games
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Keywords
- Theta* algorithm, grid map, least-cost path, A* algorithm
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
