In this work, we discuss a flexible on-line trajectory planning algorithm for autonomous underwater vehicles. For dynamically allocated way-points and surge velocities, an online algorithm computes polynomials that smoothly link the paths between these way-points, based on the kinematics of the vehicle. We devise a tracking controller that compensates for the nonlinearities of the rigid body dynamics in order to render it linear in closed-loop. For the attenuation of large disturbances an extended state observer is employed that helps improve the tracking performance. Simulation studies on real-world vehicle data underscore the usuablity of the advocated approach.