Constraint-based speed profile

Determining a speed plan for an autonomous vehicle (AV) is disclosed. Planned locations of the AV for future time steps are placed in an occupancy grid. The planned locations are based on a strategic speed plan that is determined without taking world objects into account. Predicted locations of the world objects for at least some of the future time steps are placed in the occupancy grid. Respective buffer distances corresponding to the predicted locations are added in the occupancy grid. An estimated speed plan is identified for the AV based on the occupancy grid. The speed plan is obtained from the estimated speed plan. The AV is then controlled according to the speed plan.