This paper introduces a collision prediction and avoidance algorithm for multi-vehicle time-critical cooperative missions. The algorithm extends our previous results on collision avoidance based on speed adjustment and allows for safe operation in a wider range of collision scenarios. Unlike the speed-adjustment method, the new algorithm changes the shape of the vehicle’s planned trajectory by adding an appropriate detour. We show that the bounds on the changes in position, velocity and acceleration, as a result of the path replanning, are computable and depend on the collision scenarios under consideration. Hence, these bounds can be used during the mission-planning phase, to ensure that the replanned path satisfies the dynamic constraints of the vehicles.