Accurate localization is one of the biggest challenges in underwater robotics. The primary reasons behind that are unavailability of satellite-based positioning below the surface, and lack of clear features in natural water bodies for visually aided localization. As such, the common method of choice for external position referencing in underwater robots is the use of acoustic signals for computing range or direction of arrival. To that end, we have developed an acoustic range based navigation system with floating, movable beacons. In this paper, we present an approach for planning the trajectory of acoustic beacons in a way that they provide the best possible navigation support for a group of underwater vehicles. We use an information theoretic approach to beacon path planning that minimizes the group’s position uncertainty. We evaluate our approach with realistic simulations calibrated using real-world data, and present results.