격자 지도의 골격화를 이용한 Informed RRT* 기반 경로계획 기법의 개선
Improved Path Planning Algorithm based on Informed RRT* using Gridmap Skeletonization
0
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
RRT* (Rapidly exploring Random Tree*) based algorithms are widely used for path planning. Informed RRT* uses RRT* for generating an initial path and optimizes the path by limiting sampling regions to the area around the initial path. RRT* algorithms have several limitations such as slow convergence speed, large memory requirements, and difficulties in finding paths when narrow aisles or doors exist. In this paper, we propose an algorithm to deal with these problems. The proposed algorithm applies the image skeletonization to the gridmap image for generating an initial path. Because this initial path is close to the optimal cost path even in the complex environments, the cost can converge to the optimum more quickly in the proposed algorithm than in the conventional Informed RRT*. Also, we can reduce the number of nodes and memory requirement. The performance of the proposed algorithm is verified by comparison with the conventional Informed RRT* and Informed RRT* using initial path generated by A*.
Abstract
RRT* (Rapidly exploring Random Tree*) based algorithms are widely used for path planning. Informed RRT* uses RRT* for generating an initial path and optimizes the path by limiting sampling regions to the area around the initial path. RRT* algorithms have several limitations such as slow convergence speed, large memory requirements, and difficulties in finding paths when narrow aisles or doors exist. In this paper, we propose an algorithm to deal with these problems. The proposed algorithm applies the image skeletonization to the gridmap image for generating an initial path. Because this initial path is close to the optimal cost path even in the complex environments, the cost can converge to the optimum more quickly in the proposed algorithm than in the conventional Informed RRT*. Also, we can reduce the number of nodes and memory requirement. The performance of the proposed algorithm is verified by comparison with the conventional Informed RRT* and Informed RRT* using initial path generated by A*.
참고문헌 (27)
- M. Elbanhawi, "Sampling-Based Robot Motion Planning: A Review", IEEE Access, 2, pp.56~77 (2014)[DOI]
- S. M. LaValle, "Randomized Kinodynamic Planning", The International Journal of Robotics Research, 20(5), pp.378~400 (2001)[DOI]
- S. Karaman, "Sampling-based algorithms for optimal motion planning", The International Journal of Robotics Research, 30(7), pp.846~894 (2011)[DOI]
- I. Noreen, "Optimal Path Planning using RRT* based Approaches: A Survey and Future Directions", International Journal of Advanced Computer Science and Applications, 7, pp.11~ (2016)
- J. D. Gammell, "Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic", 2014 IEEE, 2014, 2997~3004
- P. E. Hart, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics, 4(2), pp.100~107 (1968)[DOI]
- J. Borenstein, "Real-time obstacle avoidance for fast mobile robots", IEEE Transactions on Systems, Man, and Cybernetics, 19(5), pp.1179~1187 (1989)[DOI]
- H. Choset, "Sensor based planning. I. The generalized Voronoi graph", 1995 IEEE International Conference on Robotics and Automation, pp.1649~1655 (1995)
- L. E. Kavraki, "Probabilistic roadmaps for path planning in high-dimensional configuration spaces", IEEE Transactions on Robotics and Automation, 12(4), pp.566~580 (1996)[DOI]
- J. Denny, "MARRT: Medial Axis biased rapidly-exploring random trees", 2014 IEEE International Conference on Robotics and Automation, pp.90~97 (2014)
- Y. Dong, "Faster RRT-based Nonholonomic Path Planning in 2D Building Environments Using Skeleton-constrained Path Biasing", Journal of Intelligent & Robotic Systems, 89(3-4), pp.387~401 (2017)
- O. Adiyatov, "Rapidly-exploring random tree based memory efficient motion planning", 2013 IEEE International Conference on Mechatronics and Automation, pp.354~359 (2013)
- J. Nasir, "RRT*-SMART: A Rapid Convergence Implementation of RRT*", International Journal of Advanced Robotic Systems, 10(7), pp.299~ (2013)[DOI]
- D. Kim, "Cloud RRT∗: Sampling Cloud based RRT∗", 2014 IEEE International Conference on Robotics and Automation, pp.2519~2526 (2014)
- N. Amenta, "The Crust and the <TEX>${\beta}$<", TEX>-Skeleton: Combinatorial Curve Reconstruction, 1998, pp.60(2), 125~135
- O. Sharma, "Voronoi Diagram Based Automated Skeleton Extraction from Colour Scanned Maps", 2006 3rd International Symposium on Voronoi Diagrams in Science and Engineering, pp.186~195 (2006)
- P. Maragos, "Morphological skeleton representation and coding of binary images", IEEE Transactions on Acoustics, Speech, and Signal Processing, 34(5), pp.1228~1244 (1986)[DOI]
- T. Y. Zhang, "A fast parallel algorithm for thinning digital patterns", Communications of the ACM, 27(3), pp.236~239 (1984)[DOI]
- Z. Guo, "Parallel thinning with two-subiteration algorithms", Communications of the ACM, 32(3), pp.359~373 (1989)[DOI]
- G. Goyal, "Skeleton Generation for Digital Images Based on Performance Evaluation Parameters", International Journal of Signal Processing, Image Processing and Pattern Recognition, 9(2), pp.47~58 (2016)
- "Radish: The robotics data set repository"[URL]
- C. Harris, "A Combined Corner and Edge Detector", 1988 Alvey Vision Conference, pp.23.1~23.6 (1988)
- R. C. Prim, "Shortest Connection Networks And Some Generalizations", The Bell System Technical Journal, 36(6), pp.1389~1401 (1957)[DOI]
- J. B. Kruskal, "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem", American Mathematical Society, 7(1), pp.48~50 (1956)
- 이희범, "샘플링 기법의 보완을 통한 RRT 기반 온라인 이동 계획의 성능 개선", 제어.로봇.시스템학회 논문지, 22(3), pp.192~198 (2016), 제어·로봇·시스템학회[DOI]
- T. C. Lee, "Building Skeleton Models via 3-D Medial Surface Axis Thinning Algorithms", CVGIP: Graphical Models and Image Processing, 56(6), pp.462~478 (1994)[DOI]
- I. Sipiran, "Harris 3D: a robust extension of the Harris operator for interest point detection on 3D meshes", The Visual Computer, 27(11), pp.963~976 (2011)[DOI]