Fast any-angle path planning on grid maps with non-collision pruning

A* on grid maps generates a path with zig-zag pattern as shown in Figure 1(a). Theta* had been proposed to produce a natural and shorter path as shown in Figure 1(b). However, it needs to perform a collision test at every cell expansion. The collision test significantly degrades computing time of Theta*. This paper proposes two pruning schemes to accelerate the collision test in Theta*: non-collision pruning and over-cautious pruning. During expanding search region, previously visited cells can entail the test result before it reaches the last cell. This paper investigates conditions which lead to such early termination. The conditions are easily incorporated with a fast collision test, Bresenham's algorithm. We performed experiments on two different types of maps: random and real maps. On real maps, the pruning schemes accelerated Theta* around two times.