Aspects of the disclosure provide for controlling an autonomous vehicle. For example, a set of potential stopping locations may be identified based on a current location of an autonomous vehicle. A set of potential states may be identified for the autonomous vehicle. A fallback cost for each potential state of the set of potential states to reach each potential stopping location of the set of potential stopping locations may be determined. A trajectory for an autonomous vehicle may be planned based on a route to a destination and the determined fallback costs. The autonomous vehicle may be controlled according to at least a portion of the trajectory.