Write your message
Volume 15 - Winter and Spring 2021                   ijmt 2021, 15 - Winter and Spring 2021: 93-105 | Back to browse issues page

XML Print

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Taheri E, Adeli A. AUV Path Planning in Dynamic Cluttered Environment through the Randomized Kinodynamic Sampling-based method. ijmt 2021; 15 :93-105
URL: http://ijmt.ir/article-1-748-en.html
1- Electrical Engineering Department, Malek Ashtar University of Technology
2- Department of Mechanical Engineering, Sharif University of Technology
Abstract:   (1356 Views)
Considering both kinematic and dynamic constraints (kinodynamic constraints) of an autonomous underwater vehicle in a Kinodynamic path planning algorithm in a dynamic large-scale workspace is an NP-Hard problem. Computational and time complexity of the kinodynamic path planning problem increase in the order O (n2) by increasing numbers of moving obstacles, AUV Kinodynamic constraints, degrees of freedoms, and workspace dimensions. This paper proposes a Randomized Kinodynamic Sub-optimal Planning (RKSP) algorithm for a man-portable class AUV. The proposed algorithm solves the path planning problem by applying a randomized sampling-based method to exploring and expanding in the workspace. RKSP re-plans the path to avoid collision with moving obstacles in a cluttered environment through a behavior-based method.  RKSP consists of three main components that tightly coupled together. The first component is a Randomized kinodynamic Planning (RKP) module that generates the random offspring waypoints and plans a feasible path by considering the AUV kinodynamic constraints. The second component is a Numerical Path Optimization (NPO) module that prunes the inappropriate edges of the path and reduces the computational complexity. The third component is a Local-Reactive kinodynamic (LRK) module that re-plans the local path through the neighborhood waypoints to avoid collision with moving obstacles in an unknown environment. RKSP path planning method is evaluated through the three different scenarios in a narrow passage, maze-like space and complex space. Results demonstrate the planned path by the proposed method is feasible and the AUV tracks the path appropriately and avoids collision with moving obstacles. Also, the total numbers of waypoints reduce in comparison to the conventional randomized methods and the planned path is near to the optimal.
Full-Text [PDF 1031 kb]   (441 Downloads)    
Type of Study: Research Paper | Subject: Other
Received: 2021/05/12 | Accepted: 2021/10/12

1. W. Kazimierski, A. Sawczak, and N. Wawrzyniak, "Analysis of Graph Searching Algorithms for Route Planning in Inland Navigation," TransNav: International Journal on Marine Navigation and Safety of Sea Transportation, vol. 9, no. 2, pp. 281--286, 2015. [DOI:10.12716/1001.09.02.17]
2. M. P. Aghababa, "3D path planning for underwater vehicles using five evolutionary optimization algorithms avoiding static and energetic obstacles," Applied Ocean Research, vol. 38, pp. 48-62, 2012. [DOI:10.1016/j.apor.2012.06.002]
3. Y. Zhuang, S. Sharma, B. Subudhi, H. Huang, and J. Wan, "Efficient collision-free path planning for autonomous underwater vehicles in dynamic environments with a hybrid optimization algorithm," Ocean Engineering, vol. 127, pp. 190-199, 2016. [DOI:10.1016/j.oceaneng.2016.09.040]
4. Z. Zeng, A. Lammas, K. Sammut, F. He, and Y. Tang, "Shell space decomposition based path planning for AUVs operating in a variable environment," Ocean Engineering, vol. 91, pp. 181-195, 2014. [DOI:10.1016/j.oceaneng.2014.09.001]
5. I. Noreen, A. Khan, and Z. Habib, "Optimal path planning using RRT* based approaches: a survey and future directions," Int. J. Adv. Comput. Sci. Appl, vol. 7, no. 11, pp. 97-107, 2016. [DOI:10.14569/IJACSA.2016.071114]
6. J. D. Hernández Vega, "Online path planning for autonomous underwater vehicles under motion constraints," 2017.
7. M. Otte, and E. Frazzoli, "RRTX: Asymptotically optimal single-query sampling-based motion planning with quick replanning," The International Journal of Robotics Research, vol. 35, no. 7, pp. 797-822, 2016. [DOI:10.1177/0278364915594679]
8. S. Karaman, and E. Frazzoli, "Incremental sampling-based algorithms for optimal motion planning," Robotics Science and Systems VI, vol. 104, no. 2, 2010. [DOI:10.15607/RSS.2010.VI.034]
9. R. Hess, R. Jerg, T. Lindeholz, D. Eck, and K. Schilling, "SRRT*-a probabilistic optimal trajectory planner for problematic area structures," IFAC-PapersOnLine, vol. 49, no. 30, pp. 331-336, 2016. [DOI:10.1016/j.ifacol.2016.11.157]
10. O. Salzman, and D. Halperin, "Asymptotically near-optimal RRT for fast, high-quality motion planning," IEEE Transactions on Robotics, vol. 32, no. 3, pp. 473-483, 2016. [DOI:10.1109/TRO.2016.2539377]
11. E. Taheri, M. H. Ferdowsi, and M. Danesh, "Fuzzy greedy RRT path planning algorithm in a complex configuration space," International Journal of Control, Automation and Systems, vol. 16, no. 6, pp. 3026-3035, 2018. [DOI:10.1007/s12555-018-0037-6]
12. W. Wang, L. Zuo, and X. Xu, "A learning-based multi-RRT approach for robot path planning in narrow passages," Journal of Intelligent & Robotic Systems, vol. 90, no. 1, pp. 81-100, 2018. [DOI:10.1007/s10846-017-0641-3]
13. Y. Dong, E. Camci, and E. Kayacan, "Faster RRT-based nonholonomic path planning in 2D building environments using skeleton-constrained path biasing," Journal of Intelligent & Robotic Systems, vol. 89, no. 3, pp. 387-401, 2018. [DOI:10.1007/s10846-017-0567-9]
14. E. Taheri, M. H. Ferdowsi, and M. Danesh, "Closed-loop randomized kinodynamic path planning for an autonomous underwater vehicle," Applied Ocean Research, vol. 83, pp. 48-64, 2019. [DOI:10.1016/j.apor.2018.12.008]
15. B. Donald, P. Xavier, J. Canny, and J. Reif, "Kinodynamic motion planning," Journal of the ACM (JACM), vol. 40, no. 5, pp. 1048-1066, 1993. [DOI:10.1145/174147.174150]
16. S. Karaman, and E. Frazzoli, "Optimal kinodynamic motion planning using incremental sampling-based methods." pp. 7681-7687.
17. C.-b. Moon, and W. Chung, "Kinodynamic planner dual-tree RRT (DT-RRT) for two-wheeled mobile robots using the rapidly exploring random tree," IEEE Transactions on industrial electronics, vol. 62, no. 2, pp. 1080-1090, 2014. [DOI:10.1109/TIE.2014.2345351]
18. D. J. Webb, and J. Van Den Berg, "Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics." pp. 5054-5061.
19. R. Bordalba, J. M. Porta, and L. Ros, "Randomized kinodynamic planning for cable-suspended parallel robots," Cable-Driven Parallel Robots, pp. 195-206: Springer, 2018. [DOI:10.1007/978-3-319-61431-1_17]
20. Q.-C. Pham, S. Caron, and Y. Nakamura, "Kinodynamic Planning in the Configuration Space via Admissible Velocity Propagation."
21. L. Palmieri, and K. O. Arras, "A novel RRT extend function for efficient and smooth mobile robot motion planning." pp. 205-211.
22. S. Yoon, D. Lee, J. Jung, and D. H. Shim, "Spline-based RRT∗ using piecewise continuous collision-checking algorithm for Car-like vehicles," Journal of Intelligent & Robotic Systems, vol. 90, no. 3, pp. 537-549, 2018. [DOI:10.1007/s10846-017-0693-4]
23. S. Stoneman, and R. Lampariello, "Embedding nonlinear optimization in RRT* for optimal kinodynamic planning." pp. 3737-3744.
24. T. Bera, D. Ghose, and S. Suresh, "Asymptotic optimality of rapidly exploring random tree," arXiv preprint arXiv:1707.03976, 2017.
25. B. Sakçak, "Optimal kinodynamic planning for autonomous vehicles," 2018.
26. K. Hauser, and Y. Zhou, "Asymptotically optimal planning by feasible kinodynamic planning in a state-cost space," IEEE Transactions on Robotics, vol. 32, no. 6, pp. 1431-1443, 2016. [DOI:10.1109/TRO.2016.2602363]
27. R. Bordalba, L. Ros, and J. M. Porta, "Kinodynamic planning on constraint manifolds," arXiv preprint arXiv:1705.07637, 2017. [DOI:10.1109/ICRA.2018.8460753]
28. M. Moll, L. Kavraki, and J. Rosell, "Randomized physics-based motion planning for grasping in cluttered and uncertain environments," IEEE Robotics and Automation Letters, vol. 3, no. 2, pp. 712-719, 2017. [DOI:10.1109/LRA.2017.2783445]
29. M. Herrero-Collantes, and J. C. Garcia-Escartin, "Quantum random number generators," Reviews of Modern Physics, vol. 89, no. 1, pp. 015004, 2017. [DOI:10.1103/RevModPhys.89.015004]
30. M. Matsumoto, and T. Nishimura, "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator," ACM Transactions on Modeling and Computer Simulation (TOMACS), vol. 8, no. 1, pp. 3-30, 1998. [DOI:10.1145/272991.272995]
31. B.-H. Jun, J.-Y. Park, F.-Y. Lee, P.-M. Lee, C.-M. Lee, K. Kim, Y.-K. Lim, and J.-H. Oh, "Development of the AUV 'ISiMI'and a free running test in an Ocean Engineering Basin," Ocean engineering, vol. 36, no. 1, pp. 2-14, 2009. [DOI:10.1016/j.oceaneng.2008.07.009]
32. T. T. J. Prestero, "Verification of a six-degree of freedom simulation model for the REMUS autonomous underwater vehicle," Massachusetts institute of technology, 2001. [DOI:10.1575/1912/3040]
33. E. Kim, S. Fan, N. Bose, and H. Nguyen, "Current Estimation and Path Following for an Autonomous Underwater Vehicle (AUV) by Using a High-gain Observer Based on an AUV Dynamic Model," International Journal of Control, Automation and Systems, vol. 19, no. 1, pp. 478-490, 2021. [DOI:10.1007/s12555-019-0673-5]
34. A. Karmozdi, M. Hashemi, H. Salarieh, and A. Alasty, "INS-DVL navigation improvement using rotational motion dynamic model of AUV," IEEE Sensors Journal, vol. 20, no. 23, pp. 14329-14336, 2020. [DOI:10.1109/JSEN.2020.3007929]

Send email to the article author

Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Creative Commons License
International Journal of Maritime Technology is licensed under a

Creative Commons Attribution-NonCommercial 4.0 International License.