IEEE/CAA Journal of Automatica Sinica
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 |
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
.
[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.
|