A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 11 Issue 6
Jun.  2024

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
S. Shi and  J. Chen,  “Adaptive space expansion for fast motion planning,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 6, pp. 1499–1514, Jun. 2024. doi: 10.1109/JAS.2023.123765
Citation: S. Shi and  J. Chen,  “Adaptive space expansion for fast motion planning,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 6, pp. 1499–1514, Jun. 2024. doi: 10.1109/JAS.2023.123765

Adaptive Space Expansion for Fast Motion Planning

doi: 10.1109/JAS.2023.123765
Funds:  This work was supported in part by the National Natural Science Foundation of China (51975236), the National Key Research and Development Program of China (2018YFA0703203), and the Innovation Project of Optics Valley Laboratory (OVL2021BG007)
More Information
  • The sampling process is very inefficient for sampling-based motion planning algorithms that excess random samples are generated in the planning space. In this paper, we propose an adaptive space expansion (ASE) approach which belongs to the informed sampling category to improve the sampling efficiency for quickly finding a feasible path. The ASE method enlarges the search space gradually and restrains the sampling process in a sequence of small hyper-ellipsoid ring subsets to avoid exploring the unnecessary space. Specifically, for a constructed small hyper-ellipsoid ring subset, if the algorithm cannot find a feasible path in it, then the subset is expanded. Thus, the ASE method successively does space exploring and space expansion until the final path has been found. Besides, we present a particular construction method of the hyper-ellipsoid ring that uniform random samples can be directly generated in it. At last, we present a feasible motion planner BiASE and an asymptotically optimal motion planner BiASE* using the bidirectional exploring method and the ASE strategy. Simulations demonstrate that the computation speed is much faster than that of the state-of-the-art algorithms. The source codes are available at

    https://github.com/shshlei/ompl

    .

     

  • loading
  • [1]
    S. M. LaValle, Planning Algorithms. Cambridge University Press, 2006.
    [2]
    S. M. LaValle and J. J. Kuffner Jr, “Randomized kinodynamic planning,” Int. J. Robot. Res., vol. 20, no. 5, pp. 378–400, 2001. doi: 10.1177/02783640122067453
    [3]
    L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robot. Autom., vol. 12, no. 4, pp. 566–580, 1996. doi: 10.1109/70.508439
    [4]
    S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” Int. J. Robot. Res., vol. 30, no. 7, pp. 846–894, 2011. doi: 10.1177/0278364911406761
    [5]
    J. D. Gammell, T. D. Barfoot, and S. S. Srinivasa, “Informed sampling for asymptotically optimal path planning,” IEEE Trans. Robot., vol. 34, no. 4, pp. 966–984, 2018. doi: 10.1109/TRO.2018.2830331
    [6]
    J. Wang, C. X.-T. Li, W. Chi, and M. Q.-H. Meng, “Tropistic RRT*: An efficient planning algorithm via adaptive restricted sampling space,” in Proc. Int. Conf. Inform. Autom., Wuyishan, China, 2018, pp. 1639–1646.
    [7]
    J. J. Kuffner and S. M. LaValle, “RRT-connect: An efficient approach to single-query path planning,” in Proc. Int. Conf. Robot. Autom., San Francisco, CA, USA, 2000, pp. 995–1001.
    [8]
    M. Otte and N. Correll, “C-forest: Parallel shortest path planning with superlinear speedup,” IEEE Trans. Robot., vol. 29, no. 3, pp. 798–806, 2013. doi: 10.1109/TRO.2013.2240176
    [9]
    Z. Wang, Y. Li, H. Zhang, C. Liu, and Q. Chen, “Sampling-based optimal motion planning with smart exploration and exploitation,” IEEE/ASME Trans. Mechatron., vol. 25, no. 5, pp. 2376–2386, 2020. doi: 10.1109/TMECH.2020.2973327
    [10]
    J. Xu, K. Song, D. Zhang, H. Dong, Y. Yan, and Q. Meng, “Informed anytime fast marching tree for asymptotically-optimal motion planning,” IEEE Trans. Ind. Electron., vol. 68, no. 6, pp. 5068–5077, 2021. doi: 10.1109/TIE.2020.2992978
    [11]
    J. D. Gammell, T. D. Barfoot, and S. S. Srinivasa, “Batch informed trees (BIT*): Informed asymptotically optimal anytime search,” Int. J. Robot. Res., vol. 39, no. 5, pp. 543–567, 2020. doi: 10.1177/0278364919890396
    [12]
    M. P. Strub and J. D. Gammell, “Advanced BIT* (ABIT*): Sampling-based planning with advanced graph-search techniques,” in Proc. Int. Conf. Robot. Autom., Paris, France, 2020, pp. 130–136.
    [13]
    M. P. Strub and J. D. Gammell, “Adaptively informed trees (AIT*) and effort informed trees (EIT*): Asymmetric bidirectional sampling-based path planning,” Int. J. Robot. Res., vol. 41, no. 4, pp. 390–417, 2022. doi: 10.1177/02783649211069572
    [14]
    A. Mandalika, R. Scalise, B. Hou, S. Choudhury, and S. S. Srinivasa, “Guided incremental local densification for accelerated sampling-based motion planning,” 2021.
    [15]
    M. Rickert, A. Sieverling, and O. Brock, “Balancing exploration and exploitation in sampling-based motion planning,” IEEE Trans. Robot., vol. 30, no. 6, pp. 1305–1317, 2014. doi: 10.1109/TRO.2014.2340191
    [16]
    S. Thakar, P. Rajendran, H. Kim, A. M. Kabir, and S. K. Gupta, “Accelerating bi-directional sampling-based search for motion planning of non-holonomic mobile manipulators,” in Proc. Int. Conf. Intell. Robots Syst., Las Vegas, NV, USA, 2020, pp. 6711–6717.
    [17]
    B. Ichter, J. Harrison, and M. Pavone, “Learning sampling distributions for robot motion planning,” in Proc. Int. Conf. Robot. Autom., Brisbane, QLD, Australia, 2018, pp. 7087–7094.
    [18]
    F. Islam, J. Nasir, U. Malik, Y. Ayaz, and O. Hasan, “RRT-smart: Rapid convergence implementation of rrt towards optimal solution,” in Proc. Int. Conf. Mechatron. Autom., Chengdu, China, 2012, pp. 1651–1656.
    [19]
    D. Hsu, T. Jiang, J. Reif, and Z. Sun, “The bridge test for sampling narrow passages with probabilistic roadmap planners,” in Proc. Int. Conf. Robot. Autom., Taipei, China, 2003, pp. 4420–4426.
    [20]
    S. Khanmohammadi and A. Mahdizadeh, “Density avoided sampling: An intelligent sampling technique for rapidly-exploring random trees,” in Proc. Int. Conf. Hybrid Intell. Syst., 2008, pp. 672–677.
    [21]
    B. Li and B. Chen, “An adaptive rapidly-exploring random tree,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 2, pp. 283–294, 2022. doi: 10.1109/JAS.2021.1004252
    [22]
    T. Zhang, J. Wang, and M. Q.-H. Meng, “Generative adversarial network based heuristics for sampling-based path planning,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 1, pp. 64–74, 2021.
    [23]
    J. Wang, W. Chi, C. Li, C. Wang, and M. Q.-H. Meng, “Neural RRT*: Learning-based optimal path planning,” IEEE Trans. Autom. Sci. Eng., vol. 17, no. 4, pp. 1748–1758, 2020. doi: 10.1109/TASE.2020.2976560
    [24]
    H. Ma, C. Li, J. Liu, J. Wang, and M. Q.-H. Meng, “Enhance connectivity of promising regions for sampling-based path planning,” IEEE Trans. Autom. Sci. Eng., pp. 1–14, 2022.
    [25]
    K. Hauser, “Lazy collision checking in asymptotically-optimal motion planning,” in Proc. Int. Conf. Robot. Autom., Seattle, WA, USA, 2015, pp. 2951–2957.
    [26]
    S. Shi, J. Chen, and Y. Li, “Hybrid safety certificate for fast collision checking in sampling-based motion planning,” IEEE Robot. Autom. Lett., vol. 8, no. 1, pp. 113–120, 2023. doi: 10.1109/LRA.2022.3223021
    [27]
    K. Solovey and M. Kleinbort, “The critical radius in sampling-based motion planning,” Int. J. Robot. Res., vol. 39, no. 2–3, pp. 266–285, 2020. doi: 10.1177/0278364919859627
    [28]
    A. H. Qureshi, Y. Miao, A. Simeonov, and M. C. Yip, “Motion planning networks: Bridging the gap between learning-based and classical motion planners,” IEEE Trans. Robot., vol. 37, no. 1, pp. 48–66, 2020.
    [29]
    I. A. Şucan, M. Moll, and L. E. Kavraki, “The Open Motion Planning Library,” IEEE Robot. Autom. Mag., vol. 19, no. 4, pp. 72–82, 2012. doi: 10.1109/MRA.2012.2205651
    [30]
    M. Moll, I. A. Şucan, and L. E. Kavraki, “Benchmarking motion planning algorithms: An extensible infrastructure for analysis and visualization,” IEEE Robot. Autom. Mag., vol. 22, no. 3, pp. 96–102, 2015. doi: 10.1109/MRA.2015.2448276
    [31]
    I. A. Şucan and L. E. Kavraki, “Kinodynamic motion planning by interior-exterior cell exploration,” in Proc. Algo. Found. Robot. VIII, Guanajuato, México, 2009, pp. 449–464.

Catalog

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

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

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

    Figures(14)  / Tables(8)

    Article Metrics

    Article views (177) PDF downloads(48) Cited by()

    Highlights

    • An adaptive space expansion (ASE) framework for motion planning which first focuses on exploring in a small promising region and then explores the outward expanded space. The successive space exploring and expanding steps can make the algorithm avoid exploring the useless space
    • A particular hyper-ellipsoid ring expansion strategy such that the algorithm can also avoid repeatedly exploring the same space. And a direct sampling method in the hyper-ellipsoid ring which is more efficient than the rejection sampling method
    • An adaptive division strategy divides a global hyper-ellipsoid into several small local hyper-ellipsoids. And then the algorithm successively does space exploring and expanding using these small hyper-ellipsoids
    • A hybrid informed sampling approach that simultaneously does two types of space exploring, one is searching for a better path, while the other is searching for a feasible path which is expected to be much better than current feasible path
    • A feasible motion planner BiASE and an asymptotically optimal motion planner BiASE* which are much faster than the state-of-the-art algorithms and are available at https://github.com/shshlei/ompl

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return