In order to enhance the behavior of autonomous service robots, we are exploring multiple paradigms for their planning and execution strategy (the way of interleaving the planning, selection and execution of actions). In this paper we focus on continuous proactive planning with multiple hypotheses in order to continuously generate multiple solution-plans from which an action can be selected when appropriate. To illustrate the concepts, we develop how it could be used for autonomous navigation in dynamic environments, and analyze the tests we realized with several instantiations. We also discuss several aspects and concerns about the proposed strategy, and how integrating more semantic information could enhance the capabilities of service robots for real-world applications.