Why is it so hard to deploy autonomous service mobile robots in unstructured human environments, and to keep them autonomous? In this talk, I will explain three key challenges, and our recent research in overcoming them: 1) ensuring robustness to environmental changes; 2) anticipating and overcoming failures; and 3) efficiently adapting to user needs. To remain robust to environmental changes, we build probabilistic perception models to explicitly reason about object permanence and distributions of semantically meaningful movable objects.