Aspects of the disclosure provide for generation of trajectories for a vehicle driving in an autonomous driving mode. For instance, information identifying a plurality of objects in the vehicle's environment and a confidence value for each of the objects is received. A set of constraints may be generated. That one or more processors are unable to solve for a trajectory given the set of constraints and an acceptable braking limit may be determined. A first constraint is identified as a constraint for which could not be solved and a first confidence value. That the vehicle should apply a maximum braking level is determined based on the identified first confidence value, a threshold, and the determination that the one or more processors are unable to solve for a trajectory. Based on the determination that the vehicle should apply the maximum braking level, the maximum braking level is applied.