Autonomous navigation in open and dynamic environments is an important challenge, requiring to solve several difficcult research problems located on the cutting edge of the state of the art. Basically, these problems may be classiffied into three main categories: a) SLAM in dynamic environments; b) Detection, characterization, and behavior prediction of the potential moving obstacles; and c) On-line motion planning and safe navigation decision based on world state predictions. This paper addresses some aspects of these problems and presents our latest approaches and results. The solutions we have implemented are mainly based on the followings paradigms: multiscale world representation of static obstacles based on the wavelet occupancy grid; adaptative clustering for moving obstacle detection inspired on Kohonen networks and the growing neural gas algorithm; and characterization and motion prediction of the observed moving entities using Hidden Markov Models coupled with a novel algorithm for structure and parameter learning.