Rapidly Exploring Random Tree for a Dual Manipulator

Rapidly Exploring Random Tree for a Dual Manipulator: History

View Latest Version

Please note this is an old version of this entry, which may differ significantly from the current revision.

Subjects: Engineering, Mechanical

Contributor:

通过引入高概率目标偏差策略可以提高快速探索随机树（RRT）的搜索效率。在存在多个复杂障碍的情况下，具有固定步长的高概率目标偏差策略将落入局部最优，从而降低搜索效率。

dual manipulator
rapidly exploring random trees
angle selection

1. Introduction

Path planning is an essential component of robot motion planning and is a research hotspot in the field of robotics and other related intelligent fields [1]. Among them, the manipulator, as an important industrial robot, has autonomy and intelligence levels that are crucial for improving production efficiency and quality. Path planning can help the manipulator automatically plan the optimal path, reduce dependence on staff, and improve the autonomy of the manipulator. Path planning can be flexibly adjusted and optimized according to different task characteristics, thereby improving the motion accuracy and speed of the manipulator, which directly affects production efficiency and quality. Compared with a single manipulator, the form of a dual manipulator collaborative operation can meet the needs of complex, intelligent, and compliant modern industrial systems, and dual manipulators have more advantages in efficiency and performance [2,3] and are gradually gaining attention in the industry. Path planning for dual manipulators is an important work of collaborative operations [4]. To enhance the adaptability and flexibility of dual-manipulator systems, it is necessary to flexibly adjust and optimize paths based on various production environments and task requirements. The equipment transformation and upgrading of production lines are of great significance, but there are high requirements for efficiency, real-time performance, and safety in collaborative operations [5]. To address these challenges, researchers are continuously developing and improving various path planning methods for dual manipulators to enhance their efficiency and precision and meet different demands in industrial production environments. Therefore, different path planning algorithms need to be designed or selected for various fields to achieve the goal of fast matching and application.

2. Rapidly Exploring Random Tree for a Dual Manipulator

The classic 3D path planning algorithms for robots can be roughly divided into three categories. The first type of path planning algorithm is based on searches, such as Dijkstra and A* algorithms [6,7]. This algorithm is based on a graph structure in which each node represents the robot’s location, and each edge represents its movement path. By searching through the graph structure and calculating a heuristic function for each node to evaluate the distance to the endpoint, the optimal path is found. Qing et al. [8] proposed an improved Dijkstra algorithm that saves all equidistant shortest paths during the path search process, although it can solve several shortest path planning problems; in some cases, it may be difficult to obtain the complete graph structure, and there are issues such as large search space, high computational complexity, and poor real-time performance.

The second type of path planning algorithm is based on rules, such as the artificial potential field method [9,10]. The main idea is to design an artificial potential field to simulate the perception and decision-making process of the robot during movement and achieve path planning. The artificial potential field method has the advantages of simple algorithm implementation, easy understanding and use, rapid calculation of robot movement paths, and high real-time performance. Therefore, Xia et al. [11] proposed an improved velocity potential field (IVPF) algorithm based on the artificial potential field method to address the inherent drawbacks of traditional algorithms. However, utilizing tangential velocity to avoid local minimum problems leads to poor path quality. The artificial potential field method only considers the relationship between the robot and obstacles, ignoring the constraints among robots themselves, which may lead to locally optimal solutions in some cases.

To address this issue, the third type of path planning algorithm based on sampling is widely applied in various fields, such as the rapidly exploring random tree (RRT) [12] and probabilistic roadmap (PRM) [13]. The main idea is to search for the optimal feasible path through random sampling in the environment. Sampling-based algorithms are not limited by the type of environment and can be applied to path planning problems in various complex environments, with high robustness and reliability. Li et al. [14] improved the PRM algorithm by using a pseudorandom sampling strategy with the spatial principal axis as a reference axis and optimized the path using Bezier curves. However, the roadmap construction rate is unstable in three-dimensional environments. Liu et al. [15] proposed a grid-local PRM method, which has high efficiency and real-time performance. However, this type of algorithm has weak scalability and a low roadmap reuse rate. To address this issue, the RRT algorithm and its variations have been proposed. The RRT algorithm has wide applicability, high efficiency, strong scalability, good determinism, and real-time computation, which effectively solves the path planning problem with high-dimensional space constraints. As a result, the RRT algorithm has become one of the most commonly used and effective algorithms in path planning.

在此基础上，Kuffner等人[16]通过在起点节点和目标节点同时随机扩展路径，提出了一种RRT连接双树算法。它在搜索性能方面优于RRT算法。但是，由于随机性，很难找到最佳路径。为了解决这个问题，学者们对RRT连接算法进行了一些改进。例如，Kang等人[17]基于三角形不等式原理，通过重新布线路径节点，提出了一种基于三角形不等式原理的RRT连接算法，该算法在路径长度方面具有出色的性能。但是，可能存在问题，例如具有尖角的不可微分线性部分和机械手运动学的约束。基于动态步长[18]的思想，Li等人[19]通过在RRT算法中变换随机节点的搜索空间，并根据目标和当前点中障碍物的位置自适应调整搜索步长，提出了一种可变步长RRT（VT-RRT）。该算法有效减少了路径规划时间，优化了采样方向。但是，它会生成太多路径节点，从而导致路径更长。为了改善可变步长带来的不利影响，Zhang等[20]提出了一种基于人工势场和双向快速探索随机树（BiRRT-APF）算法的机械手路径规划方法，旨在解决搜索效率低、随机性高的问题。但是，它的目标导向很差。Shao等人[21]提出了一种基于目标偏差RRT算法（G-RRT）的运动规划方法，该方法通过引导随机抽样的方向来减少无效搜索。但是，单向搜索效率较低，并且生成的路径不是最佳的。Liu等[22]提出了一种目标偏差双向快速探索随机树（GBI-RRT）算法，提高了节点扩展的成功率。但是，在复杂和高维环境中，该算法会产生冗余节点，导致路径过于复杂。路径规划算法的类型如下表1所示，以及每种算法的优缺点。由于存在重叠的工作空间，双机械手的路径规划应同时应对静态和动态障碍物的干扰。针对上述内容，采用基于采样的RRT路径规划算法来改进和优化算法的不足，并部署在双机械手上。

表 1.路径规划算法的类型。

类型	算法	裁判。	优势	弊	缺点的原因
基于搜索算法。	迪克斯特拉和A*等。	[6，7，8]	在合理的时间找到最佳路径。	搜索空间大，计算复杂度高，实时性能差。	在复杂的环境中，它面临着大量的路径搜索计算。
基于规则算法。	APF 和变体等	[9，10，11]	快速路径计算和高实时性能。	局部最优很容易发生。	忽略了机器人之间的相互约束。
基于采样算法。	PRM和变体等	[13，14，15]	高效率和实时性能。	路线图重用率低，内存消耗高。	生成大量候选路径需要相对较高的计算成本。
基于采样算法。	RRT和变体等	[12，16，17，18，19，20，21，22 ]	适用性强，实时性高，效率高，可扩展性强。	树节点多，路径质量差。	受随机因素影响，结果可能不稳定。

针对上述问题，提出一种双向势场概率步长RRT算法，用于双机械手的角度选择路径规划。本文的主要贡献如下：

(1): 基于RRT连接算法和双向搜索特性，引入高目标概率偏差策略，使随机点沿目标方向进行采样。
(2): 角度选择用于限制双树搜索的方向，避免对周围区域的冗余采样。
(3): 基于动态步长思想，创新性地将随机值作为步长参数，并通过随机性的动态变化自适应调整搜索步长以应对环境。引入人工势场法应对多障碍环境。
(4): 贪婪算法用于路径优化，去除路径上的冗余节点并找到最短路径。

This entry is adapted from the peer-reviewed paper 10.3390/s23115172

© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.