We present an approach for planning collision-free paths on-line for an underwater multi-robot system, which is composed by a leading Autonomous Underwater Vehicle (AUV) endowed with a multibeam sonar and high processing capabilities and a second AUV. While the leading AUV follows a safe, pre-planned survey path, the second vehicle, herein referred to as Camera Vehicle (CV), must survey the bottom in close proximity while following the leader, complementing its survey capabilities. Due to their proximity to the bottom, the CV is exposed to a collision threat. We address this problem by incrementally building a 3D map of the environment onboard the leading vehicle by means of its multibeam sonar. Using this map, we plan on-line 3D paths that are transferred to the CV for close and safe surveying of the bottom. These paths are planned using the Transition-based RRT (T-RRT) algorithm, which is an RRT-variant that considers a cost function defined over the vehicle’s configuration space, or costmap for short. By defining a costmap in terms of distance to the bottom and path distance, we are able to keep the paths at a desired offset distance from the bottom for constant-resolution surveying. We have integrated our path planning system with the software architecture of the SPARUS-II and GIRONA500 AUVs. We demonstrate the feasibility of our approach in simulation. The multi-robot system presented is based on the context of the MORPH FP7 EU project.