In this paper we report about ongoing research on navigation assistance in virtual environments. Our aim is to contribute to the development of forms of navigation assistance that enable non-professional visitors of a virtual environment to find their way without previous training. The environment used in this research is a virtual theatre that models a real world music theatre. This virtual theatre can be used for exploration as well as for transactions and goal-directed search for information. We first present some design principles for navigation assistance in virtual environments and some design criteria for assistance by personal agents. Subsequently we describe how these principles and criteria have been implemented in our experimental virtual theatre environment. Finally we give an overview of future research plans.