By utilizing onboard sensors such as side-scan or forward-looking sonar, autonomous underwater robots can perform many useful tasks, such as exploring and searching for targets in underwater environments. In order to recognize and classify objects with high confidence, however, these mobile sensors must obtain multiple looks or "views" for each target using different positions and orientations that allow for a different interpretation based on local occlusions and environmental conditions. As a result, when tasked with classifying many targets, the mobile sensor must find the most efficient path through multiple configurations in an effort to reduce the cost and time required by each underwater mission. This dissertation presents a novel and general approach, referred to as informative multi-view planning (IMVP), that simultaneously determines the most informative sequence of views and the shortest path between them. The approach is demonstrated both in simulations and sea tests using an unmanned underwater vehicle (UUV) equipped with a side-scan sonar (SSS) and engaged in underwater multi-target classification. Both simulation and experimental results show that IMVP achieves excellent classification performance while reducing the total time required by the mission by up to half the time required by state-of-the-art multi-view path planning methods. One reason is that IMVP utilizes knowledge of the automatic target recognition (ATR) algorithm, as well as prior measurements, in order to determine the most informative views. Additionally, by using knowledge of the target location and field-of-view (FOV) geometry, IMVP is able to find the shortest path between them by solving a traveling salesman problem with neighborhoods (TSPN). In this dissertation, a novel physics-inspired algorithm based on Lin-Kernighan heuristic (LKH) is developed for searching for the optimal TSPN path for multiple non-disjoint neighborhoods. It is shown that the LKH algorithm is able to decrease the computational complexity of TSPN solutions by leveraging the intersections of valuable neighborhoods using computational geometry constructs known as coverage cones. When compared to state-of-the-art TSPN algorithms, the proposed method is able to find shorter paths with either comparable or reduced computation. The advantages of the LKH algorithm are found to become more significant as the number of intersecting neighborhoods increases, thus also allowing the mobile sensor to observe multiple targets from a single configuration.