Methods and systems for determination of a routing policy for an autonomous vehicle

Methods and systems for determining an optimal routing policy for an autonomous vehicle. A set of states representing portions of lanes is determined, with a set of costs for actions (stay in lane, lane change, forced lane change) associated with each state; a lane change action has a non-deterministic outcome with a probability based on the length of the state, and an optimal routing policy is computed over the resulting model.