Evaluating and refining undersea cable path planning algorithms: A comparative study

This paper compares three automated path-planning algorithms based on publicly available data. The algorithms include a Dijkstra-based algorithm (DBA) that improves on the straightforward application of Dijkstra’s algorithm, which restricts the path only to the grid edges. We present a fair and comprehensive comparison method for evaluating multiple algorithms—DBA, the Fast Marching Method (FMM), and a great circle-based method. To evaluate the performance of automated path-planning methods, we compare them based on two main criteria: (1) the total weighted cost which is a combined measure of various costs and risks of the cable path according to their weights, and (2) the algorithm’s runtime. FMM achieves a proven minimal weighted cost cable path solution given the data. This is not the case for the other two alternatives. On the other hand, DBA may have a runtime advantage over FMM. The paper discusses the sensitivity of DBA and FMM to diagonal configurations and to variation in the triangulation of the manifold, finding that DBA is more significantly affected by these factors than FMM. Furthermore, we explore how cable direction metrics can influence the performance of these methods. Through this comparative analysis, we aim to provide insights into the efficiency and effectiveness of these methods in practical scenarios and provide a useful reference for the industry in choosing the best approach for automatic cable path planning software.