Theta*
swMATH ID:  31693 
Software Authors:  Kenny Daniel, Alex Nash, Sven Koenig, Ariel Felner 
Description:  Theta*: AnyAngle Path Planning on Grids. 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 anyangle pathplanning algorithms that avoid this shortcoming. Basic Theta* and AnglePropagation 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. AnglePropagation Theta* achieves a better worstcase 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 AnglePropagation 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 postsmoothed 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 nonuniform traversal costs and introduce variants of Theta* which provide different tradeoffs between path length and runtime. 
Homepage:  https://arxiv.org/abs/1401.3843 
Keywords:  Computational Geometry; arXiv_cs.CG; Artificial Intelligence; arXiv_cs.AI; AnyAngle Path Planning; Grids 
Related Software:  Matlab; Visual MISER; MISER3; OpenStreetMap; BPA; COMSOL; D*Lite; OPTRAGEN; RIOTS_95; SeDuMi; Anya; Algorithm 97 
Cited in:  10 Publications 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

Theta\(^*\): anyangle path planning on grids. Zbl 1205.68373 Daniel, Kenny; Nash, Alex; Koenig, Sven; Felner, Ariel 
2010

all
top 5
Cited by 31 Authors
all
top 5
Cited in 9 Serials
all
top 5