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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 2077-1312 |