Method and apparatus for two-stage planning

• US 9,857,184 B2
• Filed: 01/28/2016
• Issued: 01/02/2018
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Applied Invention, LLC
• Original Assignee: Applied Invention, LLC
• Inventors: Kaehler, Adrian, Williams, Kjerstin, Duttweiler, Mark E.
• Primary Examiner(s): Edwards, Jerrah
• Assistant Examiner(s): Williams, Kelly D
• Application Number:
  US15/009,779
• Publication Number:
  US 20160153794A1
• Time in Patent Office: 705 Days
• CPC Class Codes: B60W 30/00 Purposes of road vehicle drive control systems not related to the control of a particular sub-unit, e.g. of systems using conjoint control of vehicle sub-units
• CPC Class Codes: B60W 30/10 Path keeping cruise control for automatically following a preceding vehicle B60W30/165
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G05D 1/0212 with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287

Abstract

A plan through a space having a near field and a far field is determined. Using a sensor device, measurements of the far field are obtained and stored in an electronic memory. A processor uses the measurements to determine the viability of each far field plan among a plurality of candidate far field plans. The processor also determines a flexibility score for each of the candidate far field plans and selects a composite plan comprising the viable far field plan having a highest flexibility score among the viable candidate far field plans.

Claims

1. A computer implemented method of determining a plan through a space including a near field, wherein the near field extends along a roadway from a starting transverse line through a current position to a first transverse line though a first future position at a first future time, the method comprising:

with a sensor device, obtaining measurements of a far field that extends along the roadway from the first transverse line to a second transverse line through a second future position at a second future time;

storing said measurements in an electronic memory;

with a processor, determining, based on said measurements of said far field, a viability of each far field plan among a plurality of candidate far field plans;

with said processor, determining a flexibility score for each of said candidate far field plans; and

with said processor, selecting a composite plan comprising a far field plan having the highest flexibility score among those candidate far field plans that have been determined to be viable;

wherein the near field is characterized by a first degree of fidelity in measurements obtained by the sensor device, wherein the far field is characterized by a second degree of fidelity in the measurements obtained by the sensor device, wherein the second degree of fidelity in the measurements is lower than the first degree of fidelity in the measurements.

2. The method of claim 1, further comprising:

with a sensor device, obtaining measurements of said near field; and

with said processor, determining, based on said measurements of said near field, a viability of each near field plan among a plurality of candidate near field plans;

wherein said composite plan additionally comprises a viable near field plan that is compatible with said far field plan having the highest flexibility score.

3. The method of claim 1, further comprising:

with said processor, determining the adjacency of said candidate far field plans, wherein a first of said candidate far field plans is adjacent to a second of said candidate far field plans if it is possible to transition directly from said first candidate far field plan to said second candidate far field plan after arrival at the boundary between said near field and said far field; and

wherein said flexibility score is based upon any of;

the number of intervening far field plans between a candidate far field plan and a nearest non-viable far field plan;

the physical distance between a candidate far field plan and the nearest non-viable far field plan; and

the number of far field plans adjacent to a candidate far field plan.

4. The method of claim 1, wherein said composite plan comprises a trajectory for an autonomous vehicle;

and

wherein said near field and said far field comprise near and far regions along a driving surface.

5. The method of claim 1, wherein said candidate far field plans comprise offset curves from a roadway centerline.

6. The method of claim 2, wherein said candidate near field plans comprise a set of candidate maneuvers;

and

wherein each candidate maneuver is a transition in said near field between a current microlane and a destination microlane selected from among all microlanes, including said current microlane.

7. An apparatus for determining a plan through a space including a near field, wherein the near field extends along a roadway from a starting transverse line through a current position to a first transverse line though a first future position at a first future time, the apparatus comprising:

a sensor device;

a processor configured for determining, based on measurements taken with the sensor device obtaining measurements of a far field that extends along the roadway from the first transverse line to a second transverse line through a second future position at a second future time, a viability of each far field plan among a plurality of candidate far field plans;

said processor configured for determining a flexibility score for each of said candidate far field plans; and

said processor configured for selecting a composite plan comprising a far field plan having the highest flexibility score among those candidate far field plans that have been determined to be viable;

wherein the near field is characterized by a first degree of fidelity in measurements obtained by the sensor device, wherein the far field is characterized by a second degree of fidelity in the measurements obtained by the sensor device, wherein the second degree of fidelity in the measurements is lower than the first degree of fidelity in the measurements.

8. The apparatus of claim 7, further comprising:

said processor determining, based on measurements taken with a sensor device of said near field, a viability of each near field plan among a plurality of candidate near field plans;

wherein said composite plan additionally comprises a viable near field plan that is compatible with said far field plan having the highest flexibility score.

9. The apparatus of claim 7, further comprising:

said processor configured for determining the adjacency of said candidate far field plans, wherein a first of said candidate far field plans is adjacent to a second of said candidate far field plans if it is possible to transition directly from said first candidate far field plan to said second candidate far field plan after arrival at the boundary between said near field and said far field; and

wherein said flexibility score is based upon any of;

the number of intervening far field plans between a candidate far field plan and a nearest non-viable far field plan;

the physical distance between a candidate far field plan and the nearest non-viable far field plan; and

the number of far field plans adjacent to a candidate far field plan.

10. The apparatus of claim 7, wherein said composite plan comprises a trajectory for an autonomous vehicle;

and

wherein said near field and said far field comprise near and far regions along a driving surface.

11. The apparatus of claim 7, wherein said candidate far field plans comprise offset curves from a roadway centerline.

12. The apparatus of claim 8, wherein said candidate near field plans comprise a set of candidate maneuvers;

and

wherein each candidate maneuver is a transition in said near field between a current microlane and a destination microlane selected from among all microlanes, including said current microlane.

13. The apparatus of claim 7, wherein said candidate far field plans comprise segments of microlanes passing through said far field.

14. The apparatus of claim 13, further comprising:

said processor calculating a scalar traversability score for each of said microlanes in said far field and determining that the corresponding far field plan is viable if said traversability score is above a predetermined threshold;

wherein said traversability score is based upon any of the roughness of a roadway surface along said microlanes, the curvature of said microlanes, and the presence or absence of any obstacles along said microlanes.

15. The apparatus of claim 7, further comprising:

said processor setting said flexibility score to 0 for each non-viable far field plan, thereby eliminating said non-viable far field plans from further consideration;

for each viable far field plan, said processor setting said flexibility score to one greater than the number of said candidate far field plans between said viable far field plan and a nearest impassable far field plan.

16. The apparatus of claim 12, further comprising:

for those instances when two or more far field plans share said highest flexibility score, said processor selecting a composite plan by comparing a quantitative cost of said candidate maneuver within said composite plan.

17. The apparatus of claim 16, further comprising:

said processor using sensor measurements to discretely characterize the near field terrain on a grid of cells, wherein each cell within said grid of cells is evaluated using multiple criteria;

said processor combining said multiple criteria to determine a maximum traversal speed for said cell;

wherein the cost of each cell is inversely proportional to said traversal speed; and

wherein said quantitative cost of said candidate maneuver is proportional to the sum, along said candidate maneuver, of the products of said cost of each cell and the length of said candidate maneuver within that cell.

18. The apparatus of claim 16, wherein among composite plans comprising far field microlanes with equal flexibility scores, said processor selects the composite plan comprising the candidate maneuver with the lowest quantitative cost.

19. The apparatus of claim 13, further comprising:

when evaluating each far field plan, said processor making a Boolean determination for the microlane within each far field plan;

wherein a microlane is determined to be either passable or impassable and said flexibility score is determined for each of said far field plans based on said Boolean determination.

20. The apparatus of claim 13, further comprising:

when evaluating each far field plan, said processor computing a scalar traversability score for the microlane within each far field plan.