Coordinating Tethered Autonomous Underwater Vehicles towards Entanglement-Free Navigation

This paper proposes an algorithm that provides operational strategies for multiple tethered autonomous underwater vehicle (T-AUV) systems for entanglement-free navigation. T-AUVs can perform underwater tasks under reliable communication and power supply, which is the most substantial benefit of their operation. Thus, if one can overcome the entanglement issues while utilizing multiple tethered vehicles, the potential applications of the system increase including ecosystem exploration, infrastructure inspection, maintenance, search and rescue, underwater construction, and surveillance. In this study, we focus on developing strategies for task allocation, path planning, and scheduling that ensure entanglement-free operations while considering workload balancing among the vehicles. We do not impose restrictions on the size or shape of the vehicles at this stage; our primary focus is on efficient tether management as an initial work on the topic. To achieve entanglement-free navigation, we propose a heuristic based on the primal-dual technique, which enables initial task allocation and path planning while minimizing the maximum travel cost of the vehicles. Although this heuristic often