Autonomous robots need the ability to perceive and model their environment and to make appropriate decisions in complex situations on their own. The complexity results from the high-dimensional perceptions, the large number of possible actions and the uncertainty about the state of the world. Probabilistic approaches offer ways for addressing these problems since they allow for explicitly modeling noise, for making decisions under uncertainty, and thus for acting robustly. In this talk, I will present recent approaches for solving different problems in the context of robot navigation and will point out challenges to address in order to build more flexible systems. This includes techniques for building maps of the environment and for relating built models with existing information sources. These are important capabilities for robots to robustly navigate in dynamic environments and crowded city scenes