ETRI-Knowledge Sharing Plaform



논문 검색
구분 SCI
연도 ~ 키워드


학술대회 Fast Any-angle Path Planning on Grid Maps with Non-collision Pruning
Cited 21 time in scopus Download 0 time Share share facebook twitter linkedin kakaostory
최성록, 이재영, 유원필
International Conference on Robotics and Biomimetics (ROBIO) 2010, pp.1051-1056
10MC4100, u-Robot 인지인프라 기술개발(주관 : u-City 환경기반 하이브리드 u-로봇 서비스 시스템 기술개발), 유원필
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 제안 키워드
Collision test, Computing time, Early Termination, Grid Map, Zig-zag, cell expansion, path planning, search region