Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An efficient RRT-based motion planning algorithm for autonomous underwater vehicles under cylindrical sampling constraints

  • Published:
Autonomous Robots Aims and scope Submit manuscript

Abstract

Quickly finding high-quality paths is of great significance for autonomous underwater vehicles (AUVs) in path planning problems. In this paper, we present a cylinder-based heuristic rapidly exploring random tree (Cyl-HRRT*) algorithm, which is the extension version of the path planner presented in our previous publication. Cyl-HRRT* increases the likelihood of sampling states that can improve the current solution by biasing the states into a cylindrical subset, thus providing better paths for AUVs. A direct greedy sampling method is proposed to explore the space more efficiently and accelerate convergence to the optimum. To reasonably balance the optimization accuracy and the number of iterations, a beacon-based adaptive optimization strategy is presented, which adaptively establishes a cylindrical subset for the next focused sampling according to the current path. Furthermore, the Cyl-HRRT* algorithm is shown to be probabilistically complete and asymptotically optimal. Finally, the Cyl-HRRT* algorithm is comprehensively tested in both simulations and real-world experiments. The results reveal that the path generated by the Cyl-HRRT* algorithm greatly improves the power savings and mobility of the AUV.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Cai, M., Wang, Y., Wang, S., Wang, R., Ren, Y., & Tan, M. (2020). Grasping marine products with hybrid-driven underwater vehicle-manipulator system. IEEE Transactions on Automation Science and Engineering, 17(3), 1443–1454.

    Google Scholar 

  2. Zhang, F., Marani, G., Smith, R. N., & Choi, H. T. (2015). Future trends in marine robotics. IEEE Robotics & Automation Magazine,22(1), 14–122.

  3. Jaillet, L., Cortés, J., & Simeon, T. (2010). Sampling-based path planning on configuration-space costmaps. IEEE Transactions on Robotics, 26(4), 635–646.

    Article  Google Scholar 

  4. Lu, Y. A., Tang, K., & Wang, C. Y. (2021). Collision-free and smooth joint motion planning for six-axis industrial robots by redundancy optimization. Robotics and Computer-Integrated Manufacturing, 68, 102091.

    Article  Google Scholar 

  5. Sakcak, B., Bascetta, L., Ferretti, G., et al. (2019). Sampling-based optimal kinodynamic planning with motion primitives. Autonomous Robots, 43, 1715–1732.

    Article  Google Scholar 

  6. Hart, P. E., Nilsson, N. J., & Raphae, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.

    Article  Google Scholar 

  7. Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research, 5(1), 90–98.

    Article  Google Scholar 

  8. Janson, L., & Pavone, M. (2015). Fast marching trees: A fast marching sampling-based method for optimal motion planning in many dimensions. The International Journal of Robotics Research, 34(7), 883–921.

    Article  Google Scholar 

  9. Dong, L., Ming, C., & Yu, D. (2017). Episodic memory-based robotic planning under uncertainty. IEEE Transactions on Industrial Electronics, 64(2), 1762–1772.

    Article  Google Scholar 

  10. Petres, C., Pailhas, Y., Patron, P., Petillot, Y., Evans, J., & Lane, D. (2007). Path planning for autonomous underwater vehicles. IEEE Transactions on Robotics, 23(2), 331–341.

    Article  Google Scholar 

  11. Garau, B., Alvarez, A., & Oliver, G. (2005). Path planning of autonomous underwater vehicles in current fields with complex spatial variability: An A* approach. In Proceedings of IEEE ICRA (pp. 194–198).

  12. Wang, T., Le Maître, O. P., Hoteit, I., & Knio, O. M. (2016). Path planning in uncertain flow fields using ensemble method. Ocean Dynamics, 66(10), 1231–1251.

    Article  Google Scholar 

  13. Aghababa, M. P. (2012). 3D path planning for underwater vehicles using five evolutionary optimization algorithms avoiding static and energetic obstacles. Applied Ocean Research, 38, 48–62.

    Article  Google Scholar 

  14. Wang, T., Lima, R. M., Giraldi, L., & Knio, O. M. (2019). Trajectory planning for autonomous underwater vehicles in the presence of obstacles and a nonlinear flow field using mixed integer nonlinear programming. Computers & Operations Research, 101, 55–75.

    Article  MathSciNet  MATH  Google Scholar 

  15. Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research, 30(7), 846–894.

    Article  MATH  Google Scholar 

  16. Yu, F., Chen, Y., Zhang, X., & Xin, X. (2019). Rapidly-exploring random trees based on cylindrical sampling space. In 2019 IEEE international conference on robotics and biomimetics (ROBIO) (pp. 539–544).

  17. Karaman, S., & Frazzoli, E. (2010). Incremental sampling-based algorithms for optimal motion planning. Robotics Science and Systems, 104(2).

  18. Gammell, J. D., Barfoot, T. D., & Srinivasa, S. S. (2018). Informed sampling for asymptotically optimal path planning. IEEE Transactions on Robotics, 34(49), 66–984.

    Google Scholar 

  19. Akgun, B., & Stilman, M. (2011). Sampling heuristics for optimal motion planning in high dimensions. In IEEE/RSJ international conference on intelligent robots and systems (pp. 2640–2645).

  20. Burget, F., Bennewitz, M., & Burgard, W. (2016). BI2RRT*: An efficient sampling-based path planning framework for task-constrained mobile manipulation. In IEEE/RSJ international conference on intelligent robots and systems (IROS)(pp. 3714–3721).

  21. Heiden, E., Palmieri, L., Koenig, S., Arras, K. O., & Sukhatme, G. S. (2018). Gradient-informed path smoothing for wheeled mobile robots. In IEEE international conference on robotics and automation (ICRA) (pp. 1710–1717).

  22. Reid, W., Fitch, R., Göktoğan, A. H., & Sukkarieh, S. (2020). Sampling based hierarchical motion planning for a reconfigurable wheel-on-leg planetary analogue exploration rover. Journal of Field Robotics, 37(5), 786–811.

    Article  Google Scholar 

  23. Otte, M., & Correll, N. (2013). C-FOREST: Parallel shortest path planning with super linear speedup. IEEE Transactions on Robotics, 29(3), 798–806.

    Article  Google Scholar 

  24. Wang, J., Chi, W., Li, C., Wang, C., & Meng, M.Q.-H. (2020). Neural RRT*: Learning-based optimal path planning’’. IEEE Transactions on Automation Science and Engineering, 17(4), 1748–1758.

    Article  Google Scholar 

  25. Gammell, J. D., Srinivasa, S. S., & Barfoot, T. D. (2014). Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. In 2014 IEEE/RSJ international conference on intelligent robots and systems (pp. 2997–3004).

  26. Gammell, J. D., Barfoot, T. D., & Srinivasa, S. S. (2020). Batch Informed Trees (BIT*): Informed asymptotically optimal anytime search’’. The International Journal of Robotics Research, 39(5), 543–567.

    Article  Google Scholar 

  27. Dai, Y., Yu, S., & Yan, Y. (2020). An adaptive EKF-FMPC for the trajectory tracking of UVMS. IEEE Journal of Oceanic Engineering, 45(3), 699–713.

    Article  Google Scholar 

  28. Li, B., & Chen, B. (2022). An adaptive rapidly-exploring random tree. IEEE/CAA Journal of Automatica Sinica, 9(2), 283–294.

    Article  Google Scholar 

  29. Ma, Y., Gong, Y., Xiao, C., Gao, Y., & Zhang, J. (2019). Path planning for autonomous underwater vehicles: An ant colony algorithm incorporating alarm pheromone. IEEE Transactions on Vehicular Technology, 68(1), 141–154.

    Article  Google Scholar 

  30. Antonelli, G., & Chiaverini, S. (2003). Fuzzy redundancy resolution and motion coordination for underwater vehicle-manipulator systems. IEEE Transactions on Fuzzy Systems, 11(1), 109–120.

    Article  Google Scholar 

  31. Cieślak, P. C., Simoni, R., Rodríguez, P. R., et al. (2020). Practical formulation of obstacle avoidance in the Task-Priority framework for use in robotic inspection and intervention scenarios. Robotics and Autonomous Systems, 124, 103396.

    Article  Google Scholar 

  32. Lin, W., Anwar, A., Li, Z., Tong, M., Qiu, J., & Gao, H. (2019). Recognition and pose estimation of auto parts for an autonomous spray painting robot. IEEE Transactions on Industrial Informatics, 15(3), 1709–1719.

    Article  Google Scholar 

Download references

Acknowledgements

Grateful acknowledgement is given to the National Natural Science Foundation of China with Grant No. 52075293, Natural Science Foundation of Shandong Province with Grant No. ZR2019MEE019 and Research Project of Teaching Reform for Shandong University at Weihai with Grant No. Z2019022.

Author information

Authors and Affiliations

  1. Department of Mechanical, Electrical and Information Engineering, University of Shandong University at Weihai, Weihai, 264209, China

    Fujie Yu, Huaqing Shang, Qilong Zhu, Hansheng Zhang & Yuan Chen

Authors
  1. Fujie Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Huaqing Shang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Qilong Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hansheng Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Yuan Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yuan Chen.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A Proofs of Lemma 1

Appendix A Proofs of Lemma 1

Lemma 1

(The necessity of adding states in the admissible heuristic estimate). Adding a state from the admissible heuristic estimate, \(\textbf{x}_{\text{ new } } \in X_{\hat{c}}\), is a necessary condition for RRT* to improve the current solution,

$$\begin{aligned} c_{i+1}<c_{i} \Longrightarrow \textbf{x}_{\text{ new } } \in X_{\hat{c}} \end{aligned}$$
(12)

This condition is necessary but not sufficient to improve the solution as the ability of states in \(X_{\hat{c}}\) to provide better solutions at any iteration depends on the structure of the tree (i.e., its optimality).

Proof

At the end of iteration \(i+1\), the cost of the best solution found by RRT* will be the minimum of the previous best solution, \(c_i\), and the best cost of any new or newly improved solutions, \(c_\textrm{new}\),

$$\begin{aligned} c_{i+1} = \textrm{min} \left\{ c_i, c_{\textrm{new}}\right\} . \end{aligned}$$
(13)

Each iteration of RRT* only adds connections to or from the newly added state, \(x_{\textrm{new}}\), and therefore all new or modifified paths pass through this new state. The cost of any of these new paths that extend to the goal region will be bounded from below by the cost of the optimal solution of a path through \(x_{\textrm{new}}\),

$$\begin{aligned} c_{\textrm{new}} \ge f(x_{\textrm{new}}). \end{aligned}$$
(14)

Lemma 1 is now proven by contradiction. Assume that RRT* has a solution with cost ci after iteration i and that it is improved at iteration \(i+1\) by adding a state not in the omniscient set, \(c_{i+1} < c_i\), \(x_{\textrm{new}} \notin X_f\). By (3), the costs of solutions through any \(x_{\textrm{new}} \notin X_f\) are bounded from below by the current solution,

$$\begin{aligned} f(x_{\textrm{new}}) \ge c_i, \end{aligned}$$
(15)

which by (14) is also a bound on the cost of any new or modifified solutions, \(c_{\textrm{new}} \ge f (x_{\textrm{new}}) \ge c_i\).

By (13), the cost of the best solution found by RRT* at the end of iteration \(i+1\) must therefore be \(c_i\). This contradicts the assumption that the solution was improved by a state not in the omniscient set and proves Lemma 1. \(\square \)

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yu, F., Shang, H., Zhu, Q. et al. An efficient RRT-based motion planning algorithm for autonomous underwater vehicles under cylindrical sampling constraints. Auton Robot 47, 281–297 (2023). https://doi.org/10.1007/s10514-023-10083-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10514-023-10083-y

Keywords

Search

Navigation