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.
Contributor:
Youyu Liu
,
Wanbao Tao
,
Shunfang Li
,
Yi Li
,
Qijie Wang

The search efficiency of a rapidly exploring random tree (RRT) can be improved by introducing a high-probability goal bias strategy. In the case of multiple complex obstacles, the high-probability goal bias strategy with a fixed step size will fall into a local optimum, which reduces search efficiency.

  • 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.
On this basis, Kuffner et al. [16] proposed an RRT-connect double tree algorithm by randomly expanding paths at the same time at the start and goal nodes. It is superior to the RRT algorithm in terms of search performance. However, it is difficult to find the optimal path due to randomness. To solve this problem, scholars made some improvements to the RRT-connect algorithm. For example, based on the triangle inequality, Kang et al. [17] proposed an RRT-connect algorithm based on the triangle inequality principle by re-wiring path nodes, which has outstanding performance in terms of path length. However, there may be problems, such as non-differentiable linear sections with sharp corners and constraints with the kinematics of the manipulator. Based on the idea of dynamic step size [18], Li et al. [19] proposed a variable step size RRT (VT-RRT) by transforming the search space of random nodes in the RRT algorithm and adaptively adjusting the search step size according to the goal and the position of obstacles in the current point. This algorithm effectively reduces path planning time and optimizes sampling direction. However, it generates too many path nodes, resulting in longer paths. To improve the adverse effects of variable step size, Zhang et al. [20] proposed a path planning method for a manipulator based on the artificial potential field and bidirectional rapidly exploring random tree (BiRRT-APF) algorithm, aiming to solve the problem of low search efficiency and high randomness. However, its goal orientation is poor. Shao et al. [21] proposed a motion planning method based on the goal bias RRT algorithm (G-RRT), which reduces invalid searches by guiding the direction of random sampling. However, the one-way search is less efficient, and the resulting path is not optimal. Liu et al. [22] proposed a goal bias bidirectional rapidly exploring random tree (GBI-RRT) algorithm, which improves the success rate of node expansion. However, in complex and high-dimensional environments, this algorithm generates redundant nodes, resulting in overly complex paths. The types of path planning algorithms are shown in Table 1 below, as well as the advantages and disadvantages of each algorithm. Due to the existence of overlapping workspaces, the path planning of dual manipulators should deal with the interference of static and dynamic obstacles at the same time. In response to the above content, a sampling-based RRT path planning algorithm is adopted to improve and optimize the shortcomings of the algorithm and is deployed on a dual manipulator.
Table 1. The types of path planning algorithms.
Types Algorithms Refs. Advantages Disadvantages Reasons for Disadvantages
Based on search algorithms. Dijkstra and A*, etc. [6][7][8] Find the optimal path at a reasonable time. Large search space, high computational complexity, and poor real-time performance. In complex environments, it faces a large amount of path search calculations.
Based on rules algorithms. APF and variants, etc. [9][10][11] Fast path calculation and high real-time performance. Local optima are prone to occur. Neglecting the mutual constraints between robots.
Based on sampling algorithms. PRM and variants, etc. [13][14][15] High efficiency and real-time performance. Low reuse rate of roadmap and high memory consumption. Generating a large number of candidate paths comes with relatively high computational costs.
RRT and variants, etc. [12][16][17][18][19][20][21][22] Strong applicability, high real-time performance, high efficiency, and scalability. There are many tree nodes and poor path quality. Affected by random factors, the results may be unstable.
Regarding the aforementioned issues, this research proposes a bidirectional potential field probabilistic step-size RRT algorithm for the path planning of dual manipulators by angle selection. The main contributions of this research are as follows:
(1)
 Based on the RRT-connect algorithm and the characteristics of bidirectional searches, the high goal probability bias strategy is introduced to enable the random points to be sampled along the goal direction.
(2)
 Angle selection is used to limit the direction of dual-tree searches and avoid redundant sampling to the surrounding area.
(3) 
Based on the idea of dynamic step size, random values are innovatively used as step size parameters, and the search step size is adaptively adjusted by the dynamic changes of randomness to cope with the environment. The artificial potential field method is introduced to deal with multi-obstacle environments.
(4)
 A greedy algorithm is used for path optimization, removing redundant nodes on the path and finding the shortest path.

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

References

  1. Xu, M.; David, J.M.; Kim, S.H. The fourth industrial revolution: Opportunities and challenges. Int. J. Financ. Res. 2018, 9, 90–95.
  2. Turlapati, S.H.; Campolo, D. Towards Haptic-Based Dual-Arm Manipulation. Sensors 2022, 23, 376.
  3. Weng, W.T.; Huang, H.P.; Zhao, Y.L.; Lin, C.Y. Development of a Visual Perception System on a Dual-Arm Mobile Robot for Human-Robot Interaction. Sensors 2022, 22, 9545.
  4. Afsari, K.; Gupta, S.; Afkhamiaghda, M.; Lu, Z. Applications of collaborative industrial robots in building construction. In Proceedings of the 54th ASC Annual International Conference Proceedings, Minneapolis, MA, USA, 18–21 April 2018; pp. 472–479.
  5. Buhl, J.F.; Grønhøj, R.; Jørgensen, J.K.; Mateus, G.; Pinto, D.; Sørensen, J.K.; Bøgh, S.; Chrysostomou, D. A dual-arm collaborative robot system for the smart factories of the future. Procedia Manuf. 2019, 38, 333–340.
  6. Wang, H.; Yu, Y.; Yuan, Q. Application of Dijkstra Algorithm in Robot Path-Planning. In Proceedings of the 2011 Second International Conference on Mechanic Automation and Control Engineering, Hohhot, China, 15–17 July 2011; pp. 1067–1069.
  7. Bayili, S.; Polat, F. Limited-Damage A*: A path search algorithm that considers damage as a feasibility criterion. Knowl.-Based Syst. 2011, 24, 501–512.
  8. Qing, G.; Zheng, Z.; Yue, X. Path-Planning of Automated Guided Vehicle Based on Improved Dijkstra Algorithm. In Proceedings of the 2017 29th Chinese Control and Decision Conference (CCDC), Chongqing, China, 28–30 May 2017; pp. 7138–7143.
  9. Warren, C.W. Global Path Planning Using Artificial Potential Fields. In Proceedings of the 1989 International Conference on Robotics and Automation, Scottsdale, AZ, USA, 14–19 May 1989; pp. 316–321.
  10. Ge, S.S.; Cui, Y.J. Dynamic motion planning for mobile robots using potential field method. Auton. Robot. 2002, 13, 207–222.
  11. Xia, X.; Li, T.; Sang, S.; Cheng, Y.; Ma, H.; Zhang, Q.; Yang, K. Path Planning for Obstacle Avoidance of Robot Arm Based on Improved Potential Field Method. Sensors 2023, 23, 3754.
  12. Rodriguez, S.; Tang, X.; Lien, J.M.; Amato, N.M. An Obstacle-Based Rapidly-Exploring Random Tree. In Proceedings of the 2006 IEEE International Conference on Robotics and Automation, ICRA 2006, Orlando, FL, USA, 15–19 May 2006; pp. 895–900.
  13. Sánchez, G.; Latombe, J.C. On delaying collision checking in PRM planning: Application to multi-robot coordination. Int. J. Robot. Res. 2002, 21, 5–26.
  14. Li, Q.; Xu, Y.; Bu, S.; Yang, J. Smart vehicle path planning based on modified PRM algorithm. Sensors 2022, 22, 6581.
  15. Liu, Y.Y.; Chen, B.; Zhang, X.Y.; Li, R.J. Research on the Dynamic Path Planning of Manipulators Based on a Grid-Local Probability Road Map Method. IEEE Access 2021, 9, 101186–101196.
  16. Kuffner, J.; LaValle, S.M. RRT-Connect: An Efficient Approach to Single-Query Path Planning. In Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA, USA, 24–28 April 2000; pp. 473–479.
  17. Kang, J.-G.; Lim, D.-W.; Choi, Y.-S.; Jang, W.-J.; Jung, J.-W. Improved RRT-connect algorithm based on triangular inequality for robot path planning. Sensors 2021, 21, 333.
  18. Zhang, Z.; Wu, D.F.; Gu, J.D.; Li, F.S. A Path-Planning Strategy for Unmanned Surface Vehicles Based on an Adaptive Hybrid Dynamic Stepsize and Target Attractive Force-RRT Algorithm. J. Mar. Sci. Eng. 2019, 7, 132.
  19. Li, Z.; Ma, H.; Zhang, X.; Fei, Q. Path Planning of the Dual-Arm Robot Based on VT-RRT Algorithm. In Proceedings of the 2019 Chinese Control Conference (CCC), Guangzhou, China, 27–30 July 2019; pp. 4359–4364.
  20. Zhang, N.; Cui, C.; Wu, G. Path planning of a 5-dof robotic arm based on BiRRT-APF algorithm considering obstacle avoidance. Proc. Inst. Mech. Eng. Part C J. Mech. Eng. Sci. 2022, 236, 9282–9292.
  21. Shao, J.; Xiong, H.; Liao, J.; Song, W.; Chen, Z.; Gu, J.; Zhu, S. RRT-GoalBias and Path Smoothing Based Motion Planning of Mobile Manipulators with Obstacle Avoidance. In Proceedings of the 2021 IEEE International Conference on Real-Time Computing and Robotics (RCAR), Xining, China, 15–19 July 2021; pp. 217–222.
  22. Liu, H.; Zhang, X.; Wen, J.; Wang, R.; Chen, X. Goal-biased bidirectional RRT based on curve-smoothing. IFAC-Pap. 2019, 52, 255–260.
More
© 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.
This entry is offline, you can click here to edit this entry!
Video Production Service
Feedback