In this paper, we propose a method to automate the exploration of unknown underwater structures for autonomous underwater vehicles (AUVs). The proposed algorithm iteratively incorporates exteroceptive sensor data and replans the next-best-view (NBV) in order to fully map an underwater structure. This approach does not require prior environment information. However, a safe exploration depth and the exploration area (defined by a bounding box, parametrized by its size, location and resolution) must be provided by the user. The algorithm operates online by iteratively conducting the following three tasks: 1) Profiling sonar data is firstly incorporated into a 2-dimensional (2D) grid map, where voxels are labeled according to their state (a vox...