Relevant Region sampling strategy with adaptive heuristic for asymptotically optimal path planning
Sampling-based planning algorithm is a powerful tool for solving planning problems in high-dimensional state spaces. In this article, we present a novel approach to sampling in the most promising regions, which significantly reduces planning time-consumption. The RRT# algorithm defines the Relevant...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2023-09-01
|
| Series: | Biomimetic Intelligence and Robotics |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S266737972300027X |
| _version_ | 1827808261203558400 |
|---|---|
| author | Chenming Li Fei Meng Han Ma Jiankun Wang Max Q.-H. Meng |
| author_facet | Chenming Li Fei Meng Han Ma Jiankun Wang Max Q.-H. Meng |
| author_sort | Chenming Li |
| collection | DOAJ |
| description | Sampling-based planning algorithm is a powerful tool for solving planning problems in high-dimensional state spaces. In this article, we present a novel approach to sampling in the most promising regions, which significantly reduces planning time-consumption. The RRT# algorithm defines the Relevant Region based on the cost-to-come provided by the optimal forward-searching tree. However, it uses the cumulative cost of a direct connection between the current state and the goal state as the cost-to-go. To improve the path planning efficiency, we propose a batch sampling method that samples in a refined Relevant Region with a direct sampling strategy, which is defined according to the optimal cost-to-come and the adaptive cost-to-go, taking advantage of various sources of heuristic information. The proposed sampling approach allows the algorithm to build the search tree in the direction of the most promising area, resulting in a superior initial solution quality and reducing the overall computation time compared to related work. To validate the effectiveness of our method, we conducted several simulations in both SE(2)and SE(3)state spaces. And the simulation results demonstrate the superiorities of proposed algorithm. |
| first_indexed | 2024-03-11T22:24:41Z |
| format | Article |
| id | doaj.art-326dec84e76e4279bbdc6ec49da51828 |
| institution | Directory Open Access Journal |
| issn | 2667-3797 |
| language | English |
| last_indexed | 2024-03-11T22:24:41Z |
| publishDate | 2023-09-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Biomimetic Intelligence and Robotics |
| spelling | doaj.art-326dec84e76e4279bbdc6ec49da518282023-09-24T05:17:16ZengElsevierBiomimetic Intelligence and Robotics2667-37972023-09-0133100113Relevant Region sampling strategy with adaptive heuristic for asymptotically optimal path planningChenming Li0Fei Meng1Han Ma2Jiankun Wang3Max Q.-H. Meng4Department of Electronic Engineering, The Chinese University of Hong Kong, Hong Kong 999077, ChinaDepartment of Electronic Engineering, The Chinese University of Hong Kong, Hong Kong 999077, ChinaDepartment of Electronic Engineering, The Chinese University of Hong Kong, Hong Kong 999077, ChinaDepartment of Electronic and Electrical Engineering, Southern University of Science and Technology, Shenzhen 518055, China; Corresponding author.Department of Electronic Engineering, The Chinese University of Hong Kong, Hong Kong 999077, China; Department of Electronic and Electrical Engineering, Southern University of Science and Technology, Shenzhen 518055, China; Shenzhen Research Institute of the Chinese University of Hong Kong, Shenzhen 518057, China; Corresponding author.Sampling-based planning algorithm is a powerful tool for solving planning problems in high-dimensional state spaces. In this article, we present a novel approach to sampling in the most promising regions, which significantly reduces planning time-consumption. The RRT# algorithm defines the Relevant Region based on the cost-to-come provided by the optimal forward-searching tree. However, it uses the cumulative cost of a direct connection between the current state and the goal state as the cost-to-go. To improve the path planning efficiency, we propose a batch sampling method that samples in a refined Relevant Region with a direct sampling strategy, which is defined according to the optimal cost-to-come and the adaptive cost-to-go, taking advantage of various sources of heuristic information. The proposed sampling approach allows the algorithm to build the search tree in the direction of the most promising area, resulting in a superior initial solution quality and reducing the overall computation time compared to related work. To validate the effectiveness of our method, we conducted several simulations in both SE(2)and SE(3)state spaces. And the simulation results demonstrate the superiorities of proposed algorithm.http://www.sciencedirect.com/science/article/pii/S266737972300027XPath planningAsymptotical optimalityRelevant RegionAdaptive heuristic |
| spellingShingle | Chenming Li Fei Meng Han Ma Jiankun Wang Max Q.-H. Meng Relevant Region sampling strategy with adaptive heuristic for asymptotically optimal path planning Biomimetic Intelligence and Robotics Path planning Asymptotical optimality Relevant Region Adaptive heuristic |
| title | Relevant Region sampling strategy with adaptive heuristic for asymptotically optimal path planning |
| title_full | Relevant Region sampling strategy with adaptive heuristic for asymptotically optimal path planning |
| title_fullStr | Relevant Region sampling strategy with adaptive heuristic for asymptotically optimal path planning |
| title_full_unstemmed | Relevant Region sampling strategy with adaptive heuristic for asymptotically optimal path planning |
| title_short | Relevant Region sampling strategy with adaptive heuristic for asymptotically optimal path planning |
| title_sort | relevant region sampling strategy with adaptive heuristic for asymptotically optimal path planning |
| topic | Path planning Asymptotical optimality Relevant Region Adaptive heuristic |
| url | http://www.sciencedirect.com/science/article/pii/S266737972300027X |
| work_keys_str_mv | AT chenmingli relevantregionsamplingstrategywithadaptiveheuristicforasymptoticallyoptimalpathplanning AT feimeng relevantregionsamplingstrategywithadaptiveheuristicforasymptoticallyoptimalpathplanning AT hanma relevantregionsamplingstrategywithadaptiveheuristicforasymptoticallyoptimalpathplanning AT jiankunwang relevantregionsamplingstrategywithadaptiveheuristicforasymptoticallyoptimalpathplanning AT maxqhmeng relevantregionsamplingstrategywithadaptiveheuristicforasymptoticallyoptimalpathplanning |