There is increasing interest in the deployment and operation of multiple autonomous marine vehicles (AMVs) for a number of challenging scientific and commercial operational mission scenarios. Some of the missions, such as geotechnical surveying and 3D marine habitat mapping, require that a number of heterogeneous vehicles operate simultaneously in small areas, often in close proximity of each other. In these circumstances safety, reliability, and efficient multiple vehicle operation are key ingredients for mission success. Additionally, the deployment and operation of multiple AMVs at sea are extremely costly in terms of the logistics and human resources required for mission supervision, often during extended periods of time. These costs can be greatly minimized by automating the deployment and initial steering of a vehicle fleet to a predetermined configuration, in preparation for the ensuing mission, taking into account operational constraints. This is one of the core issues addressed in the scope of the Widely Scalable Mobile Underwater Sonar Technology project (WiMUST), an EU Horizon 2020 initiative for underwater robotics research.WiMUST uses a team of cooperative autonomous marine robots, some of which towing streamers equipped with hydrophones, acting as intelligent sensing and communicating nodes of a reconfigurable moving acoustic network. In WiMUST, the AMVs maintain a fixed geometric formation through cooperative navigation and motion control. Formation initialization requires that all the AMVs start from scattered positions in the water and maneuver so as to arrive at required target configuration points at the same time in a completely automatic manner. This paper describes the decoupled prioritized vehicle motion planner developed in the scope of WiMUST that, together with an existing system for trajectory tracking, affords a fleet of vehicles the above capabilities, while ensuring inter-vehicle collision and streamer entanglement avoidance. Tests with a fleet of seven marine vehicles show the efficacy of the system planner developed.