A Low-Complexity Path-Planning Algorithm for Multiple USVs in Task Planning Based on the Visibility Graph Method
Path planning for multiple unmanned surface vehicles (USVs) in task planning is a high-complexity problem. When the number of USVs is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>n</mi></semantic...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-03-01
|
| Series: | Journal of Marine Science and Engineering |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2077-1312/13/3/556 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850090421733031936 |
|---|---|
| author | Kai Xue Zhiqin Huang Ping Wang Zeyu Xu Decheng Kong |
| author_facet | Kai Xue Zhiqin Huang Ping Wang Zeyu Xu Decheng Kong |
| author_sort | Kai Xue |
| collection | DOAJ |
| description | Path planning for multiple unmanned surface vehicles (USVs) in task planning is a high-complexity problem. When the number of USVs is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>n</mi></semantics></math></inline-formula>, the computational complexity is usually as high as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced><mrow><msup><mi>n</mi><mn>2</mn></msup></mrow></mfenced></mrow></semantics></math></inline-formula>, as paths need to be planned from different start points to different target points. In this paper, we propose a low-complexity path-planning algorithm (LCPP) for multiple USVs based on the visibility graph method. First, all paths between the start points, target points, and obstacle vertices are separately planned with the low-complexity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced><mi>n</mi></mfenced></mrow></semantics></math></inline-formula>. After that, the Dijkstra algorithm is employed to find the shortest path from each start point to all target points, also with the low-complexity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced><mi>n</mi></mfenced></mrow></semantics></math></inline-formula>. To enhance the safety of each USV traveling along the edge of obstacles, the parameters of the adaptive line-of-sight (ALOS) guidance algorithm are optimized using the simulated annealing algorithm. The simulation results show that this algorithm outperforms others in calculation time when dealing with a large number of USVs. |
| format | Article |
| id | doaj-art-b276fb9e10c343f7b7ca62b649bd7f30 |
| institution | DOAJ |
| issn | 2077-1312 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Journal of Marine Science and Engineering |
| spelling | doaj-art-b276fb9e10c343f7b7ca62b649bd7f302025-08-20T02:42:34ZengMDPI AGJournal of Marine Science and Engineering2077-13122025-03-0113355610.3390/jmse13030556A Low-Complexity Path-Planning Algorithm for Multiple USVs in Task Planning Based on the Visibility Graph MethodKai Xue0Zhiqin Huang1Ping Wang2Zeyu Xu3Decheng Kong4College of Mechanical and Electrical Engineering, Harbin Engineering University, Harbin 150001, ChinaCollege of Mechanical and Electrical Engineering, Harbin Engineering University, Harbin 150001, ChinaCollege of Mechanical and Electrical Engineering, Harbin Engineering University, Harbin 150001, ChinaCollege of Mechanical and Electrical Engineering, Harbin Engineering University, Harbin 150001, ChinaCollege of Mechanical and Electrical Engineering, Harbin Engineering University, Harbin 150001, ChinaPath planning for multiple unmanned surface vehicles (USVs) in task planning is a high-complexity problem. When the number of USVs is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>n</mi></semantics></math></inline-formula>, the computational complexity is usually as high as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced><mrow><msup><mi>n</mi><mn>2</mn></msup></mrow></mfenced></mrow></semantics></math></inline-formula>, as paths need to be planned from different start points to different target points. In this paper, we propose a low-complexity path-planning algorithm (LCPP) for multiple USVs based on the visibility graph method. First, all paths between the start points, target points, and obstacle vertices are separately planned with the low-complexity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced><mi>n</mi></mfenced></mrow></semantics></math></inline-formula>. After that, the Dijkstra algorithm is employed to find the shortest path from each start point to all target points, also with the low-complexity <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced><mi>n</mi></mfenced></mrow></semantics></math></inline-formula>. To enhance the safety of each USV traveling along the edge of obstacles, the parameters of the adaptive line-of-sight (ALOS) guidance algorithm are optimized using the simulated annealing algorithm. The simulation results show that this algorithm outperforms others in calculation time when dealing with a large number of USVs.https://www.mdpi.com/2077-1312/13/3/556path planninglow complexityunmanned surface vehiclevisibility graphline of sight |
| spellingShingle | Kai Xue Zhiqin Huang Ping Wang Zeyu Xu Decheng Kong A Low-Complexity Path-Planning Algorithm for Multiple USVs in Task Planning Based on the Visibility Graph Method Journal of Marine Science and Engineering path planning low complexity unmanned surface vehicle visibility graph line of sight |
| title | A Low-Complexity Path-Planning Algorithm for Multiple USVs in Task Planning Based on the Visibility Graph Method |
| title_full | A Low-Complexity Path-Planning Algorithm for Multiple USVs in Task Planning Based on the Visibility Graph Method |
| title_fullStr | A Low-Complexity Path-Planning Algorithm for Multiple USVs in Task Planning Based on the Visibility Graph Method |
| title_full_unstemmed | A Low-Complexity Path-Planning Algorithm for Multiple USVs in Task Planning Based on the Visibility Graph Method |
| title_short | A Low-Complexity Path-Planning Algorithm for Multiple USVs in Task Planning Based on the Visibility Graph Method |
| title_sort | low complexity path planning algorithm for multiple usvs in task planning based on the visibility graph method |
| topic | path planning low complexity unmanned surface vehicle visibility graph line of sight |
| url | https://www.mdpi.com/2077-1312/13/3/556 |
| work_keys_str_mv | AT kaixue alowcomplexitypathplanningalgorithmformultipleusvsintaskplanningbasedonthevisibilitygraphmethod AT zhiqinhuang alowcomplexitypathplanningalgorithmformultipleusvsintaskplanningbasedonthevisibilitygraphmethod AT pingwang alowcomplexitypathplanningalgorithmformultipleusvsintaskplanningbasedonthevisibilitygraphmethod AT zeyuxu alowcomplexitypathplanningalgorithmformultipleusvsintaskplanningbasedonthevisibilitygraphmethod AT dechengkong alowcomplexitypathplanningalgorithmformultipleusvsintaskplanningbasedonthevisibilitygraphmethod AT kaixue lowcomplexitypathplanningalgorithmformultipleusvsintaskplanningbasedonthevisibilitygraphmethod AT zhiqinhuang lowcomplexitypathplanningalgorithmformultipleusvsintaskplanningbasedonthevisibilitygraphmethod AT pingwang lowcomplexitypathplanningalgorithmformultipleusvsintaskplanningbasedonthevisibilitygraphmethod AT zeyuxu lowcomplexitypathplanningalgorithmformultipleusvsintaskplanningbasedonthevisibilitygraphmethod AT dechengkong lowcomplexitypathplanningalgorithmformultipleusvsintaskplanningbasedonthevisibilitygraphmethod |