A control architecture for executing multi-vehicle search algorithms is presented. The proposed hierarchical structure consists of three control layers: maneuver controllers, vehicle supervisors and team controllers. The system model is described as a dynamic network of hybrid automata in the programming language Shift and allows reasoning about specification and dynamical properties in a formal setting. The particular search problem that is studied is that of finding the minimum of a scalar field using a team of autonomous submarines. As an illustration, a coordination scheme based on the Nelder-Mead simplex optimization algorithm is presented and illustrated through simulations.