A heuristic for task allocation and path planning of multiple tethered underwater robots considering workload balance

This paper introduces a heuristic approach to address the operational challenges of task allocation and path planning of multiple tethered underwater robot (TUR) systems while ensuring tether entanglement avoidance. Multiple TUR systems, benefiting from bottomless power and stable communication via tethers, hold significant potential for various applications, including ecosystem exploration, infrastructure inspection, maintenance, search and rescue, underwater construction, and surveillance. However, successful operations rely on preventing tether entanglement. Our preliminary research developed a heuristic that involves task assignment and subsequent task reordering to mitigate entanglement issues. Building upon this foundation, we present a simple iterative heuristic that simultaneously allocates tasks while proactively considering potential entanglements during operations. We evaluated the proposed algorithm through simulation testing with varying problem sizes and presented the results compared with our preliminary work. The computational results demonstrate the algorithm’s efficacy and potential for real-time application, offering reliable solutions within reasonable timeframes. This research contributes to advancing the field of operational research in the application of underwater robotics and holds promise for practical implementation in multiple TUR systems.