A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 9 Issue 2
Feb.  2022

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2022  >  9(2): 283-294
B. H. Li and B. D. Chen, “An adaptive rapidly-exploring random tree,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 2, pp. 283–294, Feb. 2022. doi: 10.1109/JAS.2021.1004252
Citation: B. H. Li and B. D. Chen, “An adaptive rapidly-exploring random tree,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 2, pp. 283–294, Feb. 2022. doi: 10.1109/JAS.2021.1004252
shu

An Adaptive Rapidly-Exploring Random Tree

doi: 10.1109/JAS.2021.1004252

  • Institute of Artificial Intelligence and Robotics, Xi’an Jiaotong University, Xi’an 710049, China

Funds:  This work was supported in part by the National Science Foundation of China (61976175, 91648208) and the Key Project of Natural Science Basic Research Plan in Shaanxi Province of China (2019JZ-05)
More Information
    Abstract
  • Sampling-based planning algorithms play an important role in high degree-of-freedom motion planning (MP) problems, in which rapidly-exploring random tree (RRT) and the faster bidirectional RRT (named RRT-Connect) algorithms have achieved good results in many planning tasks. However, sampling-based methods have the inherent defect of having difficultly in solving planning problems with narrow passages. Therefore, several algorithms have been proposed to overcome these drawbacks. As one of the improved algorithms, Rapidly-exploring random vines (RRV) can achieve better results, but it may perform worse in cluttered environments and has a certain environmental selectivity. In this paper, we present a new improved planning method based on RRT-Connect and RRV, named adaptive RRT-Connect (ARRT-Connect), which deals well with the narrow passage environments while retaining the ability of RRT algorithms to plan paths in other environments. The proposed planner is shown to be adaptable to a variety of environments and can accomplish path planning in a short time.

     

    • FullText(HTML)
  • loading
    • References(26)
  • [1]
    L. E. Kavraki, P. Svestka, J. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robotics and Automation, vol. 12, no. 4, pp. 566–580, 1996. doi: 10.1109/70.508439
    [2]
    S. M. Lavalle, “Rapidly-exploring random trees : A new tool for path planning,” Iowa State University, Tech. Rep. 98-11,Oct. 1998.
    [3]
    X. Tang and F. Chen, “Robot path planning algorithm based on bi-rrt and potential field,” in Proc. IEEE Int. Conf. Mechatronics and Automation (ICMA), 2020, pp. 1251–1256.
    [4]
    C. Yuan, W. Zhang, G. Liu, X. Pan, and X. Liu, “A heuristic rapidlyexploring random trees method for manipulator motion planning,” IEEE Access, vol. 8, pp. 900–910, 2020. doi: 10.1109/ACCESS.2019.2958876
    [5]
    W. Xinyu, L. Xiaojuan, G. Yong, S. Jiadong, and W. Rui, “Bidirectional potential guided RRT* for motion planning,” IEEE Access, vol. 7, pp. 95046–95057, 2019. doi: 10.1109/ACCESS.2019.2928846
    [6]
    H. Zhang, Y. Wang, J. Zheng, and J. Yu, “Path planning of industrial robot based on improved RRT algorithm in complex environments,” IEEE Access, vol. 6, pp. 53296–53306, 2018. doi: 10.1109/ACCESS.2018.2871222
    [7]
    A. Tahirovic and M. Ferizbegovic, “Rapidly-exploring random vines (RRV) for motion planning in configuration spaces with narrow passages,” in Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 2018, pp. 7055–7062.
    [8]
    J. J. Kuffner and S. M. LaValle, “Rrt-connect: An efficient approach to single-query path planning,” in Proc. ICRA Millennium Conf. IEEE Int. Conf. Robotics and Automation, 2000, vol. 2, pp. 995–1001.
    [9]
    D. Hsu, Tingting Jiang, J. Reif, and Zheng Sun, “The bridge test for sampling narrow passages with probabilistic roadmap planners,” in Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 2003, vol. 3, pp. 4420–4426.
    [10]
    A. Yershova, L. Jaillet, T. Simeon, and S. M. LaValle, “Dynamicdomain RRTs: Efficient exploration by controlling the sampling domain,” in Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 2005, pp. 3856–3861.
    [11]
    S. Khanmohammadi and A. Mahdizadeh, “Density avoided sampling: An intelligent sampling technique for rapidly-exploring random trees,” in Proc. Eighth Int. Conf. Hybrid Intelligent Systems, 2008, pp. 672–677.
    [12]
    Liangjun Zhang and D. Manocha, “An efficient retraction-based RRT planner,” in Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 2008, pp. 3743–3750.
    [13]
    S. Rodriguez, S. Thomas, R. Pearce, and N. M. Amato, “RESAMPL: A region-sensitive adaptive motion planner”, Algorithmic Foundation of Robotics VII. Berlin, Heidelberg: Springer, 2008, pp. 285–300.
    [14]
    A. Shkolnik and R. Tedrake, “Sample-based planning with volumes in configuration space,” arXiv preprint arXiv:1109.3145, 2011.
    [15]
    M. Strandberg, “Augmenting RRT-planners with local trees,” in Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 2004, vol. 4, pp. 3258–3262.
    [16]
    Rodriguez, Xinyu Tang, Jyh-Ming Lien, and N. M. Amato, “An obstaclebased rapidly-exploring random tree,” in Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 2006, pp. 895–900.
    [17]
    S. Dalibard and J.-P. Laumond, “Linear dimensionality reduction in random motion planning,” Int. J. Robotics Research, vol. 30, no. 12, pp. 1461–1476, 2011. doi: 10.1177/0278364911403335
    [18]
    J. Lee, O. Kwon, L. Zhang, and SE. Yoon, “SR-RRT: Selective retraction-based RRT planner,” in Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 2012, pp. 2543–2550.
    [19]
    W. Wang, L. Zuo, and X. Xu, “A learning-based multi-RRT approach for robot path planning in narrow passages,” J. Intelligent &Robotic Systems, vol. 90, no. 1−2, pp. 81–100, 2018.
    [20]
    T. Lai, F. Ramos, and G. Francis, “Balancing global exploration and local-connectivity exploitation with rapidly-exploring random disjointedtrees,” in Proc. Int. Conf. Robotics and Automation (ICRA), 2019, pp. 5537–5543.
    [21]
    T. Lai, P. Morere, F. Ramos, and G. Francis, “Bayesian local samplingbased planning,” IEEE Robotics and Automation Letters, vol. 5, no. 2, pp. 1954–1961, 2020. doi: 10.1109/LRA.2020.2969145
    [22]
    P. Rajendran, S. Thakar, A. M. Kabir, B. C. Shah, and S. K. Gupta, “Context-dependent search for generating paths for redundant manipulators in cluttered environments,” in Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems (IROS), 2019, pp. 5573– 5579.
    [23]
    S. R. Lindemann and S. M. LaValle, “Incrementally reducing dispersion by increasing voronoi bias in RRTs,” in Proc. IEEE Int. Conf. Robotics and Automation (ICRA), 2004, vol. 4, pp. 3251–3257.
    [24]
    S. R. Lindemann and S. M. LaValle, “Steps toward derandomizing RRTs,” in Proc. 24th Int. Workshop on Robot Motion and Control (IEEE), 2004, pp. 271–277.
    [25]
    A. Guttman, “R-trees: A dynamic index structure for spatial searching,” in Proc. ACM SIGMOD International Conf. Management of Data, 1984, pp. 47–57.
    [26]
    L. G. D. O. Véras, F. L. L. Medeiros, and L. N. F. Guimaráes, “Systematic literature review of sampling process in rapidly-exploring random trees,” IEEE Access, vol. 7, pp. 50933–50953, 2019. doi: 10.1109/ACCESS.2019.2908100
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(8)  / Tables(5)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1935) PDF downloads(86) Cited by()

    Highlights

    • Fast RRT algorithm for narrow passage: This paper proposes an improved RRT algorithm which can better deal with the planning task with narrow passage environment. The algorithm improves the planning speed and success rate of RRT algorithm for narrow passage task
    • Rapid planning of common environment: Although the new algorithm increases the amount of computation because of dealing with narrow channel environment, it can still deal with common planning tasks quickly without great performance loss
    • Simple algorithm flow: The new algorithm improves the sampling process of the original RRT algorithm, simplifies the local environment judgment process of RRV algorithm, and uses dual tree search to enhance the stability of the algorithm. The whole process of the algorithm is simple and unified, easy to understand and implement

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return