Theta*: Any-Angle Path Planning on Grids

Abstract

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 unreal-istic looking, since the possible headings are artificially con-strained. We present Theta*, a variant of A*, that propagates information along grid edges without constraining the paths to grid edges. Theta * is simple, fast and finds short and real-istic looking paths. We compare Theta * against both Field D*, the only other variant of A * that propagates informa-tion 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 real-istic looking paths than either of these existing techniques.