Title :
Fast any-angle path planning on grid maps with non-collision pruning
Author :
Choi, Sunglok ; Lee, Jae-Yeong ; Yu, Wonpil
Author_Institution :
Robot & Cognitive Syst. Res. Dept., Electron. & Telecommunica tions Res. Inst. (ETRI), Daejeon, South Korea
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.
Keywords :
collision avoidance; mobile robots; Bresenham algorithm; Theta; any-angle path planning; cell expansion; collision test; grid maps; noncollision pruning; over-cautious pruning; zig-zag pattern; Acceleration; Biological system modeling; Cost function; Euclidean distance; Path planning; Roads; Robots;
Conference_Titel :
Robotics and Biomimetics (ROBIO), 2010 IEEE International Conference on
Conference_Location :
Tianjin
Print_ISBN :
978-1-4244-9319-7
DOI :
10.1109/ROBIO.2010.5723473