Theta*: Any-Angle Path Planning on Grids

By Alex Nash, Kenny Daniel, Sven Koenig, Ariel Felner. AAAI Conference on Artificial Intelligence, 2007

877 citations recorded by the source corpus.

Grids with blocked and unblocked cells are often used to represent terrain in computer games and robotics. However, paths formed by grid edges can be sub-optimal and unrealistic looking, since the possible headings are artificially constrained. We present Theta*, a variant of A*, that propagates informati on along grid edges without constraining the paths to grid edges. Theta* is simple, fast and finds short and realistic looking paths. We compare Theta* against both Field D*, the only other variant of A* that propagates information along grid edges without constraining the paths to grid edges, and A* with post-smoothed paths. Although neither path planning method is guaranteed to find shortest paths, we show experimentally that Theta* finds shorter and more realistic looking paths than either of these existing techniques.

Subfields: Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/34d4111436c1dbdff9ed612045d8516c2ee42eb0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Path Planning for the Mobile Robot: A Review (2018, background): “Liu et al. [29] presented a GA with two-layer encoding to settle the path planning.”
Path Planning for Autonomous Mobile Robots: A Review (2021, background): “Nash et al. [171] created Theta* for this purpose.”
A constrained A* approach towards optimal path planning for an unmanned surface vehicle in a maritime environment containing dynamic obstacles and ocean currents (2018, background): “A modiﬁed A* algorithm, Theta*, for search in 3D Euclidean space at all orientation was implemented for USV path planning complying with heading angle of USV and compared with conventional grid based 3D path planners (Kim et al., 2012).”
Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments (2010, methodology): “Much of the prior work on search algorithms for path planning (Ersson and Hu 2001 Koenig and Likhachev 2002 Ferguson and Stentz 2005 Nash et al. 2007) yields fast algorithms for discrete state spaces, but those algorithms tend to produce paths that are nonsmooth and do not generally satisfy the…”
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles (2016, background): “ization of the conﬁguration space is that the resulting optimal path on such graph may be signiﬁcantly longer than the true shortest path in the conﬁguration space. Any-angle path planning algorithms [120]–[122] are designed to operate on grids, or more generally on graphs representing cell decompos”
A Comprehensive Review of Coverage Path Planning in Robotics Using Classical and Heuristic Algorithms (2021, methodology): “Thus, the Theta algorithm is based on any angle pathfinding solver [180], and the Lazy Theta algorithm can address the limitation.”