Citation: Liu, Y.; Zhao, Y.; Yan, S.;
Song, C.; Li, F. A Sampling-Based
Algorithm with the Metropolis
Acceptance Criterion for Robot
Motion Planning. Sensors 2022, 22,
9203. https://doi.org/10.3390/
s22239203
Academic Editors: Luis Payá, Oscar
Reinoso García and Helder Jesus
Araújo
Received: 21 October 2022
Accepted: 23 November 2022
Published: 26 November 2022
Publisher’s Note: MDPI stays neutral
with regard to jurisdictional claims in
published maps and institutional affil-
iations.
Copyright: © 2022 by the authors.
Licensee MDPI, Basel, Switzerland.
This article is an open access article
distributed under the terms and
conditions of the Creative Commons
Attribution (CC BY) license (https://
creativecommons.org/licenses/by/
4.0/).
Article
A Sampling-Based Algorithm with the Metropolis Acceptance
Criterion for Robot Motion Planning
Yiyang Liu
1,2,3,4
, Yang Zhao
1,2,3,5,
* , Shuaihua Yan
1,2,3,6
, Chunhe Song
1,2,3,
* and Fei Li
1,2,3,7
1
Key Laboratory of Networked Control Systems, Chinese Academy of Sciences, Shenyang 110016, China
2
Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China
3
Institutes for Robotics and Intelligent Manufacturing, Chinese Academy of Sciences, Shenyang 110169, China
4
Kunshan Intelligent Equipment Research Institute, Kunshan 215300, China
5
School of Automation and Electrical Engineering, Shenyang Ligong University, Shenyang 110159, China
6
School of Computer Science and Technology, University of Chinese Academy of Sciences,
Beijing 100049, China
7
College of Information Science and Engineering, Northeastern University, Shenyang 110819, China
* Correspondence: zhaoyang2@sia.cn (Y.Z.); songchunhe@sia.cn (C.S.)
Abstract:
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.
Keywords:
motion planning; sampling-based algorithms; RRT; Metropolis acceptance criterion;
asymptotic optimality
1. Introduction
Robotics is evolving rapidly and has dramatically improved the efficiency of industrial
production and the convenience of people’s lives. Motion planning is indispensable in
robotics, which requires finding a feasible path from the initial state to the target state
subject to obstacle avoidance constraints. Nowadays, motion planning has been widely
applied to various robots, including but not limited to industrial robots [
1
,
2
], free-floating
space robots [3], rescue robots [4], medical robots [5], and autonomous vehicles [6].
According to the research order and fundamental principles, various motion planning
algorithms can be mainly divided into four categories: bionic algorithms, artificial potential
field methods, grid-based searches, and sampling-based algorithms [
7
]. The ant colony
algorithm [
8
], one of the representative bionic algorithms, draws a lesson from the behavior
of ants exploring paths to find food, showing strong robustness. However, it has the
problems of slow convergence and a poor quality of the solution when dealing with large-
scale problems [
9
]. The artificial potential field (APF) [
10
] method assumes a gravitational
force of the goal state and repulsive forces of the obstacles. By calculating their resultant
force, the following motion state of the moving object can be determined. Though APF has
a simple structure and a small amount of computation, it is faced with the disadvantages of
a local minimum value, large path oscillations, and complex path searches between similar
Sensors 2022, 22, 9203. https://doi.org/10.3390/s22239203 https://www.mdpi.com/journal/sensors
