The absence of GPS underwater makes navigation for Autonomous Underwater Vehicles (AUVs) a difficult challenge. Without an external reference in the form of acoustic beacons at known positions, the vehicle has to rely on proprioceptive information obtained through a compass, a Doppler Velocity Logger (DVL) or an Inertial Navigation System (INS). Independent of the quality of the sensors used, the error in the position estimate based on dead-reckoning information grows without bound. Typical navigation errors are 0.5% to 2% of distance traveled for vehicles traveling within a few hundred meters of the sea floor such that their DVL has a lock on the bottom. Errors as low as 0.1% can be obtained with large and expensive INS systems, but for vehicles relying only on a compass and a speed estimate can be as high as 10%. By surfacing the AUV can obtain a position update through its GPS, but this is impossible (under ice) or undesirable for many applications. The use of static beacons in the form of a Long Baseline (LBL) array limits the operation area to a few km2 and requires a substantial deployment effort before operations, especially in deep water. As underwater vehicles become more reliable and affordable the simultaneous use of several AUVs recently became a viable option and multi-vehicle deployments will become standard in the upcoming years. This will not only make entirely new types of missions which rely on cooperation possible, but will also allow each individual member of the group to benefit from navigation information obtained from other members. For optimal cooperative localization a few dedicated Communication and Navigation Aid-AUVs (CNAs), which maintain an accurate estimate of their position through sophisticated DVL and INS sensors, can enable a much larger group of vehicles with less sophisticated navigation suites to maintain an accurate position.