Experiments showed that Hierarchical Task Network (HTN) planners are suitable to find solutions for nontrivial tasks in complex scenarios. Mobile service robots are able to execute actions which may constitute the basic building blocks to achieve high-level goals. However, only few experiments demonstrate the application of a general purpose deliberative planner in the domain of mobile service robots. One challenging problem arises from the fact that adaptive AI-based planners presume the closed-world assumption (CWA) and are therefore unable to deal with incomplete information. Unknown objects which are not represented in the planning domain, for example, cannot be integrated into the planning process. Since mobile service robots act in a real dynamic environment and construct or adapt their world model autonomously based on sensory data, they are inevitably confronted with uncertain and incomplete information about the world. This conflict between simplified assumptions for planning on the one hand and the complexity of the real world on the other constitutes a major problem of modern robotics. This paper describes two approaches to dealing with incomplete world knowledge in the context of HTN robot planning. Several experiments demonstrate that the approaches can successfully be applied in a dynamic and unstructured environment.