{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T18:15:27Z","timestamp":1775326527002,"version":"3.50.1"},"reference-count":27,"publisher":"MDPI AG","issue":"23","license":[{"start":{"date-parts":[[2022,11,26]],"date-time":"2022-11-26T00:00:00Z","timestamp":1669420800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key R&amp;D Program of China","award":["2021YFB3301400"],"award-info":[{"award-number":["2021YFB3301400"]}]},{"name":"National Key R&amp;D Program of China","award":["XLYC1907057"],"award-info":[{"award-number":["XLYC1907057"]}]},{"name":"National Key R&amp;D Program of China","award":["2021-MS-030"],"award-info":[{"award-number":["2021-MS-030"]}]},{"name":"National Key R&amp;D Program of China","award":["2022-Z03"],"award-info":[{"award-number":["2022-Z03"]}]},{"name":"LiaoNing Revitalization Talents Program","award":["2021YFB3301400"],"award-info":[{"award-number":["2021YFB3301400"]}]},{"name":"LiaoNing Revitalization Talents Program","award":["XLYC1907057"],"award-info":[{"award-number":["XLYC1907057"]}]},{"name":"LiaoNing Revitalization Talents Program","award":["2021-MS-030"],"award-info":[{"award-number":["2021-MS-030"]}]},{"name":"LiaoNing Revitalization Talents Program","award":["2022-Z03"],"award-info":[{"award-number":["2022-Z03"]}]},{"name":"Nature Science Foundation of Liaoning province","award":["2021YFB3301400"],"award-info":[{"award-number":["2021YFB3301400"]}]},{"name":"Nature Science Foundation of Liaoning province","award":["XLYC1907057"],"award-info":[{"award-number":["XLYC1907057"]}]},{"name":"Nature Science Foundation of Liaoning province","award":["2021-MS-030"],"award-info":[{"award-number":["2021-MS-030"]}]},{"name":"Nature Science Foundation of Liaoning province","award":["2022-Z03"],"award-info":[{"award-number":["2022-Z03"]}]},{"name":"State Key Laboratory of Robotics","award":["2021YFB3301400"],"award-info":[{"award-number":["2021YFB3301400"]}]},{"name":"State Key Laboratory of Robotics","award":["XLYC1907057"],"award-info":[{"award-number":["XLYC1907057"]}]},{"name":"State Key Laboratory of Robotics","award":["2021-MS-030"],"award-info":[{"award-number":["2021-MS-030"]}]},{"name":"State Key Laboratory of Robotics","award":["2022-Z03"],"award-info":[{"award-number":["2022-Z03"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/s22239203","type":"journal-article","created":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T08:13:09Z","timestamp":1669623189000},"page":"9203","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A Sampling-Based Algorithm with the Metropolis Acceptance Criterion for Robot Motion Planning"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7839-050X","authenticated-orcid":false,"given":"Yiyang","family":"Liu","sequence":"first","affiliation":[{"name":"Key Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang 110016, China"},{"name":"Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China"},{"name":"Institutes for Robotics and Intelligent Manufacturing, Chinese Academy of Sciences, Shenyang 110169, China"},{"name":"Kunshan Intelligent Equipment Research Institute, Kunshan 215300, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1182-9351","authenticated-orcid":false,"given":"Yang","family":"Zhao","sequence":"additional","affiliation":[{"name":"Key Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang 110016, China"},{"name":"Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China"},{"name":"Institutes for Robotics and Intelligent Manufacturing, Chinese Academy of Sciences, Shenyang 110169, China"},{"name":"School of Automation and Electrical Engineering, Shenyang Ligong University, Shenyang 110159, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7137-8719","authenticated-orcid":false,"given":"Shuaihua","family":"Yan","sequence":"additional","affiliation":[{"name":"Key Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang 110016, China"},{"name":"Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China"},{"name":"Institutes for Robotics and Intelligent Manufacturing, Chinese Academy of Sciences, Shenyang 110169, China"},{"name":"School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 100049, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8392-1777","authenticated-orcid":false,"given":"Chunhe","family":"Song","sequence":"additional","affiliation":[{"name":"Key Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang 110016, China"},{"name":"Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China"},{"name":"Institutes for Robotics and Intelligent Manufacturing, Chinese Academy of Sciences, Shenyang 110169, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fei","family":"Li","sequence":"additional","affiliation":[{"name":"Key Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang 110016, China"},{"name":"Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China"},{"name":"Institutes for Robotics and Intelligent Manufacturing, Chinese Academy of Sciences, Shenyang 110169, China"},{"name":"College of Information Science and Engineering, Northeastern University, Shenyang 110819, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,11,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"102322","DOI":"10.1016\/j.rcim.2022.102322","article-title":"A sampling-based motion planning method for active visual measurement with an industrial robot","volume":"76","author":"Fang","year":"2022","journal-title":"Robot. Comput.-Integr. Manuf."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"102091","DOI":"10.1016\/j.rcim.2020.102091","article-title":"Collision-free and smooth joint motion planning for six-axis industrial robots by redundancy optimization","volume":"68","author":"Lu","year":"2021","journal-title":"Robot. Comput-Integr. Manuf."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1051\/jnwpu\/20203951005","article-title":"Non-inverse kinematics of free-floating space robot based on motion planning of sampling","volume":"39","author":"Zhang","year":"2021","journal-title":"J. Northwest. Polytech. Univ."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.robot.2017.05.007","article-title":"Gait and trajectory rolling planning and control of hexapod robots for disaster rescue applications","volume":"95","author":"Deng","year":"2017","journal-title":"Robot. Auton. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"144136","DOI":"10.1109\/ACCESS.2020.3014532","article-title":"Development of a New Medical Robot System for Minimally Invasive Surgery","volume":"8","author":"Niu","year":"2020","journal-title":"IEEE Access"},{"key":"ref_6","first-page":"30","article-title":"Probabilistic anticipation and control in autonomous car following","volume":"27","author":"Wang","year":"2017","journal-title":"IEEE Trans. Control Syst. Technol."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"113425","DOI":"10.1016\/j.eswa.2020.113425","article-title":"PQ-RRT*: An improved path planning algorithm for mobile robots","volume":"152","author":"Li","year":"2020","journal-title":"Expert Syst. Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1162\/106454699568728","article-title":"Ant algorithms for discrete optimization","volume":"5","author":"Dorigo","year":"1999","journal-title":"Artif. Life"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Wang, Y., Han, T., Jiang, X., Yan, Y., and Liu, H. (2020). Path Planning of Pattern Transfer Based on Dual-Operator and a Dual-Population Ant Colony Algorithm for Digital Mask Projection Lithography. Entropy, 22.","DOI":"10.3390\/e22030295"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1177\/027836498600500106","article-title":"Real-time obstacle avoidance for manipulators and mobile robots","volume":"5","author":"Khatib","year":"1986","journal-title":"Int. J. Robot. Res."},{"key":"ref_11","unstructured":"Koren, Y., and Borenstein, J. (1991, January 9\u201311). Potential field methods and their inherent limitations for mobile robot navigation. Proceedings of the IEEE International Conference on Robotics and Automation, Sacramento, CA, USA."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.artint.2003.12.001","article-title":"Lifelong planning A*","volume":"155","author":"Koenig","year":"2004","journal-title":"Artif. Intell."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1177\/02783640122067453","article-title":"Randomized kinodynamic planning","volume":"20","author":"LaValle","year":"2001","journal-title":"Int. J. Robot. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1109\/70.508439","article-title":"Probabilistic roadmaps for path planning in high-dimensional configuration spaces","volume":"12","author":"Kavraki","year":"1996","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Wei, K., and Ren, B. (2018). A Method on Dynamic Path Planning for Robotic Manipulator Autonomous Obstacle Avoidance Based on an Improved RRT Algorithm. Sensors, 18.","DOI":"10.3390\/s18020571"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2024","DOI":"10.1109\/LRA.2018.2801881","article-title":"COLREG-RRT: An RRT-based COLREGS-compliant motion planner for surface vehicle navigation","volume":"3","author":"Chiang","year":"2018","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Tang, X., and Chen, F. (2020, January 13\u201316). Robot path planning algorithm based on Bi-RRT and potential field. Proceedings of the IEEE International Conference on Mechatronics and Automation (ICMA), Beijing, China.","DOI":"10.1109\/ICMA49215.2020.9233539"},{"key":"ref_19","unstructured":"Kuffner, J.J., and LaValle, S.M. (2000, January 24\u201328). RRT-connect: An efficient approach to single-query path planning. Proceedings of the 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065), San Francisco, CA, USA."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Kang, J.G., Lim, D.W., Choi, Y.S., Jang, W.J., and Jung, J.W. (2021). Improved RRT-Connect Algorithm Based on Triangular Inequality for Robot Path Planning. Sensors, 21.","DOI":"10.3390\/s21020333"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1177\/0278364911406761","article-title":"Sampling-based algorithms for optimal motion planning","volume":"30","author":"Karaman","year":"2011","journal-title":"Int. J. Robot. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"113124","DOI":"10.1016\/j.eswa.2019.113124","article-title":"A batch informed sampling-based algorithm for fast anytime asymptotically-optimal motion planning in cluttered environments","volume":"144","author":"Xu","year":"2020","journal-title":"Expert Syst. Appl."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Gammell, J.D., Srinivasa, S.S., and Barfoot, T.D. (2014, January 14\u201318). Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Chicago, IL, USA.","DOI":"10.1109\/IROS.2014.6942976"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.eswa.2019.01.032","article-title":"Quick-RRT*: Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate","volume":"123","author":"Jeong","year":"2019","journal-title":"Expert Syst. Appl."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"7244","DOI":"10.1109\/TIE.2020.2998740","article-title":"MOD-RRT*: A Sampling-Based Algorithm for Robot Path Planning in Dynamic Environment","volume":"68","author":"Qi","year":"2021","journal-title":"IEEE Trans. Ind. Electron."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1109\/TIV.2022.3150748","article-title":"GMR-RRT*: Sampling-Based Path Planning Using Gaussian Mixture Regression","volume":"7","author":"Wang","year":"2022","journal-title":"IEEE Trans. Intell. Veh."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"108771","DOI":"10.1016\/j.cie.2022.108771","article-title":"Feedback RRT* algorithm for UAV path planning in a hostile environment","volume":"174","author":"Guo","year":"2022","journal-title":"Comput. Ind. Eng."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/23\/9203\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:27:23Z","timestamp":1760146043000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/23\/9203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,26]]},"references-count":27,"journal-issue":{"issue":"23","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["s22239203"],"URL":"https:\/\/doi.org\/10.3390\/s22239203","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,26]]}}}