The paper focuses on the navigation subsystem of a mobile robot which operates in human environments to carry out different tasks, such as transporting waste in hospitals or escorting people in exhibitions. The paper describes a hybrid approach (Roaming Trails), which integrates a priori knowledge of the environment with local perceptions in order to carry out the assigned tasks efficiently and safely: that is, by guaranteeing that the robot can never be trapped in deadlocks even when operating within a partially unknown dynamic environment. The article includes a discussion about the properties of the approach, as well as experimental results recorded during real-world experiments.