The present disclosure provides autonomous vehicle systems and methods that include or otherwise leverage a motion planning system that solves gridlock as part of determining a motion plan for an autonomous vehicle (AV). In particular, a scenario generator within a motion planning system can determine one or more keep clear areas associated with the lane sequence, each keep clear area indicative of a region along the nominal path in which gridlock prevention is desired. A gridlock constraint can be generated for each of the one or more keep clear areas, each constraint being defined as a constraint area in a multi-dimensional space. A low-cost trajectory path can be determined through a portion of the multi-dimensional space that minimizes exposure to the constraint areas and that is consistent with all constraints generated for the one or more objects of interest and the one or more keep clear areas.