Coral reef ecosystems worldwide are rapidly changing due to a host of natural and anthropogenic ecological pressures including climate change, disease outbreaks such as stony coral tissue loss disease, and invasive species. This motivates taking comprehensive inventories of reefs as soon and as often as possible, enabling early and continuous detection of new threats with the goal of aiding conservation and restoration efforts. However, the size and number of the world’s reefs makes it infeasible to monitor them at sufficient spatiotemporal resolutions via only diver-based surveys and manual analysis. To help overcome this challenge, we present a novel vision based semantic perception algorithm on an Autonomous Underwater Vehicle (AUV) platform, capable of automatically constructing, in realtime, 3D reef models and maps that depict a reef’s benthic composition. The innovative robot system consists of an Autonomous Surface Vehicle (ASV) and one or more AUVs, designed by our lab. These vehicles are small enough to be packed in airline baggage, making it feasible for a small team to deploy them anywhere at low-cost. The ASV provides realtime AUV monitoring and enables the AUVs to localize themselves precisely so that they can repeat identical reef surveys. The forward and downward facing stereo-camera systems on each AUV enable them to conduct concurrent benthic mapping, fish surveys, biodiversity assessments, and coral disease surveys. The stereo-imagery is converted into 3D models, enabling accurate size estimation of fish and corals as well as 3D modeling of entire reefs. A key feature of our system is the automatic discovery of the “topics” used to label each 0.5 m2 (adjustable) grid cell of the benthos, which we show can be mapped to ecologically relevant categories such as “hard coral”, “soft coral”, and “seagrass”. It accomplishes this using a novel unsupervised spatiotemporal topic modeling algorithm we developed. We compare the benthic composition reports generated by this algorithm to those produced by scientist divers at the same reef sites around the US Virgin Islands. Furthermore, the algorithm can flag novel or unusual observations; we explore the potential of using this capability to identify coral diseases and bleaching without training data. We also explore how our robots can be used in scientist-in-the-loop approaches to guide targeted scientific analysis, and how they will be augmented to enable bio-acoustic biodiversity monitoring.