Trajectory generation using motion primitives

• US 10,379,538 B1
• Filed: 12/15/2017
• Issued: 08/13/2019
• Est. Priority Date: 03/20/2017
• Status: Active Grant

• Current Assignee: Zoox Inc. (Amazon.com, Inc.)
• Original Assignee: Zoox Inc. (Amazon.com, Inc.)
• Inventors: Sheckells, Matthew, Caldwell, Timothy, Kobilarov, Marin
• Primary Examiner(s): Lee, Tyler J
• Application Number:
  US15/843,596
• Time in Patent Office: 606 Days
• CPC Class Codes: B60W 10/20 including control of steering systems
• CPC Class Codes: B60W 2552/20 Road profile, i.e. the change in elevation or curvature of a plurality of continuous road segments
• CPC Class Codes: B60W 2552/30 Road curve radius
• CPC Class Codes: B60W 30/10 Path keeping cruise control for automatically following a preceding vehicle B60W30/165
• CPC Class Codes: B60W 40/072 Curvature of the road
• CPC Class Codes: B60W 60/0011 involving control alternatives for a single driving scenario, e.g. planning several paths to avoid obstacles
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0212 with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria

Abstract

In autonomous driving, it is often useful to plan trajectories in a curvilinear coordinate frame with respect to some reference trajectory, like a path produced by a hi-level route planner. This disclosure includes techniques for developing efficient approximate path coordinate motion primitives appropriate for fast planning in autonomous driving scenarios. These primitives are approximate in that particular quantities, like the path length, acceleration, and track offset trajectory, are known with some degree of certainty, and values that depend on the curvature of the reference path can be bound. Such approximate motion primitives can be used to control the autonomous vehicle to follow the trajectory in an environment.

Claims

1. A system comprising:

one or more processors; and

one or more computer-readable media storing instructions executable by the one or more processors, wherein the instructions program the one or more processors to;

determine a reference trajectory for an autonomous vehicle to follow in an environment, the reference trajectory based at least in part on a centerline associated with a portion of a road in the environment;

determine one or more segments of the reference trajectory, a segment of the one or more segments having a plurality of points, wherein each point of the plurality of points is associated with a same sign of a curvature value, and wherein the curvature value of the segment varies linearly with respect to an arc length along the reference trajectory;

determine an acceleration value of the autonomous vehicle, wherein the each point of the plurality of points is associated with the acceleration value;

determine a lateral offset of the autonomous vehicle relative to the reference trajectory;

determine, based at least in part on the lateral offset, an upper bound for an arc length associated with the segment;

determine, based at least in part on the lateral offset, a lower bound for the arc length associated with the segment;

define an approximate motion primitive associated with the segment; and

control the autonomous vehicle based, at least in part, on the approximate motion primitive.

2. The system of claim 1, wherein the segment is a first segment associated with a first curvature value, wherein the plurality of points is a first plurality of points, wherein the approximate motion primitive is a first approximate motion primitive, and wherein the instructions, when executed by the one or more processors, further program the one or more processors to:

determine a second segment of the reference trajectory, the second segment having a second plurality of points, wherein each point of the second plurality of points is associated with a second curvature value that is opposite the first curvature value;

define a second approximate motion primitive associated with the second segment; and

control the autonomous vehicle based, at least in part, on the second approximate motion primitive.

3. The system of claim 1, wherein the instructions, when executed by the one or more processors, further program the one or more processors to:

determine that the lateral offset associated with the segment is based at least in part on a cubic function in time.

4. The system of claim 1, wherein the instructions, when executed by the one or more processors, further program the one or more processors to:

determine a heuristic arc length of the segment of the reference trajectory based at least in part on the lower bound for the arc length, the upper bound for the arc length, and the lateral offset.

5. The system of claim 1, wherein the instructions, when executed by the one or more processors, further program the one or more processors to:

determine lower bound values and upper bound values associated with each segment of the one or more segments; and

determine an upper bound arc length of the reference trajectory based at least in part on the lower bound values and the upper bound values associated with each segment.

6. The system of claim 1, wherein the approximate motion primitive is associated with one or more of an acceleration, lateral offset, or a velocity.

7. The system of claim 1, wherein at least one of the lower bound or the upper bound of the arc length associated with the segment is based, at least in part, on a minimum lateral offset and a maximum lateral offset, the lateral offset being defined as a cubic polynomial in time.

8. The system of claim 1, wherein the instructions, when executed by the one or more processors, further program the one or more processors to:

determine a transition point of the reference trajectory where a sign of trajectory curvature changes from a positive curvature value to a negative curvature value; and

determine the segment based at least in part on the transition point of the reference trajectory.

9. A method comprising:

determining a reference trajectory for an autonomous vehicle to follow in an environment;

determining a segment of the reference trajectory, the segment having a plurality of points, wherein each point of the plurality of points is associated with a same sign of a curvature value;

determining an acceleration value of the autonomous vehicle;

determining a lateral offset of the autonomous vehicle relative to the reference trajectory;

determining, based at least in part on the lateral offset, an upper bound for an arc length associated with the segment;

determining, based at least in part on the lateral offset, a lower bound for the arc length associated with the segment;

defining an approximate motion primitive associated with the segment; and

controlling the autonomous vehicle based, at least in part, on the approximate motion primitive.

10. The method of claim 9, wherein the segment is a first segment associated with a first curvature value, wherein the plurality of points is a first plurality of points, wherein the approximate motion primitive is a first approximate motion primitive, and wherein the curvature value is a first curvature value, the method further comprising:

determining a second segment of the reference trajectory, the second segment having a second plurality of points, wherein each point of the second plurality of points is associated with a second curvature value that is opposite the first curvature value;

defining a second approximate motion primitive associated with the second segment; and

controlling the autonomous vehicle based, at least in part, on the second approximate motion primitive.

11. The method of claim 9, wherein the lateral offset is a cubic polynomial in time, and wherein one or more of the upper bound or the lower bound is based, at least in part, on a maximum lateral offset and a minimum lateral offset.

12. The method of claim 9, wherein the approximate motion primitive is associated with an arc length as an average of the upper bound for the arc length and the lower bound for the arc length.

13. The method of claim 9, wherein a curvature of the segment varies linearly with respect to the arc length of the segment.

14. The method of claim 9, wherein a state of the autonomous vehicle is defined as having the arc length, the lateral offset, an angular offset, and a velocity in a path-centric coordinate system, the method further comprising:

determining a subsegment of the segment, the subsegment having a plurality of points associated with velocity having the same sign.

15. The method of claim 9, further comprising:

determining a transition point of the reference trajectory where a sign of a trajectory curvature changes from a positive curvature value to a negative curvature value; and

determining the segment based at least in part on the transition point of the reference trajectory.

16. A non-transitory computer-readable medium storing instructions that, when executed, cause one or more processors to perform operations comprising:

determining a reference trajectory for an autonomous vehicle to follow in an environment;

determining a segment of the reference trajectory, the segment having a plurality of points, wherein each point of the plurality of points is associated with a same sign of a curvature;

determining an acceleration of the autonomous vehicle;

determining a lateral offset of the autonomous vehicle relative to the reference trajectory;

determining, based at least in part on the lateral offset, an upper bound for an arc length associated with the segment;

determining, based at least in part on the lateral offset, a lower bound for the arc length associated with the segment;

defining an approximate motion primitive associated with the segment; and

controlling the autonomous vehicle based, at least in part, on the approximate motion primitive.

17. The non-transitory computer-readable medium of claim 16, wherein:

the lateral offset is a cubic polynomial in time, and

one or more of the lower bound or the upper bound is based, at least in part, on a maximum lateral offset and a minimum lateral offset.

18. The non-transitory computer-readable medium of claim 16, wherein the acceleration is a constant, and wherein the curvature of the segment varies linearly with respect to the arc length of the segment.

19. The non-transitory computer-readable medium of claim 16, wherein an arc length of the approximate motion primitive is based, at least in part, on a heuristic of the lower bound for the arc length and the upper bound for the arc length.

20. The non-transitory computer-readable medium of claim 16, wherein one or more of the upper bound or the lower bound is based, at least in part, on a total distance traveled.