Abstract: Objectives Aiming at the typical application scenarios of underwater vehicles performing search tasks in the target sea area, this paper studies and analyzes how to achieve efficient no-dead coverage search in the unknown sea area without prior information and detection capability constraints. Methods A mathematical model of path planning for searching unknown sea area was established, and a heuristic solution based on two-stage programming was designed for random search strategy. Results In the rectangular sea area, the efficiency of parallel search or spiral search was the highest, and the efficiency of “Z-word” search was the lowest. In the circular sea area, the spiral search efficiency is the highest. In the irregular sea area, parallel search, “Z-word search” and spiral search cannot be directly applied, and random search can find a group of near optimal solutions without approximate processing of the sea area. Conclusions The mathematical model established in this paper can meet the conditions of "full coverage of unknown sea area" and "complete search in the shortest time". The designed two-stage stochastic search planning model algorithm can solve the problem without discretization of physical space, constraint conditions and decision variables. A random search route satisfying the requirement of full coverage is planned for any irregularly connected sea area.