A Sampling-Based Algorithm with the Metropolis Acceptance Criterion for Robot Motion Planning
Motion planning is one of the important research topics of robotics. As an improvement of Rapidly exploring Random Tree (RRT), the RRT* motion planning algorithm is widely used because of its asymptotic optimality. However, the running time of RRT* increases rapidly with the number of potential path...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-11-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/22/23/9203 |
| _version_ | 1827642485198815232 |
|---|---|
| author | Yiyang Liu Yang Zhao Shuaihua Yan Chunhe Song Fei Li |
| author_facet | Yiyang Liu Yang Zhao Shuaihua Yan Chunhe Song Fei Li |
| author_sort | Yiyang Liu |
| collection | DOAJ |
| description | Motion planning is one of the important research topics of robotics. As an improvement of Rapidly exploring Random Tree (RRT), the RRT* motion planning algorithm is widely used because of its asymptotic optimality. However, the running time of RRT* increases rapidly with the number of potential path vertices, resulting in slow convergence or even an inability to converge, which seriously reduces the performance and practical value of RRT*. To solve this issue, this paper proposes a two-phase motion planning algorithm named Metropolis RRT* (M-RRT*) based on the Metropolis acceptance criterion. First, to efficiently obtain the initial path and start the optimal path search phase earlier, an asymptotic vertex acceptance criterion is defined in the initial path estimation phase of M-RRT*. Second, to improve the convergence rate of the algorithm, a nonlinear dynamic vertex acceptance criterion is defined in the optimal path search phase, which preferentially accepts vertices that may improve the current path. The effectiveness of M-RRT* is verified by comparing it with existing algorithms through the simulation results in three test environments. |
| first_indexed | 2024-03-09T17:32:54Z |
| format | Article |
| id | doaj.art-77c35c7f6529481da02c5277ad4a51b0 |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-03-09T17:32:54Z |
| publishDate | 2022-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-77c35c7f6529481da02c5277ad4a51b02023-11-24T12:10:14ZengMDPI AGSensors1424-82202022-11-012223920310.3390/s22239203A Sampling-Based Algorithm with the Metropolis Acceptance Criterion for Robot Motion PlanningYiyang Liu0Yang Zhao1Shuaihua Yan2Chunhe Song3Fei Li4Key Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang 110016, ChinaKey Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang 110016, ChinaKey Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang 110016, ChinaKey Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang 110016, ChinaKey Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang 110016, ChinaMotion planning is one of the important research topics of robotics. As an improvement of Rapidly exploring Random Tree (RRT), the RRT* motion planning algorithm is widely used because of its asymptotic optimality. However, the running time of RRT* increases rapidly with the number of potential path vertices, resulting in slow convergence or even an inability to converge, which seriously reduces the performance and practical value of RRT*. To solve this issue, this paper proposes a two-phase motion planning algorithm named Metropolis RRT* (M-RRT*) based on the Metropolis acceptance criterion. First, to efficiently obtain the initial path and start the optimal path search phase earlier, an asymptotic vertex acceptance criterion is defined in the initial path estimation phase of M-RRT*. Second, to improve the convergence rate of the algorithm, a nonlinear dynamic vertex acceptance criterion is defined in the optimal path search phase, which preferentially accepts vertices that may improve the current path. The effectiveness of M-RRT* is verified by comparing it with existing algorithms through the simulation results in three test environments.https://www.mdpi.com/1424-8220/22/23/9203motion planningsampling-based algorithmsRRTMetropolis acceptance criterionasymptotic optimality |
| spellingShingle | Yiyang Liu Yang Zhao Shuaihua Yan Chunhe Song Fei Li A Sampling-Based Algorithm with the Metropolis Acceptance Criterion for Robot Motion Planning Sensors motion planning sampling-based algorithms RRT Metropolis acceptance criterion asymptotic optimality |
| title | A Sampling-Based Algorithm with the Metropolis Acceptance Criterion for Robot Motion Planning |
| title_full | A Sampling-Based Algorithm with the Metropolis Acceptance Criterion for Robot Motion Planning |
| title_fullStr | A Sampling-Based Algorithm with the Metropolis Acceptance Criterion for Robot Motion Planning |
| title_full_unstemmed | A Sampling-Based Algorithm with the Metropolis Acceptance Criterion for Robot Motion Planning |
| title_short | A Sampling-Based Algorithm with the Metropolis Acceptance Criterion for Robot Motion Planning |
| title_sort | sampling based algorithm with the metropolis acceptance criterion for robot motion planning |
| topic | motion planning sampling-based algorithms RRT Metropolis acceptance criterion asymptotic optimality |
| url | https://www.mdpi.com/1424-8220/22/23/9203 |
| work_keys_str_mv | AT yiyangliu asamplingbasedalgorithmwiththemetropolisacceptancecriterionforrobotmotionplanning AT yangzhao asamplingbasedalgorithmwiththemetropolisacceptancecriterionforrobotmotionplanning AT shuaihuayan asamplingbasedalgorithmwiththemetropolisacceptancecriterionforrobotmotionplanning AT chunhesong asamplingbasedalgorithmwiththemetropolisacceptancecriterionforrobotmotionplanning AT feili asamplingbasedalgorithmwiththemetropolisacceptancecriterionforrobotmotionplanning AT yiyangliu samplingbasedalgorithmwiththemetropolisacceptancecriterionforrobotmotionplanning AT yangzhao samplingbasedalgorithmwiththemetropolisacceptancecriterionforrobotmotionplanning AT shuaihuayan samplingbasedalgorithmwiththemetropolisacceptancecriterionforrobotmotionplanning AT chunhesong samplingbasedalgorithmwiththemetropolisacceptancecriterionforrobotmotionplanning AT feili samplingbasedalgorithmwiththemetropolisacceptancecriterionforrobotmotionplanning |