Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-13T11:26:18.920Z Has data issue: false hasContentIssue false
  • English
  • Français

ADD-RRV for motion planning in complex environments

Published online by Cambridge University Press:  14 May 2021

Peng Cai Open the ORCID record for Peng Cai [Opens in a new window] ,
Xiaokui Yue  and
Hongwen Zhang
Peng Cai
Affiliation:
National Key Laboratory of Aerospace Flight Dynamics, Northwestern Polytechnical University, Xi’an 710072, P. R. China
Xiaokui Yue*
Affiliation:
National Key Laboratory of Aerospace Flight Dynamics, Northwestern Polytechnical University, Xi’an 710072, P. R. China
Hongwen Zhang
Affiliation:
National Key Laboratory of Aerospace Flight Dynamics, Northwestern Polytechnical University, Xi’an 710072, P. R. China
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we present a novel sampling-based motion planning method in various complex environments, especially with narrow passages. We use online the results of the planner in the ADD-RRT framework to identify the types of the local configuration space based on the principal component analysis (PCA). The identification result is then used to accelerate the expansion similar to RRV around obstacles and through narrow passages. We also propose a modified bridge test to identify the entrance of a narrow passage and boost samples inside it. We have compared our method with known motion planners in several scenarios through simulations. Our method shows the best performance across all the tested planners in the tested scenarios.

Keywords

Motion planningComplex environmentsLocal space identificationPrincipal component analysisBridge test
Type
Article
Information
Robotica , Volume 40 , Issue 1 , January 2022 , pp. 136 - 153
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Rasekhipour, Y., Khajepour, A., Chen, S. K. and Litkouhi, B., “A potential field-based model predictive path-planning controller for autonomous road vehicles,” IEEE Trans. Intell. Transp. Syst. 18(5), 1255–1267 (2016).CrossRefGoogle Scholar
Li, D., Li, Q., Cheng, N. and Song, J., “Extended RRT-based Path Planning for Flying Robots in Complex 3D Environments with Narrow Passages,” IEEE International Conference on Automation Science and Engineering (CASE) (2012) pp. 1173–1178.Google Scholar
Rybus, T., “Point-to-point motion planning of a free-floating space manipulator using the rapidly-exploring random trees (RRT) method,” Robotica, 38(6), 957–982 (2020).CrossRefGoogle Scholar
McEvoy, M., Komendera, E. and Correll, N., “Assembly Path Planning for Stable Robotic Construction,” IEEE International Conference on Technologies for Practical Robot Applications (TePRA) (2014) pp. 1–6.Google Scholar
Vonásek, V. and Kozlíková, B., “Tunnel Detection in Protein Structures Using Sampling-based Motion Planning,” 11th International Workshop on Robot Motion and Control (RoMoCo) (2017) pp. 185–192.Google Scholar
Hart, P. E., Nilsson, N. J. and Raphael, B., “A formal basis for the heuristic determination of minimum cost paths,” IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968).Google Scholar
Khatib, O., “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots,” Proceedings of the IEEE International Conference on Robotics and Automation (1985) pp. 500–505.Google Scholar
Hosseininejad, S. and Dadkhah, C., “Mobile robot path planning in dynamic environment based on cuckoo optimization algorithm,” Int. J. Adv. Robot. Syst. 16(2), 1–13 (2019).CrossRefGoogle Scholar
LaValle, S. M., Planning Algorithms (Cambridge University Press, Cambridge, England, United Kingdom, 2006).CrossRefGoogle Scholar
Kavraki, L. E., Svestka, P., Latombe, J.-C. and Overmars, M. H., “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robot. Automat. 12(4), 566–580 (1996).CrossRefGoogle Scholar
LaValle, S. M., “Rapidly-exploring random trees: A new tool for path planning,” TR 98-11 (Computer Science Department, Iowa State University, 1998).Google Scholar
Hsu, D., Latombe, J.-C. and Kurniawati, H., “On the probabilistic foundations of probabilistic roadmap planning,” Int. J. Robot. Res. 25(7), 627–643 (2006).CrossRefGoogle Scholar
Hsu, D., Kavraki, L. E., Latombe, J.-C., Motwani, R. and Sorkin, S., “On Finding Narrow Passages with Probabilistic Roadmap Planners,” Robotics: the Algorithmic Perspective: 1998 Workshop on the Algorithmic Foundations of Robotics (1998) pp. 141–154.Google Scholar
Boor, V., Overmars, M. H. and Van Der Stappen, A. F., “The Gaussian Sampling Strategy for Probabilistic Roadmap Planners,” Proceedings of the IEEE International Conference on Robotics and Automation (1999) pp. 1018–1023.Google Scholar
Hsu, D., Jiang, T., Reif, J. and Sun, Z., “The Bridge Test for Sampling Narrow Passages with Probabilistic Roadmap Planners,” Proceedings of the IEEE International Conference on Robotics and Automation (2003) pp. 4420–4426.Google Scholar
Yershova, A., Jaillet, L., Siméon, T. and LaValle, S. M., “Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain,” Proceedings of the IEEE International Conference on Robotics and Automation (2005) pp. 3856–3861.Google Scholar
Jaillet, L., Yershova, A., La Valle, S. M. and Siméon, T., “Adaptive Tuning of the Sampling Domain for Dynamic-Domain RRTs,” IEEE/RSJ International Conference on Intelligent Robots and Systems (2005) pp. 2851–2856.Google Scholar
Zhang, L. and Manocha, D., “An Efficient Retraction-based RRT Planner,” Proceedings of the IEEE International Conference on Robotics and Automation (2008) pp. 3743–3750.Google Scholar
Wilmarth, S. A., Amato, N. M. and Stiller, P. F., “MAPRM: A Probabilistic Roadmap Planner with Sampling on the Medial Axis of the Free Space,” Proceedings of the IEEE International Conference on Robotics and Automation (1999) pp. 1024–1031.Google Scholar
Denny, J., Greco, E., Thomas, S. and Amato, N. M., “MARRT: Medial Axis Biased Rapidly-Exploring Random Trees,” Proceedings of the IEEE International Conference on Robotics and Automation (2014) pp. 90–97.Google Scholar
Lee, J., Kwon, O., L. Zhang and S.-e. Yoon, “SR-RRT: Selective Retraction-based RRT Planner,” Proceedings of the IEEE International Conference on Robotics and Automation (IEEE, 2012) pp. 2543–2550.Google Scholar
Rodriguez, S., Tang, X., Lien, J.-M. and Amato, N. M., “An Obstacle-based Rapidly-Exploring Random Tree,” Proceedings of the IEEE International Conference on Robotics and Automation (2006) pp. 895–900.Google Scholar
Van den Berg, J. P. and Overmars, M. H., “Using workspace information as a guide to non-uniform sampling in probabilistic roadmap planners,” Int. J. Robot. Res. 24(12), 1055–1071 (2005).CrossRefGoogle Scholar
Luna, R., Moll, M., Badger, J. and Kavraki, L. E., “A scalable motion planner for high-dimensional kinematic systems,” Int. J. Robot. Res. 39(4), 361–388 (2020).CrossRefGoogle Scholar
Szádeczky-Kardoss, E. and Kiss, B., “Extension of the Rapidly Exploring Random Tree Algorithm with Key Configurations for Nonholonomic Motion Planning,” IEEE International Conference on Mechatronics (2006) pp. 363–368.Google Scholar
Wang, W., Zuo, L. and Xu, X., “A learning-based multi-RRT approach for robot path planning in narrow passages,” J. Intell. Robot. Syst. 90(1–2), 81–100 (2018).CrossRefGoogle Scholar
Vonásek, V., “Motion Planning of 3D Objects Using Rapidly Exploring Random Tree Guided by Approximate Solutions,” IEEE 23rd International Conference on Emerging Technologies and Factory Automation (ETFA) (2018) pp. 713–720.Google Scholar
Vonásek, V. and Pěniěka, R., “Computation of Approximate Solutions for Guided Sampling-Based Motion Planning of 3D Objects,” 12th International Workshop on Robot Motion and Control (RoMoCo) (2019) pp. 231–238.Google Scholar
Dalibard, S. and Laumond, J.-P., “Linear dimensionality reduction in random motion planning,” Int. J. Robot. Res. 30(12), 1461–1476 (2011).CrossRefGoogle Scholar
Tahirovic, A. and Ferizbegovic, M., “Rapidly-Exploring Random Vines (RRV) for Motion Planning in Configuration Spaces with Narrow Passages,” Proceedings of the IEEE International Conference on Robotics and Automation (2018) pp. 7055–7062.Google Scholar
Bergen, G. v. d., “A fast and robust GJK implementation for collision detection of convex objects,” J. Graphics Tools 4(2), 7–25 (1999).CrossRefGoogle Scholar