BROWSE
Detail
Conference Paper
Fast Any-angle Path Planning on Grid Maps with Non-collision Pruning
Cited 22 time in 
Share 
Share
- Authors
- Sung Lok Choi, Jae Yeong Lee, Won Pil Yu
- Issue Date
- 2010-12
- Citation
- International Conference on Robotics and Biomimetics (ROBIO) 2010, pp.1051-1056
- Language
- English
- Type
- Conference Paper
- Abstract
- 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. © 2010 IEEE.
- KSP Keywords
- Collision test, Computing time, Early Termination, Grid Map, Zig-zag, cell expansion, path planning, search region