Processing circuitry selects surrogate time instances respectively representing temporal subsets of a time duration of a first intermediate trajectory for a robot. The processing circuitry determines surrogate constraints respectively associated the surrogate time instances, the surrogate constraints require a distance between the robot and an obstacle to satisfy a safe distance requirement at the surrogate time instances. The processing circuitry determines an adjustment from the first intermediate trajectory to a second intermediate trajectory based on the surrogate constraints. The processing circuitry determines a first strict surrogate constraint for a first surrogate time instance representing a first temporal subset based on the first temporal subset, the first strict surrogate constraint ensures the safe distance requirement being satisfied in the first temporal subset in response to the first strict surrogate constraint being satisfied. The processing circuitry performs a safety check of the second intermediate trajectory according to the first strict surrogate constraint.