Adaptive Space Expansion for Fast Motion Planning

Shenglei Shi; Jiankui Chen

doi:10.1109/JAS.2023.123765

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 11.8, Top 4% (SCI Q1)

CiteScore: 17.6, Top 3% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2024 > In Press, Accepted Manuscript

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

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

PDF( 2748 KB)

Adaptive Space Expansion for Fast Motion Planning

doi: 10.1109/JAS.2023.123765

Shenglei Shi^,,
Jiankui Chen^{,
,}

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

Abstract

Abstract

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.
- Adaptive space expansion (ASE),
- hyper-ellipsoid ring,
- informed sampling,
- motion planning

FullText(HTML)

References(31)

References

[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.

Supplements(0)

Cited By

Proportional views

Proportional views

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

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

Figures(14) / Tables(8)

Get Citation

PDF

XML

Article Metrics

Article views (83) PDF downloads(27)

Adaptive Space Expansion for Fast Motion Planning

doi: 10.1109/JAS.2023.123765

Abstract

References

Proportional views

Catalog

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

Article Metrics

Export File

Citation

Format

Content