BTO-RRT:点群データを直接用いる高速・最適・滑らかな経路計画アルゴリズム
BTO-RRT: A rapid, optimal, smooth and point cloud-based path planning algorithm
点群環境でロボットの経路計画を行うため、双方向RRT-connectとk-d木による障害物回避、3段階最適化を組み合わせ、3Dマップの離散化を経ずに点群を直接使って滑らかで動的に実行可能な経路を生成する手法を提案した。
著者: Zhaoliang Zheng, Thomas R. Bewley, Falko Kuester, Jiaqi Ma
分類: cs.RO, cs.SY, eess.SY
原文アブストラクト
This paper explores a rapid, optimal smooth path-planning algorithm for robots (e.g., autonomous vehicles) in point cloud environments. Derivative maps such as dense point clouds, mesh maps, Octomaps, etc. are frequently used for path planning purposes. A bi-directional target-oriented point planning algorithm, directly using point clouds to compute the optimized and dynamically feasible trajectories, is presented in this paper. This approach searches for obstacle-free, low computational cost, smooth, and dynamically feasible paths by analyzing a point cloud of the target environment, using a modified bi-directional and RRT-connect-based path planning algorithm, with a k-d tree-based obstacle avoidance strategy and three-step optimization. This presented approach bypasses the common 3D map discretization, directly leveraging point cloud data and it can be separated into two parts: modified RRT-based algorithm core and the three-step optimization. Simulations on 8 2D maps with different configurations and characteristics are presented to show the efficiency and 2D performance of the proposed algorithm. Benchmark comparison and evaluation with other RRT-based algorithms like RRT, B-RRT, and RRT star are also shown in the paper. Finally, the proposed algorithm successfully achieved different levels of mission goals on three 3D point cloud maps with different densities. The whole simulation proves that not only can our algorithm achieves a better performance on 2D maps compared with other algorithms, but also it can handle different tasks(ground vehicles and UAV applications) on different 3D point cloud maps, which shows the high performance and robustness of the proposed algorithm. The algorithm is open-sourced at \url{https://github.com/zhz03/BTO-RRT}
