Theta*: Any-Angle Path Planning on Grids

Alex Nash, Kenny Daniel, Sven Koenig, Ariel Felner

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 information 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.

Subjects: 15.7 Search; 15. Problem Solving

Submitted: Apr 24, 2007


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.