Example methods for multistage autonomous vehicle motion planning include obtaining sensor data descriptive of an environment of the autonomous vehicle; identifying one or more objects in the environment based on the sensor data; generating a plurality of candidate strategies, wherein each candidate strategy of the plurality of candidate strategies comprises a set of discrete decisions respecting the one or more objects, wherein generating the plurality of candidate strategies includes: determining that at least two strategies satisfy an equivalence criterion, such that the plurality of candidate strategies include at least one candidate strategy corresponding to an equivalence class representative of a plurality of different strategies that are based on different discrete decisions; determining candidate trajectories respectively for the plurality of candidate strategies; and initiating control of the autonomous vehicle based on a selected candidate trajectory.