A Bidirectional Interpolation Method for Post-Processing in Sampling-Based Robot Path Planning
This paper proposes a post-processing method called bidirectional interpolation method for sampling-based path planning algorithms, such as rapidly-exploring random tree (RRT). The proposed algorithm applies interpolation to the path generated by the sampling-based path planning algorithm. In this s...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-11-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/21/21/7425 |
| _version_ | 1797511740526690304 |
|---|---|
| author | Tae-Won Kang Jin-Gu Kang Jin-Woo Jung |
| author_facet | Tae-Won Kang Jin-Gu Kang Jin-Woo Jung |
| author_sort | Tae-Won Kang |
| collection | DOAJ |
| description | This paper proposes a post-processing method called bidirectional interpolation method for sampling-based path planning algorithms, such as rapidly-exploring random tree (RRT). The proposed algorithm applies interpolation to the path generated by the sampling-based path planning algorithm. In this study, the proposed algorithm is applied to the path created by RRT-connect and six environmental maps were used for the verification. It was visually and quantitatively confirmed that, in all maps, not only path lengths but also the piecewise linear shape were decreased compared to the path generated by RRT-connect. To check the proposed algorithm’s performance, visibility graph, RRT-connect algorithm, Triangular-RRT-connect algorithm and post triangular processing of midpoint interpolation (PTPMI) were compared in various environmental maps through simulation. Based on these experimental results, the proposed algorithm shows similar planning time but shorter path length than previous RRT-like algorithms as well as RRT-like algorithms with PTPMI having a similar number of samples. |
| first_indexed | 2024-03-10T05:52:19Z |
| format | Article |
| id | doaj.art-ca8778797c9e40a2a908d66ddde16efa |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-03-10T05:52:19Z |
| publishDate | 2021-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-ca8778797c9e40a2a908d66ddde16efa2023-11-22T21:41:26ZengMDPI AGSensors1424-82202021-11-012121742510.3390/s21217425A Bidirectional Interpolation Method for Post-Processing in Sampling-Based Robot Path PlanningTae-Won Kang0Jin-Gu Kang1Jin-Woo Jung2Department of Artificial Intelligence, Dongguk University, Seoul 04620, KoreaDepartment of Computer Science and Engineering, Dongguk University, Seoul 04620, KoreaDepartment of Computer Science and Engineering, Dongguk University, Seoul 04620, KoreaThis paper proposes a post-processing method called bidirectional interpolation method for sampling-based path planning algorithms, such as rapidly-exploring random tree (RRT). The proposed algorithm applies interpolation to the path generated by the sampling-based path planning algorithm. In this study, the proposed algorithm is applied to the path created by RRT-connect and six environmental maps were used for the verification. It was visually and quantitatively confirmed that, in all maps, not only path lengths but also the piecewise linear shape were decreased compared to the path generated by RRT-connect. To check the proposed algorithm’s performance, visibility graph, RRT-connect algorithm, Triangular-RRT-connect algorithm and post triangular processing of midpoint interpolation (PTPMI) were compared in various environmental maps through simulation. Based on these experimental results, the proposed algorithm shows similar planning time but shorter path length than previous RRT-like algorithms as well as RRT-like algorithms with PTPMI having a similar number of samples.https://www.mdpi.com/1424-8220/21/21/7425bidirectional interpolation methodpost-processingRRT-connecttriangular RRT-connectmidpoint interpolationsampling-based path planning |
| spellingShingle | Tae-Won Kang Jin-Gu Kang Jin-Woo Jung A Bidirectional Interpolation Method for Post-Processing in Sampling-Based Robot Path Planning Sensors bidirectional interpolation method post-processing RRT-connect triangular RRT-connect midpoint interpolation sampling-based path planning |
| title | A Bidirectional Interpolation Method for Post-Processing in Sampling-Based Robot Path Planning |
| title_full | A Bidirectional Interpolation Method for Post-Processing in Sampling-Based Robot Path Planning |
| title_fullStr | A Bidirectional Interpolation Method for Post-Processing in Sampling-Based Robot Path Planning |
| title_full_unstemmed | A Bidirectional Interpolation Method for Post-Processing in Sampling-Based Robot Path Planning |
| title_short | A Bidirectional Interpolation Method for Post-Processing in Sampling-Based Robot Path Planning |
| title_sort | bidirectional interpolation method for post processing in sampling based robot path planning |
| topic | bidirectional interpolation method post-processing RRT-connect triangular RRT-connect midpoint interpolation sampling-based path planning |
| url | https://www.mdpi.com/1424-8220/21/21/7425 |
| work_keys_str_mv | AT taewonkang abidirectionalinterpolationmethodforpostprocessinginsamplingbasedrobotpathplanning AT jingukang abidirectionalinterpolationmethodforpostprocessinginsamplingbasedrobotpathplanning AT jinwoojung abidirectionalinterpolationmethodforpostprocessinginsamplingbasedrobotpathplanning AT taewonkang bidirectionalinterpolationmethodforpostprocessinginsamplingbasedrobotpathplanning AT jingukang bidirectionalinterpolationmethodforpostprocessinginsamplingbasedrobotpathplanning AT jinwoojung bidirectionalinterpolationmethodforpostprocessinginsamplingbasedrobotpathplanning |