Vehicle navigation in dynamic environments is an important challenge, especially when the motion of the objects populating the environment is unknown. Traditional motion planning approaches are too slow to be applied in real-time to this domain, hence, new techniques are needed. Recently, iterative planning has emerged as a promising approach. Nevertheless, existing iterative methods do not provide a way to es- timate the future behavior of moving obstacles and use the resulting estimates in trajectory computa- tion. This paper presents an iterative planning ap- proach that addresses these two issues. It consists of two complementary methods: 1) a motion prediction method which learns typical behaviors of objects in a given environment. 2) an iterative motion planning technique based on the concept of Velocity Obsta- cles.