Dynamic routing for autonomous vehicles

1. A method for maneuvering a vehicle, the method comprising:

generating, by one or more processors, a route for a trip from a first location to a destination using map information, the map information including roadway segments defining the shape and location of roadways, the map information also identifying at least one no-go roadway segment defining roadway segments where the vehicle is not able to drive in an autonomous mode;

identifying, by the one or more processors, from the map information, a set of no-go roadway segments relevant to the route from the plurality of no-go roadway segments;

determining, by the one or more processors, a local region around a current location of the vehicle, the local region corresponding to a geographic area including both locations that the vehicle is able to reach from the current location within a pre-determined period of time as well as a region behind the vehicle at the current location;

identifying, by the one or more processors, a local map region by performing a graph cut on the map information, the local map region including roadway segments of the map information;

filtering, by the one or more processors, the set of the plurality of no-go roadway segments from the roadway segments of the local map region;

assigning, by the one or more processors, a cost value to each roadway segment of the filtered roadway segments of the local map region;

using, by the one or more processors, any assigned cost values to determining a plan for maneuvering the vehicle for a predetermined period of time into the future; and

maneuvering, by the one or more processors, the vehicle according to the plan.

2. The method of claim 1 , further comprising identifying at least one additional no-go roadway segment which would not allow the vehicle to reach the destination using a graph walk starting from the destination, and the set of no-go roadway segments includes the at least one no-go roadway segment as well as at least one additional roadway segment.

3. The method of claim 1 , wherein the local region is determined periodically and the set of no-go roadway segments are identified only once for the trip.

4. The method of claim 1 , wherein a cost value is assigned to a roadway segment of the filtered roadway segments of the local map region based on a construction area corresponding to the roadway segment.

5. The method of claim 1 , wherein a cost value is assigned to a roadway segment of the filtered roadway segments of the local map region based on an unprotected left turn corresponding to the roadway segment.

6. The method of claim 1 , wherein a cost value is assigned to a roadway segment of the filtered roadway segments of the local map region based on a time to reach the destination from the roadway segment.

7. The method of claim 1 , further comprising:

storing at least one assigned cost value in a local cache;

determining a second local region at least partially overlapping with the local region;

identify a second local map region including roadway segments of the map information that correspond to locations within the second local region;

filter the set of the plurality of no-go roadway segments from the roadway segments of the second local map region;

assigning a cost value to each roadway segment of the filtered roadway segments of the second local map region by retrieving the at least one assigned cost value from the local cache;

using any assigned cost values for each roadway segment of the filtered roadway segments of the second local map region to determining a second plan for maneuvering the vehicle for a second predetermined period into the future; and

maneuvering the vehicle according to the second plan.

8. The method of claim 1 , wherein the plan includes a set of connected roadway segments of the filtered roadway segments of the local map region that lead out of the local region and have a lowest accumulation of cost values.

9. The method of claim 1 , wherein determining the plan includes determining whether a lane change for the vehicle should be forced.

10. The method of claim 1 , wherein determining the plan includes determining whether a turn should be executed to move the vehicle between two lane roadway segments.

11. The method of claim 1 , wherein determining the plan includes identifying a secondary path when a primary path corresponding to the roadway segments of the route is not available.

12. The method of claim 1 , further comprising identifying a second set of no-go roadway segments using a graph walk on the map information starting from the destination and moving towards the staring location; and wherein filtering the set of no-go roadway segments includes removing any segments of the second set of no-go roadway segments.

13. The method of claim 1 , wherein identifying the second set of no-go roadway segments includes identifying segments of the map information that will not get the vehicle to the destination.

14. A system for maneuvering a vehicle, the system comprising one or more processors configured to:

generate a route for a trip from a first location to a destination using map information, the map information including roadway segments defining the shape and location of roadways, the map information also identifying a plurality of no-go roadway segments defining roadway segments where the vehicle is not able to drive in an autonomous mode;

identify a set of no-go roadway segments relevant to the route from the plurality of no-go roadway segments;

determine a local region around a current location of the vehicle, the local region corresponding to a geographic area including both locations that the vehicle is able to reach from the current location within a pre-determined period of time as well as a region behind the vehicle at the current location;

identify a local map region by performing a graph cut on the map information, the local map region including roadway segments of the map information;

filter the set of the plurality of no-go roadway segments from the roadway segments of the local map region;

assign a cost value to each roadway segment of the filtered roadway segments of the local map region;

use any assigned cost values to determining a plan for maneuvering the vehicle for a predetermined period into the future; and

maneuver the vehicle according to the plan.

15. The method of claim 14 , wherein the one or more processors are further configured to identify at least one additional no-go roadway segment which would not allow the vehicle to reach the destination using a graph walk starting from the, and the set of no-go roadway segments includes the at least one no-go roadway segment as well as the at least one additional roadway segment.

16. The method of claim 14 , wherein the local region is determined periodically and the set of no-go roadway segments are identified only once for the trip.

17. The method of claim 14 , wherein a cost value is assigned to a roadway segment of the filtered roadway segments of the local map region based on a construction area corresponding to the roadway segment.

18. The method of claim 14 , wherein a cost value is assigned to a roadway segment of the filtered roadway segments of the local map region based on an unprotected left turn corresponding to the roadway segment.

19. The method of claim 14 , wherein a cost value is assigned to a roadway segment of the filtered roadway segments of the local map region based on a time to reach the destination from the roadway segment.

20. A non-transitory, computer readable medium on which instructions are stored, the instructions, when performed by one or more processors, cause the one or more processors to perform a method for maneuvering a vehicle, the method comprising:

generating a route for a trip from a first location to a destination using map information, the map information including roadway segments defining the shape and location of roadways, the map information also identifying a plurality of no-go roadway segments defining roadway segments where the vehicle is not able to drive in an autonomous mode;

identifying a set of no-go roadway segments relevant to the route from the plurality of no-go roadway segments;

determining a local region around a current location of the vehicle, the local region corresponding to a geographic area including both locations that the vehicle is able to reach from the current location within a pre-determined period of time as well as a region behind the vehicle at the current location;

identifying a local map region by performing a graph cut on the map information, the local map region including roadway segments of the map information;

filtering the set of no-go roadway segments from the roadway segments of the local map region;

assigning a cost value to each roadway segment of the filtered roadway segments of the local map region;

using any assigned cost values to determining a plan for maneuvering the vehicle for a predetermined period into the future; and

maneuvering the vehicle according to the plan.