Lazy theta*: Any-angle path planning and path length analysis in 3d

Grids with blocked and unblocked cells are often used to rep-resent continuous 2D and 3D environments in robotics and video games. The shortest paths formed by the edges of 8-neighbor 2D grids can be up to ≈ 8 % longer than the short-est paths in the continuous environment. Theta * typically finds much shorter paths than that by propagating informa-tion along graph edges (to achieve short runtimes) without constraining paths to be formed by graph edges (to find short “any-angle ” paths). We show in this paper that the short-est paths formed by the edges of 26-neighbor 3D grids can be ≈ 13 % longer than the shortest paths in the continuous environment, which highlights the need for smart path plan-ning algorithms in 3D. Theta * can be applied to 3D grids in a straight-forward manner, but it performs a line-of-sight check for each unexpanded visible neighbor of each expanded vertex and thus it performs many more line-of-sight checks per expanded vertex on a 26-neighbor 3D grid than on an 8-neighbor 2D grid. We therefore introduce Lazy Theta*, a variant of Theta * which uses lazy evaluation to perform only one line-of-sight check per expanded vertex (but with slightly more expanded vertices). We show experimentally that Lazy Theta * finds paths faster than Theta * on 26-neighbor 3D grids, with one order of magnitude fewer line-of-sight checks and without an increase in path length