Autonomous underwater vehicles (AUVs) have successfully performed complex behaviors in the service of military objectives. These behaviors have involved individual vehicles, but multiple vehicles operating autonomously and collaboratively are required to engage in open environment missions such as mine countermeasures (MCM). This requires that vehicles communicate with one another, exchanging information that can be processed logically to ensure flexible, coordinated behavioral responses. In this paper, field experiments involving a fleet of five communicating AUVs operating collaboratively underwater are described. These experiments focus on three behaviors: vehicle replacement, leader replacement, and fleet self-organization. These behaviors are not choreographed in advance or controlled by an operator as they unfold; rather, they arise when the vehicles identify the need to respond to changing circumstances and do so in a collaborative fashion. This identification and coordinated response is dependent on a language for communicating environmental information and logics that process this information. The language and logics used to support the field experiments are also presented.