Routing multiple autonomous vehicles using local and general route planning

1. A method to route a plurality of autonomous vehicles, comprising:

executing, by a batch routing system, a plurality of route workers, the batch routing system being a computing system;

receiving, by the batch routing system, a first general route cost request from a first autonomous vehicle, the first general route cost request describing a first trip endpoint and a first set of local route endpoints comprising a first local route endpoint and a second local route endpoint;

selecting, by the batch routing system, a first route worker from the plurality of route workers for responding to the first general route cost request, the selecting of the first route worker being based at least in part on a location of the first autonomous vehicle;

determining, by the first route worker, a first set of general routes for the first autonomous vehicle, the first set of general routes comprising a first general route from the first local route endpoint to a first trip endpoint and a second general route from the second local route endpoint to the first trip endpoint, the determining of the first set of general routes being based at least in part on cached data generated by the first route worker while determining a previous set of general routes for a second autonomous vehicle different than the first autonomous vehicle; and

sending, by the batch routing system, a first general route cost reply to the first autonomous vehicle, the first general route cost reply indicating a first set of costs associated with the first set of general routes, the first set of costs comprising a first general cost for the first general route and a second general cost for the second general route.

2. The method of claim 1 , wherein the first general route cost request comprises an identifier of the first autonomous vehicle, the method further comprising:

selecting a first route worker executing at the batch routing system using the identifier;

generating the first general route by the first route worker; and

generating the second general route by the first route worker.

3. The method of claim 2 , wherein generating the first general route by the first route worker comprises applying a constrained routing graph generated using at least one routing graph modification associated with the first autonomous vehicle.

4. The method of claim 2 , further comprising:

receiving, by the batch routing system, a first general route cost request from a third autonomous vehicle, the first general route cost request from the third autonomous vehicle comprising an identifier of the third autonomous vehicle, wherein the first autonomous vehicle is of a first type and the third autonomous vehicle is of a second type different than the first type;

selecting a second route worker executing at the batch routing system using the identifier of the third autonomous vehicle; and

generating a first general route cost for the third autonomous vehicle using the second route worker, wherein the generating of the first general route cost for the third autonomous vehicle is based at least in part on at least one routing graph modification associated with the second type and not associated with the first type.

5. The method of claim 2 , wherein generating the first general route comprises generating graph expansion data, further comprising:

receiving, by the batch routing system, a second general route cost request from the first autonomous vehicle, the second general route cost request describing a second set of local route endpoints;

selecting, by the batch routing system, the first route worker to generate general routes for the second general route cost request; and

generating, by the first route worker, a third general route from a third local route endpoint indicated by the second general route cost request to the first trip endpoint, wherein the generating of the third general route is based at least in part on the graph expansion data.

6. The method of claim 5 , further comprising:

receiving a first general route cost request from a third autonomous vehicle, the first general route cost request from the third autonomous vehicle describing a second trip endpoint;

determining that the second trip endpoint corresponds to a same graph element as the first trip endpoint; and

generating at least one general route responsive to the first general route cost request from the third autonomous vehicle using the first route worker.

7. The method of claim 1 , further comprising:

determining a metric describing route cost requests received by the batch routing system; and

initiating at least one route worker based at least in part on the metric.

8. The method of claim 1 , further comprising:

receiving, by the batch routing system, routing graph modification data describing a first routing graph modification; and

determining, by the batch routing system, that the first routing graph modification is for the first autonomous vehicle, wherein the determining of the first set of general routes is based at least in part on the first routing graph modification.

9. A batch routing system for routing a plurality of autonomous vehicles, the batch routing system comprising:

at least one processor; and

a non-transitory machine-readable medium having instructions thereon that, when executed by the at least one processor, cause the at least one processor to perform operations comprising:

executing a plurality of route workers;

receiving a first general route cost request from a first autonomous vehicle, the first general route cost request describing a first trip endpoint and a first set of local route endpoints comprising a first local route endpoint and a second local route endpoint;

selecting, a first route worker from the plurality of route workers for responding to the first general route cost request, the selecting of the first route worker being based at least in part on a location of the first autonomous vehicle;

determining, by the first route worker, a first set of general routes for the first autonomous vehicle, wherein the first set of general routes comprises a first general route from the first local route endpoint to a first trip endpoint and a second general route from the second local route endpoint to the first trip endpoint, the determining of the first set of general routes being based at least in part on cached data generated by the first route worker while determining a previous set of general routes for a second autonomous vehicle different than the first autonomous vehicle; and

sending a first general route cost reply to the first autonomous vehicle, the first general route cost reply indicating a first set of costs associated with the first set of general routes, wherein the first set of costs comprises a first general cost for the first general route and a second general cost for the second general route.

10. The batch routing system of claim 9 , wherein the first general route cost request comprises an identifier of the first autonomous vehicle, the operations further comprising:

selecting a first route worker executing at the batch routing system using the identifier;

generating the first general route by the first route worker; and

generating the second general route by the first route worker.

11. The batch routing system of claim 10 , wherein generating the first general route by the first route worker comprises applying a constrained routing graph generated using at least one routing graph modification associated with the first autonomous vehicle.

12. The batch routing system of claim 10 , the operations further comprising:

receiving a first general route cost request from a third autonomous vehicle, the first general route cost request from the third autonomous vehicle comprising an identifier of the third autonomous vehicle, wherein the first autonomous vehicle is of a first type and the third autonomous vehicle is of a second type different than the first type;

selecting a second route worker executing at the batch routing system using the identifier of the third autonomous vehicle; and

generating a first general route cost for the third autonomous vehicle using the second route worker, wherein the generating of the first general route cost for the third autonomous vehicle is based at least in part on at least one routing graph modification associated with the second type and not associated with the first type.

13. The batch routing system of claim 10 , wherein generating the first general route comprises generating graph expansion data, the operations further comprising:

receiving a second general route cost request from the first autonomous vehicle, the second general route cost request describing a second set of local route endpoints;

selecting the first route worker to generate general routes for the second general route cost request; and

generating, by the first route worker, a third general route from a third local route endpoint indicated by the second general route cost request to the first trip endpoint, wherein the generating of the third general route is based at least in part on the graph expansion data.

14. The batch routing system of claim 13 , the operations further comprising:

receiving a first general route cost request from a third autonomous vehicle, the first general route cost request from the third autonomous vehicle describing a second trip endpoint;

determining that the second trip endpoint and the first trip endpoint correspond to a common graph element; and

generating at least one general route responsive to the first general route cost request from the third autonomous vehicle using the first route worker.

15. The batch routing system of claim 13 , the operations further comprising:

determining a metric describing route cost requests received by the batch routing system; and

initiating at least one route worker based at least in part on the metric.

16. The batch routing system of claim 9 , the operations further comprising:

receiving routing graph modification data describing a first routing graph modification; and

determining that the first routing graph modification is for the first autonomous vehicle, wherein the determining of the first set of general routes is based at least in part on the first routing graph modification.

17. A non-transitory machine-readable medium having instructions thereon that, when executed by at least one processor, cause the at least one processor to perform operations comprising:

executing a plurality of route workers;

receiving a first general route cost request from a first autonomous vehicle, the first general route cost request describing a first trip endpoint and a first set of local route endpoints comprising a first local route endpoint and a second local route endpoint;

selecting a first route worker from the plurality of route workers for responding to the first general route cost request, the selecting of the first route worker being based at least in part on a location of the first autonomous vehicle;

determining, by the first route worker, a first set of general routes for the first autonomous vehicle, wherein the first set of general routes comprises a first general route from the first local route endpoint to a first trip endpoint and a second general route from the second local route endpoint to the first trip endpoint, the determining of the first set of general routes being based at least in part on cached data generated by the first route worker while determining a previous set of general routes for a second autonomous vehicle different than the first autonomous vehicle; and

sending a first general route cost reply to the first autonomous vehicle, the first general route cost reply indicating a first set of costs associated with the first set of general routes, wherein the first set of costs comprises a first general cost for the first general route and a second general cost for the second general route.

18. The non-transitory machine-readable medium of claim 17 , wherein the first general route cost request comprises an identifier of the first autonomous vehicle, the operations further comprising:

selecting a first route worker executing at the non-transitory machine-readable medium using the identifier;

generating the first general route by the first route worker; and

generating the second general route by the first route worker.

19. The non-transitory machine-readable medium of claim 18 , wherein generating the first general route by the first route worker comprises applying a constrained routing graph generated using at least one routing graph modification associated with the first autonomous vehicle.

20. The non-transitory machine-readable medium of claim 17 , the operations further comprising:

receiving a first general route cost request from a third autonomous vehicle, the first general route cost request from the third autonomous vehicle comprising an identifier of the third autonomous vehicle, wherein the first autonomous vehicle is of a first type and the third autonomous vehicle is of a second type different than the first type;

selecting a second route worker executing at the non-transitory machine-readable medium using the identifier of the third autonomous vehicle; and

generating a first general route cost for the third autonomous vehicle using the second route worker, wherein the generating of the first general route cost for the third autonomous vehicle is based at least in part on at least one routing graph modification associated with the second type and not associated with the first type.