With growing interest in the application of research to problems that arise in real-world contexts, issues raised by consideration of uncertain states and unreliable operators are receiving increased attention in artificial intelligence research. In this paper, a model is presented for dealing with such concerns. The model is a probabilistic generalization of the familiar notion of problem space. The specification of uncertain states and unreliable operators is discussed. Problem-solving search methods are described. The need for information gathering is established. Search methods are generalized to produce tree-structured plans incorporating the use of such operators. Several application domains for our model are discussed.