AbstractThis paper shows how existing methods of probabilistic least‐squares classification based on Gaussian processes can be used to construct a probabilistic representation of a habitat map using data collected by an autonomous underwater vehicle (AUV). A novel adaptive habitat classifying algorithm is presented, which uses a Monte Carlo simulation technique to select the most informative mission from a set of candidates. Approximations are presented to assign upper and lower bounds to the information expected from the candidate missions. This allows missions to be efficiently pruned from the set of candidates so that the algorithm converges to a preferred candidate with a reduced number of simulations. The performance of this algorithm is evaluated in an experiment carried out using an AUV at Jervis Bay, Australia. © 2010 Wiley Periodicals, Inc.