Path Planning and Collision Avoidance in Unknown Environments for USVs Based on an Improved D* Lite
Source abstract
Abstract
Path planning and collision avoidance during autonomous navigation in unknown environments is a crucial issue for unmanned surface vehicles (USVs). This paper improves the traditional D* Lite algorithm and achieves multi-goal path planning and collision avoidance for USVs in unknown and complex environments. By expanding the adjacent search range and setting a safe distance for USVs, we solve the issue of limited steering maneuverability in USVs with fewer DOF during autonomous navigation. We propose an approach to optimize the planned path during navigation by comparing the estimated distance with the actual distance between the current waypoint and the goal waypoint. A minimum binary heap is used to optimize the priority queue of the D* Lite and significantly reduce the path search time. Simulation results show that the improved D * Lite can significantly reduce the path planning time, optimize the planned path and solve the issue of limited steering maneuverability in USVs. We apply the algorithm to a real USV for further tests. Experimental results show that the USV can plan an optimized path while avoiding both static and dynamic obstacles in complex environments with a safe distance during autonomous navigation.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Maritime Navigation and Safety · Robotic Path Planning Algorithms · Maritime Security and History
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computing, Xi’an Jiaotong-Liverpool University, Suzhou 215123, China
Jiangnan Rural Commercial Bank, Jintan District, Changzhou 213200, China
References (31)
Show source-provided references
1. Real-time remote monitoring of water quality: A review of current applications, and advancements in sensor, telemetry, and computing technologies10.1016/j.jembe.2004.02.022 ↗
2. Unmanned surface vehicles: An overview of developments and challenges10.1016/j.arcontrol.2016.04.018 ↗
3. Li, Z., Bachmayer, R., and Vardy, A. (2017, January 19–22). Vector field path following control for unmanned surface vehicles. Proceedings of the OCEANS 2017-Aberdeen, Aberdeen, UK.10.1109/OCEANSE.2017.8084878 ↗
4. A constrained A* approach towards optimal path planning for an unmanned surface vehicle in a maritime environment containing dynamic obstacles and ocean currents10.1016/j.oceaneng.2018.09.016 ↗
5. An adaptive obstacle avoidance algorithm for unmanned surface vehicle in complicated marine environments10.1109/JAS.2014.7004666 ↗
6. The improved dijkstra’s shortest path algorithm and its application10.1016/j.proeng.2012.01.110 ↗
7. DL-RRT* algorithm for least dose path Re-planning in dynamic radioactive environments10.1016/j.net.2018.11.018 ↗
8. A formal basis for the heuristic determination of minimum cost paths10.1109/TSSC.1968.300136 ↗
9. Cabreira, T.M., Brisolara, L.B., and Ferreira, P.R. (2019). Survey on coverage path planning with unmanned aerial vehicles. Drones, 3.10.3390/drones3010004 ↗
10. D* lite algorithm based path planning of mobile robot in static Environment
11. Stentz, A. (1994). The D* Algorithm for Real-Time Planning of Optimal Traverses, Robotics Institute, Carnegie Mellon University. Technical Report.
12. Stentz, A. (1995, January 20–25). The focussed dˆ* algorithm for real-time replanning. Proceedings of the International Joint Conference on Artificial Intelligence, Montreal, QC, Canada.
13. Implementation of Path Finding on 2D Game Maps
14. Guo, J., Liu, L., Liu, Q., and Qu, Y. (2009, January 16). An Improvement of D* Algorithm for Mobile Robot Path Planning in Partial Unknown Environment. Proceedings of the 2009 Second International Conference on Intelligent Computation Technology and Automation, Changsha, China.10.1109/ICICTA.2009.561 ↗
15. Yan, B., Chen, T., Zhu, X., Yue, Y., Xu, B., and Shi, K. (2020, January 16–17). A Comprehensive Survey and Analysis on Path Planning Algorithms and Heuristic Functions. Proceedings of the Science and Information Conference, London, UK.10.1007/978-3-030-52249-0_39 ↗
16. Likhachev, M., and Koenig, S. (2005, January 5–10). A Generalized Framework for Lifelong Planning A* Search. Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling (ICAPS 2005), Monterey, QC, USA.
17. Ferguson, D., and Stentz, A. (2007). Field D*: An interpolation-based path planner and replanner. Robotics Research, Springer.10.1007/978-3-540-48113-3_22 ↗
18. Koenig, S., and Likhachev, M. (1August, January 28). Dˆ* lite. Proceedings of the AAAI Conference on Artificial Intelligence, Edmonton, AB, Canada.
19. Fast replanning for navigation in unknown terrain10.1109/TRO.2004.838026 ↗
20. Oral, T., and Polat, F. (2012, January 4–7). A multi-objective incremental path planning algorithm for mobile agents. Proceedings of the 2012 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, Macau, China.10.1109/WI-IAT.2012.143 ↗
21. Ferguson, D., and Stentz, A. (2005, January 18–22). The delayed D* algorithm for efficient path replanning. Proceedings of the 2005 IEEE International Conference on Robotics and Automation, Barcelona, Spain.
22. Al-Mutib, K., AlSulaiman, M., Emaduddin, M., Ramdane, H., and Mattar, E. (2011, January 20–22). D* lite based real-time multi-agent path planning in dynamic environments. Proceedings of the 2011 Third International Conference on Computational Intelligence, Modelling & Simulation, Langkawi, Malaysia.10.1109/CIMSim.2011.38 ↗
23. Yu, J., Liu, G., Zhao, Z., Wang, X., Xu, J., and Bai, Y. (2020, January 6–8). Improved D* Lite algorithm path planning in complex environment. Proceedings of the 2020 Chinese Automation Congress (CAC), Shanghai, China.10.1109/CAC51589.2020.9327404 ↗
24. Yue, W., Franco, J., Cao, W., and Yue, H. (2011, January 21–24). ID* Lite: Improved D* Lite algorithm. Proceedings of the 2011 ACM Symposium on Applied Computing, TaiChung, Taiwan.10.1145/1982185.1982483 ↗
25. Yun, S.C., Ganapathy, V., and Chien, T.W. (2010, January 3–5). Enhanced D* Lite Algorithm for mobile robot navigation. Proceedings of the 2010 IEEE Symposium on Industrial Electronics and Applications (ISIEA), Penang, Malaysia.
26. Le, A.T., Bui, M.Q., Le, T.D., and Peter, N. (2017, January 10–12). D* Lite with Reset: Improved Version of D* Lite for Complex Environment. Proceedings of the IEEE International Conference on Robotic Computing, Taichung, Taiwan.10.1109/IRC.2017.52 ↗
27. A 2-opt guided discrete antlion optimization algorithm for multi-depot vehicle routing problem
28. Ravankar, A., Ravankar, A.A., Kobayashi, Y., Hoshino, Y., and Peng, C.C. (2018). Path smoothing techniques in robot navigation: State-of-the-art, current and future challenges. Sensors, 18.10.3390/s18093170 ↗
29. Zagradjanin, N., Pamucar, D., and Jovanovic, K. (2019). Cloud-based multi-robot path planning in complex and crowded environment with multi-criteria decision making using full consistency method. Symmetry, 11.10.3390/sym11101241 ↗
30. Optimizing binary heaps10.1007/s00224-017-9760-2 ↗
31. Yang, L., Qi, J., Song, D., Xiao, J., Han, J., and Xia, Y. (2016). Survey of robot 3D path planning algorithms. J. Control. Sci. Eng., 2016.10.1155/2016/7426913 ↗