1. A method of linearizing a trajectory of an autonomous vehicle about a reference path, the method comprising: by a computing device: receiving a reference path for an autonomous vehicle, wherein the reference path defines a proposed trajectory for the autonomous vehicle in a Cartesian reference frame_i identifying an objective based on the received reference path, wherein the objective comprises a longitudinal component and a lateral component; projecting the objective from the Cartesian reference frame into a curvilinear coordinate frame; decoupling the longitudinal component and the lateral component; linearizing the lateral component about the received reference path to obtain a lateral problem; solving the lateral problem to obtain a refined lateral path in a curvilinear coordinate frame; mapping the refined lateral path from the curvilinear coordinate frame to the

Cartesian reference frame to generate a new reference path for the autonomous vehicle; and repeating the identifying, projecting, decoupling, linearizing, solving and mapping using the new reference path which is different from the received reference path.

1

AMENDED SHEET (ARTICLE 19)

2. The method of claim 1, wherein the objective comprises a criterion that factors into a path planning decision for the autonomous decision.

3. The method of claim 2, wherein the objective comprises one or more of the following; one or more traffic rules; travel within one or more road boundaries; collision avoidance; maintaining safe distances; or overtaking another vehicle.

4. The method of claim 1, wherein projecting the objective into a curvilinear coordinate frame comprises: determining one or more vertices of the received reference path that are affected by the objective; and for each of the one or more vertices that are affected by the objective, determining: a lateral position associated with the autonomous vehicle that satisfies the objective, and a speed associated with the autonomous vehicle that satisfies the objective.

5. The method of claim 1, wherein linearizing the lateral component about the received reference path comprises:

2

AMENDED SHEET (ARTICLE 19) generating a speed profile along the received reference path that indicates a curvature and a speed associated with the autonomous vehicle as a function of time; and sampling the speed profile at one or more points.

6. The method of claim 1, wherein the new reference path is generated by: identifying a reference curve that corresponds to the curvilinear coordinate frame; identifying an obstacle in the curvilinear coordinate frame, wherein the obstacle is represented by a lateral distance to the obstacle as a function of longitudinal distance along the reference curve; at one or more longitudinal locations along the reference curve, determining a margin representing a lateral offset at which a representation of the autonomous vehicle will contact the obstacle; and generating the new reference path using the margin.

7. The method of claim 6, further comprising: determining whether a difference between the new reference path and a previous version of the new reference path satisfy a convergence measure; and in response to determining that the difference between the new reference path and a previous version of the new reference path satisfy the convergence measure, returning the new reference path.

3

AMENDED SHEET (ARTICLE 19)

8. The method of claim 7, wherein returning the new reference path comprises returning the new reference path to a motion planning system of the autonomous vehicle.

9. (Canceled)

10. The method of claim 1, further comprising causing the autonomous vehicle to implement the new reference path by adjusting one or more operational parameters of the autonomous vehicle based on the new reference path.

11. A system of linearizing a trajectory of an autonomous vehicle about a reference path, the system comprising: a computing device; and a computer-readable storage medium comprising one or more programming instructions that, when executed, cause the computing device to perform the following operations: receive a reference path for an autonomous vehicle, wherein the reference path defines a proposed trajectory for the autonomous vehicle in a Cartesian reference frame; identify an objective based on the received reference path, wherein the objective comprises a longitudinal component and a lateral component; project the objective from the Cartesian reference frame into a curvilinear coordinate frame; decouple the longitudinal component and the lateral component;

4

AMENDED SHEET (ARTICLE 19) linearize the lateral component about the received reference path to obtain a lateral problem; solving the lateral problem to obtain a refined lateral path in the curvilinear coordinate frame; map the refined lateral path from the curvilinear frame to the Curvilinear reference frame to generate a new reference path for the autonomous vehicle; and repeating the identify operation, the project operation, the decouple operation, the linearize operation, the solve operation and the map operations using the new reference path which is different from the received reference path.

12. The system of claim 11, wherein the objective comprises a criterion that factors into a path planning decision for the autonomous decision.

13. The system of claim 12, wherein the objective comprises one or more of the following; one or more traffic rules; travel within one or more road boundaries; collision avoidance; maintaining safe distances; or overtaking another vehicle.

14. The system of claim 11, wherein the one or more programming instructions that, when executed, cause the computing device to project the objective into a curvilinear coordinate frame

5

AMENDED SHEET (ARTICLE 19) comprise one or more programming instructions that, when executed, cause the computing device to: determine one or more vertices of the received reference path that are affected by the objective; and for each of the one or more vertices that are affected by the objective, determining: a lateral position associated with the autonomous vehicle that satisfies the objective, and a speed associated with the autonomous vehicle that satisfies the objective.

15. The system of claim 11, wherein the one or more programming instructions that, when executed, cause the computing device to linearize the lateral component about the received reference path comprise one or more programming instructions that, when executed, cause the computing device to: generate a speed profile along the received reference path that indicates a curvature and a speed associated with the autonomous vehicle as a function of time; and sample the speed profile at one or more points.

16. The system of claim 11, wherein the new reference path is generated by: identifying a reference curve that corresponds to the curvilinear coordinate frame; identifying an obstacle in the curvilinear coordinate frame, wherein the obstacle is represented by a lateral distance to the obstacle as a function of longitudinal distance along the reference curve;

6

AMENDED SHEET (ARTICLE 19) at one or more longitudinal locations along the reference curve, determining a margin representing a lateral offset at which a representation of the autonomous vehicle will contact the obstacle; and generating the new reference path using the margin.

17. The system of claim 16, wherein the computer-readable storage medium further comprises one or more programming instructions that, when executed, cause the computing device to: determine whether a difference between the new reference path and a previous version of the new reference path satisfy a convergence measure; and in response to determining that the difference between the new reference path and a previous version of the new reference path satisfy the convergence measure, return the new reference path.

18. The system of claim 17, wherein the one or more programming instructions that, when executed, cause the computing device to return the new reference path comprise one or more programming instructions that, when executed, cause the computing device to return the new reference path to a motion planning system of the autonomous vehicle.

19. (Canceled)

7

AMENDED SHEET (ARTICLE 19)

20. The system of claim 11 , wherein the computer-readable storage medium further comprises one or more programming instructions that, when executed, cause the computing device to cause the autonomous vehicle to implement the new reference path by adjusting one or more operational parameters of the autonomous vehicle based on the new reference path.

21. A non-transitory computer-readable medium that stores instructions that is configured to, when executed by at least one computing device, cause the at least one computing device to perform operations comprising: receive a reference path for an autonomous vehicle, wherein the reference path defines a proposed trajectory for the autonomous vehicle in a Cartesian reference frame^ identify an objective based on the received reference path, wherein the objective comprises a longitudinal component and a lateral component; project the objective from the Cartesian reference frame into a curvilinear coordinate frame; decouple the longitudinal component and the lateral component; linearizing the lateral component about the received reference path to obtain a lateral problem; solving the lateral problem to obtain a refined lateral path in a curvilinear coordinate frame; mapping the refined lateral path from the curvilinear coordinate frame to the Cartesian reference frame to generate a new reference path for the autonomous vehicle; and

8

AMENDED SHEET (ARTICLE 19) repeat the identifying, projecting, decoupling, linearizing, solving and mapping using the new reference path which is different from the received reference path.

9

AMENDED SHEET (ARTICLE 19)