The problem of real-time motion planning of a mobile robot in an environment containing moving obstacles is examined. The considered dynamic model, constraints, and assumptions are presented. Objects, including the robot, are modeled as convex polyhedra. Collision avoidance is guaranteed if the minimum distance between the robot and the objects is nonzero. A nominal trajectory is assumed to be known from offline planning. The main idea is to change the velocity along the nominal trajectory so that collisions are avoided. Furthermore, consistency with the nominal plan is desirable. An optimization problem is stated, and a close-to-optimal solution is derived. Simulation results verify the value of the proposed strategy.